我在python中有一个元组列表和一个单独的点,例如[(1,2),(2,5),(6,7),(9,3)]和(2,1),我想找出由单个点到点列表的所有组合所创建的最快路径(基本上我想找到从(2,1)开始到达所有点的最有效方法)。我有一个manhattanDistance函数,可以取2点,输出距离。但是,我的算法给出了不一致的答案(由于某种原因,启发式算法关闭了)
正确的方法是什么?在
这是我以前的算法:
def bestPath(currentPoint,goalList):
sum = 0
bestList = []
while len(goallist) > 0:
for point in list:
bestList.append((manhattanD(point,currentPoint),point))
bestTup = min(bestList)
bestList = []
dist = bestTup[0]
newP = bestTup[1]
currentPoint = newP
sum += dist
return sum
如果这与旅行推销员问题类似,那么您需要检查一下NetworkXpython模块。在
试着找出所有的组合,然后检查最短的距离。在
因为你没有那么多的观点,你可以很容易地使用一种尝试各种可能性的解决方案。在
以下是您可以做的:
首先获取所有组合:
然后创建一个函数,给出组合的长度:
^{pr2}$最后是一个测试所有可能性的函数:
最后你可以:
相关问题 更多 >
编程相关推荐