---
title: Dynamic programming / Weighted Interval Scheduling
tags: 演算法(交大OCW)
---
:::success
Dynamic programming 的 programming，不是編寫程式的 programming
而是來自於「Mathematical programming」，又叫「Mathematical optimization」
也就是數學中的「最佳化」，應用數學的一個分支，參考 [維基](https://zh.wikipedia.org/zh-tw/%E6%9C%80%E4%BC%98%E5%8C%96)
:::
:::warning
*Richard E. Bellman 1953*
:::
:::info
跟 DAC 有點不一樣。雖然兩者都是從小問題兜出大問題，但是 DAC 會把每個小問題全部展開，DP 則不會這麼做，而是會 Implicitly 的展開小問題，而且對這些小問題的順序也很講究
:::

# Weighted Interval Scheduling

一樣是給你很多工作，有開始跟結束的時間，不過這次多了「權重」，或者又叫「value」，這次的目標是要取得最大的「value」

如下面的例子，就是選擇權重分別為 26 跟 16 的這兩份工作


原本 Greedy 的地方講到的是沒有「權重」的，或者說權重都是 1 ，又叫 unit-weighted

因此就是做越多事情越好；但是有了權重後就不再是這樣了，像下面有了權重後，如果根據 當初得到的 Greedy Rule ，選擇最早結束的，會選到權重都是 1 的那兩份工作

但是很顯然的，最後權重最高的是選擇中間的工作


# Induction Base

DP 最重要的一步就是，在一開始決定要以甚麼作為 Induction 的 Base
也就是每一步要以甚麼作為依據推進

先給一堆工作，並**以結束時間排序**


## Induction on Time

:::danger
這裡要重新編寫
:::

既然這裡是排程問題，那就不妨選擇「時間」

### 出問題

但是這會遇到一個問題，在假設P(n=k)的時候，如果以時間當作 k 的話，不同的 k 會有不同的區間

像下面的兩張圖說明了 t' 取在不同的位置，則「假設 P(n=t') 成立」這個步驟，結果會是不同的

下圖中 P(t') 代表了紅色圈圈的權重最大值


下圖中 P(t') 代表了紫色圈圈的權重最大值


所以 Induction on Time 不是個好選擇

## Induction on Interval Index

改成以每個工作的 index 作為 Induction Base 就不會有上面的問題了
不過要記得是排序過後的 index，才不會有上面的問題

:::info
整體來說 DP 最重要且困難的步驟，就是在決定 Induction Base
以及為了找到合適的 Base，把資料做適當的處裡；像這裡就是把工作以結束時間排序
:::

為了要寫成歸納法的形式，也就是下一項跟前面的結果有關
所以下圖用了一個技巧，就是讓每個 index 紀錄沒有衝突的工作數量


### Pseudo Code

Compute-Opt 就有用到代入上面的函數 p ，這樣就可以很方便的寫出歸納的形式

程式碼只有 2 行，非常簡潔


下面就是說明有 6 個工作時的最佳選擇要怎麼找

要嘛就是不包含第 6 個工作，而這等同於 5 個工作時的最佳選擇


要嘛就是包含第 6 個工作，這等同於第 6 個工作的權重加上 3 個工作的最佳選擇


當我們把整個程式碼展開，會得到下面的流程

但是可以發現，紅色的部分是重複的內容，如果這些也給他執行下去，那時間花費可不得了


所以我們就有了 DP 的一個技巧 Memoization

## Memoization：Top-Down

就是把計算過的內容給存起來，下次就可以直接取值不用重算一次


重新改寫的程式碼，就是多了判斷的一行，以及把算好的存起來


因此最後的流程就會變成下圖，時間只要 O(n)


## Iteration：Bottom-Up

不過有了「存起來」的想法，代表我們其實也可以從頭開始做，時間也是 O(n)
只要記得定義好起點，像下面就是M[0]


### 總結

- 要記得 Iteration 對於「順序」很重要
- 這樣才能確確保後面的內容一定可以被算出來，迴圈可以正常運作
- 由於 Memoization 只有需要時，才會執行部分的小部件，也就是說不是所有的小部件都用到
- 所以有時會比 Iteration 快一點點
- 由於跟 DAC 都師出同門，所以通常會先以 DAC 的角度去想如何執行遞迴的部分，然後再以 DP 執行
- 執行時間跟空間高度取決於「紀錄」這項步驟時所花的時間
- 也就是把資料存起來的這項步驟
- 那個存好的東西又叫 table


---

# DP 的一些「重點」

當一個問題有下面這三個屬性，就可以用 DP

- 子問題數量是 polynomial 而不是 exponential
- 老師說子問題的數量就是 table 的大小，如果是 exponential 會很花時間
- 那就算用了 DP 一樣很慢
- 主要的問題可以由子問題的結果求出
- 也就是遞迴的部分
- 子問題會自然的「從小到大」，並伴隨著很好計算的遞迴形式
- 老師說這是他覺得最重要的部分
-
:::info
老師說當你發現這個問題存在一個不變的「Order」的話，那你有很大的機會可以使用 DP
:::

---

另外老師參考演算法的聖經 Introduction to Algorithm 裡面有提到的

如果一個問題可以用 DP 求解，會具備兩個特性

- Optimal Structure：問題的解一定是由子問題的解兜出來的
- 老師說這個會需要簡單敘述的證明，也就是說明是如何遞迴的
- Overlapping subproblem：在上面提到的的例子中，或者下面的圖，就是紅色重複的部分

還有就是

- DP 通常處理最佳化問題
- 這也是他名字的由來
- DP 最適合那些有不變線性序列的問題
- 跟上面的『不變的「Order」』是同一件事


---

然後老師也參考了另一個教演算法的教授，有提到使用 DP 的步驟

1. 寫出遞迴的形式
- 可以從 DAC 的角度開始想，要怎麼拆
3. 確認子問題的總數是 Polynimial
4. 確認子問題運算的順序
- 這就是為甚麼需要『不變的「Order」』


---

# 回顧

下面回顧了目前學到的三大技巧

:::info
- 老師說有空來提一下 Quick Sort，他也是用 DAC ，不過他跟 Merge Sort 不一樣，不是用拆成兩個同樣大小，而是拆成部一樣大小的兩半
- Reuccrence relation 可以說是自己定義自己
- 如果發現子問題沒有 Overlapping，告訴了你不要用 DP 要用 DAC
:::

---

# 例子 Fibonacci Sequence

:::warning
雖然這不是一個最佳化問題，但是這個序列的結構跟 DP 的思考方式是一樣的
:::

$$
F_{n}=F_{n-1}+F_{n-2},\ \ \ F_{0}=0,\ F_{1}=1
$$

如果我就直接給他遞迴下去，會出現下面的問題


沒錯，Overlapping；一旦去除 Overlapping，整棵樹會變成下圖


## Memoization


## Iteration


---

# 例子 Maze Routing

:::info
實際上這跟 VLSI 的繞線問題一樣
:::

兩點，只能走直線，會有障礙物


# Lee's Algorithm

- 先以 Iteration，從起點向外擴散出每格的最短路徑；又叫 Wave Propogation
- 有最短距離的格子就不用執行
- 直到碰到終點就停止