java - Java: 巡回セールスマン - 発見された多項式アルゴリズム

Question

編集: このアルゴリズムの改善が見つかりました。ぜひご覧ください。

この質問は私の古い質問の改善です。ここで、 Java コード サンプルを示し、私のアルゴリズムを詳しく説明したいと思います。

巡回セールスマン問題の正確な解を得るための多項式アルゴリズムを見つけたと思います。私の実装は5つのステップから構築されています:

• 1) クイックセットアップ
• 2)解決策を探す
• 3)停止条件 1
• 4) 停止条件 2
• 5) 停止条件 3

ステップ 2 と 3 から始めたいと思います。ここで間違っていなければ、残りをお見せします。

これからお見せするのは、多項式アルゴリズムではなく、時間 O(n^2 2^n) で問題を解決するHeld–Karp アルゴリズムの改良です。

braut アルゴリズムを使用して 6 都市のルートを解決したいとしましょう。(6-1) あります！=そのための120のオプションがあるため、それらすべてをテストして、確立された最短ルートを返す必要があります。そのため、次のようになります (都市名は次のとおりです: A、B、C、D、E、F):

• オプション 1 : A -> B -> C -> D -> E -> F -> A
• オプション 2 : A -> B -> C -> D -> F -> E -> A
• オプション 3 : A -> C -> B -> D -> E -> F -> A
• オプション 4 : A -> C -> B -> D -> F -> E -> A
• .
• .
• オプション120

ここで、オプション 1 と 2 を計算した後、オプション 3 と 4 をスキップできると言っています。それは簡単です: オプション 1 を計算するとき、都市 D から始まり、都市 A で終わり、都市 E、F を通過する最短ルートを計算する必要があります。実際には、オプション 1 と 2 を計算します。最初と最後の都市を強制する 4 つの都市のマップを作成します。この例では、オプション 1 を計算するときに、そこからの最短経路のデータを保持する D、E、F、A のマップを作成します。 D から A から E、F まで。したがって、オプション 3 と 4 の計算を開始すると、都市 D に到達した時点で停止できます。これは、都市 D で開始し、都市 A で終了し、都市 E、F を通過する最短ルートが既にわかっているためです。

これは、私がアルゴリズムで使用した原則です。ブルートアルゴリズムを実行し、すべてのサブ結果をマッピングしました。これらの結果はサブルートではありません。混乱しないでください。これらは、最短ルートを見つけるために実行する必要がある計算の一部にすぎません。そのため、同じ計算を行っていることに気付くたびに、マップからの解を使用しました。

これは、19 の都市で実行された私のアルゴリズムの出力です。これはほんの一例ですが、それ以上の意味があります。実際、これは 19 都市のすべての結果を表しています。19 都市の入力が何であれ、アルゴリズムは常に同じ量のマップを作成し、同じ量のアクションを実行し、同じ時間で解決します。

Source(19)  [10.0,65.0, 34.0,52.0, 37.0,98.0, 39.0,44.0, 43.0,37.0, 45.0,89.0, 66.0,79.0, 69.0,74.0, 7.0,76.0, 70.0,15.0, 77.0,27.0, 78.0,11.0, 78.0,13.0, 80.0,5.0, 81.0,38.0, 82.0,64.0, 87.0,7.0, 90.0,61.0, 93.0,31.0]
Finish MapEngine test after 321550 mills
Created: 20801457
Map(3)  Write    2448       Read     34272
Map(4)  Write    12240      Read     159120
Map(5)  Write    42840      Read     514080
Map(6)  Write    111384     Read     1225224
Map(7)  Write    222768     Read     2227680
Map(8)  Write    350064     Read     3150576
Map(9)  Write    437580     Read     3500640
Map(10) Write    437580     Read     3084270
Map(11) Write    352185     Read     2344256
Map(12) Write    245131     Read     1382525
Map(13) Write    135638     Read     570522
Map(14) Write    54320      Read     156758
Map(15) Write    15077      Read     27058
Map(16) Write    2809       Read     2087
Map(17) Write    306        Read     0
Map(18) Write    18         Read     0
Map(19) Write    1          Read     0

