:::danger
Design Strategies for Computer Algorithms
===
:::
# Prune and Search(一)
---
## 1.Definition
**Divide and Conqure**的一個特例，**Divide and Conqure**是將原本的大問題
拆成許多小問題，將小問題解決就等於將原本的問題解決了。而**Prune and Search**是**Divide and Conqure**的一個特例，將原本問題分成許多小問題後，挑出其中對於解決問題有重要性的小問題來解決(**Search**)，放棄其他小問題(**Prune**)來減少解決問題所需要花的時間。
時間複雜度大多是$O(N)$
而通式為 $T(n) \leq T((1-\alpha)n) + p(n)$
$0 < \alpha < 1$ is the fraction to prune the solution sapce in each iteration
而$p(n)$是每次iteration所花的時間

---
## Ex.The Selection Problem
#### Given distinct number $a_1, a_2,...,a_n$, determine the $kth$ smallest one.
#### 從一個數列中找到第$~kth~$個小的數字。
>解決問題的原則為
>*Median in the Median*

**時間複雜度$~O(N)$**
1.先將所有數字分成數群，分群的時間複雜度為$O(N)$。
2.在將每群分別做排序，對常數數量排序的時間複雜度為$O(1)$(目前$O(N)*O(1)=O(N)$)
3.用Recurrsive找出每群中間的數字，並在找出在這些中間數字中的中間數(**Median and Median**)
*假設總數為$~n~$分成$~r~$群在這Recurrsive中所花的時間複雜度為$T(\frac{n}{r})$*
4.將中間值當成$P$，用此$P$來作為index，來區分出$~<P~$或$~>P~$的區域在根據題目要求在特定區域尋找特定值。
所使用的Recurrsive function會有以下時間複雜度。

> $T(n) \leq T(n/5) + T(3n/4) + O(n)$
---
找到$P$要用$O(n)$的時間複雜度，在用$T(3n/4)$的時間去找在特定$P$範圍內答案
因為其他小問題因為$P$的原因而直接被捨棄所以會為$T(3n/4)$。

## Ex. The 2-dimensional linear programming problem

**時間複雜度$~O(N)$**
**Minimize** $~~~a'x'+b'y'$
**Subject to** $~a_ix+b_iy+c_i \leq 0\quad$ $i = 1,2,...,n$
先將其Simplify變成
找到最小的 $y$ 在 $a_ix + b_i y + c_i \leq 0$的限制條件下。
這個轉換須花$~O(N)~$的時間複雜度

### 問題分析
------
>- 在滿足給訂條件情況(Constraint)會產生一個半平面(Fig2直線上箭頭朝向的方向)。
>- 而這些Constraint所圍起來的範圍為Fessible Region。
>- 在Fessible Region中的最小$~y~$所對應的$~x~$值為$Optimal~Solution$。

### 問題分析(續)
1.先將$N$個Constraints分成三個群，分別是$~I^0, I^+, I^-$。(用$~b_i$來決定箭頭朝上朝下)
>- $I^0~$
May be combined into a single constraint
$u_1 \leq x \leq u_2$
>- $I^+$
$b_i$ 為正
$b_i$ 為負
>- $I^-$

2.不斷的跑$~x_m$就能求出在fessible region上$~I^-$最高點$~\alpha~$和$~I^+~$最低點$~\beta~$
(此處可用Prune來將問題簡化)
$\alpha=(\alpha_x,\alpha_y)~~$ $\beta=(\beta_x, \beta_y)$
$\alpha_x \leftarrow x_m\quad~~~\beta_x \leftarrow x_m~$
$\alpha_y \leftarrow max\{(-a_ix_m-c_i)/b~|~a_i+b_iy+c_i \leq 0 \in~I^-\}$
$\beta_y \leftarrow min\{(-a_ix_m-c_i)/b~|~a_i+b_iy+c_i \leq 0 \in~I^+\}$

3.在求出通過$~\alpha~$和$~\beta~$的$~maximum(mininum)~slope$分
別為$Smax(Smin)$和$Tmax(Tmin)$


4.根據以上資料可以求出六種情況。

#### 六種情況
>- 最佳解在右邊
>
>- 最佳解在左邊
>
>- 最低點即為最佳點
>
>- 如果存在fessible region，最佳解會在右邊
>
>- 如果存在fessible region，最佳解會在左邊
>
>- fessible region不存在(無解)
>
>

根據以上性質就能利用Prune and Search來解決這個問題
而詳細內容請看