Algorithm (Part II) 大複習(完結)

國立臺東大學資訊工程學系

### Greedy Algorithms 對於許多最佳化問題，使用動態規劃來確定最佳選擇有些過度，更簡單、更有效率的演算法就可以了，也就是說，它做出局部最優選擇，希望這個選擇能帶來全域最優解。 The Activity-selection Problem 安排一間只能容納一個活動的會議室。

在活動選擇問題中，我們希望從一堆會互相重疊的活動中，挑出最多個彼此不重疊的活動。這個問題可以被有效地解決，是因為它具備一個叫做「最佳子結構」的特性。簡單來說，這個特性表示：我們可以把整個排程問題拆成幾個小問題來處理，並且每個小問題的最佳解可以合併成整體的最佳解。舉例來說，假設我們在安排活動的過程中，決定要選擇某一個特定的活動，接下來我們只需要考慮兩件事： 1.在這個活動開始之前，有哪些活動可以安排？ 2.在這個活動結束之後，又有哪些活動可以安排？只要我們在前後兩個時間區段中，分別找出最適合的活動安排，加上中間這個選定的活動，就可以拼出一個完整的排程方案。而且，只要整體的安排是最好的，那前後兩段的安排也必須是各自區段中的最優選擇。這種「大問題可以被分成幾個獨立子問題，解完再組合」的特性，正是遞迴與動態規劃能夠用在這個問題上的關鍵理由。 📌 用動態規劃來解活動選擇問題我們想知道，在某段時間內可以安排的最多活動數量。假設你已經知道某個活動要被選進來，這時你就可以把整段時間切成「選擇這個活動前」與「選擇這個活動後」兩段。這樣總數量就是「前段最多能選的活動數」加上「後段最多能選的活動數」再加 1（因為我們選了一個活動）。但問題是，我們不知道應該選哪個活動。所以，我們必須嘗試每一個可能的活動，看哪一個切法能讓總數最多。如果這段時間內完全沒有活動可以選，那最大數就是 0。這個做法很完整，但需要試很多組合，效率不高。 📌 貪婪策略的直覺出發點我們應該選擇一個能夠「保留最多時間給其他活動」的活動。如果我們選一個很晚結束的活動，就佔掉了太多時間。相反地，如果我們選擇一個最早結束的活動，後面能接得上的活動就比較多。所以，最佳策略是「每次都選結束時間最早的活動」。 A Recursive Greedy Algorithm 用來從已排序的活動中選出最大數量的互不重疊活動集合。每次挑出第一個可排的活動後，遞迴處理剩下的子問題。 RECURSIVE-ACTIVITY-SELECTOR(s, f, k, n) m = k + 1 while m ≤ n and s[m] < f[k] m = m + 1 if m ≤ n return {a_m} ∪ RECURSIVE-ACTIVITY-SELECTOR(s, f, m, n) else return ∅ An Iterative Greedy Algorithm 行為等價但效率較高（節省堆疊記憶體），用來選出最大數量不重疊的活動集合。 GREEDY-ACTIVITY-SELECTOR(s, f, n) A = {a_1} // select the first activity k = 1 // last selected activity index for m = 2 to n if s[m] ≥ f[k] // check if compatible A = A ∪ {a_m} k = m // update last selected return A 📌 設計貪婪演算法的步驟 1.確認問題有最佳子結構。 2.發展遞迴解法。 3.驗證貪婪選擇後只剩一個子問題。 4.證明這樣的選擇是安全的。 4.實作遞迴演算法。 6.將其改為效率較高的迴圈版本。 📌 貪婪與 DP 的差異比較貪婪法：每步都選擇「局部最優」，希望得到「整體最優」。動態規劃：每一步的選擇依賴於之前子問題的最佳解，通常是 bottom-up 解法。 📌 Greedy vs. DP（0-1 Knapsack 問題） 1.定義 0-1 背包問題：小偷有一個容量為 W 的背包，要選擇若干個物品放進去，每個物品都有重量與價值。限制：每個物品只能「全拿」或「不拿」——不能分割。問題：該選哪幾個物品，讓總價值最大？這個問題具有最佳子結構特性如果選了某個物品，那剩下的問題就是在「剩餘容量」下選擇「剩餘物品」。 2.問題：這個問題能不能用貪婪法解？（答案：不一定）貪婪策略失敗的例子：有三個物品，單位價值最高的是 item 1。貪婪策略會選 item 1，但實際上選 item 2 + item 3 會讓總價值更高。結論：對 0-1 背包問題，貪婪法不保證找出最佳解。如果小偷用貪婪法先拿了單位價值最高的 item 1，結果可能是這個物品太重、佔空間太多，導致背包裝不滿或其他更有價值的組合放不進來，反而讓總價值變少。也就是說：空間沒用好，效益變低。選 item 1 時剩下的容量是 10，也許在選 item 2 的另一個情況下也剩下容量 10，這時可以共用子問題的答案，避免重算。這種「一個大問題拆成多個小問題」而且這些小問題會重複出現的特性，正是動態規劃的代表特色。 📌Greedy vs. DP（Fractional Knapsack 問題） 1.定義分數背包問題跟 0-1 背包一樣，但這次允許拿「一部分」的物品。類比：0-1 是「金條」，Fractional 是「金砂」。這個問題就可以用貪婪法有效解決。這個問題也有最佳子結構特性如果選了某項物品的一部分，那剩下的問題就是再裝滿剩餘空間。剩餘空間可能再裝一些其他物品或原物品剩下的部分。

