c++ - 仅访问选定的城市并重新开始的最低成本？

Question

我理解旅行商问题。假设我只想访问选定的城市并返回开始，该怎么做？

假设我的成本矩阵是，

  A B C D
A 0 1 2 1
B 1 0 1 2
C 2 1 0 1
D 1 2 1 0

如果我想访问所有城市并回到 A。我的最短路径是A->B->C->D，最短距离是4。

假设我只想访问 B 和 D。我怎样才能找到最小距离？

这是修改旅行商问题？有人可以帮我为这种情况做蛮力算法吗？

Answer 1

您可以首先运行 Floyd-Warshall 来计算所有节点对之间的最短路径。参见维基百科文章。一旦你有了压缩成本矩阵，你就可以消除所有你不感兴趣的城市。从那里它是标准的旅行推销员。

由于旅行推销员是 NP 完备的，因此在它之前运行 Floyd-Warshall 的复杂性并不重要。

如果您想要完整的方向（包括绕行无趣的城市以缩短路径，您将不得不返回 Floyd-Warshall 并重建路径。

Answer 2

我手头没有我的代码，但这里有一些建议和伪代码可以帮助您：我将通过在内存中存储一​​个向量以及上述距离矩阵来解决这个问题。就像是：

struct Location{
bool visited;
bool mustVisit;
}

Vector<Location> locationVec;

用问题中的位置填充向量，标记是否必须访问它们，并始终将访问设置为 false。然后是有趣的部分！您需要创建 locationVec 的排列。我会递归地执行此操作，例如：

void addLocation(int & curLength, int & maxLength, int & curDistance, Vector<Location> &locationVec, Location* lastVisited)
if(curLenth == maxLength){
//check if currentDistance is less than the previously generated best difference, if so
//replace it
lastVisited->visited=0;
return;
}

//Add the next location
for (int& i : locationVec){
//Check if the location has been visited, and if it must be visited.
//If so: mark as visited, point lastVisited to it, and break
//Also add from lastVisited to the new location to your curDistance
curLength++;
}

addLocation(curLength, maxLength, curDistance, locationVec, lastVisited);
return;
}

那应该让你开始。当您将visited 从visited = 1 更改为visited = 0 时，请记住从currentDist 中减去，因为您实际上是在“未访问”这座城市。您可能还需要跟踪 lastlastvisited，具体取决于您的具体实现。

如果您需要加快速度（您可能会，旅行推销员非常慢），请查看 Branch and Bound：http ://en.wikipedia.org/wiki/Branch_and_bound