旅行商问题的时间复杂度（递归公式）

Question

根据这个动态规划的递归公式(Held–Karp algorithm)，可以求出最小代价。我在C ++中输入了这段代码并实现了（neighbor向量是相同的集合并且v是成本矩阵）：

递归公式：

C(i,S) = min { d(i,j) + C(j,S-{j}) }

我的代码：

#include <iostream>
#include <vector>
#define INF 99999
using namespace std;
vector<vector<int>> v{ { 0, 4, 1, 3 },{ 4, 0, 2, 1 },{ 1, 2, 0, 5 },{ 3, 1, 5, 0 } };
vector<int> erase(vector<int> v, int j)
{
    v.erase(v.begin() + j);
    vector<int> vv = v;
    return vv;
}
int TSP(vector<int> neighbor, int index)
{
    if (neighbor.size() == 0)
        return v[index][0];
    int min = INF;
    for (int j = 0; j < neighbor.size(); j++)
    {
        int cost = v[index][neighbor[j]] + TSP(erase(neighbor, j), neighbor[j]);
        if (cost < min)
            min = cost;
    }
    return min;
}
int main()
{
    vector<int> neighbor{ 1, 2, 3 };
    cout << TSP(neighbor, 0) << endl;
    return 0;
}

实际上，erase函数从集合中删除元素j（即neighbor向量）

我知道防止重复计算的动态规划（如 Fibonacci 函数），但它没有重复计算，因为如果我们绘制此函数的树，我们会看到函数的参数（即 S和公式中的 i 如下图）永远不会相同，也不会重复计算。我的问题是，这次是 O(n!)?

图片：如果是，为什么？这个函数和公式完全一样，做的事情也完全一样。问题出在哪里？是重复计算吗？

Answer 1

你的算法时间复杂度是O(n!)。很容易理解您的代码正在猜测路径的下一个节点。正好有 n!不同的路径。您的代码实际上多次计算相同的值。例如，如果您运行 TSP({1, 2, 3, 4}, 0) 并且它尝试顺序 {1, 2, 3} 和 {2, 1, 3}。很明显，代码将运行 TSP({4}, 3) 两次。要摆脱这个商店已经计算出的面具和开始节点的答案。

旅行商问题的时间复杂度（递归公式）

Time complexity of the travelling salesman problem (Recursive formulation)

c++

algorithm

computer-science

traveling-salesman

time-complexity