動態算法

動態算法涉及多階段決策過程的最優化。它把已知問題分為許多階段或許多子問題，然後按順序求解各個子問題。在每種情況下，列出各種可能的局部解，然後根據某些條件，從局部解中挑選出那些有可能產生最優結果的解。前一子問題的解為後一子問題的求解提供有用的信息，從而大大減少了計算量。最後一個子問題的解就是初始問題的解。也就是説，在多階段決策問題中，各個階段採取的決策，一般來説是與時間有關的，決策依賴於當前狀態，又隨即引起狀態的轉移，一個決策序列就是在變化的狀態中產生出來的。故有“動態”的含義，通常稱這種解決多階段決策最優化的過程為動態規劃方法。動態規劃的目標就是要在所有容許選擇的決策序列中選取一個會獲得問題最優解的決策序列，即最優決策序列。

動態算法所遵循的原則是最優性原理，它可描述如下：

一個最優決策序列具有下述性質：無論初始狀態和第一步決策是什麼，餘下的決策必須按照前一次決策所產生的新狀態構成一個最優決策序列。也就是説，不論前面的狀態和策略如何，後面的最優策略只取決於由最初策略所決定的當前狀態。

如果所求解問題的最優性原理成立，則説明用動態算法有可能解決該問題。而解決問題的關鍵在於獲取各階段間的遞推關係式。貝爾曼認為，利用最優性原理以及所獲得的遞推關係式去求解最優決策序列可以使枚舉量急劇下降。

動態算法的設計方法對於不同問題有不同的表達方式。這是由於各種問題的性質各不相同所造成的，所以，判定最優解的條件也不相同。因此，不存在一種通用的動態規劃算法。如果存在一個決策序列，它包含有非局部最優的決策子序列時，該決策序列一定不是最優的。

滿足最優性原理的問題可以試着使用動態規劃算法。然而，動態算法只是考察求解多階段決策問題的一種途徑，而不是一種特殊算法。不想線性規劃那樣，具有一個標準的數學表達式和明確的定義。

無論是使用向前處理法還是使用向後處理法，都將所有子問題的最優解保存下來，這樣做的目的是為了便於逐步遞推得到原問題的最優解並避免對它們的重複計算。 ^[1]