先選 A（10 單位）：全部裝入 → $80（剩 30）再選 B（20 單位）：全部裝入 → $100（剩 10）最後選 C 的前 10 單位（30 的 1/3）： → 價值 = $90 × (10 / 30) = $30 A：$80 B：$100 C（部分）：$30 總價值 = $210 -------------------------------------------------------------------------------------------------------- ### Single-Source Shortest Paths 如何用更聰明的演算法找出最短路徑，而不是窮舉所有可能。圖是有向、帶權重的（weighted, directed graph）。路徑的權重是沿路所有邊的權重總和。我們定義兩點間最短路徑的距離 δ(u,v)：如果有路徑，就取所有路徑的最小總權重。如果沒路徑，定義為無限大 ∞。換句話說，最短路徑就是權重加總最小的合法走法。最短路徑問題的 4 種常見變形： 1.單源最短路徑（Single-source）從一個起點到所有點的最短路徑（如 Dijkstra、Bellman-Ford）。 2.單終點最短路徑（Single-destination）所有點到一個終點的最短路徑（可視為反圖的單源問題）。 3.單對點最短路徑（Single-pair）僅查詢某個特定點對之間的最短路徑。 4.全點對最短路徑（All-pairs）圖中每對點之間的最短路徑（如 Floyd-Warshall）。 Negative-weight Edges 如果圖中沒有負權重環（cycle），即使有些邊權重是負的，最短路徑仍然是有定義的。如果有一個負權重環可以從起點走到，那最短路徑就不再有意義，因為你可以一直繞那個環、路徑越繞越短。結果會導致某些點的最短距離變成無限小（定義為 −∞）。所以：只要有負環被走到，最短路徑就不能定義，要特別偵測處理。像 Dijkstra 的演算法不允許有負權重邊（會導致錯誤計算）。 Bellman-Ford 演算法可以處理負邊，只要沒有負環存在。多數演算法能夠偵測負環，如果有，就會報告「這個圖有問題，無法定義最短路」。 Can a shortest path contain a cycle? 最短路徑中能包含「環」嗎？答案是不能：如果路徑中包含一個負環：你會一直繞它變短，所以沒有最短。如果包含一個正權重環：去掉它會讓路徑變更短，代表原本的不是最短。所以只要有環，不論正或負，都會被視為不必要，應該去除。結論：真正的最短路徑一定是無環的（acyclic）路徑。 How about 0-weight cycles? 那「權重為 0 的環」能不能存在？雖然 0 環不會改變總權重，但它也沒幫助。所以可以放心地把 0 環從路徑中刪除而不影響結果。最短路徑都可以假設是沒有環的簡單路徑（simple path），最多只有 |V|-1 條邊（最多走過每個點一次）。這裡是在強化觀念：最短路徑一定是「不重複點」的直通路徑，不會來回繞。 Representing Shortest Paths 很多應用需要不只是「距離」，還要知道「怎麼走」。所以我們會為圖中每個節點維護一個前驅節點（predecessor），從終點可以反查回去。這樣就可以從終點一路 trace 回來，找到完整路徑。 📌Predecessor Subgraph（前驅子圖）當最短路徑演算法執行時，每個節點會記錄它的前一個節點（也就是它的「π 值」）。這些前驅資訊會構成一個圖，稱為前驅子圖（predecessor subgraph）。這棵子圖就像 BFS 生成的「搜尋樹」，只不過現在是記錄最短路徑的構造過程。 📌Shortest-paths Tree（最短路徑樹）最短路徑樹定義：是從單一來源點（例如 s）出發的有向子圖，符合：所有能從 s 到達的點都包含在裡面。是一棵樹（每個點只有一個前驅）。每一條從 s 到某點的路徑，都是圖中對應的最短路徑。最短路徑本身不一定唯一（可能有多條距離一樣的路徑）。所以最短路徑樹也不一定唯一！ 📌Breadth-first Tree（BFS 樹） BFS 是一個特殊情況的最短路徑演算法，目標是找出邊數最少的路徑。對於無權圖來說，BFS 會生成一棵 BFS 樹，每條從 s 出發的路徑，就是最短路徑（最少邊數）。每個點的前驅 π[v] 就是 BFS 過程中第一次拜訪該點的來源節點。所有從 s 可達的節點會被記錄在 π 中。這棵 BFS 樹就是最短路徑樹（在邊權都為 1 的情況下）。 📌Relaxation 在最短路徑演算法中（如 Dijkstra 或 Bellman-Ford），Relaxation 是一個核心操作，其目的是不斷「嘗試更新」從起點到某一節點的目前已知最短距離。每次檢查一條邊時，都會判斷經由某個中繼點是否能讓總距離更短。如果能，就更新那個節點的距離估計值（distance estimate）與前驅（predecessor）。核心概念： 1.估計值為上界：每個節點的估計距離初始為無限大，只會隨時間降低，不會變大。 2.更新條件：如果透過中繼點的路徑比目前已知的距離更短，就進行更新。 3.更新內容：縮短該點的距離估計值。記錄是哪個點帶來這個更新（即前驅節點）。 4.只有 Relaxation 會改變估計值與前驅節點。 5.演算法差異： Dijkstra：每條邊只需 Relax 一次。 Bellman-Ford：每條邊最多 Relax |V| - 1 次（頂點數 - 1）。 RELAX(u, v, w): # u, v 是邊的起點與終點 # w(u, v) 是這條邊的權重 if v.d > u.d + w(u, v): v.d = u.d + w(u, v) v.π = u 📌Dijkstra’s Algorithm Dijkstra 演算法用來解決單源最短路徑問題，其前提是圖中所有邊的權重皆為非負值。它透過貪婪策略，每次選擇當前與起點距離估計最小的頂點，並「鬆弛」其所有鄰接邊，以更新其他頂點的最短路徑估計值。初始化所有節點的最短路徑估計為無限大、前驅為 NIL，起點 sss 的估計為 0： INITIALIZE-SINGLE-SOURCE(G, s): for each vertex v in G.V: v.d = ∞ v.π = NIL s.d = 0 DIJKSTRA(G, w, s): 1 INITIALIZE-SINGLE-SOURCE(G, s) 2 S = ∅ 3 Q = ∅ 4 for each vertex u in G.V: 5 INSERT(Q, u) 6 while Q ≠ ∅: 7 u = EXTRACT-MIN(Q) 8 S = S ∪ {u} 9 for each vertex v in G.Adj[u]: 10 RELAX(u, v, w) 11 if RELAX updated v.d: 12 DECREASE-KEY(Q, v, v.d)

