###### tags: `演算法` # 演算法 期末整理 (done) ## 1. (DP)多階圖最小成本路徑 ==似乎不考(?)== ![](https://i.imgur.com/P33raTt.png) `Input:` $具n個頂點的k階多階圖G(V,E), 其中V=⋃_{i=1..k} P_i, P_i \cap P_j = \varnothing for \ i \neq j, \\ P_1 = \{s\}, P_k = \{t\}, <x,y> \in E \rightarrow (x \in P_i \wedge y \in P_{i+1}), <x,y>的權重為w[x,y]$ `Output:`$path[1..k], d[s], 其中path[1..k]紀錄第1階(節點1)到第k階(節點n)的最小成本路徑, \\ d[s]紀錄最小成本路徑總成本$ ```cpp= d[t] = 0; d[x] = INF, for x != t; // 陣列d[x]儲存節點x到節點t的最小距離 for i = k-1 to 1 do // 由第k-1階到第1階 for every node x in P_i do for every edge (x, y) in E do if (d[x] > w[x,y] + d[y]) do d[x] = w[x,y] + d[y] next[x] = y // 代表在最短路徑中節點x的下節點為y path[1] = s; path[k] = t; // path[j]表示路徑中第j階的節點 for j = 2 to k-1 do path[j] = next[path[j-1]]; return path[s], d[s] ``` ## 2. (DP)矩陣鏈乘積 `Input:` $陣列 p[1...n], 代表矩陣 A[i] 的維度為 p[i-1] * p[i]$ `Output:`$最小乘法次數m[1,n], 矩陣乘法分割位置s$ ```cpp= MATRIX_CHAIN_ORDER(p) n = length[p]–1 // 矩陣數 for i = 1 to n m[i,i] = 0 for l = 2 to n // level 2 to n for i = 1 to n–l+1 j = i+l–1 m[i,j] = INF for k = i to j–1 q = m[i,k] + m[k+1,j] + p[i-1]*p[k]*p[j] if q < m[i,j] m[i,j] = q s[i,j] = k return m[1,n], s ``` Example: `p = [30, 35, 15, 5, 10, 20, 25]` ![`矩陣圖`](https://i.imgur.com/pc9vuMU.png) ```cpp= PRINT_OPTIMAL_PARENS(s, i, j) if i == j print "A_i" else print "(" PRINT_OPTIMAL_PARENS(s, i, s[i,j]) PRINT_OPTIMAL_PARENS(s, s[i,j]+1, j) print ")" ``` ## 3. (DP)最小編輯成本 ==似乎不考(?)== * 定義：給定字串A,B，利用以下操作將A改成B的最低成本 * 操作1(Cost1): 在字串A刪除一個字元 * 操作2(Cost2): 在字串A插入一個字元 * 操作3(Cost3): 在字串A將一個字元換成另一個字元 * c[i, j] 中儲存將 A 的子字串 $a_1a_2...a_m$ 轉為 B 的子字串 $b_1b_2...b_n$ 的最小成本， 其中 $0 \leq i \leq m$ 且 $0 \leq j \leq n$ ```cpp= // 邊界條件 for i = 0 to m c[i,0] = i * Cost1 for j = 0 to n c[0,j] = j * Cost2 // 遞迴關係 if a_i == b_j c[i,j] = c[i-1,j-1] else c[i,j] = min(c[i-1,j] + Cost1, c[i,j-1] + Cost2, c[i-1,j-1]+ Cost3 ) // 答案 return c[m,n] ``` ## 4. (DP)最佳二元搜尋樹 (類似2.) `Input:` $陣列 p[i = 1...n], 代表已排序序列K=<k_1, ..., k_n>被搜尋機率， \\ 陣列 q[i = 0...n], 代表搜尋目標 d_i 不在K中的機率, 其中 k_i < d_i < k_{i+1}$ `Output:`$最佳二元搜尋樹的期望搜索成本e[1,n], 各子樹樹根root$ ```cpp= OPTIMAL_BST(p,q,n) for i = 1 to n+1 e[i,i–1] = q[i-1] w[i,i–1] = q[i-1] for l = 1 to n // level 1 to n for i = 1 to n–l+1 j = i+l–1 e[i, j] = INF w[i, j] = w[i, j–1] + p[j] + q[j] // 第i~j項機率總和 for r = i to j t = e[i,r–1] + e[r+1,j] + w[i,j] if t < e[i,j] e[i,j] = t root[i,j] = r return e[1,n], root ``` Example: `p = [0.15, 0.10, 0.05, 0.10, 0.20]` `q = [0.05, 0.10, 0.05, 0.05, 0.05, 0.10]` ![`矩陣圖`](https://i.imgur.com/2iE2Sdz.png) ## 5. (DP)子集合加總 (類似0/1背包) ![子集合加總問題](https://i.imgur.com/b5DipRa.png) ![子集合加總演算法](https://i.imgur.com/TueF5bk.png) ## 6. Tree Searching ### 6-1. 廣度優先搜尋(BFS) ```= 設定起始節點p為解答空間樹的root，並建立一個只包含p的queue。 檢查queue的第一個元素是否為目標節點。若是，則輸出目標節點所對應的解答並停止。 移除queue的第一個節點，將其未被拜訪過的子節點一一加入queue。 若queue為空，則回報無解答並停止。否則，跳至步驟2。 ``` [`BFS舉例`](https://i.imgur.com/NTgGQ90.png) ### 6-2. 深度優先搜尋(DFS) ```= 設定起始節點p為解答空間樹的root，並建立一個只包含p的stack。 檢查stack的頂端元素是否為目標節點。若是，則輸出目標節點所對應的解答並停止。 移除stack的頂端節點。將其未被拜訪過的子節點一一加入stack。 若stack為空，則回報無解答並停止。否則，跳至步驟2。 ``` [`DFS舉例1`](https://i.imgur.com/EXRyZsU.png) [`DFS舉例2`](https://i.imgur.com/uPgfzS4.png) ### 6-3. 登山搜尋(Hill-climbing Search) = DFS + 評估函數 ```= 設定起始節點p為解答空間樹的root，並建立一個只包含p的stack。 檢查stack的頂端元素是否為目標節點。若是，則輸出目標節點所對應的解答並停止。 移除stack的頂端節點。將其未被拜訪過的子節點[由評估函數所算的優先度低的先加入]stack。 若stack為空，則回報無解答並停止。否則，跳至步驟2。 ``` [`HCS舉例`](https://i.imgur.com/rYlEJXj.png) ### 6-4. 最佳優先搜尋(Best-Frist Search) = BFS + DFS + 評估函數 ```= 設定起始節點p為解答空間樹的root，並建立一個只包含p的heap。 檢查heap中優先度最高的元素是否為目標節點。若是，則輸出目標節點所對應的解答並停止。 移除heap優先度最高的節點。將其未被拜訪過的子節點[由評估函數所算的優先度]加入heap中。 若heap為空，則回報無解答並停止。否則，跳至步驟2。 ``` [`Best-Frist Search舉例`](https://i.imgur.com/SajCveP.png) ### 6-5. 實例 * 漢米爾頓迴路 **[NPC問題]** ![](https://i.imgur.com/m6t7WJn.png) * [解答空間樹_完整](https://i.imgur.com/O0rBzD2.png) * [解答空間樹_廣度優先](https://i.imgur.com/E9AxpcT.png) * [解答空間樹_深度優先](https://i.imgur.com/B7lJLT1.png) * 旅行銷售員問題：求出「邊加權總合最小或長度最短」的漢米爾頓迴路 [**NP-hard問題**] * 尤拉迴路問題 * 尤拉路徑 or 尤拉鏈：無向圖上經過每個邊恰好一次的路徑。 **[P問題]** * 尤拉迴路：無向圖上經過每個邊恰好一次的迴路。 **[P問題]** ## 7. 回溯演算法 #我覺得根本就是DFS = = * 八皇后問題 * 皇后棋子：可以從八個方向攻擊對方的棋子。 * 如何在一個8×8的西洋棋棋盤上放置8個不會互相攻擊的皇后棋子。 ```cpp= PutQueen(i,n) // 以放有i個皇后，總共要放n個皇后 j = 0 // j代表行(column)編號, j = 0 to n-1 while j < n if i列j行可放置皇后棋子 q[i] = j // 編號為i的皇后放在第i列第j行上 if i == n-1 // n個皇后棋子均已放置妥當 return q else PutQueen(i+1,n) j++ return Failure ``` [`圖解，讓你看看什麼是回朔ㄏㄏ，根本就只是stack退回去啊= =`](https://i.imgur.com/q1ezr34.png) ## 8. 分支定界演算法 * 重點： * 找出好的機制在搜尋解答的過程中，擴展解答空間樹產生分支。 * 找出好的機制設定**上界**與**下界**，使許多分支**終止搜尋**。 * [旅行推銷員問題之分支(重點)](https://i.imgur.com/Hv9gHLd.png)，其他請看PPT。 ## 9. A*演算法 = 最佳優先搜尋 + 「特殊」評估函式 * 可被視為一個分支定界演算法的特例，當第一個可行解被走訪時，所有在堆積(優先佇列)中的節點都被終止。 * 評估函式：$f(n) = g(n) + h(n)$ * $g(n):$ 從root至節點n的==當前成本==。 * $h(n):$ 從節點n到目標節點的==評估的未來成本==。 * $h^*(n):$ 從節點n到目標節點的==**實際**的未來成本==。 * $f^*(n):$ 從root至節點n再到目標節點的==**實際**成本==。 * $h(n) \leq h^*(n)$ * 證明： 1. $f(n) = g(n)+h(n) \leq g(n)+h^*(n) = f^*(n)$ 2. 令 $x$ 為目標節點。可得 $f^*(x) = f(x)+h(x) = f(x)+0 = f(x)$ 3. 假設 $x$ 不是最佳節點，則必存在一個已存在heap中的，但是未被選擇的節點 $y$，使得 $f^*(y) < f^*(x)$ 4. 因我們使用最佳優先搜尋法，故可得 $f(x) \leq f(y)$ 5. 由不等式(1)(2)(4)可得 $f^*(x) = f(x) \leq f(y) \leq f^*(y)$ $\rightarrow f^*(x) \leq f^*(y)$，與(3)矛盾，故得證 $x$ 為最佳節點。 * [解多階圖最短路徑問題](https://imgur.com/a/f74Jc)（from PPT） ## 10. 最大流演算法 ```c= FORD_FULKERSON(G,s,t) for each edge (u,v) in E of G f[u,v] = 0 f[v,u] = 0 while there exists a path p from s to t in the residual network G_f c_f(p) = min(c_f[u,v]: (u,v) in p) // 流量最小邊的值 for each edge (u,v) in p f[u,v] = f[u,v] + c_f(p) f[v,u] = f[v,u] - c_f(p) c[u,v] = c[u,v] - c_f(p) c[v,u] = c[v,u] + c_f(p) ``` [`Ford-Fulkerson演算法 圖解`](https://i.imgur.com/Og6yRzO.png) [`Edmons-Karp演算法`](https://i.imgur.com/QKWGUig.png)` = Ford-Fulkerson演算法 + BFS` [`多起點終點 => 單起點&終點`](https://i.imgur.com/KzaOkHS.png) ## 11. 最小成本最大流演算法 * 最小成本最大流問題為 * 先找出由源點到匯點的最大流 * 再找出達成此最大流的最小成本 * [\[複習\] Bellman-Ford最短路徑演算法](https://i.imgur.com/k6TCfdY.png) ```cpp= Min_Cost_Max_Flow(G) 先不看成本參數找出最大流f 加入成本參數計算f的成本c while true 計算G_f 用Bellman-Ford在G_f上找負成本循環 if 無負成本循環 return f, c else 在循環中環繞以減低總成本直到循環中的一個邊的容量用盡為止 ``` ## 12. [匈牙利演算法](https://zh.wikipedia.org/wiki/%E5%8C%88%E7%89%99%E5%88%A9%E7%AE%97%E6%B3%95) 解 ==**最大權重完美二分匹配**== $\leftrightarrow$ 解 ==**最大化問題**== [二分匹配(Bipartite Matching)](http://www.csie.ntnu.edu.tw/~u91029/Matching.html#2) 用匈牙利演算法解決最大化問題，先將各個元素換成以最大元素減去其本身。 接著套用標準的匈牙利演算法： ```cpp= 藉由列的減法變轉陣列：每一列皆減去該列中的最小元素。 計算覆蓋元素0的最少直線數。如果直線數與陣列的大小相同，跳到步驟6。 藉由行的減法變轉陣列：每一行皆減去該行中的最小元素。 計算覆蓋元素0的最少直線數。如果直線數與陣列的大小相同，跳到步驟6。 找出未被覆蓋的元素中最小者，將所有未覆蓋元素中減去此元素值，並增加這個元素值到被兩條直線覆蓋的元素中，回到步驟4。 只從元素0去找出極大二分配對，並套用此配對到原始陣列中以找出最小成本。 ``` ## 13. 問題變轉(Problem Reduction) * $A \propto B:$ 問題 $A$ 變轉為(reduces to)問題 $B$。 * 若且唯若$A$可藉由任何能解決$B$的演算法而獲得解決。 * ![](https://i.imgur.com/Mg6v9Ug.png) * $LowerBound(B) = T(ALG_B)$ * $LowerBound(A) \leq T(ALG_A) \leq T(tr_1) + T(ALG_B) + T(tr_2)$ * if $T(tr_1) + T(tr_2) \leq L(A) \\ \rightarrow L(A) \leq T(ALG_A) \leq T(ALG_B) = L(B) \\ \rightarrow 假設A的下界是已知的，若A \propto B，且變轉中的轉形時間複雜度比A的問題下界還低，\\ 則A的下界亦是B的下界。$ * [凸包問題(The convex hull problem)](https://i.imgur.com/RAVq46g.png) * [凸包(convex hull)問題的下界](https://i.imgur.com/IvL9lCu.png) * $\because「排序問題」\propto「凸包問題」，且「排序問題」的下界為 \Omega(nlogn)$ $\therefore「凸包問題」的下界亦為 \Omega(nlogn)$ ## 14. NP-Completeness理論 #幹拎德這是三小鬼東西= = * ![](https://i.imgur.com/N5daReA.png) * P：此類問題，可用 ==**確定性**多項式(時間)== 演算法解決。 * NP：此類==決策問題==，可用 ==**非確定性**多項式(時間)== 演算法解決。 * NP-hard：每個NP問題皆可 ==多項式時間**變轉**== 為此類問題。 * NP-complete (NPC)：此類問題 ==屬於**NP-hard**也屬於**NP**==。 * ==確定性==演算法：需滿足以下條件 * 0或多個輸入 * 1個以上的輸出 * 有限性(finiteness)：步驟數有限而且步驟執行會終止 * 明確性(definiteness)：每個步驟必須明確且不含糊(unambiguous) * 有效性(effectiveness)：每個步驟必須是有效可行的(feasible) * ==非確定性==演算法 * 包含兩個階段： 1. 猜測(guess) / 選擇(choice) 2. 檢查(check)：檢查後使演算法「==成功/不成功==」結束 * 假設：NP演算法永遠會在第一階段非確定性地(事先無法確定地知道結果)做出對的猜測或選擇使演算法成功結束。 * 實務面：能執行NP演算法的機器目前==並不存在== * 理論面：若問題$A$能以NP演算法解決，則$A \in$ **NP** * 三個特別敘述： 1. `Success`：演算法成功結束 2. `Failure`：演算法不成功結束 3. `Choice(S)`：從集合S裡任意地選出一個元素，$O(1)$ * 假設: `Choice(S)`是一個非確定性敘述，但它一定會挑中一個可以讓演算法成功結束的元素(除非這種元素不存在)。 * 實例：[非確定漢米爾頓迴路演算法](https://i.imgur.com/KRN8Qpw.png) $\rightarrow 「漢米爾頓迴路問題」\in$ **NP** * 問題的 ==決策版本== vs ==原始版本== * 例如：旅行銷售員(TSP)問題 * 原始版本$O$：給定圖找最短的旅途(tour)或巡環(cycle) * 決策版本$D$：給定圖是否具有一個旅途的總長度$\leq$常數c * 答案只會是：是 or 否 * $D \propto O$ * ==**NPC證明**== 方法 * 欲證明 $Q \in$ **NPC**： 1. 證明 $Q \in$ **NP**：寫一個可解 $Q$ 的NP演算法 2. 證明 $\exists \ Q' \in$ **NPC** s.t. $Q' \propto Q$ * 存在一個函數$f(x)$為polynomial-time computable * $f(x)$使得對所有 $x$ 而言，$x\in L_1$ iff $f(x) \in L_2$。 ($L_1$ 為 $Q’$ 問題的解集合；$L_2$ 為 $Q$ 問題的解集合) * 已知的**NPC**問題：**SAT**問題(滿足問題，**Sat**isfiability Problem)： * 給一個布林函數$E(x),x=\{x_1,...,x_n\}$，若存在一組輸入當作 $x$ s.t. $E(x)=True$，則回傳`Success`；否則回傳`Failure`。 * $E(x)$ 為[CNF](https://zh.wikipedia.org/wiki/%E5%90%88%E5%8F%96%E8%8C%83%E5%BC%8F)，即數位電路中的product of sum，例：$(x_1 \lor x_2) \land (x_4 \lor \lnot x_5)$ * Cook’s Theorem：證明**SAT**問題 $\in$ **NPC**，[詳細](https://en.wikipedia.org/wiki/Cook%E2%80%93Levin_theorem#Proof)就別看了，很難也不重要Orz 1. 所有**NP**問題 $\propto$ **SAT**問題 2. **SAT** $\in$ **P** $\leftrightarrow$ **NP** = **P**，但目前無法證明，也似乎不成立 * [舉例：證明3SAT問題為NPC](https://imgur.com/a/cn0oX) * 已知的**NPC**問題： 1. SAT問題 2. 3SAT問題：如 $E(x) = (x_1 \lor x_2 \lor \lnot x_4) \land (\lnot x_3 \lor x_4 \lor \lnot x_5)$，變數三個一組 3. [集合覆蓋問題](https://zh.wikipedia.org/wiki/%E9%9B%86%E5%90%88%E8%A6%86%E7%9B%96%E9%97%AE%E9%A2%98) 4. 0/1背包問題 5. 旅行推銷員問題 6. [分割問題](https://i.imgur.com/0d4fBV7.png) 7. [著色問題](https://zh.wikipedia.org/wiki/%E5%9B%BE%E7%9D%80%E8%89%B2%E9%97%AE%E9%A2%98) 8. 完全圖或[分團問題](https://zh.wikipedia.org/wiki/%E5%88%86%E5%9C%98%E5%95%8F%E9%A1%8C) 9. [點覆蓋問題](https://zh.wikipedia.org/wiki/%E8%A6%86%E7%9B%96_(%E5%9B%BE%E8%AE%BA)) 10. [支配集合問題](https://i.imgur.com/WxhKW95.png) * 參考：from 課程網站 * [Recipe, Cook and Carp](http://staff.csie.ncu.edu.tw/jrjiang/alg2017Fall/Recipe,%20Cook%20and%20Carp.pdf) * [NPC理論測驗及解答](http://staff.csie.ncu.edu.tw/jrjiang/alg2017Fall/AlgQuiz%28ANS%292013-11-26.pdf)