導語：動態規劃案例教學設計探討一文來源于網友上傳，不代表本站觀點，若需要原創文章可咨詢客服老師，歡迎參考。

［摘要］在運籌學的分支體系中，動態規劃因其應用的廣泛性而占有十分重要的地位。針對動態規劃教學中的難點，可以以最短路問題為引例，以大家耳熟能詳的名稱對動態規劃中的基本概念進行闡釋，并對最優性原理、無記憶性與記憶性進行比較系統的闡述，指出最優性原理表現在最短路問題中即是“最短路徑的子路徑必然是最短的”。最后，還可以以最短路分析動態規劃求解時常用的“空間換時間”策略。

［關鍵詞］動態規劃；最優性原理；無記憶性；記憶性

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

一、案例的選擇

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

二、相關概念的解釋

動態規劃相關概念繁多，從階段、狀態開始，到過程指標函數，剛接觸時，不少學生感到一頭霧水，十分茫然。而借助于最短路問題，將動態規劃的相關概念與最短路問題中大家耳熟能詳的名稱相對應，則十分有助于學生對動態規劃基本概念的把握。

三、最優性原理的解釋教材[1]

對最優性原理作了如下表述：無論過去的決策和狀態如何，對前面的決策所形成的當前狀態而言，余下的決策序列必須構成最優策略，即最優策略的子策略總是最優的。

四、無記憶性與記憶性

在動態規劃一章中，教師經常會提到“無記憶性”與“記憶性”兩個看似完全矛盾的概念，不少學生也感到十分茫然。其實，這兩個概念在動態規劃中得到了完美的統一。“無記憶性”指的是可用動態規劃方法求解的多階段決策問題，在劃分階段時，狀態必須滿足的一個特性，也稱為無后效性或馬爾科夫性。其實質是：某階段的狀態一旦確定，則此后過程的演變不再受此前各狀態及決策的影響。即“未來與過去無關”，當前的狀態是此前歷史的一個完整總結，此前的歷史只能通過當前的狀態去影響過程未來的演變。[1]“記性性”指的是用動態規劃方法求解多階段決策問題時（以逆序為例），為求得第K步最優子策略fk（Sk），必須先計算出從第K＋1階段的各狀態出發所對應的最優子策略fk＋1（Sk＋1），并由第K＋1步的最優子策略fk＋1（Sk＋1）去求取第K步最優子策略fk（Sk）。這些后續狀態對應的最優子策略實際上構成了一張查找表（LookupTable）。[3]為更好地理解無記憶性與記憶性，仍以最短路問題為例進行說明。假設有一個可分為10個階段的最短路問題，每階段有10個狀態可供選擇。“無記憶性”指的是當游客在第k階段處于狀態Sk時，則該游客從Sk出發到終點的最短路徑（K步最優子策略）只與Sk相關，而與Sk之前的狀態、決策無任何關系。“記憶性”指的是當用動態規劃方法求解最短路問題時，第K步最優子策略是由第K步的決策和第K＋1步的最優子策略共同決定的，而第K＋1步的最優子策略已在之前求出并存放于內存之中，這就是記憶性。動態規劃的記憶性可節省大量的計算時間，但會占用較多的計算機內存，即常用的“空間換時間”策略。以上題為例，10個階段每階段10個狀態的最短路問題，如果采用窮舉法，則需要計算的路徑條數（相當于動態規劃中的全策略）為109條，每條路徑需要進行10次加法運算；在109條路徑中找出最短路徑需要進行109－1次比較運算，則總的基本運算是11＊109－1次。而采用動態規劃方法時，每階段的每個狀態需要進行10次加法運算和9次比較運算，則總的基本運算次數為1539次（其中加法運算810次，比較運算729次），和窮舉法比較可節省大量的計算時間。從該例題的分析可知，一個多階段決策問題之所以可采用有“記憶性”的動態規劃方法求解，恰恰是因為該問題在劃分階段時，各階段的自然特征（即狀態）滿足“無記憶性”。因此，我們說，“記憶性”與“無記憶性”在動態規劃中得到了完美的統一。

五、結束語

經教學實踐證明，在動態規劃教學中以最短路為引例，有利于學生對動態規劃相關概念的理解，尤其有利于學生掌握最優性原理和無記憶性、記憶性這些晦澀難懂的原理與性質，為學生學好、用好動態規劃打下了良好基礎。

［參考文獻］

［1］胡運權.運籌學教程（第四版）［M］．北京：清華大學出版社，2012：191-232．

［2］［M］．普林斯頓大學出版社，1957：58-92．

［3］北京：人民郵電出版社，2008：744-754．

［4］《運籌學》教材編寫組.運籌學（第三版）［M］．北京：清華大學出版社，2005：194-215．

［5］韓伯棠.管理運籌學（第二版）［M］．北京：高等教育出版社，2005：256-262．

作者:劉光霆 蔡萬銘 沈鑫 向朝參 單位:后勤工程學院