-------------------------------------------------------------------------------------------------------- ### Graph Algorithms DFS 是一種圖遍歷方式，特色是「儘可能往深處走」。它會持續走訪一條路徑直到沒有未走訪的鄰居，才會回頭（backtrack）。當目前的節點沒有新邊可走時，就會回到它的前一個節點（類似迷宮中走到底才回頭）。過程會重複直到從起點可以到的所有節點都拜訪過。 DFS 探索過的邊會形成一個稱為前驅子圖的結構：這個子圖一定包含所有節點（即使來自不同來源）。每個節點 v 都會記錄從哪個節點 v.π 被拜訪而來。這些邊 (v.π, v) 組成一個或多個 DFS 樹（森林）。前驅子圖中的邊都是樹邊（tree edge），代表探索時產生的邊。 DFS(G): 對每個頂點 u：初始化 u.color = WHITE, u.π = NIL 設定 time = 0 對每個 u：如果 u.color 是 WHITE： DFS-VISIT(G, u) DFS-VISIT(G, u): time++ u.d = time u.color = GRAY 對每個 u 的鄰居 v：如果 v.color 是 WHITE： v.π = u DFS-VISIT(G, v) time++ u.f = time u.color = BLACK 📌Edges 分類 Tree Edge：當 v 是第一次被發現時，從 u → v 的那條邊就是 tree edge。 Back Edge：連接一個節點 u 回到它祖先 v 的邊。若是自環（self-loop）也算 back edge。 Forward Edge：從 u 指向一個 DFS 樹中已經探索過的子孫節點 v 的邊，但這條邊不是探索時產生的。 Cross Edge：兩個沒有祖孫關係的節點之間的邊（可以跨樹或樹內非祖先之間）。執行時間分析主程式對所有節點的迴圈是 Θ(V)。每個節點只會被 DFS-VISIT 探訪一次。每個節點的鄰居最多處理 |Adj[v]| 次。所以整體時間複雜度是 Θ(V + E)，非常高效！括號結構定理 Parenthesis Theorem 描述 DFS 中時間戳記之間的結構關係：對任兩個節點 u 和 v，有三種情況其一會成立： [u.d, u.f] 和 [v.d, v.f] 完全不重疊 → 無祖孫關係 u 的時間區間包在 v 裡 → u 是 v 的子孫 v 的時間區間包在 u 裡 → v 是 u 的子孫若 u.d < v.d，就有兩種可能： v 在 u 仍為 GRAY 時被發現 ⇒ v 是 u 的子孫。所以 v 的探索時間 v.d, v.f 包在 u.d, u.f 裡。若不是子孫關係，則區間完全不重疊。 📌Kruskal’s Algorithm Kruskal 的演算法也是一種貪婪策略，但它不從某個點擴展，而是直接處理整體邊集合。它的想法是把所有邊依權重排序後，一條一條挑最小的加進來，只要不形成環就加入生成樹。為了避免環的產生，會使用 Union-Find 結構（Disjoint Set）來確認「加入這條邊後會不會讓兩個節點連到同一顆樹」。 MST-Kruskal(G, w) 1 A = ∅ // 初始化 MST 邊集合 2 for each vertex v ∈ G.V 3 Make-Set(v) // 每個頂點視為一棵獨立的樹 4 create a single list of edges in G.E 5 sort the edges by weight w (in increasing order) 6 for each edge (u, v) in sorted list 7 if Find-Set(u) ≠ Find-Set(v) 8 A = A ∪ {(u, v)} // 加進 MST 9 Union(u, v) // 合併集合 10 return A Prim 的演算法是一種「貪婪演算法」，用來建立最小生成樹（Minimum Spanning Tree, MST）。它從某個起始點 r 開始，每次選擇目前不在樹中、但與樹相連且權重最小的邊，將相對應的頂點加入 MST。它會維護一個 min-priority queue（最小優先佇列），每個節點都有一個 .key 值，表示目前所知道的連到該節點的最小邊權重。 MST-Prim(G, w, r) 1 for each vertex u ∈ G.V 2 u.key = ∞ 3 u.π = NIL 4 r.key = 0 5 Q = ∅ 6 for each vertex u ∈ G.V 7 Insert(Q, u) 8 while Q ≠ ∅ 9 u = Extract-Min(Q) // 選擇 key 最小的 u 10 for each vertex v in G.Adj[u] 11 if v ∈ Q and w(u, v) < v.key 12 v.π = u // 更新父節點 13 v.key = w(u, v) // 更新最小邊權重 14 Decrease-Key(Q, v, w(u, v)) --------------------------------------------------------------------------------------------------------

臺東大學板

國立臺東大學資訊工程學系25/4/13

Algorithm (Part I) 大複習

Agenda，1. Insertion Sort，2. Merge-Sort，ymptotic Efficiency，currences，5.HeapSort，6.QuickSort，unting S