[After-class]Dynamic Programming
"Dynamic Programming主要是用在最佳化(optimization)問題上,當我們需要找到最好的方式來做某件事情時.通常用不同方法來做某件事情的數目是指數的,所以用暴力搜尋來找最佳解除了在較小的問題大小之外,再計算上是不可行的.然而,我們可以將Dynamic Programming應用在當問題有著我們可以利用的特定數量的結構的這樣情況中.[@more@]
簡單的子問題:一定有某種方式可以將全域最佳化問題切割成子問題,每一個子問題都
和原始問題有類似的結構.另外,應該要有一個簡單的方式以少量的索引
(像是i j k 依此類推)來定義子問題.
子問題最佳化性質:一個全域問題的最佳解必須能夠使用一些相對簡單的組合運算,由
子問題的最佳解組合而成.我們不應該能夠找出包含子問題的次最
佳解的全域最佳解.
子問題重疊:一般來講對於不相關子問題的最佳解也可以包含子問題.確實,這樣的重疊
增進了儲存有對於子問題的解的動態規劃演算法的效率.
"
Groups:
