解决一个扩展的最短哈密顿路径问题

Question

我在思考最短哈密顿路径（SHP）问题的扩展，但无法找到解决方法。我知道它是NP完全问题，但我想在这里寻求想法，因为我不想简单地用蛮力解决问题。

这个扩展非常简单：给定一个具有n个顶点的无向完全加权图，找到端点为v和u的最短哈密顿路径。

因此，蛮力仍需要O(n!)时间，因为剩下的n-2个顶点可以以(n-2)!种方式访问。我试图找到一种可能稍微快些的解决方法。到目前为止，我尝试解决这个问题的努力都没有结果。

是否有人有利用终点顶点的知识的想法？最好附带一些伪代码进行说明。找到的解决方案必须是最优的。

我猜它可以通过整数规划来解决，因为终点节点的知识相当限制，并且易于避免循环，但它并不能真正利用问题的组成。

- Undreren

Answer 1

如果你想找到连接所有节点的最短路径，那么你应该看一下旅行商算法。我不明白为什么你把它作为HSP来解决。我唯一能想到的原因是你想指定起始城市，但这应该很容易解决（如果你需要，我可以发布它），只需稍微改变你的图表即可。

编辑：如何调整你的图表

添加1个节点（称之为E），并仅将其连接到你的起始和结束节点。TSP将通过连接所有节点来计算你的问题的解决方案。由于E只能通过从起点到E再到终点才能到达，所以解决方案（一个循环）将包含开始-E-结束。然后，你删除与E和从E出发的2条边，就得到了最优解。在TSP中，从起点到终点的路径将是最优的。

- Origin

---

好的，就像我在回答中所说的那样，你可以更改你的图表以满足你的需求。我已经添加了相关内容。 - Origin

TSP有一个要求，即旅游必须从同一点开始和结束，因此寻找一个循环。连接所有点的最短循环不是连接所有点的最短路径（不需要返回起点）相同的旅游。 - Lawrence Weru

Answer 2

你可以使用元启发式算法。有许多种类的算法（局部搜索，构造性搜索等）。其中一种可能基于以下内容：

对于属于顶点集X的每个x：
- 找到最接近x的顶点集C。
- 过滤集合C以包括路径P中的一个顶点。
重复此过程，直到X的所有顶点都包含在路径P中。
结束。

- Lucia Pasarin

---

我正在寻找一种找到最优解的方法。我会立即在我的答案中澄清这一点。 - Undreren