動態(tài)規(guī)劃案例教學(xué)設(shè)計

[摘 要]在運籌學(xué)的分支體系中，動態(tài)規(guī)劃因其應(yīng)用的廣泛性而占有十分重要的地位。針對動態(tài)規(guī)劃教學(xué)中的難點，可以以最短路問題為引例，以大家耳熟能詳?shù)拿Q對動態(tài)規(guī)劃中的基本概念進行闡釋，并對最優(yōu)性原理、無記憶性與記憶性進行比較系統(tǒng)的闡述，指出最優(yōu)性原理表現(xiàn)在最短路問題中即是“最短路徑的子路徑必然是最短的”。最后，還可以以最短路分析動態(tài)規(guī)劃求解時常用的“空間換時間”策略。

[關(guān)鍵詞]動態(tài)規(guī)劃;最優(yōu)性原理;無記憶性;記憶性

[中圖分類號] TP399 [文獻標(biāo)識碼] A [文章編號] 2095-3437（2016）01-0108-02

在運籌學(xué)的分支體系中，動態(tài)規(guī)劃因其應(yīng)用的廣泛性而占有十分重要的地位。但動態(tài)規(guī)劃僅僅是解決某類特殊的多階段決策問題的一種方法，不具有統(tǒng)一的數(shù)學(xué)模型和算法步驟[1]，而且概念多，因此學(xué)生普遍反應(yīng)“動態(tài)規(guī)劃真的有用但確實難學(xué)”。本文以最短路問題為案例，對動態(tài)規(guī)劃相關(guān)概念、最優(yōu)性原理、無記憶性等進行了闡釋。

一、案例的選擇

可用動態(tài)規(guī)劃求解的問題很多，如最短路、資源分配、生產(chǎn)與存儲等，而最短路問題因其空間特征明顯，易于劃分階段、易于描述每階段開始和結(jié)束時的狀態(tài)，以及在每個狀態(tài)之下做出的決策、每次決策產(chǎn)生的決策指標(biāo)值等，因此，對初學(xué)者而言，最易接受和理解的例子還是最短路問題。本文以最短路問題作為引例，幫助學(xué)生們理解和掌握動態(tài)規(guī)劃的相關(guān)概念及基本方程、最優(yōu)性原理等。

二、相關(guān)概念的解釋

動態(tài)規(guī)劃相關(guān)概念繁多，從階段、狀態(tài)開始，到過程指標(biāo)函數(shù)，剛接觸時，不少學(xué)生感到一頭霧水，十分茫然。而借助于最短路問題，將動態(tài)規(guī)劃的相關(guān)概念與最短路問題中大家耳熟能詳?shù)拿Q相對應(yīng)，則十分有助于學(xué)生對動態(tài)規(guī)劃基本概念的把握。相關(guān)概念具體對應(yīng)關(guān)系如表1所示。

從上表可知，動態(tài)規(guī)劃的基本概念在最短路問題中都可找到與之對應(yīng)的解釋，非常有助于學(xué)生掌握動態(tài)規(guī)劃問題的實質(zhì)。

三、最優(yōu)性原理的解釋

教材[1]對最優(yōu)性原理作了如下表述：無論過去的決策和狀態(tài)如何，對前面的決策所形成的當(dāng)前狀態(tài)而言，余下的決策序列必須構(gòu)成最優(yōu)策略，即最優(yōu)策略的子策略總是最優(yōu)的。

對最優(yōu)性原理，部分學(xué)生將其理解為：組成最優(yōu)策略的決策必須是最優(yōu)的。產(chǎn)生這種誤解的原因是將決策與策略相混淆。在動態(tài)規(guī)劃中，決策指的是在某種狀態(tài)下作出的一種選擇，是一種瞬時行為。決策無優(yōu)劣之分，每一步?jīng)Q策會產(chǎn)生一個決策指標(biāo)值rk（Sk，Xk），它只是說明本次決策產(chǎn)生的益損值;而策略是由一系列決策所組成，策略是決策的集合，策略有優(yōu)劣之分，度量策略優(yōu)劣的數(shù)量指標(biāo)值就是指標(biāo)函數(shù)值fk（Sk）。一般而言，指標(biāo)函數(shù)值是決策指標(biāo)值的和或積的形式，即

fk（Sk）=opt（rj（Sj，Xj））或fk（Sk）=opt（rj（Sj，Xj））。

因此，單步?jīng)Q策的最優(yōu)化一般不可能產(chǎn)生全策略的最優(yōu)化，而子策略的最優(yōu)化必將導(dǎo)致全策略的最優(yōu)化，這可由下面的Bellman方程看出。

fk（Sk）=opt（rk（Sk，Xk）？茌fk+1（Sk+1））fn+1（Sn+1）=0或1

Bellman方程可作如下解釋：第K步子策略的最優(yōu)性是由第K步的決策（注意：不是第K步的最優(yōu)決策）與第K+1步的最優(yōu)子策略產(chǎn)生的，即K+1步子策略的最優(yōu)性必將導(dǎo)致K步子策略的最優(yōu)性，K步子策略的最優(yōu)性必將導(dǎo)致K-1步子策略的最優(yōu)性，依此類推，直至1步子策略即全過程策略的最優(yōu)性。

