--- # System prepended metadata title: 課程｜演算法設計方法論 tags: [課程] --- # 演算法設計方法論 ## 1. Dynamic Programming (DP) - **Principle Of Optimality：subsize 的 optimal 解，是原 size optimal 解的一部分。** - Multistage Graph - 找出 $S\rightarrow T$ 的最短距離 - 令 $l_{ij}$ 為 $a_{ij}$ 到 $T$ 的最短距離 - $(l_{31},l_{32},l_{33})\rightarrow(l_{21},l_{22},l_{23})\rightarrow(l_{11},l_{12},l_{13})\rightarrow S$ - 令 $p_{ij}$ 為 $S$ 到 $a_{ij}$ 的最短距離 - $(p_{11},p_{12},p_{13})\rightarrow(p_{21},p_{22},p_{23})\rightarrow(p_{31},p_{32},p_{33})\rightarrow T$ - Optimal Parenthesization - $c(i,j)$ $\text{= i 到 j 的最小 cost}\\=\text{i 到 j 總和}~+~\min\limits_k(~c(i,k)+c(k+1,j)~)$ - 時間複雜度：$O(n^3)$ - Longest Common Subsequence - $L(i,j)$ $=\text{A[ 1 : i ] 和 B[ 1 : j ] 的最小 cost}\\= max\{L(i-1,j), L(i,j-1), L(i-1,j-1)+l_{ij}\}$ - 時間複雜度：$O(mn)$ - 0/1 Knapsack Problem - $f(k,g)$ $\text{= 前 k 個物品，重量限制 g 的最佳 cost}\\=p_kx_k^*+f(k-1,g-w_kx_k^*)$ $~~~~~~~~~~~=max\{f(k-1,g)~,~~p_k+f(k-1,g-w_k)\}$ - 時間複雜度：$O(nM)$，為 pseudo polynomial time - Integer Knapsack Problem - $f(k,g)$ $\text{= 前 k 個物品，重量限制 g 的最佳 cost}\\= max\{p_kx_k+f(k-1,g-w_kx_k)~|~x_k=0,1,...,g/w_k~\}$ $~~~~~~~~~~~=max\{f(k-1,g)~,~~p_k+f(k,g-w_k)\}$ - 時間複雜度為$O(nM)$，為 pseudo polynomial time - Traveling Salesman Problem - $L(i,S)$ $\text{= 從 i 出發，經過 S 所有元素再回到點 1}\\=min_{j\in S}\{d_{ij}+L(j,S-\{j\})\}$ - 時間複雜度為$O(n2^n)$ - Maximum Weight Independent Set In Tree - $M(i)$ $\text{= 選了節點 i 的最大 cost}\\=w(i)+\sum M'(j)$ - $M'(i)$ $\text{= 不選節點 i 的最大 cost}\\=\sum max(M(j),M'(j))$ - 時間複雜度為$O(n)$ ## 2. Prune-and-Search (P&S) - 時間複雜度可表示為 $T(n) = T((1 - α)n) + p(n)$ - $T(αn)$ 是被刪除的那些子問題 - $p(n)$ 為了刪除不重要的子問題所花的時間 - **Binary Search** - **[Selection Problem](https://ideone.com/uSuPXu)** - 1：把原本數列 5 個一組，共 $\lceil n/5\rceil$ 組， $O(1)$ 算出每一組 median - 2：把 $\lceil n/5\rceil$ 組的 median，挑出 median of median，花時間 $T(n/5)$ - 3：以 MOM 把數列分成三個 set，花時間 $O(n)$ - 4：至少可以刪除掉 $n/4$ 的答案，變成 size 更小的子問題 $T(3n/4)$ - 5：重複直到可以 $O(1)$ 解掉 - 時間複雜度：$T(n)=T(n/5) + O(n) +T(3n/4) = O(n)$ - **The 2-dimensional linear programming problem** - 1：所有限制條件中，如果有垂直線，則更新 $x_l,~x_r$ - 2：根據 $b$ 的正負號，把限制條件分成 $I^+$ 和 $I^-$ - 3：把 $I^+$ 和 $I^-$ 同一組中的線，兩兩配對求交點 - 如果平行的話，一條可以捨去 - 如果交點在 $x_l,~x_r$ 之外，一條可以捨去 - 4：對所有在 $[x_l,x_r]$ 中的交點 $r$，找出 median $x_m$ - 5：找出 $x^*$ 在 $x_m$ 哪一側 - 如果 $x_m = x^*$ 或是 無解，則演算法結束 - 否則更新 $x_l 或 x_r$ - 6：約有 $n/4$ 對可以確定交點和 $x^*$ 相對位置，每一對 prune 掉其中一條線 - 根據講義有六種不同的 case - 7：重複直到可以在 $O(1)$ 直接解出 - 時間複雜度：$T(n) \le T(3n/4) + O(n) = O(n)$ - **The 1-dimensional smallest circle enclosing n points** - 1：把所有點兩兩配成一對，有 $n/2$ 對 - 2：找出每對中垂線和 $y=y_m$ 的交點 - 如果有兩點落在同一條鉛直線上，prune 掉離 $y=y_m$ 比較近的那點。 - 3：找出這些交點的 median $x_m$ - 4：找出 $x^*$ 在 $x_m$ 的哪一側 - 定義 $I$ 為最遠點，看 $I$ 的分布是在兩側或同一側 - 5：約有 $n/4$ 對可以確定中垂線交點和 $x^*$ 相對位置，每一對 prune 掉比較近的點 - 6：重複直到可以在 $O(1)$直接解出 - 時間複雜度：$T(n) \le T(3n/4) + O(n) = O(n)$ - **The 2-dimensional smallest circle enclosing n points** - **給定一條直線，可以在 $O(n)$ 決定 $(x_c,y_c)$ 在直線的哪一側。** - 首先找到該直線上最好的點 $(x^*,y_m)$ - 再根據 $I$ 的分布決定在直線的哪一側 - 只有一點：知道哪一側 - 有 arc 大於 180 度：$(x^*,y_m)$ 就是最佳解 - 沒有 arc 大於 180 度：根據 $p$ 和 $q$ 哪一側點比較近，可知道哪一側 - 1：把所有點兩兩配成一對 $(p,q)$，共 $n/2$ 對 - 2：每對找出中垂線 $L$，共 $n/2$ 條 - 3：每條中垂線算和 $x$ 軸夾角 $α$ - 4：找出所有夾角的 median，$α_m$ - 5：把中垂線依夾角分成兩堆 $L^+,~L^-$，每堆有 $n/4$ 條 - 6：把 $L^+$ 和 $L^-$ 的中垂線兩兩配成一對，共 $n/4$ 對 - 每一對恰好都有一條線角度 $>α_m$，有一條線角度 $<α_m$ - 7：**每一對解出中垂線交點，有n/4點。$\rightarrow$ 標的** - 8：找出斜率為 $α_m$ 且平分中垂線交點的線 $LA$，兩側各有 $n/8$ 點 - 9：決定 $(x_c,y_c)$ 在這條線 $LA$ 哪一邊 - 10：找出鉛直線 $LB$，把 $LA$ 中 $(x_c,y_c)$ 的另一側交點平分，兩側各有 $n/16$ 點 - 11：決定 $(x_c,y_c)$ 在這條線 $LB$ 哪一邊 - 12：現在平面被分成四個區域，把 $(x_c,y_c)$ 的對面區域，挑出不會碰到 $(x_c,y_c)$ 的中垂線，有 $n/16$ 條，每條可以挑出離 $(x_c,y_c)$ 比較近的點，有 $n/16$ 點，把他們 prune 掉 - 13：重複直到可以在 $O(1)$ 直接解出 - 時間複雜度：$T(n) \le T(15n/16) + O(n) = O(n)$ - **Weighted Center of a Tree** (作業) - **給定距離 leaf node $t$ 的點 $x$，可以在 $O(n)$ 決定 center 在 $x$ 哪一側。** - 1：花 $O(n)$ 找出 $T$ 的 Centroid $c$ - 2：花 $O(n)$ 時間，決定 center 在 c 的哪一子樹 - (1)如果鄰居滿足 $r(x)=r_i(x)=r_j(x)$，則這時 $x$ 就是center - (2)否則也可以知道 center 在某個 $T_i(x)$上 - 3：對所有不在 $T_i(x)$ 的 vertex，至少有 $n/2$ 個，把他們配成 $n/4$ 對 - 每一對 $(u,v)$ ，去算出 $t$ 值使得 $w_u(d(u,x)+t) = w_v(d(v,x)+t)$ - 如果 $t$ 不存在，則可以 prune 掉其中一個 vertex - 4：把那些 $t$ 挑出 median $t_m$ 出來 - 5：決定 center 在 $T_i(x)$ 中和 $x$ 距離 $t_m$ 地方的相對位置 - 6：約有 $n/8$ 對可以確定 center 和兩點的相對位置，每一對 prune 掉一個點 - 7：剩下的點仍然會形成一棵樹，整理成 size 為 $7n/8$ 的相同問題 - 8：重複直到可以在 $O(1)$ 解完 - 時間複雜度：$T(n) \le T(7n/8) + O(n) = O(n)$ ## 3. Branch-and-Bound (B&B) - 基本觀念 - **通常是求最大值或最小值的 NP hard 問題，用樹展開所有可能性**： - BFS ： 從最上層 state 先展開 - DFS ： 從現在 state 先展開 - DFID ： DFS 但是每次限定展開層數 - Best First Search ： 每一個state量化成分數，透過該分數來選擇 - Hill Climbing ： 透過量化資料，決定 DFS 要進入哪個 state - 對一個最大化的問題 - 整棵樹：紀錄目前最大的可行解，也就是 optimal value 的 **lower bound**。 - 每節點：計算 **upper bound**，也就是可以達到的最大值。 - **Branch：** - 選擇最大 upper bound 的節點，把它展開下一層 - **Bound：** - 某節點 **UB** $\le$ 整棵樹 **LB** ，則該節點以下不用展開。 - The 0/1 Knapsack problem - 問題： - $\max 10x_1+10x_2+12x_3+18x_4$ - $2x_1+4x_2+6x_3+9x_4\le15,~~x_i\in\{0,1\}$ - 整棵樹的 lower bound： - 從左到右依序 assign 1 或 0 得到 feasible solution。 - 每個節點的 upper bound： - 用 greedy 的方式從 CP 值最高的物品開始選。 - 例子： - ![](https://i.imgur.com/8HZzOWf.png) - The Traveling Sales Man - 問題： - 給定 $DAG$，求出經過每個點 weight 最小的 path - ![](https://i.imgur.com/JR3lG5u.png) - 觀察： - 每個節點存一個 reduced cost matrix $A$ - 轉換到下一節點時 - 把 $A$ 的 **row** $i$ 和 **col** $j$ 全設成 $\infty$ - 把 $A(j,1)$ 設成 $\infty$ - 計算 reduced cost $r$ - 整棵樹的 upper bound： - 走到 leaf node，或任找 feasible solution，紀錄可行解的最小值。 - 每個節點的 lower bound： - $R\rightarrow S$ - $lb_S=lb_R+A(i,j)+r$ - 也就是 cost matrix 的 reduced cost，至少要花這麼多 weight - The A* Algorithm - 本質上就是一種 best first search，自己定義一個 evaluation function，再展開最有可能的 node。 - **最大值的問題不可以低估，最小值的問題不可以高估** - 以 shortest path 為例： - ![](https://i.imgur.com/dxCg6Qm.png) - 定義 cost function $f(i)$： - $S$ 到 $i$ 距離 $+$ $i$ 的最小向外距離 - 沒有高估 - ![](https://i.imgur.com/CdyFpnh.png) - 第一個回合展開 $v_1$ - ![](https://i.imgur.com/1lCMIBW.png) - 第二個回合展開 $v_2$ 或 $v_4$ ## 4. Divide-and-Conquer (D&C) - 基本觀念 - ![](https://i.imgur.com/qxRV3Df.png) - **Divide**：切割問題成子問題 - **Conquer**：遞迴呼叫相同演算法 - **Merge**：將子問題的答案，組合出原本問題的答案 - 最複雜的分析是 Merge： - 1.$T(n)=2T(n/2)+O(1)=O(n)$ - 2.$T(n)=2T(n/2)+O(n)=O(nlogn)$ - 3.$T(n)=2T(n/2)+O(n^2)=O(n^2)$ - **Merge Sort** - Merge 步驟： - 用 $O(m+n)$ 將兩個 sorted array 合成一個 sorted array。 - $T(n)=2T(n/2)+O(n)=O(nlogn)$ - **Matrix multiplication** - 一般作法： - ![](https://i.imgur.com/fbl9npI.png) - $T(n)=8T(n/2)+O(n^2)=O(n^3)$ - Strassen’s Method： - ![](https://i.imgur.com/zgzo4Fc.png) - $T(n)=7T(n/2)+O(n^2)=O(n^{log_27})$ - **The Convex Hull Problem** - Graham’s Scan - 1.任意挑一個 Convex Hull 內部的點 $x$。 $O(1)$ - 2.將所有點，依照和 $x$ 夾角排序。 $O(nlogn)$ - 3.任意挑一個 Convex Hull 上的點 $y$。 $O(n)$ - 4.依照排序結果從 $y$ 開始，每三點挑出在 convex hull 上的點。 $O(n)$ - 依照中間的點是否再比較近的地方分成兩種 case。 - 時間：$T(n)=O(nlogn)$ - Jarvis’ March - 1.任意挑一個 Convex Hull 上的點 $y$。 $O(n)$ - 2.從 $y$ 開始，逆時針挑出在 convex hull 上的點。 $O(hn)$ - 時間：$T(n)=O(hn)$ - Divide-and-Conquer (基本上是 Graham’s Scan 的延伸) - Divide and Conquer： - 分成兩個相等大小子問題 $A,B$ ，遞迴解決 $CH(A),CH(B)$ - Merge： - 1.任意挑一個 $CH(A)$ 內部的點 $p$。 $O(1)$ - 2.決定 $p$ 是否在 $CH(B)$ 內部。 $O(n)$ - 在內部：直接將兩個 sorted list 合成一個 sorted list。 - 在外部：透過 $CH(B)$ 和 $p$ 相對位置，合成一個 sorted list。 - 找出 $CH(B)$ 中夾角最大和最小的點 $u,v$，看是否都在 $p$ 同一側 - 3.利用 Graham’s Scan ，每三點挑出在 $CH(A\cup B)$ 上的點。 $O(nlogn)$ - 時間：$T(n)=2T(n/2)+O(n)=O(nlogn)$ - **The 2-dimensional closest pair problem** - Presort 所有點 $y$ 座標，得到 $y$ 的順序。(在最一開始) - 1.Divide：依照 $x$ 座標，將點分成相同大小左右兩部分 $L,R$。 - 2.Conquer：$L,R$ 分別去解出最近距離 $d_L,d_R$。 - 3.Merge： - 對於左右的 sorted list $S_L,S_R$，找出距離比 $min(d_L,d_R)$ 還要小的點對。 - 方法一：使用兩個指標，比較複雜。 - 方法二：先 merge 成一個 sorted list，每個點只要比較 6 個點。 - 時間：$T(n)=2T(n/2)+O(n)=O(nlogn)$ - **The Iso-Oriented Line Segment Intersection Problem** - Presort 所有垂直線兩端點 $y$ 座標，得到 $y$ 的順序。(在最一開始) - **標的：垂直線，水平線的端點。** - 1.Divide：依照 $x$ 座標，將標的分成相同大小左右兩部分 $L,R$。 - 2.Conquer：$L,R$ 分別紀錄： - ![](https://i.imgur.com/SkiGbH4.png) - type 1,2,3 的 Intersection Point。 - 右邊界上水平線的照 $y$ 順序 $\tilde{R}$ - 左邊界上水平線的照 $y$ 順序 $\tilde{L}$ - $V$：垂直線照 $y$ 排序。 - 3.Merge： - 給定：$\tilde{L}_L,\tilde{R}_L,\tilde{L}_R,\tilde{R}_R$ - $\tilde{L}\tilde{R}\leftarrow\tilde{R}_L\cap\tilde{L}_R$ - $\tilde{L}\leftarrow\tilde{L}_L+(\tilde{L}_R-\tilde{L}\tilde{R})$ - $\tilde{R}\leftarrow\tilde{R}_R+(\tilde{R}_L-\tilde{L}\tilde{R})$ - 給定 $V_L,V_R$ 為左右兩部分垂直線，找出 Intersection Point。 - $V_L$ 和 $\tilde{L}_R-\tilde{L}\tilde{R}$ 的 Intersection Point。 - $V_R$ 和 $\tilde{R}_L-\tilde{L}\tilde{R}$ 的 Intersection Point。 - 時間： - $T(n)=2T(n/2)+O(n)=O(nlogn)$ - 總共 $=T(n)+O(nlogn)+O(s)=O(nlogn+s)$ - **Voronoi Diagram Construction** - 問題定義與介紹： - 平面上給定 $n$ 個點，找出每個點 $i$ 的地盤 $V(i)$。 - 每一個 Voronoi Diagram ，有一個對應的 Delaunay graph。 - 如果沒有四點共圓，則對應的為 Delaunay triangulation。 - 定理：每一個 $n$ 點的 Voronoi Diagram，最多只有 $2n-4$ 個點和 $3n-6$ 個邊。 - 定理：一個 Voronoi Polygon $V(i)$ 是 unbounded $\iff$ $i$ 在圓圖的 convex hull 上。 - 一個 Voronoi Diagram 包含以下資料(結構)： - Voronoi vertices 的點座標 - Voronoi edges 連結那些 Voronoi vertices - Voronoi edges 對應原圖的兩點 - 原圖每點的照順時針序的每個 Voronoi edges - 分治解法： - 1.Divide：依照 $x$ 座標，將點分成相同大小左右兩部分 $L,R$。 - 2.Conquer：$L,R$ 分別去解出 $VD(L),VD(R)$。 - 3.Merge：找出 dividing line $P$，使得到 $L$ 和 $R$ 一樣近，並刪除 $VD(L),VD(R)$ 超過 $P$ 的部分。 - ![](https://i.imgur.com/cj2vRAo.png) - 定理：dividing line $P$ 是 $y$ 的連續函數，且頭尾是兩條射線。 - 找 $P$ 的兩個步驟： - Step 1：找出頭尾兩條射線 - 射線必定是 $CH(L\cup R)$ 上，一個橫跨 $L$ 和 $R$ 的邊的中垂線 - 1.我們透過 $VD(L),VD(R)$ 去找 $CH(L),CH(R)$ - 2.透過 $VD(L),VD(R)$ 合成 $CH(L\cup R)$ 並找出對應的邊及中垂線。 - Step 2：透過 zigzag walk 找到 $P$ - 觀察： - $P$ 總是往下走 - 當碰到 $VD(L)$ 的邊時，要往右轉。 - 當碰到 $VD(R)$ 的邊時，要往左轉。 - 1.檢查 $P$ 現在在 $VD(L)$ 和 $VD(R)$ 離哪個點最近 - 2.比較會先碰到 $VD(L)$ 的邊或是 $VD(R)$ 的邊。 - 時間：$T(n)=2T(n/2)+O(n)=O(nlogn)$ - 其他常見應用： - 1.All Nearest Neighbor 最近鄰居 - 問題：給定平面上 n 個點，找出每個點的最近鄰居集合。 - 一個點 $i$ 和其最近鄰居，定義了 $V(i)$ 的其中一邊。 - 因此給定 $VD(G)$ ，則可以在 $O(n)$ 解完此問題。 - 2.Nearest Beighbor Search Problem - 問題：給定平面上 n 個點。每次 query 點 $x$，找出 $x$ 的最近鄰居集合。 - 1.先花 $O(nlogn)$ 時間，$O(n)$ 空間，建構 Voronoi Diagram。 - 2.每次花 $O(logn)$ 時間，尋找點 $x$ 位在哪一個 Voronoi Polygon 內部。 - 3.Euclidean Minimum Spanning Tree Problem 平面上找最小生成樹 - Kruskal：$O(n^2)$ - Prim：$O(n^2logn)$ - 定理：每個 Euclidean Minimum Spanning Tree 都是 Delaunay graph 的子圖。 - 定理：Planar Graph 的 MST 問題可以在 $O(n)$ 解完。 - 1.花 $O(nlogn)$ 時間，建構 Voronoi Diagram。 - 2.花 $O(n)$ 時間，建構 Delaunay Graph。 - 3.花 $O(n)$ 時間，找 Delaunay Graph 上的 Minimum Spanning Tree。