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








スクリーンセーバー

ちょー時間がかかるけど正しい答えが得られる巡回セールスマン問題(2010年7月31日公開、2010年07月31日14:13:10第0回の改訂)

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

ここでは巡回セールスマン問題の答えを時間がかかる方法で求めています。
画面をクリックすると緑の点が表れます。４つ以上クリックするとそれらの点を全て巡らなければならないときの最適な順序が線で表示されます。
Ｎは対象となる点の数、TSP_dはそのときのひかれた線の長さの合計、route_numはその答えがいくつの組み合わせから選ばれたかを表しています。さらに右上の?/?というのは、計算の進捗状況をあらわします。点の数が多くなればなるほど計算時間がかかります。たくさん点をクリックしてしまったときには、待ち時間の目安にしてください。
実をいうと、このプログラムの欠点は、この待ち時間の目安になる数字?1/?2の?2がroute_numと一致しないこと、?2がroute_numの２倍であるということで、必要以上に計算しないでよいルートを計算している、逆順は計算しなくてよいのに、やってしまっている、ということです。逆順を計算しなくていい、というロジックを入れることは可能なのですが、それをいれるとかえって計算が遅くなってしまうので、今回はあきらめてしまいました。今後の課題ということでお許しください。
●Javaプログラムのダウンロード(tsploop.java 8KB)
ご意見、ご感想、お問い合わせ、お願い等がございましたら、お気軽に、
メール送信フォームからメールを送るか、
●掲示板に書き込むか、
どちらかお好きな方法で、ご連絡お願いいたします。

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