Pythonリスト内のポイント間の最短距離を見つけるクリーナーメソッド？

Question

私はタプルのリストと個々のポイントをpythonで持っています。 [（1,2）、（2,5）、（6,7）、（9,3）]、および（2,1）であり、個々の点のすべての組み合わせによって可能な最速の経路（基本的には、（2,1）から始まるすべての点に到達する最も効率的な方法を見つけたいと思っています）。私はそれを2点と距離を出力することができますmanhattanDistance関数を持っています。しかし、私のアルゴリズムは私に矛盾した答えを与えています（何らかの理由でヒューリスティックがオフになっています）

これを行う正しい方法は何でしょうか？ここで

は、私の以前のアルゴリズムです：

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 

Answer 1

あなたはあまり意味がないので、あらゆる可能性を試すソリューションを簡単に使用できます。ここで

は、あなたが何ができるかです：

まず、すべての組み合わせを取得：最後に

def combination_length(start_point, combination): 
    lenght = 0 
    previous = start_point 
    for elem in combination: 
     lenght += manhattanDistance(previous, elem) 

    return length 

機能：

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

Answer 2

は最短距離をチェックし、すべての組み合わせを探してみてください。

Answer 3

を、これは巡回セールスマン問題のようなものであれば、あなたはNetworkXのpythonモジュールをチェックアウトしたいです。