Jān*_*ris 9 algorithm traveling-salesman
我有一个求解器可以解决正常的对称TSP问题.解决方案意味着通过所有节点的最短路径,而不限制哪个节点是路径中的第一个节点和最后一个节点.
有没有办法转换问题,以便确保特定节点作为起始节点,另一个节点作为终端节点？
一种方法是将I - 一个非常大的距离 - 添加到这些起始/结束节点和所有其他节点之间的所有距离(在起始节点和结束节点之间的距离上加两倍),因此解算器很想仅访问它们一次(从而使它们成为路径的起点和终点).
这种方法有什么大的缺点,还是有更好的方法来做到这一点？
nha*_*tdh 16
您可以添加一个虚拟节点,该节点连接到具有权重0的边的起始和结束节点.由于TSP必须包含虚拟节点,因此最终结果必须包含序列start - dummy node - end(没有其他方法可以到达虚节点).因此,您可以使用指定的起始和结束节点获得最短的Hamilton路径.即使图中的边缘为负,此解决方案也应该有效.
| 归档时间： |
|
| 查看次数： |
5467 次 |
| 最近记录： |