現(xiàn)在，再結(jié)合最短路問題來分析最優(yōu)性原理。生活中的常識告訴我們，最短路有一個重要特性：如果由起點A經(jīng)過H點和P點而到達終點T是一條最短路線，則由點H出發(fā)經(jīng)過P點而到達終點T的這條子路線，對于從點H出發(fā)到達終點T的所有可能選擇的不同路線來說，必定也是最短路線。此特性用反證法易證。因為如果不是這樣，則從點H到T點有另一條距離更短的路線存在，把它和原來最短路線由A點到達H點的那部分連接起來，就會得到一條由A點到終點T的新路線，它比原來那條最短路線的距離還要短。這與假設(shè)矛盾，是不可能的。

因此，借助最短路徑問題的相關(guān)常識，最優(yōu)性原理可表述為：最短路徑的子路徑必然是最短的。

四、無記憶性與記憶性

在動態(tài)規(guī)劃一章中，教師經(jīng)常會提到“無記憶性”與“記憶性”兩個看似完全矛盾的概念，不少學(xué)生也感到十分茫然。其實，這兩個概念在動態(tài)規(guī)劃中得到了完美的統(tǒng)一。

“無記憶性”指的是可用動態(tài)規(guī)劃方法求解的多階段決策問題，在劃分階段時，狀態(tài)必須滿足的一個特性，也稱為無后效性或馬爾科夫性。其實質(zhì)是：某階段的狀態(tài)一旦確定，則此后過程的演變不再受此前各狀態(tài)及決策的影響。即“未來與過去無關(guān)”，當(dāng)前的狀態(tài)是此前歷史的一個完整總結(jié)，此前的歷史只能通過當(dāng)前的狀態(tài)去影響過程未來的演變。[1]

“記性性”指的是用動態(tài)規(guī)劃方法求解多階段決策問題時（以逆序為例），為求得第K步最優(yōu)子策略fk（Sk），必須先計算出從第K+1階段的各狀態(tài)出發(fā)所對應(yīng)的最優(yōu)子策略fk+1（Sk+1），并由第K+1步的最優(yōu)子策略fk+1（Sk+1）去求取第K步最優(yōu)子策略fk（Sk）。這些后續(xù)狀態(tài)對應(yīng)的最優(yōu)子策略實際上構(gòu)成了一張查找表（Lookup Table）。[3]為更好地理解無記憶性與記憶性，仍以最短路問題為例進行說明。

假設(shè)有一個可分為10個階段的最短路問題，每階段有10個狀態(tài)可供選擇。“無記憶性”指的是當(dāng)游客在第k階段處于狀態(tài)Sk時，則該游客從Sk出發(fā)到終點的最短路徑（K步最優(yōu)子策略）只與Sk相關(guān)，而與Sk之前的狀態(tài)、決策無任何關(guān)系。

“記憶性”指的是當(dāng)用動態(tài)規(guī)劃方法求解最短路問題時，第K步最優(yōu)子策略是由第K步的決策和第K+1步的最優(yōu)子策略共同決定的，而第K+1步的最優(yōu)子策略已在之前求出并存放于內(nèi)存之中，這就是記憶性。動態(tài)規(guī)劃的記憶性可節(jié)省大量的計算時間，但會占用較多的計算機內(nèi)存，即常用的“空間換時間”策略。

以上題為例，10個階段每階段10個狀態(tài)的最短路問題，如果采用窮舉法，則需要計算的路徑條數(shù)（相當(dāng)于動態(tài)規(guī)劃中的全策略）為109條，每條路徑需要進行10次加法運算;在109條路徑中找出最短路徑需要進行109-1次比較運算，則總的基本運算是11*109-1次。

而采用動態(tài)規(guī)劃方法時，每階段的每個狀態(tài)需要進行10次加法運算和9次比較運算，則總的基本運算次數(shù)為1539次（其中加法運算810次，比較運算729次），和窮舉法比較可節(jié)省大量的計算時間。

從該例題的分析可知，一個多階段決策問題之所以可采用有“記憶性”的動態(tài)規(guī)劃方法求解，恰恰是因為該問題在劃分階段時，各階段的自然特征（即狀態(tài)）滿足“無記憶性”。因此，我們說，“記憶性”與“無記憶性”在動態(tài)規(guī)劃中得到了完美的統(tǒng)一。

五、結(jié)束語

經(jīng)教學(xué)實踐證明，在動態(tài)規(guī)劃教學(xué)中以最短路為引例，有利于學(xué)生對動態(tài)規(guī)劃相關(guān)概念的理解，尤其有利于學(xué)生掌握最優(yōu)性原理和無記憶性、記憶性這些晦澀難懂的原理與性質(zhì)，為學(xué)生學(xué)好、用好動態(tài)規(guī)劃打下了良好基礎(chǔ)。

[ 參 考 文 獻 ]

[1] 胡運權(quán).運籌學(xué)教程（第四版）[M].北京：清華大學(xué)出版社，2012：191-232.

[2] Bellman R. E.Dynamical Programming[M].普林斯頓大學(xué)出版社，1957：58-92.

[3] Hamdy A. Taha. Operations Research：An introduction（第8版）[M].北京：人民郵電出版社，2008：744-754.

[4] 《運籌學(xué)》教材編寫組.運籌學(xué)（第三版）[M].北京：清華大學(xué)出版社，2005：194-215.

[5] 韓伯棠.管理運籌學(xué)（第二版）[M].北京：高等教育出版社，2005：256-262.

[責(zé)任編輯：王 品]