0) 295.5947584525372>   [10.0,65.0, 34.0,52.0, 39.0,44.0, 43.0,37.0, 70.0,15.0, 78.0,13.0, 78.0,11.0, 80.0,5.0, 87.0,7.0, 77.0,27.0, 93.0,31.0, 81.0,38.0, 90.0,61.0, 82.0,64.0, 69.0,74.0, 66.0,79.0, 45.0,89.0, 37.0,98.0, 7.0,76.0, 10.0,65.0]

Source(19)は入力都市です。私のPCでは321550 mills計算に時間がかかりました（約5分）。Created: 20801457作成された検索インスタンスの数を表します (マップを使用した、またはマップを作成したすべての時間。この数をよりよく理解するには、コードを確認する必要があります)。Map(3)作成された 3 つの都市のマップの数について話します。2448 の 3 都市マップを作成し、34272 回使用しました。

私のアルゴリズムがN都市のルートで K 都市のサイズで生成するマップの数は次のようになります: マップの最初の都市を選択できる回数:残りの都市: (n-1)! / ((n - k - 1)! * (k-1)!)。それはnに来ます！/ ((n - k - 1)! * (k-1)!) . サイズ 3 のマップの作成がアトミック アクションであると仮定すると、私のアルゴリズムの効率は、これらすべてのマップの合計になります。

したがって、私のアルゴリズムには次の効率があります。

N * (N - 1) * (N - 2) / 2! + N * (N - 1) * (N - 2) * (N - 3) / 3! + N * (N - 1) * (N - 2) * (N - 3) (N -4) / 4! + ... ん！/ (N - 1)! = N * (N - 1) * (N - 2) / 2! + N * (N - 1) * (N - 2) * (N - 3) / 3! + N * (N - 1) * (N - 2) * (N - 3) (N -4) / 4! + ... N

では、これはどのような効率でしょうか。

O(N^C*2^N)の指数関数のように見えます。ここで、C は 1 より少し小さいです。これは、N を 7 から 100 までの効率アルゴリズムを解いて見つけ、以前の結果 (N = 9 で N = 8 の結果、N = 24 で N = 23 の結果) と比較すると、 N の数が多いと、比較結果は 2 になります。それから、従来の動的計画法アルゴリズムの効率についても同じことを行いました。これが私が得たもののリストです：

列 1 は N、列 2 は私のアルゴリズム効率の比較、列 3 は動的計画法アルゴリズムの比較、列 4 は私のアルゴリズム効率乗算 N 比較です。

