もう一度(これでだめな時は更新してください。) : 新しいNと場所で描き直します。
自動的編正しい答えが得られる場合もある巡回セールスマン問題
(始点と終点が同じ場合)

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








スクリーンセーバー

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

上はJAVAで作られています。メモリを大量に使ったり、重くなるかもしれません。その時は、ごめんなさい。
実行後に画面をスクロールしたり、アプレット全体が画面に入ってないと、間違った画面になるかもしれないので、気をつけてください。画面の大きさを決めてから”もう一度”をクリックするか、更新(reload)してください。


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


さて、本バージョン8では、また正確な解を速く求めたいという観点から、2つの努力をしています。
a) 2つの線分が交わるかどうか何度も計算するのは面倒なので、配列にためるようにします。(50*50*50*50という4次元配列を使っているのでかなりメモリを使うのです。すみません。)
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プログラムのダウンロード(tspv8.java)

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


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