根据此用于动态规划的递归公式（Held–Karp算法），可以找到最低成本。我在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函数），但是它没有重复计算，因为如果我们绘制此函数的树，我们会看到函数的参数（即Sandi在公式中，如下图所示）是永远不一样，也没有重复的计算。我的问题是，这次是O（n！）吗？

图片： 如果是，为什么？此函数与公式完全相同，并且功能完全相同。问题出在哪儿？它在做重复的计算吗？