Pythonで最短経路アルゴリズムを記述するにはどうすればよいですか?

Python で最短パス アルゴリズムを記述するにはどうすればよいですか?

最短パス アルゴリズムは、重み付けされたエッジを持つグラフで開始ノードからターゲット ノードまでの最短パスを見つけるために使用されるアルゴリズムです。その中でも、最も有名で古典的なアルゴリズムは、ダイクストラのアルゴリズムと A* アルゴリズムの 2 つです。この記事では、Python を使用してこれら 2 つのアルゴリズムを作成する方法を説明し、コード例を示します。

1. ダイクストラのアルゴリズム

ダイクストラのアルゴリズムは、非負のエッジの重みを持つグラフ内の最短パスを見つけるための貪欲なアルゴリズムです。開始ノードから開始され、ターゲット ノードが見つかるか、すべての可能なノードが展開されるまで、他のノードに徐々に展開されます。具体的な手順は次のとおりです。

1) 決定された最短パスのノードを保存する集合 S を作成します。
2) 開始ノードを現在のノードとして初期化し、その最短パス長を 0 に設定し、他のノードの最短パス長を無限大に設定します。
3) 現在のノードに隣接するノードをトラバースし、それらの最短パス長を現在のノードのパス長にエッジの重みを加えたものに更新します。
4) 最短経路が未定のノードの中から最も近いノードを新たなカレントノードとして選択し、集合 S に追加します。
5) ターゲット ノードが最短パスであると判断されるまでステップ 3 と 4 を繰り返し、アルゴリズムが終了します。

次は、ダイクストラのアルゴリズムを Python で実装するコード例です:

def dijkstra(graph, start, end):
    # 节点集合
    nodes = set(graph.keys())
    # 起始节点到各个节点的最短路径长度字典
    distance = {node: float('inf') for node in nodes}
    # 起始节点到各个节点的最短路径字典
    path = {node: [] for node in nodes}
    # 起始节点到自身的最短路径长度为0
    distance[start] = 0

    while nodes:
        # 找到当前节点中最小距离的节点
        min_node = min(nodes, key=lambda node: distance[node])
        nodes.remove(min_node)

        for neighbor, weight in graph[min_node].items():
            # 计算经过当前节点到相邻节点的路径长度
            new_distance = distance[min_node] + weight
            if new_distance < distance[neighbor]:
                # 更新最短路径
                distance[neighbor] = new_distance
                path[neighbor] = path[min_node] + [min_node]

    return distance[end], path[end] + [end]

2. A* アルゴリズム

A* アルゴリズムは、評価検索アルゴリズムです。 . ヒューリスティック関数を使用して重み付きグラフの最短経路を解決します。現在のノードからターゲット ノードまでのパス長をヒューリスティック関数によって推定し、推定値が最小のノードを選択して検索します。具体的な手順は次のとおりです。

1) ノードとその評価を保存するための優先キューを作成します。
2) 開始ノードを現在のノードとして初期化し、優先キューに追加します。
3) 優先キューからの評価が最小のノードを現在のノードとして取得します。
4) 現在のノードがターゲット ノードの場合、アルゴリズムは終了し、最短パスが返されます。
5) 現在のノードに隣接するノードを走査し、それらの評価を計算し、優先キューに追加します。
6) ターゲット ノードが見つかるか優先キューが空になるまでステップ 3 ～ 5 を繰り返し、その後アルゴリズムは終了します。

以下は、Python で A* アルゴリズムを実装するためのコード例です:

from queue import PriorityQueue

def heuristic(node, end):
    # 启发式函数，估计从当前节点到目标节点的路径长度
    return abs(node[0] - end[0]) + abs(node[1] - end[1])

def a_star(graph, start, end):
    # 起始节点到各个节点的最短路径字典
    path = {start: []}
    # 起始节点到各个节点的路径估值字典
    f_value = {start: heuristic(start, end)}
    # 创建一个优先队列，用于存储节点及其估值
    queue = PriorityQueue()
    queue.put((f_value[start], start))

    while not queue.empty():
        _, current = queue.get()

        if current == end:
            return path[current] + [end]

        for neighbor in graph[current]:
            next_node = path[current] + [current]
            if neighbor not in path or len(next_node) < len(path[neighbor]):
                # 更新最短路径
                path[neighbor] = next_node
                # 更新路径估值
                f_value[neighbor] = len(next_node) + heuristic(neighbor, end)
                queue.put((f_value[neighbor], neighbor))

    return None

概要

上記のコード例を通じて、Python を使用して以下を記述する方法を確認できます。ダイクストラ アルゴリズムや A* アルゴリズムなどの最短パス アルゴリズム。これら 2 つのアルゴリズムは、重み付きグラフ上の最短経路問題を解決するのに非常に効果的です。実際のアプリケーションでは、特定のニーズに応じて適切なアルゴリズムを選択し、アルゴリズムの効率と精度を向上させることができます。

以上がPythonで最短経路アルゴリズムを記述するにはどうすればよいですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。