algorithm - 在完整的无向加权图中寻找哈密顿路径与哈密顿电路

Question

我有一个带权重的完整图(调整矩阵)。我已经构建了一个解决方案，用于使用分支定界找到该图中的最小汉密尔顿电路(旅行商问题)。我现在一直在寻找具有给定开始和结束节点的最佳汉密尔顿路径。如果没有给定的开始和结束节点，最好的解决方案是哈密尔顿电路——电路中最长的边。

除了用给定的开始和结束节点简单地强制寻找最佳哈密顿路径之外，我想不出其他解决方案。请提供一些有关如何处理此问题的指示。

Answer 1

给定的起始节点和结束节点等价于结束节点和起始节点之间的有向边必须是TSP旅行的一部分的约束。

所以你可以简单地改变你的邻接矩阵:

• 将所有从所需结束节点的出边设置为无限权重，除了到起始节点的边
• 将所有传入边设置为所需起始节点的无限权重，除了来自结束节点的边
• 也将从起始节点到结束节点的边设置为无限权重(以确保您不会得到反向解决方案，如果您的邻接矩阵不对称，这可能会有所不同)

这与您的实现使用的分支方法非常相似。