Bagaimana untuk menulis algoritma laluan terpendek dalam Python?

Bagaimana untuk menulis algoritma laluan terpendek dalam Python?

Algoritma laluan terpendek ialah algoritma yang digunakan untuk mencari laluan terpendek dari nod permulaan ke nod sasaran dalam graf dengan tepi berwajaran. Antaranya, dua algoritma yang paling terkenal dan klasik ialah algoritma Dijkstra dan algoritma A*. Artikel ini akan menerangkan cara menulis kedua-dua algoritma ini menggunakan Python dan memberikan contoh kod.

1. Algoritma Dijkstra

Algoritma Dijkstra ialah algoritma tamak untuk mencari laluan terpendek dalam graf dengan pemberat tepi bukan negatif. Ia bermula dengan nod permulaan dan secara beransur-ansur berkembang ke nod lain sehingga nod sasaran ditemui atau semua nod yang mungkin dikembangkan. Langkah-langkah khusus adalah seperti berikut:

1) Buat set S untuk menyimpan nod laluan terpendek yang ditentukan.
2) Mulakan nod permulaan sebagai nod semasa, tetapkan panjang laluan terpendeknya kepada 0 dan tetapkan panjang laluan terpendek nod lain kepada infiniti.
3) Lintas nod bersebelahan dengan nod semasa dan kemas kini panjang laluan terpendeknya kepada panjang laluan nod semasa ditambah dengan berat tepi.
4) Pilih nod terdekat daripada nod dengan laluan terpendek yang tidak ditentukan sebagai nod semasa baharu dan tambahkannya pada set S.
5) Ulang langkah 3 dan 4 sehingga nod sasaran ditentukan sebagai laluan terpendek, dan algoritma tamat.

Berikut ialah contoh kod untuk melaksanakan algoritma Dijkstra dalam 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* algoritma

🎜🎜 * algoritma ialah algoritma carian penilaian untuk mencari laluan terpendek dalam graf berwajaran dengan fungsi heuristik. Ia menganggarkan panjang laluan dari nod semasa ke nod sasaran melalui fungsi heuristik dan memilih nod dengan anggaran terkecil untuk carian. Langkah khusus adalah seperti berikut:

1) Buat baris gilir keutamaan untuk menyimpan nod dan penilaiannya.
2) Mulakan nod permulaan sebagai nod semasa dan tambahkannya pada baris gilir keutamaan.
3) Ambil nod dengan nilai terkecil daripada baris gilir keutamaan sebagai nod semasa.
4) Jika nod semasa ialah nod sasaran, algoritma tamat dan laluan terpendek dikembalikan.
5) Lintas nod bersebelahan dengan nod semasa, kira penilaiannya dan tambahkannya pada baris gilir keutamaan.
6) Ulang langkah 3 hingga 5 sehingga nod sasaran ditemui atau baris gilir keutamaan kosong, kemudian algoritma tamat.

Berikut ialah contoh kod untuk melaksanakan algoritma A* dalam Python:

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

Ringkasan

Melalui contoh kod di atas, kita boleh lihat cara menggunakan Python Tulis algoritma laluan terpendek, termasuk algoritma Dijkstra dan algoritma A*. Kedua-dua algoritma ini sangat berkesan untuk menyelesaikan masalah laluan terpendek pada graf berwajaran. Dalam aplikasi praktikal, algoritma yang sesuai boleh dipilih mengikut keperluan khusus untuk meningkatkan kecekapan dan ketepatan algoritma.

Atas ialah kandungan terperinci Bagaimana untuk menulis algoritma laluan terpendek dalam Python?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!