[解決済み] このHeld-Karp TSP Pseudocodeの説明をお願いします。

質問

巡回セールスマン問題に対するHeld-Karpアルゴリズムを、以下のような擬似コードで実装しようとしている。

(ここで見つけたものです。 https://en.wikipedia.org/wiki/Held%E2%80%93Karp_algorithm#Example.5B4.5D )

アルゴリズムは手書きでできるのですが、実際にコードで実装するのに苦労しています。どなたかわかりやすく解説していただけると幸いです。

これもよくわからない。

この部分は、開始都市から接続都市までの距離を設定するためのものだと思っていました。もしそうなら、以下のようになるのではないでしょうか？ C({1}, k) := d1,k であって C({k}, k) := d1,k ? 私が完全に誤解しているだけなのでしょうか？

また、このアルゴリズムは15～20都市を超えるとあまりうまくいかないと聞いたことがあるので、40都市程度では、何か良い代替手段があるでしょうか？

どのように解決するのですか？

ヘルドカープとは ダイナミックプログラミング のアプローチになります。

動的計画法では、タスクをサブタスクに分割し、quot;動的関数"を使って、すでに計算された小さなサブタスクの結果を使って大きなサブタスクを解決し、最終的にタスクを解決します。

DPアルゴリズムを理解するためには、サブタスクと動的関数をどのように定義しているかを理解することが不可欠です。

Held-Karpの場合、サブタスクは以下の通りです。

与えられた頂点の集合に対して S とある頂点の k   ( 1 ∉ S , k ∈ S )

C(S,k) は、頂点 1 のすべての頂点を通過し S で終了します。 k .

このサブタスクの定義を考えると、なぜ初期化なのかは明らかです。

C({k}, k) := d(1,k)

からのパスの最小の長さは 1 から k をトラバースして {k} からのエッジだけです。 1 から k .

次に、"dynamic function"です。

余談だが、DPアルゴリズムは次のように書くことができる。 トップダウンまたはボトムアップ . この疑似コードはボトムアップ型である。つまり、小さいタスクから順に計算し、その結果を大きいタスクに使用する。より具体的には、集合のサイズが大きくなる順に計算します。 S からスタートし |S|=1 まで上がり |S| = n-1 (すなわち S を除くすべての頂点を含む 1 ).

では、あるタスクを考えてみましょう。 S, k . からのパスに相当することを覚えておいてください。 1 を経由して S で終わる。 k .

に分割しています。

• からのパス 1 のすべての頂点を通過する。 S ただし k ( S\k ) で終わり、その頂点は m   ( m ∈ S , m ≠ k ):  C(S\k, m)
• からのエッジ m から k

を破るために考えられるすべての方法を調べれば、簡単にわかることです。 C(S,k) の答えは、このように、その中から最小の経路を見つけることである。 C(S, k) .

最後に、すべての C(S, k) に対して |S| = n-1 の欠けたエッジでサイクルを完了させる。 k から 1 :  d(1,k) . 最小のサイクルが最終的な結果です。

についてですが。

また、このアルゴリズムは15～20都市を超えるとあまりうまくいかないと聞いているので、40都市程度では、何か良い代替手段があるでしょうか？

Held-Karpのアルゴリズムの複雑さはθ(n²2)です。 ⁿ ). 40² * 2 ⁴⁰ ≈ 1.75 * 10 ¹⁵ これは、1台のマシンで合理的に計算するのは不可能だと言えるでしょう。

David Eisenstatが提案したように、以下のようなアプローチもあります。 混合整数計画法 N=40の場合、この問題を十分に高速に解くことができます。

例えば、以下をご覧ください。 このブログの記事 と このプロジェクト を構築しています。