c++ - 保存通过递归回溯找到的最佳路径

Question

我已经部分解决了a problem on the UVA judge (见下面的代码)，具有递归回溯/动态编程和位掩码。

这为包含的测试用例提供了正确的最终答案，但是，我还必须打印最佳路径路线，我不确定如何将其保存在递归例程中。

问题是一个旅行商问题，基本上问题是这样的:

给定 n 坐标，找到所有这些坐标之间的最短路径。

#include<iostream>
#include<cmath>
#include<climits>
#include<cstdio>
using namespace std;

#define MAX_N 10

struct Computer{
  double x;
  double y;
};

Computer computers[MAX_N];
double dist[MAX_N][MAX_N];
double DP[MAX_N][1 << MAX_N];

size_t n; 

double d(Computer a, Computer b) {
  return sqrt(pow((a.x - b.x), 2.0) + pow((a.y - b.y), 2.0)) + 16.0;
}

double recurse(int i, int switched)
{
  if(switched == (1 << n) - 1) return 0;
  if(DP[i][switched] != 0) return DP[i][switched];

  double local_min = INT_MAX;
  for(int j = 0; j < n; j++)
    if(i != j && !(switched & (1 << j)))
      local_min = min(dist[i][j] + recurse(j, switched | (1 << j)), local_min);

  return DP[i][switched] = local_min;
}

int main()
{
  for(unsigned int p = 1; cin >> n; p++) {
    if(n == 0) return 0;
    memset(DP, 0, sizeof DP);

    for(size_t i = 0; i < n; ++i) {
      Computer c; cin >> c.x >> c.y;
      computers[i] = c;
    }

    for(size_t i = 0; i < n; ++i) for(size_t j = 0; j < n; ++j)
      dist[i][j] = d(computers[i], computers[j]);

    printf("%d: %.2f\n", p, recurse(0, 1));
  }
}

Answer 1

存储路径的一种常见方法是跟踪附加 map ，该 map 存储寻路者到达当前点所采用的节点。当您找到到达结束节点的最佳路线时，您可以查询这张 map ，直到您回到起始节点。