有一个非常重要的事实导致多项式时间算法：
由于点位于一些轴线，它们产生路径图，这意味着，每3个顶点
v1,v2,v3中，如果
v2是间
v1和
v3，然后之间的距离
v1和
v3等于之间的距离
v1与
v2加之间的距离
v2和
v3。因此，例如
v1，如果我们从obj
开始。首先到达
v2然后到达的路径的函数值
v3将始终小于首先到达
v3然后返回的路径的值，
v2因为：
value of the first path = w[2]*D(v1,v2)+W[3]*(D(v1,v2)+D(v2,v3))
value of the second path = w[3]*D(v1,v3)+W[2]*((v1,v3)+D(v3,v2)) =w[3]*D(v1,v2)+w[3]*D(v2,v3)+w[2]*(D(v1,v2)+2*D(v3,v2))
如果我们从第二个值中减去第一个路径值，那么
w[2]*2*D(v3,v2)除非您考虑负权重，否则将等于或大于0。
所有这些意味着，如果我们位于某个点上，则始终应该只考虑两个选项：转到左侧的最接近未访问点或右侧的最接近未访问点。
这非常重要，因为它为我们提供了
2^n可能的路径，而不是
n!可能的路径（例如在“旅行推销员问题”中）。
可以使用动态编程在多项式时间内解决路径图上的TSP /最小权哈密顿路径，您应该应用完全相同的方法，但要修改计算目标函数的方式。
由于您不知道起始顶点，因此必须运行此算法
n时间，每次都从不同的顶点开始，这意味着运行时间将乘以
n。