7   2.55769     2.72222     2.98397 
8   2.40601     2.61224     2.74973 
9   2.31562     2.53125     2.60507 
10  2.2582      2.46913     2.50912 
11  2.21972     2.42        2.44169 
12  2.19258     2.38016     2.39191 
13  2.17251     2.34722     2.35356 
14  2.15701     2.31952     2.32293 
15  2.14456     2.29591     2.29774 
16  2.13424     2.27555     2.27652 
17  2.12548     2.25781     2.25832 
18  2.1179      2.24221     2.24248 
19  2.11124     2.22839     2.22853 
20  2.10533     2.21606     2.21614 
21  2.10003     2.205       2.20503 
22  2.09525     2.19501     2.19503 
23  2.09091     2.18595     2.18596 
24  2.08696     2.17769     2.17769 
25  2.08333     2.17013     2.17014 
26  2.08        2.1632      2.1632 
27  2.07692     2.1568      2.1568 
28  2.07407     2.15089     2.15089 
29  2.07142     2.1454      2.1454 
30  2.06896     2.1403      2.1403 
31  2.06666     2.13555     2.13555 
32  2.06451     2.13111     2.13111 
33  2.0625      2.12695     2.12695 
34  2.0606      2.12304     2.12304 
35  2.05882     2.11937     2.11937 
36  2.05714     2.11591     2.11591 
37  2.05555     2.11265     2.11265 
38  2.05405     2.10956     2.10956 
39  2.05263     2.10664     2.10664 
40  2.05128     2.10387     2.10387 
41  2.05        2.10125     2.10125 
42  2.04878     2.09875     2.09875 
43  2.04761     2.09637     2.09637 
44  2.04651     2.0941      2.0941 
45  2.04545     2.09194     2.09194 
46  2.04444     2.08987     2.08987 
47  2.04347     2.0879      2.0879 
48  2.04255     2.08601     2.08601 
49  2.04166     2.0842      2.0842 
50  2.04081     2.08246     2.08246 
51  2.04        2.0808      2.0808 
52  2.03921     2.0792      2.0792 
53  2.03846     2.07766     2.07766 
54  2.03773     2.07618     2.07618 
55  2.03703     2.07475     2.07475 
56  2.03636     2.07338     2.07338 
57  2.03571     2.07206     2.07206 
58  2.03508     2.07079     2.07079 
59  2.03448     2.06956     2.06956 
60  2.03389     2.06837     2.06837 
61  2.03333     2.06722     2.06722 
62  2.03278     2.06611     2.06611 
63  2.03225     2.06503     2.06503 
64  2.03174     2.06399     2.06399 
65  2.03125     2.06298     2.06298 
66  2.03076     2.06201     2.06201 
67  2.0303      2.06106     2.06106 
68  2.02985     2.06014     2.06014 
69  2.02941     2.05925     2.05925 
70  2.02898     2.05839     2.05839 
71  2.02857     2.05755     2.05755 
72  2.02816     2.05673     2.05673 
73  2.02777     2.05594     2.05594 
74  2.02739     2.05516     2.05516 
75  2.02702     2.05441     2.05441 
76  2.02666     2.05368     2.05368 
77  2.02631     2.05297     2.05297 
78  2.02597     2.05228     2.05228 
79  2.02564     2.05161     2.05161 
80  2.02531     2.05095     2.05095 
81  2.025       2.05031     2.05031 
82  2.02469     2.04968     2.04968 
83  2.02439     2.04907     2.04907 
84  2.02409     2.04848     2.04848 
85  2.0238      2.0479      2.0479 
86  2.02352     2.04733     2.04733 
87  2.02325     2.04678     2.04678 
88  2.02298     2.04624     2.04624 
89  2.02272     2.04571     2.04571 
90  2.02247     2.04519     2.04519 
91  2.02222     2.04469     2.04469 
92  2.02197     2.04419     2.04419 
93  2.02173     2.04371     2.04371 
94  2.0215      2.04324     2.04324 
95  2.02127     2.04277     2.04277 
96  2.02105     2.04232     2.04232 
97  2.02083     2.04188     2.04188 
98  2.02061     2.04144     2.04144 
99  2.0204      2.04102     2.04102 
100 2.0202      2.0406      2.0406 

列 3 と 4 がほぼ同じであることがわかります。これが私が見つけた方法です。

私の仕事を確認し、コードを見て、私に同意するかどうか教えてください. そうでない場合は、アルゴリズムまたは数学が正確なサンプルで機能していない場所を教えてください。私に同意する場合は、アルゴリズムのこの部分が Held-Karp アルゴリズムよりも優れていることを示すことで、wiki ページを変更するのを手伝ってください。

Answer 1

あなたの仕事は、次の 4 つの重要なポイントに基づいているようです。

1. 多項式時間の意味を理解していないようです
2. あなたのアルゴリズムは、一般的な巡回セールスマン問題を解決していないようです
3. アルゴリズムが解決する問題が巡回セールスマン問題であっても、誤った仮定に基づいているため、間違った答えが返されます。
4. アルゴリズムが正しい問題を正しく解いたとしても、多項式時間で実行されているようには見えません。

ポイント 1 については、多項式時間アルゴリズムは、家庭用コンピューターで 5 分で実行できるものではありません。「ポリ時間」、「一定時間」、「ログ時間」などの用語はすべて、アルゴリズムがスケーリングする方法を指します。アルゴリズムを 1 回実行した結果を提供しても、これについては何もわかりません。アルゴリズムの漸近的な実行時間に関する経験的データを提供するには、非常に多数のランダムな問題インスタンスを平均化する必要があります。たとえば、このグラフは、2 次元では、n 個のランダムなポイントにわたる範囲レポートO(n)の単純な方法は単純な方法によるものであり、O(n^0.5)2 次元ツリーを使用します。2 から 2^(20) の範囲のポイント数に対して 10,000 のランダムに生成された問題を解決し、いくつかの対数スケールで完了時間をプロットしました。これらの線の勾配は、アルゴリズムの漸近的な実行時間の証拠を示しています。

1 回の試行の結果は、ほぼ完全に無意味です。アルゴリズムが多項式であることを厳密に証明できない場合は、十分に分析された大規模な経験的結果のセットが、あなたの主張の証拠となり、人々の興味を引くでしょう。「大きい」という言葉を強調しなければなりません。

