瞭解旅行推銷員的時間複雜性

Question

我已經從多個來源讀取，並且從我對2^N次運行的算法的理解中瞭解到。我的問題是什麼導致TSP達到這個運行時間？我似乎無法找到一個僞代碼，所以我可以檢查它。

Answer 1

你的意思的算法是有可能的容斥：

雖然使用A*以下狀態空間尋找最短路徑：

• 狀態是由一組城市到的分區定義「訪問」集合，「未訪問」集合和「當前」節點。
• 有效的轉換是將一個節點從「當前」移動到「已訪問」以及一個從「未訪問」移動到「當前」集合的轉換。其成本等於從舊「當前」到新「當前」的距離。
• 起始狀態是：沒有城市被「訪問」，任意城市是「當前」。
• 完成狀態是：沒有城市是'未訪問'，任何城市都是'當前'。

容斥的時間複雜度是由國家的數給出：恰好有一個「當前」城市（的n因子）和所有其他城市要麼參觀或未訪問（的2^n因子）。

'A *'算法最多隻能進入一次狀態。對於每個狀態，它將最多探索'n'個其他節點並將它們推入優先級隊列。優先級隊列最多會花費'O（n）'時間來執行其操作。

因此，運行時間是O(2^n * n * n * O(n)) = O(2^n * poly(n))。進一步的洞察表明，O(2^n * poly(n))等於O(2^n)。