圖論演算法路徑尋找與最小生成樹

import heapq

def dijkstra(graph, source):
    # 初始化距離陣列和優先佇列
    distances = {vertex: float('infinity') for vertex in graph}
    distances[source] = 0
    pq = [(0, source)]
    visited = set()

    while pq:
        current_distance, current_vertex = heapq.heappop(pq)

        # 若當前頂點已被存取，則跳過
        if current_vertex in visited:
            continue

        visited.add(current_vertex)

        # 若當前頂點是目標，則終止演算法
        if current_vertex == target:
            break

        for neighbor, weight in graph[current_vertex].items():
            distance = current_distance + weight

            # 只有當新的距離更短時才更新
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(pq, (distance, neighbor))

    return distances

# 定義圖形結構
graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'A': 1, 'C': 2, 'D': 5},
    'C': {'A': 4, 'B': 2, 'D': 1},
    'D': {'B': 5, 'C': 1}
}

source = 'A'
target = 'D'

#### 內容解密：
此實作展示了迪傑斯特拉演算法的核心邏輯：
1. 使用優先佇列來高效選擇下一個待處理頂點。
2. 維護一個已存取頂點的集合，避免重複處理。
3. 動態更新鄰近頂點的最短距離。
4. 當達到目標頂點時終止演算法。
透過這些步驟，演算法確保找到從源頂點到所有其他頂點的最短路徑。

### A* 搜尋演算法

A* 搜尋演算法透過結合啟發式資訊來引導搜尋過程，從而進一步提升了迪傑斯特拉演算法的效能。A* 使用一個評估函式 f(x)，該函式由兩個部分組成：g(x) 代表從源到當前頂點 x 的實際成本，而 h(x) 代表從 x 到目標的預估成本。透過選擇一個可接受的啟發式函式（即不會高估真實成本），A* 能夠在減少搜尋節點數量的同時保證找到最佳路徑。

#### A* 搜尋演算法實作

```python
def a_star(graph, source, target, heuristic):
    # 初始化 g 和 f 值
    g_score = {vertex: float('infinity') for vertex in graph}
    g_score[source] = 0
    f_score = {vertex: float('infinity') for vertex in graph}
    f_score[source] = heuristic(source)

    open_set = [(f_score[source], source)]
    came_from = {}

    while open_set:
        current_f, current_vertex = min(open_set)
        open_set.remove((current_f, current_vertex))

        if current_vertex == target:
            # 重建路徑
            path = []
            while current_vertex in came_from:
                path.append(current_vertex)
                current_vertex = came_from[current_vertex]
            path.append(source)
            path.reverse()
            return path

        for neighbor, weight in graph[current_vertex].items():
            tentative_g_score = g_score[current_vertex] + weight

            if tentative_g_score < g_score[neighbor]:
                came_from[neighbor] = current_vertex
                g_score[neighbor] = tentative_g_score
                f_score[neighbor] = tentative_g_score + heuristic(neighbor)
                if (f_score[neighbor], neighbor) not in open_set:
                    open_set.append((f_score[neighbor], neighbor))

    return None

# 定義啟發式函式（例如曼哈頓距離）
def manhattan_heuristic(vertex):
    coordinates = {
        'A': (0, 0),
        'B': (1, 0),
        'C': (1, 1),
        'D': (2, 1)
    }
    target_coord = coordinates[target]
    vertex_coord = coordinates[vertex]
    return abs(target_coord[0] - vertex_coord[0]) + abs(target_coord[1] - vertex_coord[1])

source = 'A'
target = 'D'

#### 內容解密：
此實作展示了 A* 搜尋演算法的核心邏輯：
1. 結合實際成本 g(x) 和啟發式預估 h(x) 來計算評估函式 f(x)。
2. 使用優先佇列來管理待處理頂點，根據 f(x) 值進行排序。
3. 動態更新鄰近頂點的 g 和 f 值，並記錄路徑資訊。
4. 當達到目標頂點時重建最優路徑。
透過啟發式資訊的引導，A* 能夠在複雜圖形中高效地找到最短路徑。

### 普林姆演算法與克魯斯卡爾演算法

普林姆演算法和克魯斯卡爾演算法主要用於解決最小生成樹問題，即在一個加權無向圖中找到一棵包含所有頂點的子圖，使得該子圖的總權重最小。

#### 普林姆演算法實作

```python
def prim(graph):
    # 初始化最小生成樹和已存取集合
    mst = []
    visited = set()
    start_vertex = list(graph.keys())[0]
    visited.add(start_vertex)
    edges = [(weight, start_vertex, neighbor) for neighbor, weight in graph[start_vertex].items()]
    heapq.heapify(edges)

    while edges:
        weight, u, v = heapq.heappop(edges)

        if v not in visited:
            visited.add(v)
            mst.append((u, v, weight))

            for neighbor, neighbor_weight in graph[v].items():
                if neighbor not in visited:
                    heapq.heappush(edges, (neighbor_weight, v, neighbor))

    return mst

