PythonでA * pathfindingアルゴリズムを使って3つのデメンタルリストを実行するには

Question

私はPythonの実装A *アルゴリズムを書こうとしている学生です。私はこの質問が100回前に尋ねられたことを知っていますが、私の状況についての詳細はいくつかありますが、私は完全に理解していません。

私は10ノードの重み付け無指向グラフを持っています。私の実際のグラフにはさらに多くのノードがあります。グラフは3次元のリストとしてソートされます。グラフを生成するために書き込んだプログラムの出力を貼り付けています。

Node 1 : [[8, 3], [9, 11], [2, 12], [3, 12], [7, 6]] 
Node 2 : [[5, 6], [4, 3], [1, 12], [8, 11], [7, 1]] 
Node 3 : [[6, 2], [1, 12], [5, 7], [9, 1]] 
Node 4 : [[2, 3], [8, 2], [10, 5], [5, 10], [7, 4]] 
Node 5 : [[2, 6], [4, 10], [3, 7], [7, 8]] 
Node 6 : [[3, 2], [9, 10]] 
Node 7 : [[2, 1], [4, 4], [5, 8], [1, 6], [8, 3]] 
Node 8 : [[1, 3], [2, 11], [4, 2], [7, 3], [10, 4]] 
Node 9 : [[1, 11], [6, 10], [3, 1]] 
Node 10 : [[4, 5], [8, 4]] 

グラフは、3次元のリストとして保存されます。たとえば、インデックス0では、ノード8,9,2,3および7への接続があります。ノード8と0の間の重みは3です。ノード0と9と11の間の重みです。 。

myGraph = [[[8, 3], [9, 11], [2, 12], [3, 12], [7, 6]], [[5, 6], [4, 3], [1, 12], [8, 11], [7, 1]], [[6, 2], [1, 12], [5, 7], [9, 1]], [[2, 3], [8, 2], [10, 5], [5, 10], [7, 4]], [[2, 6], [4, 10], [3, 7], [7, 8]], [[3, 2], [9, 10]], [[2, 1], [4, 4], [5, 8], [1, 6], [8, 3]], [[1, 3], [2, 11], [4, 2], [7, 3], [10, 4]], [[1, 11], [6, 10], [3, 1]], [[4, 5], [8, 4]]] 

したがって、リストを入力として受け入れ、最適なルートを出力する、A *のPython実装を見つけることが課題です。ほとんどのグラフは辞書のデータ型の周りに構築されているようですが、それは私の状況ではありません。

3Dリストを使用してA *の独自のバージョンを作成しようとしましたが、私にとってはちょっと複雑なので運がなかったのです。

私はこれとしばらくの間苦労していたので、誰かが私に与えることができた助けを本当に感謝しています。ありがとうございました！

Answer 1

@Luai Ghunimが言ったことに詳細を追加するための未検証の疑似コードです。

まず、すでにPython標準ライブラリにある優先キューの実装がhttps://docs.python.org/3/library/heapq.htmlであることがわかります。それはあなたのtodoのリストを保存します。

第2に、そのキューに入るものはきれいに並べ替える必要があります。そのためのトリックは、最初のフィールドがソートされたものであるタプルを使用することです。このように：

[estimated_total, node, cost] 

あなたは彼らがフィールドにそれらの名前を与えることhttps://docs.python.org/3/library/collections.html#collections.namedtupleを使って素敵な見えるようにすることができます。あなたがいないと仮定しようが、それは個人的な選択です。

第3に、ノードまでの距離を推定する機能が必要です。それをestimator(node)としましょう。

最後に、私たちが特定のノードにどのように到達したかというfrom_nodeという名前の辞書が必要です。

# Start with node 0 in our lookup. 
from_node = {0: {"from_node": None, "cost": 0.0}} 
# And in our todo. 
todo = [[estimator(0), 0, 0.0]] 
while 0 < len(todo): 
    (estimated_cost, node, cost) = heapq.heappop(todo) 
    if cost == from_node[node]["cost"]: 
     if node == target_node: 
      # We have our answer and know that it is best. 
      break 
     else: 
      for (next_node, next_cost) in my_graph[node]: 
       total_cost = cost + next_cost 
       if next_node in from_node: 
        if from_node[next_node]["cost"] <= total_cost: 
         # We have a better path. 
         continue 
       from_node[next_node] = {"from": node, "cost": total_cost} 
       heapq.heappush(todo, 
        [total_cost + estimator(next_node), next_node, total_cost]) 
if target_node in from_node: 
    reversed_path = [] 
    node = target_node 
    while node is not None: 
     reversed_path.append(node) 
     node = from_node[node]["from"] 
    # AND NOW reversed(reversed_path) IS YOUR ANSWER 
else: 
    # THERE IS NO ANSWER