策略迭代法

例如，在最短路徑問題中，設給定M個點1，2，…，M。點M是目的點，с_ij>0是點i到點j的距離i≠j，с_ij=0，i,j=1,2,…,M,要求出點i到點M的最短路。記ƒ(i)為從i到M的最短路長度。此問題的動態規劃基本方程為：

其策略迭代法的程序如下：選定一初始策略u₀(i)，在這問題中，策略u(i)的意義是從點i出發走一步後到達的點，而且作為策略，它是集{1,2,…,M-1}上的函數。由u₀(i)解下列方程組求出相應的值函數ƒ₀(i)：

再由ƒ₀(i)求改進的一次迭代策略u₁(i)，使它是下列最小值問題的解：

然後，再如前面一樣，由u₁(i)求出相應的值函數ƒ₁(i)，並由ƒ₁(i)求得改進的二次迭代策略u₂(i)，如此繼續下去。

可見求解(1)的策略迭代法的程序由下列兩個基本步驟組成：

①求值計算　由策略 u_n(i)求相應的值函數ƒ_n(i)，即求下列方程的解：

②策略改進　由值函數ƒn(i)求改進的策略，即求下列最小值問題的解：

式中規定，如u_n(i)是上一問題的解，則取u_n+1(i)=u_n(i)。

在一定條件下，由任選的初始策略出發，輪換進行這兩個步驟, 經有限步N後將得出對所有i，uN+1(i)=uN(i)這樣求得的uN(i)就是最優策略，相應的值函數ƒN(i)。是方程(1)的解。

對於更一般形式的動態規劃基本方程

這裏ƒ，H，φ為給定實函數。上述兩個步驟變成：

①求值計算　由策略u_n(x)求相應的值函數 ƒ_n(x)，即求方程 之解，n=0，1，2…。

②策略改進　由值函數ƒn(x)求改進的策略un+1(x)，即求最優值問題（圖8）的解。

對於滿足適當條件的方程(2)和初始策略，上述兩個步驟的解存在，並且在一定條件下，當n→ 時，所得序列{ƒn(x)}與{un(x)}在某種意義下分別收斂於(2)的解和最優策略。

策略迭代法最初是由R.貝爾曼提出的。1960年，R.A.霍華德對於一種馬爾可夫決策過程模型，提出了適用的策略迭代法，給出了相應的收斂性證明。後來，發現策略迭代法和牛頓迭代法在一定條件下的等價性，於是，從算子方程的牛頓逼近法的角度去研究策略迭代法，得到了發展。

對於範圍很廣的一類馬爾可夫決策過程，其動態規劃基本方程可以寫成

式中ƒ∈V，對所有 γ∈Γ:r(γ)∈V，γ為 V→V的線性算子，Γ為這種算子的族，而V 則是由指標值函數所構造的函數空間。

假設 當 ƒ(γ)是方程 r(γ)+γƒ=0 的解時，它是對應於策略γ的指標值函數。

最優策略，定義為最優值問題的解。

這時由策略迭代法所求得的序列{fn}和{γn}滿足下列關係 ，其中的逆算子。 ^[1] 

當σ是加託可微時, γn+1是σ在ƒn處的加託導數。於是，上面的關係恰好表達了牛頓迭代法在算子方程中的推廣。

利用迭代算法解決問題，需要做好以下三個方面的工作：

一、確定迭代變量。在可以用迭代算法解決的問題中，至少存在一個直接或間接地不斷由舊值遞推出新值的變量，這個變量就是迭代變量。

二、建立迭代關係式。所謂迭代關係式，指如何從變量的前一個值推出其下一個值的公式（或關係）。迭代關係式的建立是解決迭代問題的關鍵，通常可以使用遞推或倒推的方法來完成。

三、對迭代過程進行控制。在什麼時候結束迭代過程？這是編寫迭代程序必須考慮的問題。不能讓迭代過程無休止地重複執行下去。迭代過程的控制通常可分為兩種情況：一種是所需的迭代次數是個確定的值，可以計算出來；另一種是所需的迭代次數無法確定。對於前一種情況，可以構建一個固定次數的循環來實現對迭代過程的控制；對於後一種情況，需要進一步分析出用來結束迭代過程的條件。

動態規劃是旦澤和貝爾曼提出的，他們關於這一定量化方法的重要著作發表於50年代。最初動態規劃指的是不確定性的線性規劃問題，而它已發展成為一個解決範圍廣泛的工商業務問題的定量技術了。

動態規劃的理論基礎為“最優化原則”。它是説一個最優策略是由最優子策略構成的。它可以定義為這樣的一個數學方法：它解決一串序貫決策問題，而這些決策中的每一個都又影響着未來的決策，且後面的決策對前面決策所決定的初始狀態來説總是最優的。這是非常重要的，因為我們很難遇到一個運行中的情況；其中的決策不影響未來的決策。經理們面對着的問題是要他們作出一系列決策，這些決策中的每一個都依賴於先前決策的結果。例如，一個生產經理可能為了得到眼前的高產量不顧未來的高產量而忽視工廠的維修工作。若每一決策只考慮它本身最優化，那麼由全部決策所得到的收益可能不是最優的。相反如果在制定第1個或後續的決策時在收益上作些犧牲，雖然使各決策次優化了，但總的收益可能更高些。這就是動態規劃的目標。

一般説來，動態規劃處理的問題都含有時間變量。但是，它可以用來處理一些本來與時間無關的問題，這隻要在靜態模型中人為地引進“時間”因素，分成時段，把它看作多階段的動態模型就能用動態規劃的方法來解決了。

在很多領域中都有動態規劃的應用。如資源分配、貨物裝運、設備更新、生產計劃和存貯、排序、確定利息策略及評價投資機會等。

動態規劃可以看成是一個把複雜的大問題分成一系列較易解決的小問題的方法。它沒有標準的格式。

動態規劃模型有4個基本概念：(1)階段。它是所給問題中被劃分成若干個相互聯繫的時期或區間。(2)狀態變量。是表示某段的出發位置。這些狀態變量的值把制定決策需要了解的所有有關係統的情況都顯示出來。狀態變量數目可能很大，對於一定的計算能力，應盡能減少狀態變量的數目。(3)決策變量。表示狀態給定以後，從該狀態到下一階段某狀態的選擇。(4)目標函數。各個不同階段的決策能力，可能是距離、利潤、成本等。 ^[2]