路徑規劃常用算法

一、最短路徑算法

最短路徑是指從起點到終點距離最短的路徑。在路徑規劃中，最短路徑算法是最基本的算法之一。最短路徑算法主要分為兩類：單源最短路徑和多源最短路徑。單源最短路徑是指從一個給定的起點到其他所有點的最短路徑。常見的單源最短路徑算法有：

1. Dijkstra算法

function Dijkstra(graph, start, end):
    dist = {start: 0}
    queue = [start]
    while queue:
        vertex = queue.pop(0)
        for neighbor in graph[vertex].keys():
            path = dist[vertex] + graph[vertex][neighbor]
            if neighbor not in dist or path < dist[neighbor]:
                dist[neighbor] = path
                if neighbor == end:
                    return dist[end]
                queue.append(neighbor)
    return -1

Dijkstra算法可以求解從單個源點出發到其他所有節點的最短路徑問題，但該算法要求必須所有邊的權值必須非負，並且求得的最短路徑不一定是全局最優解。

2. Bellman-Ford算法

function BellmanFord(graph, start, end):
    dist = {start: 0}
    for i in range(len(graph) - 1):
        for u in graph.keys():
            for v in graph[u].keys():
                if dist.get(v, float('inf')) > dist[u] + graph[u][v]:
                    dist[v] = dist[u] + graph[u][v]
    for u in graph.keys():
        for v in graph[u].keys():
            if dist.get(v, float('inf')) > dist[u] + graph[u][v]:
                return -1
    return dist[end]

Bellman-Ford算法可處理具有負權邊的圖，並且可以檢測負環。時間複雜度高於Dijkstra算法，通常用於處理邊權為負數的情況。

3. A*算法

function AStar(graph, start, end, heuristic):
    closed = set()
    open = {start: 0}
    came_from = {}
    g_score = {start: 0}
    f_score = {start: heuristic(start, end)}
    while open:
        current = min(open, key=open.get)
        if current == end:
            return reconstruct_path(came_from, end)
        del open[current]
        closed.add(current)
        for neighbor in graph[current].keys():
            if neighbor in closed:
                continue
            tentative_g_score = g_score[current] + graph[current][neighbor]
            if neighbor not in open or tentative_g_score < g_score[neighbor]:
                came_from[neighbor] = current
                g_score[neighbor] = tentative_g_score
                f_score[neighbor] = tentative_g_score + heuristic(neighbor, end)
                if neighbor not in open:
                    open[neighbor] = f_score[neighbor]
    return -1

A*算法是一種啟發式搜索算法，可以快速找到單源最短路徑。該算法使用估價函數來評估節點離目標節點的距離，並將已知最短路徑從起點到此節點的代價視為g(x)，並將估計到達目標節點的最短距離視為h(x)，利用f(x) = g(x) + h(x)來評價節點x。

二、最小生成樹算法

最小生成樹是指包含了給定的無向圖中所有節點的生成樹，並且樹上所有邊的邊權之和最小。最小生成樹算法主要包括：

1. Kruskal算法

function Kruskal(graph):
    mst = []
    sets = {i: {i} for i in graph.keys()}
    edges = [(i, j, weight) for i in graph.keys() for j, weight in graph[i].items() if i < j]
    edges.sort(key=lambda x: x[2])
    for edge in edges:
        u, v, weight = edge
        if sets[u] != sets[v]:
            mst.append(edge)
            sets[u] |= sets[v]
            sets[v] = sets[u]
    return mst

Kruskal算法是一種基於貪心的算法，每一步都選擇當前能夠加入最小生成樹的邊，直到得到一棵生成樹為止。

2. Prim算法

function Prim(graph):
    mst = []
    closed = set([next(iter(graph.keys()))])
    while len(closed) < len(graph):
        min_edge = (None, None, float('inf'))
        for u in closed:
            for v, weight in graph[u].items():
                if v not in closed and weight < min_edge[2]:
                    min_edge = (u, v, weight)
        mst.append(min_edge)
        closed.add(min_edge[1])
    return mst

Prim算法是一種從定點出發的算法，從當前已經選擇進入最小生成樹的節點出發尋找到未覆蓋節點的最短路徑，並將這條最短路徑的另一個節點加入集合中。

三、最短路搜索算法

最短路搜索算法是在給定的地圖上尋找最短路徑的算法，常用於自動駕駛、路徑規劃等應用場景。最短路搜索算法包括：

1. BFS算法

function BFS(graph, start, end):
    queue = [(start, [start])]
    visited = set()
    while queue:
        (vertex, path) = queue.pop(0)
        if vertex == end:
            return path
        if vertex in visited:
            continue
        visited.add(vertex)
        for neighbor in graph[vertex].keys():
            if neighbor not in visited:
                queue.append((neighbor, path + [neighbor]))
    return -1

BFS算法是一種廣度優先搜索算法，每一次搜索都會先遍歷當前節點的所有相鄰節點，再遍歷相鄰節點的所有相鄰節點，依次擴散，直到找到目標節點為止。

2. DFS算法

function DFS(graph, start, end):
    stack = [(start, [start])]
    visited = set()
    while stack:
        (vertex, path) = stack.pop()
        if vertex == end:
            return path
        if vertex in visited:
            continue
        visited.add(vertex)
        for neighbor in graph[vertex].keys():
            if neighbor not in visited:
                stack.append((neighbor, path + [neighbor]))
    return -1

DFS算法是一種深度優先搜索算法，每次搜索都會儘可能遞歸地深入到當前節點的子節點，直到達到目標節點或者無法逆行的終點為止。