1

我通过递归回溯/动态编程和位掩码部分解决了 UVA 判断的问题（参见下面的代码）。

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

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

给定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));
  }
}
4

2 回答 2

1

存储路径的一种常用方法是跟踪一个附加地图，该地图存储路径查找器到达当前点所采用的节点。当您找到到结束节点的最佳路线后，您可以查询此地图，直到您回到起始节点。

于 2012-09-11T11:37:26.083 回答
1

在单人谜题中收集最佳路径与保存国际象棋等两人游戏中的主要变化是一个类似的问题。请参阅此链接以了解如何实现它。

这个想法是存储一个指向向量/步骤数组的指针（国际象棋中的移动），并在您的回溯算法在迄今为止的最短路径上发现改进时更新该数组。

于 2012-09-11T11:37:34.670 回答