解决与 TSP 相关的任务
Solving a TSP-related task
我遇到的问题与基本 TSP 类似，但又不完全相同。
我有一个玩家角色的起始位置，他必须在尽可能短的时间内捡起 n 个物体。他不需要return回到原来的位置，他拿起物品的顺序也无所谓。
换句话说，问题是找到具有给定（固定）起始顶点的最小权重（距离）哈密顿路径。
我目前拥有的算法是这样的：
best_total_weight_so_far = Inf
foreach possible end vertex:
add a vertex with 0-weight edges to the start and end vertices
current_solution = solve TSP for this graph
remove the 0 vertex
total_weight = Weight (current_solution)
if total_weight < best_total_weight_so_far
best_solution = current_solution
best_total_weight_so_far = total_weight
不过这个算法似乎有点费时，因为它要解决TSP n-1次。有没有更好的办法解决原来的问题？
它是 TSP 的一个相当小的变体，显然是 NP-hard。 TSP 的任何启发式算法（对于游戏恕我直言，你真的不应该尝试做比启发式更好的事情）应该很容易根据你的情况进行修改。即使是最近的邻居也可能不会坏 - 事实上，对于您的情况，在 TSP 中使用时可能会更好，因为在最近的邻居中 return 边缘通常是最糟糕的。也许你可以使用 NN + 2-Opt 来消除边缘交叉。
关于编辑：您的问题可以很容易地简化为有向 图的 TSP 问题。将所有现有边加倍，以便每条边都被一对箭头替换。所有箭头的成本只是相应边的现有成本 除了 进入起始节点的箭头。使这些边缘成本为 0（在一天结束时 returning 没有成本）。如果您有解决有向图 TSP 的代码，那么您也可以在您的案例中使用它。
冒着速度变慢的风险（20 点应该没问题），您可以按照 John 描述的方式使用良好的旧精确 TSP 算法。 20分对于TSP来说真的很轻松-几千分的例程已经解决了，几万分的例程已经解决了。
例如，使用线性规划和分支定界。
做一个每条边有一个变量的 LP 问题（现在有更多的边，因为它是有向的），变量将在 0 和 1 之间，其中 0 表示 "don't take this edge in the solution"，1 表示 "take it" 和分数值有点意思 "take it .. a bit"（不管那是什么意思）。
成本显然是距离，除了回到起点。请参阅约翰的回答。
然后你需要约束，即对于每个节点，其入边之和为1，出边之和为1。此外，以前是一条边的一对边的总和必须小于或等于 1。现在的解决方案将由不连接的三角形组成，这是连接节点的最小方式，这样它们都有一个传入边和一个传出边，并且这些边不是两个 "the same edge"。所以必须淘汰亚游。最简单的方法（对于 20 点来说可能足够强）是将解决方案分解为连接的组件，然后对于每个连接的组件，说它的传入边的总和必须至少为 1（它可以大于 1 ), 出边也一样。再次解决 LP 问题并重复此操作，直到只有一个组件。你可以做更多的切割，比如明显的 Gomory 切割，还有花哨的特殊 TSP 切割（梳形切割、花式切割、皇冠切割……有整本关于这个的书），但你不需要这些20分。
有时，这给你的是直接的解决方案。通常开始时它会包含小数边。在那种情况下，它仍然可以很好地低估游览的时间，您可以在分支定界的框架中使用它来确定实际的最佳游览。那里的想法是选择结果中的小数边，然后选择 0 或 1（这通常会变成以前 0/1 小数的边，所以你必须保持所有 "chosen edges" 在整体中固定子树以保证终止）。现在你有两个子问题，递归地解决每个问题。每当 LP 解的估计变得比你目前找到的最佳路径长时，你可以修剪子树（因为它是一个低估，树的这一部分中的所有积分解只能是 even更糟)。您可以使用启发式解决方案来初始化 "best so far solution"，但是对于 20 点来说这并不重要，我在这里描述的技术已经足以解决 100 点问题。
我遇到的问题与基本 TSP 类似，但又不完全相同。
我有一个玩家角色的起始位置，他必须在尽可能短的时间内捡起 n 个物体。他不需要return回到原来的位置，他拿起物品的顺序也无所谓。
换句话说，问题是找到具有给定（固定）起始顶点的最小权重（距离）哈密顿路径。
我目前拥有的算法是这样的：
best_total_weight_so_far = Inf
foreach possible end vertex:
add a vertex with 0-weight edges to the start and end vertices
current_solution = solve TSP for this graph
remove the 0 vertex
total_weight = Weight (current_solution)
if total_weight < best_total_weight_so_far
best_solution = current_solution
best_total_weight_so_far = total_weight
不过这个算法似乎有点费时，因为它要解决TSP n-1次。有没有更好的办法解决原来的问题？
它是 TSP 的一个相当小的变体，显然是 NP-hard。 TSP 的任何启发式算法（对于游戏恕我直言，你真的不应该尝试做比启发式更好的事情）应该很容易根据你的情况进行修改。即使是最近的邻居也可能不会坏 - 事实上，对于您的情况，在 TSP 中使用时可能会更好，因为在最近的邻居中 return 边缘通常是最糟糕的。也许你可以使用 NN + 2-Opt 来消除边缘交叉。
关于编辑：您的问题可以很容易地简化为有向 图的 TSP 问题。将所有现有边加倍，以便每条边都被一对箭头替换。所有箭头的成本只是相应边的现有成本 除了 进入起始节点的箭头。使这些边缘成本为 0（在一天结束时 returning 没有成本）。如果您有解决有向图 TSP 的代码，那么您也可以在您的案例中使用它。
冒着速度变慢的风险（20 点应该没问题），您可以按照 John 描述的方式使用良好的旧精确 TSP 算法。 20分对于TSP来说真的很轻松-几千分的例程已经解决了，几万分的例程已经解决了。
例如，使用线性规划和分支定界。
做一个每条边有一个变量的 LP 问题（现在有更多的边，因为它是有向的），变量将在 0 和 1 之间，其中 0 表示 "don't take this edge in the solution"，1 表示 "take it" 和分数值有点意思 "take it .. a bit"（不管那是什么意思）。
成本显然是距离，除了回到起点。请参阅约翰的回答。
然后你需要约束，即对于每个节点，其入边之和为1，出边之和为1。此外，以前是一条边的一对边的总和必须小于或等于 1。现在的解决方案将由不连接的三角形组成，这是连接节点的最小方式，这样它们都有一个传入边和一个传出边，并且这些边不是两个 "the same edge"。所以必须淘汰亚游。最简单的方法（对于 20 点来说可能足够强）是将解决方案分解为连接的组件，然后对于每个连接的组件，说它的传入边的总和必须至少为 1（它可以大于 1 ), 出边也一样。再次解决 LP 问题并重复此操作，直到只有一个组件。你可以做更多的切割，比如明显的 Gomory 切割，还有花哨的特殊 TSP 切割（梳形切割、花式切割、皇冠切割……有整本关于这个的书），但你不需要这些20分。
有时，这给你的是直接的解决方案。通常开始时它会包含小数边。在那种情况下，它仍然可以很好地低估游览的时间，您可以在分支定界的框架中使用它来确定实际的最佳游览。那里的想法是选择结果中的小数边，然后选择 0 或 1（这通常会变成以前 0/1 小数的边，所以你必须保持所有 "chosen edges" 在整体中固定子树以保证终止）。现在你有两个子问题，递归地解决每个问题。每当 LP 解的估计变得比你目前找到的最佳路径长时，你可以修剪子树（因为它是一个低估，树的这一部分中的所有积分解只能是 even更糟)。您可以使用启发式解决方案来初始化 "best so far solution"，但是对于 20 点来说这并不重要，我在这里描述的技术已经足以解决 100 点问题。