もう一度(これでだめな時は更新してください。) : 新しいNと場所で描き直します。

自動的編	正しい答えが得られる場合もある巡回セールスマン問題 (始点と終点が同じ場合) ・２人・2人領域分割版 ・M人・M人領域分割版 ・M人領域分割版たまに越境する編	始点と終点が自由な場合	始点が決められていて終点は自由な場合	始点と終点が決められている場合
	正しい答えが得られる可能性もある逐次添加法による巡回セールスマン問題			ヒルベルト曲線を使ったもの
				ヒルベルト曲線の近似多角形を使ったもの
	ちょー時間がかかるけど正しい答えが得られる巡回セールスマン問題バージョン１
	ちょー時間がかかるけど正しい答えが得られる巡回セールスマン問題バージョン２
	ちょー時間がかかるけど正しい答えが得られる巡回セールスマン問題バージョン3ドローネ三角形図を使ってみる版
	ちょー時間がかかるけど正しい答えが得られる巡回セールスマン問題バージョン4ドローネ三角形図を使ってみる版パート2
	ちょー時間がかかるけど正しい答えが得られる巡回セールスマン問題バージョン5;逐次添加法とドローネ三角形図を使ってみる版
	ちょー時間がかかるけど正しい答えが得られる巡回セールスマン問題の変種1;逐次添加法と二次ドローネ三角形図を使ってみる版
	ちょー時間がかかるけど正しい答えが得られる巡回セールスマン問題の変種2;逐次添加法と三次ドローネ三角形図を使ってみる版
	ちょー時間がかかるけど正しい答えが得られる巡回セールスマン問題バージョン8;効率化頑張ってるけどなかなか成果がでない版
	最悪的非効率的巡回路		準悪的非効率的巡回路
	目指せ最短的巡回路		目指せより短いぞ的巡回路
	近い点の組の巡回路
	巡回セールスマン問題の答えの垂直二等分線達		巡回セールスマン問題の答えの垂直二等分線を中途半端にひいてできる図
クリック編	正しい答えが得られる場合もある巡回セールスマン問題 (始点と終点が同じ場合)	始点と終点が自由な場合	始点が決められていて終点は自由な場合	始点と終点が決められている場合
	ちょー時間がかかるけど正しい答えが得られる巡回セールスマン問題バージョン１
	ちょー時間がかかるけど正しい答えが得られる巡回セールスマン問題バージョン２
	ちょー時間がかかるけど正しい答えが得られる巡回セールスマン問題バージョン3ドローネ三角形図を使ってみる版
	ちょー時間がかかるけど正しい答えが得られる巡回セールスマン問題バージョン4ドローネ三角形図を使ってみる版パート2
	ちょー時間がかかるけど正しい答えが得られる巡回セールスマン問題バージョン5;逐次添加法とドローネ三角形図を使ってみる版
	ちょー時間がかかるけど正しい答えが得られる巡回セールスマン問題の変種1;逐次添加法と二次ドローネ三角形図を使ってみる版
	ちょー時間がかかるけど正しい答えが得られる巡回セールスマン問題の変種2;逐次添加法と三次ドローネ三角形図を使ってみる版
	ちょー時間がかかるけど正しい答えが得られる巡回セールスマン問題バージョン8;効率化頑張ってるけどなかなか成果がでない版
ドローネ三角形図の辺が巡回セールスマン問題の答えの一部にならない例

スクリーンセーバー

ちょー時間がかかるけど正しい答えが得られる巡回セールスマン問題バージョン8;効率化頑張ってるけどなかなか成果がでない版(クリック編)(2010年8月29日公開、2010年08月29日22:06:51第0回の改訂)

