我从多个来源以及我对它在 2^N 时间内运行的算法的理解中阅读。我的问题是什么导致 TSP 达到这个运行时间？我似乎找不到伪代码，所以我可以检查它。
问问题
12777 次
1 回答
3
您的意思的算法可能是包含排除：
使用以下状态空间找到最短路径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)。
于 2012-11-15T19:48:15.760 回答