###### tags: `ADA 8.2` `Breakpoint Selection`
# ADA 8.2: Breakpoint Selection Problem(加油站問題)

## 問題：
假設有 $n+1$ 個 $breakpoint$(加油站)，$b_{0}$ ~ $b_{n}$，加滿油可行駛的最長距離為 $C$
求找出最少停留中繼點加油的數量


:::info
理想情形：
行駛 $C$ 距離時剛好有一個中繼點（加油站）
如上圖黃色區塊
:::

:::success
實際情形：
你必須在沒油之前找個中繼點（加油站）加油
如上圖變成虛線，所以實際行駛距離並不一定都為 $C$
:::

## Greedy Algorithm
依實際情況可以使用貪婪演算法 $\rightarrow$ 在能行駛到的最遠距離 $C$ 前一個加油站加油

[Greedy Algorithm](https://hackmd.io/cAk-0w7dRb2EHzJCzrjecg)

### Step1 : Define SubPorblems
$B(i)$ : 縮短距離從 $b_{i}$ 到 $b_{n}$
然後目標找出 $B(0)$

### Step2 : Optimal Substructure
假設 $B(i)$ 的OPT為最大值index $j$
其 $b_{j} - b_{i} \le C$
而中間有 $j-i$ 個 breakpoint

找出最小的
$$B_{i} = \min_{i\lt k \le j} (1+b_{k})$$


:::danger
這裡看不太懂，我猜是從 case 1 到 case 2... 到 case j-i 由每個最小的 OPT 組成可找到 B(i) 的OPT
:::

### Step3 : Greedy Choice
去找可以行駛到的 $\color{red}{最遠}$ 加油站 $b_{j}$

#### 如何證明? $\rightarrow$ 反證法(Contradiction)
也就是要證明OPT不為Greedy Choice $b_{j}$

* 假設OPT不包含Greedy Choice(也就是不包含 $b_{j}$)
始於 $b_{i}$ 停於 $b_{k}$ ， $k \neq j$
* 如果 $k \gt j$ ， 將停在 $b_{k}$ ，超過油量行駛距離 $C$ ， 故不成立
* 如果 $k \lt j$ ， 那我們就可以替換 $b_{k}$ 成 $b_{j}$
* 則該OPT換成 $b_{j}$ 可行駛相等或更遠之距離，得證

$$B_{i}=\min_{i \lt k \le j} (1+b_{k}) \rightarrow B_{i}=(1+b_{j})$$

## Pseudo Code
* 先將所有的breakpoint做排序
* S = {0} $\rightarrow$ 所選擇的breakpoints
* p = 0 $\rightarrow$ 目前所在位置


$$
T(n) = \Theta(nlogn)
$$

:::warning
上面解讀
$b_{i+1}-b_{p} \gt C$，當 $i==p$，這種情況就算無解
因為代表有兩點距離會超出能行使最遠距離 $C$
另外下面的 $A$ 應該是指上面的 $S$ 集合
當 $i \neq p$ ， $i$ 為最大index，則將 $i$ 納入所選breakpoints $S$ 裡
$p=i$
:::