提问人：Szyszka947 提问时间：11/17/2023 最后编辑：Ulrich EckhardtSzyszka947 更新时间：11/18/2023 访问量：53
如何在旅行推销员中跟踪路径 使用 DP 和位掩码解决的问题
How to track path in Travelling Salesman Problem solved using DP and bitmasking
问：
我编写了使用 DP 解决 TSP（旅行推销员问题）的代码，但我无法弄清楚如何跟踪给出解决方案的路径。
这就是代码：
static int tsp(std::vector<std::vector<int>> const& dist, size_t current, uint64_t mask, std::vector<std::vector<int>>& dp) {
if (mask == ((size_t)1 << dist.size()) - 1)
return dist[current][0];
if (dp[mask][current] != -1)
return dp[mask][current];
int result = INT_MAX;
for (uint64_t i = 0; i < dist.size(); ++i) {
uint64_t val = (uint64_t)1 << i;
if (mask & val)
continue;
int sub = dist[current][i] + tsp(dist, i, mask | val, dp);
result = std::min(result, sub);
}
dp[mask][current] = result;
return result;
}
int main()
{
std::vector<std::vector<int>> dist{
{0, 10, 41, 31},
{10, 0, 30, 19},
{41, 30, 0, 20},
{31, 19, 20, 0}
};
std::vector<std::vector<int>> dp(1 << dist.size(), std::vector<int>(dist.size(), -1));
std::cout << (tsp(dist, 0, 1, dp) == 90);
}
我试图将它作为参数传递，并在我获得比当前节点更好的结果时使用它，但它不起作用。我认为不是，因为某些时候的最佳结果并不是整个解决方案的最佳结果（例如，整个解决方案可能会以不同的顺序访问节点，并且无法重新访问它们）。std::vector<int>& pathtsppath[i] = currenti
您可能想知道此代码如何检查节点是否被访问。我通过位掩码来做到这一点，该过程可能如下所示（对于 4 个节点 A、B、C、D）：
图表来自：main
预期路径为：（成本等于 90）0-1-3-2-0
那么，如何跟踪在TSP问题中提供最佳解决方案的路径呢？
答：
1赞
trincot
11/18/2023
#1
您可以添加一个参数（我们称之为 ），用于收集给定掩码和节点的最佳邻居。因此，它将具有与 相同的类型。linkdp
然后，在运行之后，您可以使用此数据结构来重建路径。tsp
以下是您的代码，其中包含必要的添加：
static int tsp(std::vector<std::vector<int>> const& dist,
size_t current, uint64_t mask,
std::vector<std::vector<int>>& dp,
std::vector<std::vector<int>>& link) { // new parameter
if (mask == ((size_t)1 << dist.size()) - 1)
return dist[current][0];
if (dp[mask][current] != -1)
return dp[mask][current];
int result = INT_MAX;
for (uint64_t i = 0; i < dist.size(); ++i) {
uint64_t val = (uint64_t)1 << i;
if (mask & val)
continue;
// Pass extra argument in recursive call
int sub = dist[current][i] + tsp(dist, i, mask | val, dp, link);
if (sub < result) {
result = sub;
link[mask][current] = i; // Register which neighbor was best
}
}
dp[mask][current] = result;
return result;
}
// Function to translate `link` into a path, assuming 0 is starting node
static std::vector<int> getpath(std::vector<std::vector<int>>& link) {
size_t current = 0;
uint64_t mask = 0;
std::vector<int> path;
for (int i = 0; i < link[0].size(); i++) {
path.push_back(current);
mask |= 1 << current;
current = link[mask][current];
}
return path;
}
int main() {
std::vector<std::vector<int>> dist{
{0, 10, 41, 31},
{10, 0, 30, 19},
{41, 30, 0, 20},
{31, 19, 20, 0}
};
std::vector<std::vector<int>> dp(1 << dist.size(), std::vector<int>(dist.size(), -1));
std::vector<std::vector<int>> link(1 << dist.size(), std::vector<int>(dist.size(), 0));
int res = tsp(dist, 0, 1, dp, link);
std::vector<int> path = getpath(link);
std::cout << "result " << res << "\n";
for (auto i : path)
std::cout << i << " ";
std::cout << "\n";
}
请注意，您的代码假定 0 是起始节点（请参阅基本情况），因此我在 中使用了相同的假设。getpath
评论
tsptsp