Python列表中寻找两点间最短距离的更简洁方法？

Question

我有一个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

- Quinty

---

你能展示一下这个函数的代码吗？ - Christian Dean

你知道这是旅行商问题吗？ - zvone

这是旅行商问题吗？我认为它更多地涉及找到所有可能的路径组合，然后选择最佳路径。那不是你想做的吗？ - MooingRawr

你想知道起点和每个点之间的最短路径，还是想知道包含所有点的最短路径？ - Xavier C.

while len(list) .... 哪个列表？ - Arco Bast

Answer 1

由于您没有太多的分数，您可以轻松使用尝试每种可能性的解决方案。

以下是您可以采取的步骤：

首先获取所有组合：

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

- Xavier C.

---

你必须意识到这不完全是推销员问题，因为这个解决方案没有考虑回到起点的距离。 这需要进行一些小的改变，但当我阅读你的问题时，我不认为这是你需要的。 - Xavier C.

谢谢。这应该可以工作，因为列表很小。幸运的是，我不需要回来，所以这应该没问题。 - Quinty

Answer 2

如果这与旅行商问题有任何相似之处，那么您应该查看NetworkX Python模块。

- pmueller

Answer 3

尝试找到所有组合，然后检查最短距离。

- Tanzir Uddin