tags: 演算法

演算法 期末整理 (done)

1. (DP)多階圖最小成本路徑 似乎不考(?)

Input:

$$\begin{gathered} \mathrm{具}n\mathrm{個}\mathrm{頂}\mathrm{點}\mathrm{的}k\mathrm{階}\mathrm{多}\mathrm{階}\mathrm{圖}G(V,E),\mathrm{其}\mathrm{中}V={\bigcup }_{i=1..k}{P}_i,P_i\cap P_j=\varnothing fori\ne j, \\ {P}_1=\{s\},P_k=\{t\},<x,y>\in E\to (x\in P_i\wedge y\in P_{i+1}),<x,y>\mathrm{的}\mathrm{權}\mathrm{重}\mathrm{為}w[x,y] \end{gathered}$$
Output:

$$\begin{gathered} path[1..k],d[s],\mathrm{其}\mathrm{中}path[1..k]\mathrm{紀}\mathrm{錄}\mathrm{第}1\mathrm{階}(\mathrm{節}\mathrm{點}1)\mathrm{到}\mathrm{第}k\mathrm{階}(\mathrm{節}\mathrm{點}n)\mathrm{的}\mathrm{最}\mathrm{小}\mathrm{成}\mathrm{本}\mathrm{路}\mathrm{徑}, \\ d[s]\mathrm{紀}\mathrm{錄}\mathrm{最}\mathrm{小}\mathrm{成}\mathrm{本}\mathrm{路}\mathrm{徑}\mathrm{總}\mathrm{成}\mathrm{本} \end{gathered}$$

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:

$\mathrm{陣}\mathrm{列}p[1...n],\mathrm{代}\mathrm{表}\mathrm{矩}\mathrm{陣}A[i]\mathrm{的}\mathrm{維}\mathrm{度}\mathrm{為}p[i-1]\ast p[i]$
Output:

$\mathrm{最}\mathrm{小}\mathrm{乘}\mathrm{法}\mathrm{次}\mathrm{數}m[1,n],\mathrm{矩}\mathrm{陣}\mathrm{乘}\mathrm{法}\mathrm{分}\mathrm{割}\mathrm{位}\mathrm{置}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_1{a}_2...a_m$ 轉為 B 的子字串
  $b_1{b}_2...b_n$ 的最小成本，
  其中
  $0\le i\le m$ 且
  $0\le j\le 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:

$$\begin{gathered} \mathrm{陣}\mathrm{列}p[i=1...n],\mathrm{代}\mathrm{表}\mathrm{已}\mathrm{排}\mathrm{序}\mathrm{序}\mathrm{列}K=<k_1,...,k_n>\mathrm{被}\mathrm{搜}\mathrm{尋}\mathrm{機}\mathrm{率}， \\ \mathrm{陣}\mathrm{列}q[i=0...n],\mathrm{代}\mathrm{表}\mathrm{搜}\mathrm{尋}\mathrm{目}\mathrm{標}{d}_i\mathrm{不}\mathrm{在}K\mathrm{中}\mathrm{的}\mathrm{機}\mathrm{率},\mathrm{其}\mathrm{中}{k}_i<d_i<k_{i+1} \end{gathered}$$
Output:

$\mathrm{最}\mathrm{佳}\mathrm{二}\mathrm{元}\mathrm{搜}\mathrm{尋}\mathrm{樹}\mathrm{的}\mathrm{期}\mathrm{望}\mathrm{搜}\mathrm{索}\mathrm{成}\mathrm{本}e[1,n],\mathrm{各}\mathrm{子}\mathrm{樹}\mathrm{樹}\mathrm{根}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舉例

6-2. 深度優先搜尋(DFS)

設定起始節點p為解答空間樹的root，並建立一個只包含p的stack。
檢查stack的頂端元素是否為目標節點。若是，則輸出目標節點所對應的解答並停止。
移除stack的頂端節點。將其未被拜訪過的子節點一一加入stack。
若stack為空，則回報無解答並停止。否則，跳至步驟2。

DFS舉例1
DFS舉例2

6-3. 登山搜尋(Hill-climbing Search) = DFS + 評估函數

設定起始節點p為解答空間樹的root，並建立一個只包含p的stack。
檢查stack的頂端元素是否為目標節點。若是，則輸出目標節點所對應的解答並停止。
移除stack的頂端節點。將其未被拜訪過的子節點[由評估函數所算的優先度低的先加入]stack。
若stack為空，則回報無解答並停止。否則，跳至步驟2。