graph = {
    'A': {'B': 2, 'C': 3},
    'B': {'A': 2, 'C': 1, 'D': 1},
    'C': {'A': 3, 'B': 1, 'D': 4},
    'D': {'B': 1, 'C': 4}
}

#### 內容解密：
此實作展示了普林姆演算法的核心邏輯：
1. 從一個起始頂點開始，逐步擴充套件已存取集合。
2. 使用優先佇列管理所有連線已存取和未存取頂點的邊。
3. 每次選擇權重最小的邊，將其加入最小生成樹，並擴充套件已存取集合。
透過貪心策略，普林姆演算法能夠有效地構建最小生成樹。

## 最小生成樹與路徑尋找演算法在圖論中的應用

在圖論中，除了直接的路徑尋找外，許多應用需要建構連線圖中所有頂點的生成樹，並且要求累積成本最小。這類別問題由最小生成樹（Minimum Spanning Tree, MST）演算法解決。MST演算法旨在找到一組邊，形成一棵包含所有頂點的樹，並且總邊權重最小。常見的MST演算法包括Prim演算法和Kruskal演算法。

### Prim演算法的工作原理

Prim演算法從任意一個頂點開始，逐步擴充套件MST，每次新增連線樹內頂點和樹外頂點的最小權重邊。該演算法使用優先佇列來管理候選邊，與Dijkstra演算法機制相似。以下為Prim演算法的簡要步驟：

1. 選擇任意頂點作為起始點，並將其加入MST。
2. 初始化優先佇列，包含與起始點相鄰的所有邊。
3. 當MST尚未包含所有頂點時：
   - 從佇列中移除權重最小的邊(u, v)。
   - 若v尚未在MST中，將v（及該邊）加入MST，並將v連向未被包含頂點的邊加入佇列。

Prim演算法的效率取決於所使用的資料結構。藉助適當的優先佇列，時間複雜度可達O(E log V)。

### Kruskal演算法的工作原理

Kruskal演算法首先按照權重對所有邊進行非遞減排序，然後遍歷排序後的邊，若某邊不形成環路，則將其加入MST。該演算法使用不相交集（Disjoint-Set）資料結構來高效檢測環路。以下是Kruskal演算法的偽程式碼：

1. 將所有邊按權重排序。
2. 初始化不相交集資料結構，包含所有頂點。
3. 對排序後的每條邊(u, v)：
   - 若find(u) != find(v)，表示u和v不在同一集合中，將邊(u, v)加入MST，並合併u和v所在的集合。

Kruskal演算法特別適用於稀疏圖，其整體時間複雜度主要由排序決定，通常為O(E log E)，可近似為O(E log V)。

### 兩種演算法的比較與應用

Prim和Kruskal演算法都能確保生成的生成樹在總邊權重方面是最優的。選擇使用哪種演算法通常取決於圖的結構和具體應用需求。在稠密圖中，Prim演算法因其從單一源點增量擴充套件的特性可能更受青睞，而Kruskal演算法則因其對稀疏圖中較小邊集的排序效率而更具優勢。

### 動態規劃與最佳化基礎

#### 7.1 動態規劃的核心概念

動態規劃是一種系統化的方法，用於解決複雜問題。它透過將問題分解為更小的、相互關聯的子問題來實作。這種方法依賴兩個基本原則：**重疊子問題**和**最優子結構**。

1. **重疊子問題**：當計算整體解時，多次遇到相同的子問題。動態規劃透過儲存已計運算元問題的結果，避免重複計算。
   
2. **最優子結構**：問題的最優解可以由其子問題的最優解組合而成。這意味著若要使整體問題達到最優，其子問題也必須是最優解。

#### 斐波那契數列計算的最佳化

斐波那契數列是動態規劃的一個經典例子。其定義為每個數是前兩個數之和。簡單遞迴實作會導致大量重複計算，從而使時間複雜度呈指數級增長。然而，透過引入記憶化技術，可以將其轉化為高效的動態規劃解法。

```python
def fibonacci(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fibonacci(n-1, memo) + fibonacci(n-2, memo)
    return memo[n]

def fibonacci(n, memo={}):
    if n <= 1:
        return n
    if n not in memo:
        memo[n] = fibonacci(n-1, memo) + fibonacci(n-2, memo)
    return memo[n]

def fibonacci(n):
    if n <= 1:
        return n
    fib = [0] * (n + 1)
    fib[1] = 1
    for i in range(2, n + 1):
        fib[i] = fib[i-1] + fib[i-2]
    return fib[n]