大山崇のちょー時間がかかるけど正しい答えが得られる巡回セールスマン問題バージョン8;効率化頑張ってるけどなかなか成果がでない版(クリック編)のページもう一度(これでだめな時は更新してください。新しいNと場所で描き直します。始点と終点が決められている場合ちょー時間がかかるけど正しい答えが得られる巡回セールスマン問題バージョン1ちょー時間がかかるけど正しい答えが得られる巡回セールスマン問題バージョン2ちょー時間がかかるけど正しい答えが得られる巡回セールスマン問題バージョン3ドローネ三角形図を使ってみる版ちょー時間がかかるけど正しい答えが得られる巡回セールスマン問題バージョン4ドローネ三角形図を使ってみる版パート2ちょー時間がかかるけど正しい答えが得られる巡回セールスマン問題バージョン5;逐次添加法とドローネ三角形図を使ってみる版ちょー時間がかかるけど正しい答えが得られる巡回セールスマン問題の変種1;逐次添加法と二次ドローネ三角形図を使ってみる版ちょー時間がかかるけど正しい答えが得られる巡回セールスマン問題の変種2;逐次添加法と三次ドローネ三角形図を使ってみる版ちょー時間がかかるけど正しい答えが得られる巡回セールスマン問題バージョン8;効率化頑張ってるけどなかなか成果がでない版ドローネ三角形図の辺が巡回セールスマン問題の答えの一部にならない例スクリーンセーバーちょー時間がかかるけど正しい答えが得られる巡回セールスマン問題バージョン8;効率化頑張ってるけどなかなか成果がでない版(クリック編)(2010年8月29日公開、2010年08月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までの説明です。最初に逐次添加法でまぁ、根拠はないけど正しい答えが出ることもある巡回路を計算します。次に、ドローネ三角形図で得られたパスを使って最適な巡回路を求めます。こちらもやはり最適であるホショウはないのですが、ある程度の精度は期待できるわけです。この際に、途中経過であっても点間の距離の和が1)の答えより長くなる場合は、計算の高速化のため、即刻、その先の計算をやめるということをしています。それでも最適なホショウはないのですけど。最後に全パターンを計算します。線分と線分が交差するような場合、点間の距離の和が巡回する前に2)の答えより小さい場合には、即刻計算をやめるということをしています。以上がバージョン5までの説明です。バージョン6、7のかわりに一旦変種1、2にいきました。1が二次ドローネ、2が三次ドローネでここでは、ドローネ三角形図のかわりに二(三)次ドローネ三角形図を使って巡回セールスマン問題の解を得ることに挑戦しています。ドローネ三角形図では解が得られない場合もありますが、二(三)次の場合、どうなのでしょうか。一次にくらべると辺の数は増えるので、時間はかかってしまいます。そのかわり確実に解が得られるということになれば、嬉しいのですが。本バージョン8では、また正確な解を速く求めたいという観点から、2つの努力をしています。2つの線分が交わるかどうか何度も計算するのは面倒なので、配列にためるようにします。(50*50*50*50という4次元配列を使っているのでかなりメモリを使うのです。点ABCまでのルートが決まって、A→B→C→Dで計算をしようとするとき、E、Fと行く前に、A→B→C→Dの距離と、A→C→B→Dの距離を比較します。A→C→B→Dの方が短い場合にはDを選ぶのはやめます。A→C→B→D→・・・の方が解になりうるので。いうのをやっています。成果はでていないのです。???有名な論文なのですが、みあたらない。●掲示板に書き込むか、どちらかお好きな方法で、ご連絡お願いいたします。●大山崇のホームページの利用について●大山崇のホームページ。