2 番目の点については、このアルゴリズムは、巡回セールスマン問題ではなく、ユークリッド巡回セールスマン問題を解決します。これらはさまざまな問題のセットです。この区別は技術的なものであり、ETSP は依然として NP 困難ですが、このトピックに関する 7 つの質問のいずれにも対処していない、または言及していないという事実は、解決策が有効。

3番目の点について、あなたの質問から私が理解できることから、あなたの解決策は、頂点を通る最短ハミルトン経路が頂点を通るD E F A最短ハミルトン経路に何らかの形で関連しているという仮定に基づいていE F Aます。これは誤りです。E->F->Aがそれらの頂点を通る最短経路であるとします。Dが近くにあり、その順序で現れる頂点と同一線上にあるEように選択された場合、最短経路はです。と の間の線の途中に を選択すると、最短パスは になります。前と同様の選択により、およびDEFD->E->F->ADEFE->D->F->AE->F->D->AE->F->A->Dは最短経路であり、そのような構成は任意の数の頂点に一般化できます。頂点のサブセットを通る最短のハミルトニアン パスを知っていても、別の頂点が関与した場合の状況については何もわかりません。

実際、あなたのテスト ケースの 1 つから、アルゴリズムが正しくない結果を生成することが示されています。この場合に何が起こったのかについての説明も、この問題をどのように、または修正したかについての指示もありません。

最後に、指定した合計は、二項係数n の合計よりも大きくなります。LaTeX はこのサイトではサポートされていないようです。(nCk)そのため、二項係数nchooseを使用しますk。(k)(n-k)(nCk)あなたの合計はforの合計として書き直すことができますk=1 to n。この合計は(nCk)forの合計よりも明らかに大きいためk=1 to n、この合計は よりも大きくなければなりません2^n。そのため、アルゴリズムは分析に基づいて多項式ではありません。多数の階乗を含む和が多項式で制限されることはほとんどありません。アルゴリズムの実行時間を表現するために何らかの種類の非自明な組み合わせ論が必要な場合、おそらく多項式時間で実行されません。

Answer 2

要するに、あなたのアプローチは、問題の複雑さの点で何も勝ちませんでした。

あなたのアプローチの複雑さを見てみましょう。効果的に行っているのは、同じ都市で開始および終了する 2 つのサブパスごとに長い方を削除しながら、すべてのサブパスの推移閉包を計算して、次の反復のために残りの組み合わせの数を減らすことです。都市のすべてのペア間の距離をハッシュマップに保存したと仮定すると、ルックアップ時間はO(1)になります。

ルートに含めたい n 個の都市があるとすると、 nx (n-1)個のペアがあります。

長さ 3 のすべてのサブパスの距離を計算するには、1 つの都市を選択し、選択した都市を含まないすべてのペアと組み合わせます。そのようなペアは(n-1) x (n-2)個あります。最初の位置に *n) 個の都市を選択するため、長さ 3 の3 x 2 x 1の経路を計算する必要があります。n = 3の場合、 O(n!)があることを意味します。

長さ 4 のすべてのサブパスの距離を計算するには、このプロセスを繰り返します。今回は4 x 3 x 2 x 1の計算が必要です。n = 4の場合、 O(n!)があることを意味します。これが、除去の効果が始まるポイントです。同じ都市で始まり同じ都市で終わる 2 つのパスのうち、短い方を覚えるだけで済みます。これは、長さ 4 の(4 x 3 x 2 x 1)/2パスのみが残ることを意味します。

長さ 5 のすべてのサブパスの距離を計算するには、最後のステップで行った除去から得ます。5 x (4 x 3 x 2 x 1)/2だけを計算する必要があります。n = 5の場合、 O(1/2 xn!) = O(n!)があることを意味します。今回は、同じ都市で開始および終了する 6 つのパスのうち 5 つを削除できます (前のステップで削除したため、計算さえしなかったものもあります)。残りは(5 x 4 x 3 x長さ 5 の2 x 1)/6パス。

結果として、n = 6の場合はO(1/6 xn!)になりますが、これはまだO(n!)です。さらにステップごとに、係数は小さくなります。つまり、アルゴリズムは、中間結果を保存しない単純なブルート フォース アプローチよりも高速です。しかし、あなたの複雑さはO(n!)のままです。