###### tags: `Algorithm` `test`

# 期末考重點

## 1.最佳子結構(DP問題)

若一個問題可以用於子問題相同的解法來解，亦即局部最佳解能決定全域的解，則稱此問題為最佳子結構。

例子：matrix-chain multiple、rod cutting、shortest path

### shortest path有最佳子結構


- 當$p$是$u$到$v$的最短路徑。
- $w$為$p$上的任意一點
- $p1$為$u$到$w$，是$p$的一部份
- 當$p_1$是$u\rightsquigarrow w$的最短路徑

證明：
假設$u$到$w$存在一個最短路徑$p_1'$。用$p_1'$代替$p_1$可得到包含$p_1'$的新路徑會比原本的$p_1$短。

### longest path 沒有最佳子結構

- 子路徑$q$到$r$是$q\rightarrow r$
- 簡單最長路徑$q$到$r$是$q\rightarrow s\rightarrow t\rightarrow r$
- 子路徑$r$到$t$是$r\rightarrow t$
- 簡單最長路徑$r$到$r$是$r\rightarrow q\rightarrow s\rightarrow t$

結合上述的簡單最長路徑可得
$$q\rightarrow s\rightarrow t\rightarrow r\rightarrow q\rightarrow s\rightarrow t$$
它並不是簡單路徑。

## 2.背包問題(Greedy Algorithm)

### 01背包問題
- 為NP-complete問題
- 沒有greedy choice
- 找出最有價值的子集合，總重量為$weight\le W$，W為背包可承受的重量。
### 分數背包問題
- 有最佳子結構
- 有 greedy choice
- 解決此問題，需要比較各個項目的$\frac{value}{weight}$：$\frac{v_i}{w_i}$
- 使得$\forall i，\frac{v_i}{w_i}\geq \frac{v_{i+1}}{w_{i+1}}$

## 3.圖

### 廣度優先搜尋

- 為了方便追縱進度，所有頂點將會分成3類，尚未拜訪時是白色，拜訪過後但周圍鄰居尚未拜訪完時顏色為灰色，鄰居全被拜訪過後顏色轉為黑色。
- 時間複雜度：$O(V+E)$
- 應用：二分圖測試、最短路徑演算法

### 深度優先搜尋
- 使用DFS時，邊分為Tree edge, Back edge, Forward edge, Cross edge
- Edge(u, v)可用顏色做判斷，當此邊是第一次探索時，若color(v)為
1.white $\Rightarrow$ (u, v)是tree edge
2.gray $\Rightarrow$ (u, v)是Back edge
3.back $\Rightarrow$ (u, v)可能是：
&emsp;(1)$if(d[u]<d[v])$(u比v早探索)：Forward edge
&emsp;(1)$if(d[u]>d[v])$(u比晚探索)：cross edge
- 無向圖中只有tree edge和back edge
- 有back edge $\Rightarrow$ 有cycle
- 應用：
1.強連通：
&emsp;(1)call DFS(G) to compute finish times $u.f$ for each vertex u.
&emsp;(2)creat $G^T$
&emsp;(3)call DFS($G^T$), but in the main loop of DFS, consider the vertices in order of decreasing $u.f$(as compute in line 1)
&emsp;(4)output the vertices of each tree in the depth-first forest formed in line 3 as a seperate strongly connected component
2.拓撲排序：
&emsp;(1)Call DFS(G) to compute finishing time $f(v)$ for each vertex $v$
&emsp;(2)As each vertex is finished, insert it onto the front of a link list.
&emsp;(3)Return the link list of vertices.

## 4.最小生成樹

當一張圖的所有點完全連通，稱為生成樹(spanning Tree)
當點與點不完全連通，稱為生成森林(spanning forest)

而生成樹的每條邊都有權重，權重總和最小為最小生成樹

### 定義：
- 有$|V|-1$條邊
- 沒有cycle
- 不一定唯一

Generic-MST(G, w){
    A = 0;
    while(A doesn't form a spanning tree){
        find an edge(u, v) that is safe for A
        A = A union{(u, v)}
    }
    return A
}

若$A$是$MST$的子集合，$(u,v)$是$A$中一條safe的邊，iff $A\cup{(u,v)}$也是$MST$的子集合，所以只加入safe邊

### 名詞解釋：
- cut：$(S, S-V)$為$G(V, E)$的一部份
- cross：若存在一條edge$(u, v)$其中一點在$S$另外一點在$S-V$則稱之
- respect：若有一個set A沒有cross的情形，則稱之
- light edge：若某個cut的某條邊擁有全村最小的weight，則稱之

### 演算法：
Prim's algorithm
步驟:
1.將任意節點加入樹中
2.選擇與樹距離最近的節點並加入，反覆直到所有節點都在樹中

Kruskal's algorithm
1.將所有邊由小到大排序
2.從最小的開始，選擇不會形成環的路線，直到連接所有點

## 最短路徑演算法

### Bellman-Ford 和 Dijkstra之比較

| 演算法名稱 | 假設條件 | 時間複雜度 |策略|優點|
| -------- | -------- | -------- |-------- |---------|
| Bellman-Ford | 邊的加權值可為負，不能有負cycle | $O(n^2)$ $(有查到O(VE))$ |Dynamic-progamming|可用分布式的方式實現及加權值可為負|
| Dijkstra | 邊的加權值不可為負，不能有負cycle | $O(n^3)$ $(有查到O(E*logV))$ |Greedy 阿葛|速度較快|

## All pairs shortest path

### 重新設計的理由
- Bellman-Ford在解決All pairs問題效率太差
- Dijkstra不能解決負加權值的問題

### 策略
- 加入中繼點的概念考慮點$u$和點$v$的最短路徑是否因為加入了中繼點降低成本。

## NP問題
- P:在多項式時間內可以檢查並解決的問題
- NP:在多項式時間內可以檢查的問題
- NP-C:在多項式時間內難以檢查且最複雜的問題

### NP-C問題

1.Circult SAT(布林滿足問題)
判斷一組給定的布林函數，是否能找到一組input讓其為true

應用:EDA領域(電子設計自動化)的測試、驗證

2.Subset Sum(子集合問題)
給一組集合與指定數字，能否找到全部的子集合相加剛好等於指定數字
ex:集合{7, 5, 9, 6, 2}中，能否找到子集合加總=18的組合
Ans:{7, 5, 6}

3.TSP(Travelling salesman problem, 旅行商問題)
給定城市與城市之間的距離，求解經過每一座城市並回到起始點的最短迴路

應用:DNA測序