Skip to main content
 首页 » 编程设计

python之寻找 python 列表中点之间最短距离的更简洁方法

2025年04月02日7qq78292959

我在 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)