###### tags: `演算法`

# 演算法 期末整理 (done)

## 1. (DP)多階圖最小成本路徑 ==似乎不考(?)==
`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]紀錄最小成本路徑總成本$

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$

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]`

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$

// 邊界條件
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$

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]`

## 5. (DP)子集合加總 (類似0/1背包)

## 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/O0rBzD2.png)
* [解答空間樹_廣度優先](https://i.imgur.com/E9AxpcT.png)
* [解答空間樹_深度優先](https://i.imgur.com/B7lJLT1.png)
* 旅行銷售員問題：求出「邊加權總合最小或長度最短」的漢米爾頓迴路 [**NP-hard問題**]
* 尤拉迴路問題
* 尤拉路徑 or 尤拉鏈：無向圖上經過每個邊恰好一次的路徑。 **[P問題]**
* 尤拉迴路：無向圖上經過每個邊恰好一次的迴路。 **[P問題]**

## 7. 回溯演算法 #我覺得根本就是DFS = =
* 八皇后問題
* 皇后棋子：可以從八個方向攻擊對方的棋子。
* 如何在一個8×8的西洋棋棋盤上放置8個不會互相攻擊的皇后棋子。

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. 最大流演算法

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)

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)

用匈牙利演算法解決最大化問題，先將各個元素換成以最大元素減去其本身。
接著套用標準的匈牙利演算法：

藉由列的減法變轉陣列：每一列皆減去該列中的最小元素。
計算覆蓋元素0的最少直線數。如果直線數與陣列的大小相同，跳到步驟6。
藉由行的減法變轉陣列：每一行皆減去該行中的最小元素。
計算覆蓋元素0的最少直線數。如果直線數與陣列的大小相同，跳到步驟6。
找出未被覆蓋的元素中最小者，將所有未覆蓋元素中減去此元素值，並增加這個元素值到被兩條直線覆蓋的元素中，回到步驟4。
只從元素0去找出極大二分配對，並套用此配對到原始陣列中以找出最小成本。

## 13. 問題變轉(Problem Reduction)
* $A \propto B:$ 問題 $A$ 變轉為(reduces to)問題 $B$。
* 若且唯若$A$可藉由任何能解決$B$的演算法而獲得解決。
* 
* $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理論 #幹拎德這是三小鬼東西= =
* 
* 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)