Und*_*ren 10 graph pseudocode np-complete shortest-path
我正在考虑对最短哈密顿路径(SHP)问题的扩展,我找不到解决它的方法.我知道它是NP完全的,但我想我会在这里提出想法,因为我不想简单地强行解决问题.
扩展非常简单:给定具有n个顶点的无向完整加权图,找到具有端点v和u的最短哈密顿路径.
因此,bruteforce仍然需要O(n!)时间,因为剩余的n -2个顶点可以在(n -2)中访问!方法.我试图找到一种方法,也许解决这个稍快.到目前为止,我努力寻找以有益的方式解决这个问题的方法.
有人会想知道如何利用终点顶点的知识吗？优选地与一些伪代码一起解释.找到的解决方案是最佳的.
我想它可以通过整数编程来解决,因为终端节点的知识是相当有限的,并且很容易避免循环,但它不会真正利用问题的组成.
如果您想找到连接所有节点的最短路径,那么您应该查看旅行推销员算法.我不确切地知道为什么你作为HSP接近它.我能想到的唯一原因是你想要指定你的起始城市,但是应该很容易通过改变你的图表来修复它(如果你需要我可以发布它).
编辑:添加如何调整图表
添加1个节点(称为E)并仅将其连接到起始节点和结束节点.TSP将通过连接所有节点来计算问题的解决方案.由于E只能通过从开始到E再到结束来到达,所以解决方案(循环是)将包含start-E-end.然后从E中移除2个边缘并获得最佳解决方案.在TSP中,从开始到结束的路径将是最佳的.