[解決済み] TSPの場合、Held-Karpアルゴリズムは、Brute-forceのO(n!)からO(2^n*n^2)に時間複雑性をどのように減少させるのでしょうか？[クローズド］

質問

Held-Karpアルゴリズムのキーポイントがよくわからないのですが、どのようにして時間的な複雑さを軽減しているのでしょうか？ 動的計画法を用いているので、中間結果をキャッシュから取得することで時間を節約しているのか、それとも計算の早い段階でいくつかのパスを削除しているからなのでしょうか？

また、2次元の表を使用して、1次元の計算を表示することは可能でしょうか？ 簡単なTSP問題(3または4都市)ですか？

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

Held-Karpアルゴリズムの動的計画法は、TSP問題の次のような性質を利用しています。 距離が最小のパスのすべてのサブパスは、それ自体も距離が最小である。

つまり、単純なトップダウン・アプローチですべての解を確認するのではなく、ボトムアップ・アプローチで、問題を解くのに必要な中間情報を一度に開発するのです。 と一度だけ . 最初のステップは極小のサブパスである。より大きなサブパスを解くためにステップアップするたびに、すでに計算されたすべての小さなサブパスの問題の解を調べることができるのです。また、サブパスのレベルが上がるごとに、指数関数的に時間が短縮されます。しかし、計算からパスが削除されることはなく、手順の最後にはすべてのサブ問題が解決されています。欠点は、すべての中間結果を保存するために、非常に大きなメモリサイズが必要になることです。

要約すると、Held-Karpアルゴリズムの時間短縮は、以下の事実に起因する。 決して 都市の部分集合（組み合わせ）に対する解を重複して解くことになる。しかし、ブルートフォース・アプローチでは、与えられた部分集合の組み合わせに対する解を何度も再計算することになる（与えられた全体集合の順列の中で必ずしも連続した順序ではないとはいえ）。

Wikipediaに2次元距離行列の例と疑似コードがあります。 こちら .