traveling-salesman - 了解旅行推销员的时间复杂度

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)。