traveling-salesman - 巡回セールスマンの時間計算量を理解する

Question

私は複数の情報源から、そしてそれが2^N時間で実行されるアルゴリズムの理解から読みました。私の質問は、TSPがこの実行時間を達成する原因は何ですか？擬似コードが見つからないようですので、調べてみましょう。

Answer 1

あなたが意味するアルゴリズムはおそらく包除原理です：

次の状態空間を使用して最短経路を見つけますA*。

• 状態は、都市のセットを「訪問済み」セット、「未訪問」セット、および「現在」ノードに分割することによって定義されます。
• 有効な遷移とは、1つのノードを「現在」から「訪問済み」に移動し、もう1つを「未訪問」から「現在」のセットに移動する遷移です。そのコストは、古い「現在」から新しい「現在」までの距離に等しくなります。
• 開始状態は次のとおりです。「訪問済み」の都市はなく、「現在」の任意の都市です。
• 最終状態は次のとおりです。「未訪問」の都市はなく、「現在」の都市はありません。

包含-除外の時間計算量は、州の数によって与えられます。「現在の」都市が1つだけあり（係数n）、他のすべての都市は訪問済みまたは未訪問（係数2^n）です。

'A *'アルゴリズムは、最大で1回だけ各状態に入ります。状態ごとに、最大で「n」個の他のノードを探索し、それらを優先キューにプッシュします。優先キューは、その操作を実行するのに最大で「O（n）」時間かかります。

したがって、実行時間はO(2^n * n * n * O(n))=O(2^n * poly(n))です。さらなる洞察は、それO(2^n * poly(n))がに等しいことを示していO(2^n)ます。