ここでは巡回セールスマン問題の答えを時間がかかる方法で求めています。 画面をクリックすると緑の点が表れます。４つ以上クリックするとそれらの点を全て巡らなければならないときの最適な順序が線で表示されます。 Ｎは対象となる点の数、TSP_dはそのときのひかれた線の長さの合計、route_numはその答えがいくつの組み合わせから選ばれたかを表しています。さらに右上の?/?というのは、計算の進捗状況をあらわします。点の数が多くなればなるほど計算時間がかかります。たくさん点をクリックしてしまったときには、待ち時間の目安にしてください。 実をいうと、このプログラムの欠点は、この待ち時間の目安になる数字?1/?2の?2がroute_numと一致しないこと、?2がroute_numの２倍であるということで、必要以上に計算しないでよいルートを計算している、逆順は計算しなくてよいのに、やってしまっている、ということです。逆順を計算しなくていい、というロジックを入れることは可能なのですが、それをいれるとかえって計算が遅くなってしまうので、今回はあきらめてしまいました。今後の課題ということでお許しください。 以上は、バージョン１の説明です。このページ：バージョン２では、計算時間を短縮させるために、全ての順番について長さを計算するのをやめて、２つの線分が交差する場合の組み合わせは計算対象から除く処理を追加しております。組み合わせの数が減った分だけ、幾分計算時間が短くなることがバージョン１との比較でわかります。 ここではドローネ三角形図の辺を使って、巡回セールスマンをとけるかということを確認することをしています。答えはＮＯで（文献[?]参照）、たまに、ドローネ三角形の辺でない線分が巡回セールスマン問題の答えになります。そんなことを楽しめるようにしています。 暗い青はボロノイ図、暗い赤はドローネ三角形の辺、ピンクはちょー時間をかけて求めた巡回セールスマン問題の答えバージョン２版、美登里、間違えた、緑はドローネ三角形の辺を使った場合の巡回セールスマン問題の答え（正しくない場合もあります。）です。緑の線とは別にピンクの線が見えるような場合がたまにあります。まぁ、滅多にないので、レッツチャレンジ的なのです。cntはバージョン2で関数が呼ばれる回数、delacntはドローネ三角形図のやり方で関数が呼ばれる関数、つまり計算時間の目安です。
以上がバージョン３までの説明です。
ここではさらに、ドローネ三角形図を使って得られた正しいか正しくないかわからない答えをもとに、それより大きい答えが出たらそのルートは即刻削除するという作戦をとって計算時間を短くすることに挑戦しています。まぁ、それでも結構な時間がかかるのです。
以上がバージョン４までの説明です。本バージョン５では、さらなる高速化を目指して、
1) 最初に逐次添加法でまぁ、根拠はないけど正しい答えが出ることもある巡回路を計算します。
2) 次に、ドローネ三角形図で得られたパスを使って最適な巡回路を求めます。こちらもやはり最適であるホショウはないのですが、ある程度の精度は期待できるわけです。で、この際に、途中経過であっても点間の距離の和が1)の答えより長くなる場合は、計算の高速化のため、即刻、その先の計算をやめるということをしています。まぁ、それでも最適なホショウはないのですけど。。。
3) 最後に全パターンを計算します。しかしながら、線分と線分が交差するような場合、点間の距離の和が巡回する前に2)の答えより小さい場合には、即刻計算をやめるということをしています。
以上がバージョン５までの説明です。
バージョン６、７のかわりに一旦変種１、２にいきました。１が二次ドローネ、２が三次ドローネで
ここでは、ドローネ三角形図のかわりに二（三）次ドローネ三角形図を使って巡回セールスマン問題の解を得ることに挑戦しています。ドローネ三角形図では解が得られない場合もありますが、二（三）次の場合、どうなのでしょうか。。。一次にくらべると辺の数は増えるので、時間はかかってしまいます。そのかわり確実に解が得られるということになれば、嬉しいのですが。。。
という感じでした。

さて、本バージョン８では、また正確な解を速く求めたいという観点から、２つの努力をしています。
a) ２つの線分が交わるかどうか何度も計算するのは面倒なので、配列にためるようにします。(50*50*50*50という４次元配列を使っているのでかなりメモリを使うのです。すみません。)
b) 点ABCまでのルートが決まって、A→B→C→Dで計算をしようとするとき、E、Fと行く前に、A→B→C→Dの距離と、A→C→B→Dの距離を比較します。もしA→C→B→Dの方が短い場合にはDを選ぶのはやめます。どうせA→C→B→D→・・・の方が解になりうるので。。。
というのをやっています。
しかし、あまり成果はでていないのです。おそるべしTSP。


●参考文献
[?] ???有名な論文なのですが、みあたらない。家の中大捜査中。。
●Javaプログラムのダウンロード(tspv8cli.java)

---

ご意見、ご感想、お問い合わせ、お願い等がございましたら、お気軽に、
メール送信フォームからメールを送るか、
●掲示板に書き込むか、
どちらかお好きな方法で、ご連絡お願いいたします。

---

●大山崇のホームページの利用について
●大山崇のホームページ