動態規劃與搜尋

動態規劃與搜尋——動態規劃是高效率、高消費演算法

同樣是解決最優化問題，有的題目我們採用動態規劃，而有的題目我們則需要用搜尋。這其中有沒有什麼規則呢？

我們知道，撇開時空效率的因素不談，在解決最優化問題的演算法中，搜尋可以說是「萬能」的。所以動態規劃可以解決的問題，搜尋也一定可以解決。

把乙個動態規劃演算法改寫成搜尋是非常方便的，狀態轉移方程、規劃方程以及邊界條件都可以直接「移植」，所不同的只是求解順序。動態規劃是自底向上的遞推求解，而搜尋則是自頂向下的遞迴求解（這裡指深度搜尋，寬度搜尋類似）。

反過來，我們也可以把搜尋演算法改寫成動態規劃。狀態空間搜尋實際上是對隱式圖中的點進行列舉，這種列舉是自頂向下的。如果把列舉的順序反過來，變成自底向上，那麼就成了動態規劃。

(當然這裡有個條件，即隱式圖中的點是可排序的)

正因為動態規劃和搜尋有著求解順序上的不同，這也造成了它們時間效率上的差別。在搜尋中，往往會出現下面的情況：

對於上圖(a)這樣幾個狀態構成的乙個隱式圖，用搜尋演算法就會出現重複，如上圖(b)所示，狀態c2被搜尋了兩次。在深度搜尋中，這樣的重複會引起以c2為根整個的整個子搜尋樹的重複搜尋；在寬度搜尋中，雖然這樣的重複可以立即被排除，但是其時間代價也是不小的。而動態規劃就沒有這個問題，如上圖(c)所示。

一般說來，動態規劃演算法在時間效率上的優勢是搜尋無法比擬的。（當然對於某些題目，根本不會出現狀態的重複，這樣搜尋和動態規劃的速度就沒有差別了。）而從理論上講，任何拓撲有序（現實中這個條件常常可以滿足）的隱式圖中的搜尋演算法都可以改寫成動態規劃。

但事實上，在很多情況下我們仍然不得不採用搜尋演算法。那麼，動態規劃演算法在實現上還有什麼障礙嗎？

考慮上圖(a)所示的隱式圖，其中存在兩個從初始狀態無法達到的狀態。在搜尋演算法中，這樣的兩個狀態就不被考慮了，如上圖(b)所示。但是動態規劃由於是自底向上求解，所以就無法估計到這一點，因而遍歷了全部的狀態，如上圖(c)所示。

一般說來，動態規劃總要遍歷所有的狀態，而搜尋可以排除一些無效狀態。更重要的是搜尋還可以剪枝，可能剪去大量不必要的狀態，因此在空間開銷上往往比動態規劃要低很多。

如何協調好動態規劃的高效率與高消費之間的矛盾呢？有一種折衷的辦法就是記憶化演算法(備忘錄法)。記憶化演算法在求解的時候還是按著自頂向下的順序，但是每求解乙個狀態，就將它的解儲存下來，以後再次遇到這個狀態的時候，就不必重新求解了。

這種方法綜合了搜尋和動態規劃兩方面的優點，因而還是很有實用價值的。