c++ - TSP 的动态方法

Question

我无法理解为什么该算法不返回 TSP 的最短路径。

vector<int> tsp(int n, vector< vector<float> >& cost)
{
  long nsub = 1 << n;
  vector< vector<float> > opt(nsub, vector<float>(n));

  for (long s = 1; s < nsub; s += 2)
    for (int i = 1; i < n; ++i) {
      vector<int> subset;
      for (int u = 0; u < n; ++u)
        if (s & (1 << u))
          subset.push_back(u);

      if (subset.size() == 2)
        opt[s][i] = cost[0][i];

      else if (subset.size() > 2) {
        float min_subpath = FLT_MAX;
        long t = s & ~(1 << i);
        for (vector<int>::iterator j = subset.begin(); j != subset.end(); ++j)
          if (*j != i && opt[t][*j] + cost[*j][i] < min_subpath)
            min_subpath = opt[t][*j] + cost[*j][i];
        opt[s][i] = min_subpath;
      }
    }

  vector<int> tour;
  tour.push_back(0);

  bool selected[n];
  fill(selected, selected + n, false);
  selected[0] = true;

  long s = nsub - 1;

  for (int i = 0; i < n - 1; ++i) {
    int j = tour.back();
    float min_subpath = FLT_MAX;
    int best_k;
    for (int k = 0; k < n; ++k)
      if (!selected[k] && opt[s][k] + cost[k][j] < min_subpath) {
        min_subpath = opt[s][k] + cost[k][j];
        best_k = k;
      }
    tour.push_back(best_k);
    selected[best_k] = true;
    s -= 1 << best_k;
  }
  tour.push_back(0);

  return tour;
}

例如，在只有 5 个点(图中有 5 个不同节点)的距离 cost 矩阵上，算法返回的路径不是最佳路径。任何帮助识别明显或小错误的帮助将不胜感激。或有关问题出在哪里的任何有用提示。

Answer 1

有一点看起来很奇怪，即使 i 不是子集 s 的一部分，主 for 循环也会执行一些操作。

换句话说，opt[17][8] 将被设置为 cost[0][8]。 opt[17][8]表示在节点8的状态，已经访问过节点0和4(因为5=2^0+2^4)。

这应该被标记为不可能，因为如果我们在节点 8，我们肯定已经访问过节点 8!

我建议通过更改来防止这些情况发生:

for (int i = 1; i < n; ++i) {
  vector<int> subset;

到

 for (int i = 1; i < n; ++i) {
  vector<int> subset;
  if ((s&(1<<i))==0) {
     opt[s][i]=FLT_MAX;
     continue;
  }