《算法設計與分析》第07章

《《算法設計與分析》第07章》由會員上傳分享，免費在線閱讀，更多相關內容在教育資源-天天文庫。

1、7.1一般方法和基本要素7.2每對結點間的最短路徑7.3矩陣連乘7.4最長公共子序列7.5最優(yōu)二叉搜索樹7.60/1背包7.7流水作業(yè)調度第7章動態(tài)規(guī)劃法20世紀50年代初美國數學家R.E.Bellman等人在研究多階段決策過程的優(yōu)化問題時，提出了著名的最優(yōu)化原理(principleofoptimality)，把多階段過程轉化為一系列單階段問題，創(chuàng)立了解決這類過程優(yōu)化問題的新方法——動態(tài)規(guī)劃。動態(tài)規(guī)劃(dynamicprogramming)是運籌學的一個分支，是求解決策過程(decisionprocess)最優(yōu)化的數學方法。應用

2、領域：動態(tài)規(guī)劃問世以來，在經濟管理、生產調度、工程技術和最優(yōu)控制等方面得到了廣泛的應用。例如最短路線、庫存管理、資源分配、設備更新、排序、裝載等問題，用動態(tài)規(guī)劃方法比用其它方法求解更為方便。動態(tài)規(guī)劃法的實質也是將較大問題分解為較小的同類子問題，這一點上它與分治法和貪心法類似。但動態(tài)規(guī)劃法有自己的特點。分治法的子問題相互獨立，相同的子問題被重復計算，動態(tài)規(guī)劃法解決這種子問題重疊現象。貪心法要求針對問題設計最優(yōu)量度標準，但這在很多情況下并不容易。動態(tài)規(guī)劃法利用最優(yōu)子結構，自底向上從子問題的最優(yōu)解逐步構造出整個問題的最優(yōu)解，動態(tài)規(guī)劃則

3、可以處理不具備貪心準則的問題。7.1一般方法和基本要素7.1.1一般方法最優(yōu)性原理指出，一個最優(yōu)策略具有這樣的性質，不論過去狀態(tài)和決策如何，對前面的決策所形成的狀態(tài)而言，其余決策必定構成最優(yōu)策略。這便是最優(yōu)決策序列的最優(yōu)子結構特性。利用動態(tài)規(guī)劃求解問題的前提：1)證明問題滿足最優(yōu)性原理如果對所求解問題證明滿足最優(yōu)性原理，則說明用動態(tài)規(guī)劃方法有可能解決該問題2)獲得問題狀態(tài)的遞推關系式獲得各階段間的遞推關系式是解決問題的關鍵。7.1.3多段圖問題例7－1多段圖G=(V,E)是一個帶權有向圖，它具有如下特性：圖中的結點被劃分成k?2

4、個互不相交的子集Vi，1?i?k。其中V1和Vk分別只有一個結點，V1包含源點（source）s，Vk包含匯點（sink）t。對所有邊?E，多段圖要求若u?Vi，則v?Vi＋1，1?i

5、(u,v)均具有如下性質：若∈E，則若u∈Vi，則u∈Vi＋1,即該邊將是從某段i指向i+1段，1≤i≤k－1。成本：每條邊(u,v)均附有成本c(u,v)。s到t的路徑：是一條從第1段的源點s出發(fā)，依次經過第2段的某結點v2i，經第3段的某結點v3j、…、最后在第k段的匯點t結束的路徑。該路徑的成本是這條路徑上邊的成本和。多段圖問題：求由s到t的最小成本路徑。多段圖問題的多階段決策過程：生成從s到t的最小成本路徑是在k-2個階段（除s和t外）進行某種決策的過程：從s開始，第i次決策決定Vi+1(1≤i≤k-2)中的哪

6、個結點在從s到t的最短路徑上。1.最優(yōu)性原理對多段圖問題成立假設s,v2,v3,…,vk-1,t是一條由s到t的最短路徑?！癯跏紶顟B(tài)：s●初始決策：(s,v2)，v2∈V2●初始決策產生的狀態(tài)：v2則，其余的決策：v3,...,vk-1相對于v2將構成一個最優(yōu)決策序列——最優(yōu)性原理成立。反證：若不然，設v2,q3,…,qk-1,t是一條由v2到t的更短的路徑，則s,v2,q3,…,qk-1,t將是比s,v2,v3,…,vk-1,t更短的從s到t的路徑。與假設矛盾。故，最優(yōu)性原理成立即，是v2v3,...,vk-1t構成從v2至t

7、的最短路徑2.向前處理策略求解設P(i,j)是一條從Vi中的結點j到匯點t的最小成本路徑，cost(i,j)是這條路徑的成本。1)向前遞推式cost(k,t)=02)遞推過程★第k-1段c(j,t)∈ECOST(k-1,j)=∞∈0≤i≤k-2l1l2...lpi+1t…jViVi+112345678910111297324227111181456356425V1V2V3V4V55段圖★各遞推結果第4段COST(4,9)=c(9,12)=4COST(4,10)=c(10,12)=2COST(4,11)=c(11,12)

8、=5第3段COST(3,6)=min{6+COST(4,9),5+COST(4,10)}=7COST(3,7)=min{4+COST(4,9),3+COST(4,10)}=5COST(3,8)=min{5+COST(4,10),6+COST(4,11)}=7第2