HCS舉例

6-4. 最佳優先搜尋(Best-Frist Search) = BFS + DFS + 評估函數

設定起始節點p為解答空間樹的root，並建立一個只包含p的heap。
檢查heap中優先度最高的元素是否為目標節點。若是，則輸出目標節點所對應的解答並停止。
移除heap優先度最高的節點。將其未被拜訪過的子節點[由評估函數所算的優先度]加入heap中。
若heap為空，則回報無解答並停止。否則，跳至步驟2。

Best-Frist Search舉例

6-5. 實例

• 漢米爾頓迴路 [NPC問題]
  
  
  • 解答空間樹_完整
  • 解答空間樹_廣度優先
  • 解答空間樹_深度優先
• 旅行銷售員問題：求出「邊加權總合最小或長度最短」的漢米爾頓迴路 [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退回去啊= =

8. 分支定界演算法

• 重點：
  • 找出好的機制在搜尋解答的過程中，擴展解答空間樹產生分支。
  • 找出好的機制設定上界與下界，使許多分支終止搜尋。
• 旅行推銷員問題之分支(重點)，其他請看PPT。

9. A*演算法 = 最佳優先搜尋 + 「特殊」評估函式

• 可被視為一個分支定界演算法的特例，當第一個可行解被走訪時，所有在堆積(優先佇列)中的節點都被終止。
• 評估函式：
  $f(n)=g(n)+h(n)$
  • $g(n):$ 從root至節點n的當前成本。
  • $h(n):$ 從節點n到目標節點的評估的未來成本。
  • $h^{\ast }(n):$ 從節點n到目標節點的==實際的未來成本==。
  • $f^{\ast }(n):$ 從root至節點n再到目標節點的==實際成本==。
  • $h(n)\le h^{\ast }(n)$
• 證明：
  1. $f(n)=g(n)+h(n)\le g(n)+h^{\ast }(n)=f^{\ast }(n)$
  2. 令
     $x$ 為目標節點。可得
     
     $f^{\ast }(x)=f(x)+h(x)=f(x)+0=f(x)$
  3. 假設
     $x$ 不是最佳節點，則必存在一個已存在heap中的，但是未被選擇的節點
     $y$，使得
     
     $f^{\ast }(y)<f^{\ast }(x)$
  4. 因我們使用最佳優先搜尋法，故可得
     $f(x)\le f(y)$
  5. 由不等式(1)(2)(4)可得
     
     $f^{\ast }(x)=f(x)\le f(y)\le f^{\ast }(y)$
     
     $\to f^{\ast }(x)\le f^{\ast }(y)$，與(3)矛盾，故得證
     $x$ 為最佳節點。
• 解多階圖最短路徑問題（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演算法 圖解
Edmons-Karp演算法 = Ford-Fulkerson演算法 + BFS
多起點終點 => 單起點&終點

11. 最小成本最大流演算法

• 最小成本最大流問題為
  • 先找出由源點到匯點的最大流
  • 再找出達成此最大流的最小成本
• [複習] Bellman-Ford最短路徑演算法

Min_Cost_Max_Flow(G)
    先不看成本參數找出最大流f
    加入成本參數計算f的成本c
    while true
        計算G_f
        用Bellman-Ford在G_f上找負成本循環
        if 無負成本循環
            return f, c
        else
            在循環中環繞以減低總成本直到循環中的一個邊的容量用盡為止

12. 匈牙利演算法

解 最大權重完美二分匹配

$\leftrightarrow$ 解 最大化問題
二分匹配(Bipartite Matching)

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

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

13. 問題變轉(Problem Reduction)

• $A\propto B:$ 問題
  $A$ 變轉為(reduces to)問題
  $B$。
  • 若且唯若
    $A$可藉由任何能解決
    $B$的演算法而獲得解決。
  • 
  • $LowerBound(B)=T(AL{G}_B)$
  • $LowerBound(A)\le T(AL{G}_A)\le T(t{r}_1)+T(AL{G}_B)+T(t{r}_2)$
  • if
    $$\begin{gathered} T(t{r}_1)+T(t{r}_2)\le L(A) \\ \to L(A)\le T(AL{G}_A)\le T(AL{G}_B)=L(B) \\ \to \mathrm{假}\mathrm{設}A\mathrm{的}\mathrm{下}\mathrm{界}\mathrm{是}\mathrm{已}\mathrm{知}\mathrm{的}，\mathrm{若}A\propto B，\mathrm{且}\mathrm{變}\mathrm{轉}\mathrm{中}\mathrm{的}\mathrm{轉}\mathrm{形}\mathrm{時}\mathrm{間}\mathrm{複}\mathrm{雜}\mathrm{度}\mathrm{比}A\mathrm{的}\mathrm{問}\mathrm{題}\mathrm{下}\mathrm{界}\mathrm{還}\mathrm{低}， \\ \mathrm{則}A\mathrm{的}\mathrm{下}\mathrm{界}\mathrm{亦}\mathrm{是}B\mathrm{的}\mathrm{下}\mathrm{界}。 \end{gathered}$$
• 凸包問題(The convex hull problem)
  • 凸包(convex hull)問題的下界
  • $\because 「\mathrm{排}\mathrm{序}\mathrm{問}\mathrm{題}」\propto 「\mathrm{凸}\mathrm{包}\mathrm{問}\mathrm{題}」，\mathrm{且}「\mathrm{排}\mathrm{序}\mathrm{問}\mathrm{題}」\mathrm{的}\mathrm{下}\mathrm{界}\mathrm{為}\mathrm{\Omega }(nlogn)$
    
    $\therefore 「\mathrm{凸}\mathrm{包}\mathrm{問}\mathrm{題}」\mathrm{的}\mathrm{下}\mathrm{界}\mathrm{亦}\mathrm{為}\mathrm{\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)是一個非確定性敘述，但它一定會挑中一個可以讓演算法成功結束的元素(除非這種元素不存在)。
    • 實例：非確定漢米爾頓迴路演算法
      $\to 「\mathrm{漢}\mathrm{米}\mathrm{爾}\mathrm{頓}\mathrm{迴}\mathrm{路}\mathrm{問}\mathrm{題}」\in$ NP
• 問題的 決策版本 vs 原始版本
  • 例如：旅行銷售員(TSP)問題
    • 原始版本
      $O$：給定圖找最短的旅途(tour)或巡環(cycle)
    • 決策版本
      $D$：給定圖是否具有一個旅途的總長度
      $\le$常數c
      • 答案只會是：是 or 否
    • $D\propto O$
• NPC證明 方法
  • 欲證明
    $Q\in$ NPC：
    1. 證明
       $Q\in$ NP：寫一個可解
       $Q$ 的NP演算法
    2. 證明
       $\mathrm{\exists }{Q}^{\prime }\in$ NPC s.t.
       $Q^{\prime }\propto Q$
       • 存在一個函數
         $f(x)$為polynomial-time computable
       • $f(x)$使得對所有
         $x$ 而言，
         $x\in L_1$ iff
         $f(x)\in L_2$。
         (
         $L_1$ 為
         $Q^{\prime }$ 問題的解集合；
         $L_2$ 為
         $Q$ 問題的解集合)
  • 已知的NPC問題：SAT問題(滿足問題，Satisfiability Problem)：
    • 給一個布林函數
      $E(x),x=\{x_1,...,x_n\}$，若存在一組輸入當作
      $x$ s.t.
      $E(x)=True$，則回傳Success；否則回傳Failure。
    • $E(x)$ 為CNF，即數位電路中的product of sum，例：
      $(x_1\vee x_2)\wedge (x_4\vee \mathrm{\neg }{x}_5)$
    • Cook’s Theorem：證明SAT問題
      $\in$ NPC，詳細就別看了，很難也不重要Orz
      1. 所有NP問題
         $\propto$ SAT問題
      2. SAT
         $\in$ P
         $\leftrightarrow$ NP = P，但目前無法證明，也似乎不成立
  • 舉例：證明3SAT問題為NPC
  • 已知的NPC問題：
    1. SAT問題
    2. 3SAT問題：如
       $E(x)=(x_1\vee x_2\vee \mathrm{\neg }{x}_4)\wedge (\mathrm{\neg }{x}_3\vee x_4\vee \mathrm{\neg }{x}_5)$，變數三個一組
    3. 集合覆蓋問題
    4. 0/1背包問題
    5. 旅行推銷員問題
    6. 分割問題
    7. 著色問題
    8. 完全圖或分團問題
    9. 點覆蓋問題
    10. 支配集合問題
  • 參考：from 課程網站
    • Recipe, Cook and Carp
    • NPC理論測驗及解答