我在 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
请您参考如下方法:
既然你没有那么多点,你可以很容易地使用尝试所有可能性的解决方案。
以下是您可以执行的操作:
首先获取所有组合:
>>> list_of_points = [(1,2) , (2,5), (6,7), (9,3)]
>>> list(itertools.permutations(list_of_points))
[((1, 2), (2, 5), (6, 7), (9, 3)),
((1, 2), (2, 5), (9, 3), (6, 7)),
((1, 2), (6, 7), (2, 5), (9, 3)),
((1, 2), (6, 7), (9, 3), (2, 5)),
((1, 2), (9, 3), (2, 5), (6, 7)),
((1, 2), (9, 3), (6, 7), (2, 5)),
((2, 5), (1, 2), (6, 7), (9, 3)),
((2, 5), (1, 2), (9, 3), (6, 7)),
((2, 5), (6, 7), (1, 2), (9, 3)),
((2, 5), (6, 7), (9, 3), (1, 2)),
((2, 5), (9, 3), (1, 2), (6, 7)),
((2, 5), (9, 3), (6, 7), (1, 2)),
((6, 7), (1, 2), (2, 5), (9, 3)),
((6, 7), (1, 2), (9, 3), (2, 5)),
((6, 7), (2, 5), (1, 2), (9, 3)),
((6, 7), (2, 5), (9, 3), (1, 2)),
((6, 7), (9, 3), (1, 2), (2, 5)),
((6, 7), (9, 3), (2, 5), (1, 2)),
((9, 3), (1, 2), (2, 5), (6, 7)),
((9, 3), (1, 2), (6, 7), (2, 5)),
((9, 3), (2, 5), (1, 2), (6, 7)),
((9, 3), (2, 5), (6, 7), (1, 2)),
((9, 3), (6, 7), (1, 2), (2, 5)),
((9, 3), (6, 7), (2, 5), (1, 2))]
然后创建一个函数来给出组合的长度:
def combination_length(start_point, combination):
lenght = 0
previous = start_point
for elem in combination:
lenght += manhattanDistance(previous, elem)
return length
最后一个测试所有可能性的函数:
def get_shortest_path(start_point, list_of_point):
min = sys.maxint
combination_min = None
list_of_combinations = list(itertools.permutations(list_of_points))
for combination in list_of_combination:
length = combination_length(start_point, combination)
if length < min:
min = length
combination_min = combination
return combination_min
最后你可以拥有:
import sys, itertools
def combination_length(start_point, combination):
lenght = 0
previous = start_point
for elem in combination:
lenght += manhattanDistance(previous, elem)
return length
def get_shortest_path(start_point, list_of_point):
min = sys.maxint
combination_min = None
list_of_combinations = list(itertools.permutations(list_of_points))
for combination in list_of_combination:
length = combination_length(start_point, combination)
if length < min:
min = length
combination_min = combination
return combination_min
list_of_points = [(1,2) , (2,5), (6,7), (9,3)]
print get_shortest_path((2,1), list_of_points)
