# 演算法設計方法論

## 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 值最高的物品開始選。
- 例子：
- 
- The Traveling Sales Man
- 問題：
- 給定 $DAG$，求出經過每個點 weight 最小的 path
- 
- 觀察：
- 每個節點存一個 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 為例：
- 
- 定義 cost function $f(i)$：
- $S$ 到 $i$ 距離 $+$ $i$ 的最小向外距離
- 沒有高估
- 
- 第一個回合展開 $v_1$
- 
- 第二個回合展開 $v_2$ 或 $v_4$
## 4. Divide-and-Conquer (D&C)
- 基本觀念
- 
- **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**
- 一般作法：
- 
- $T(n)=8T(n/2)+O(n^2)=O(n^3)$
- Strassen’s Method：
- 
- $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$ 分別紀錄：
- 
- 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$ 的部分。
- 
- 定理：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。