我正在考虑对最短哈密顿路径（SHP）问题的扩展，但我找不到解决它的方法。我知道它是 NP 完全的，但我想我会在这里征求意见，因为我不想简单地暴力破解这个问题。
扩展相当简单：给定一个具有n个顶点的无向、完整、加权图，找到末端顶点为v和u的最短哈密顿路径。
因此，暴力破解仍然需要 O( n !) 时间，因为剩余的n -2 个顶点可以在 ( n -2) 中访问！方法。我试图找到一种方法来稍微更快地解决这个问题。到目前为止，我为找到一种有益的方式解决这个问题的方法所做的努力都没有结果。
有人知道如何利用终端顶点的知识吗？最好与一些伪代码一起解释。需要找到最佳的解决方案。
我想这可以通过整数规划来解决，因为端节点的知识相当有限，并且很容易避免循环，但它不会真正利用问题的组成。
如果你想找到连接所有节点的最短路径，那么你应该看看旅行商算法。我不完全明白您为什么将其视为 HSP。我能想到的唯一原因是你想指定你的起始城市，但是通过稍微改变你的图表应该很容易解决这个问题（如果你需要我可以发布它）。
编辑：添加如何调整图表
添加 1 个节点（称为 E）并仅将其连接到您的起始节点和结束节点。TSP 将通过连接所有节点来计算问题的解决方案。由于 E 只能通过从 start 到 E 然后到 end 到达，因此解决方案（一个循环是）将包含 start - E - end。然后你从 E 中删除 2 条边，你就有了最优解。在 TSP 内，从开始到结束的路径将是最优的。
您可以使用元启发式算法。它们有很多种（本地搜索、建设性搜索等）。其中之一可能基于：
对于属于顶点集合 X 的每个 x：
- 找到最接近 x C 的顶点集合。
- 过滤集合 C 以便将其中一个包含在路径 P 中。
重复直到 X 的所有顶点都包含在路径 P 中路径 P.
结束。