我有一个完整的图（形容词。矩阵）与权重本文利用分枝定界法建立了求图（旅行商问题）中最小哈密顿回路的解。我现在被困在寻找给定起点和终点节点的最佳哈密顿路径上。如果没有给定的起点和终点节点，最好的解决方案是哈密顿电路的最长边。
我想不出一个解决办法，只不过是在给定的起点和终点节点下，粗暴地寻找最佳的哈密顿路径。请提供一些如何处理此问题的指针。
最佳答案
给定的开始节点和结束节点等效于一个约束，即结束节点和开始节点之间的定向边必须是TSP巡更的一部分。
所以你可以简单地改变你的邻接矩阵：
将所需结束节点的所有传出边设置为“无限权重”，但将边设置为“开始节点”
将所需开始节点的所有传入边设置为“无限权重”（Infinite Weight），结束节点的边除外
将从开始节点到结束节点的边也设置为无限权重（以确保不会得到反向解，如果相邻矩阵不是对称的，则可能会有所不同）
这与实现使用的分支方法非常相似。
关于algorithm - 在完全无向加权图中找到哈密顿路径与哈密顿回路，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/37043018/