動(dòng)態(tài)規(guī)劃算法原理及應(yīng)用

1、動(dòng)態(tài)規(guī)劃算法 劉興田（浙江工業(yè)大學(xué) 計(jì)算機(jī)學(xué)院 軟件工程1205班 201226630512）摘要：動(dòng)態(tài)規(guī)劃是解決最優(yōu)化問(wèn)題的基本方法，本文介紹了動(dòng)態(tài)規(guī)劃的基本思想和基本步驟，并通過(guò)幾個(gè)實(shí)例的分析，研究了利用動(dòng)態(tài)規(guī)劃設(shè)計(jì)算法的具體途徑。關(guān)鍵詞：動(dòng)態(tài)規(guī)劃 算法Dynamic Programming Liu xingtian(Zhe Jiang University Of Technology, Computer Science and Technology Campus, Software Engineering 1205 26630512)Abstract: Dynamic Programmi

2、ng is the most effective way to solve the problem of optimization .This dissertation introduce the thinking of Dynamic Programming and the step to using Dynamic Programming ,it also gives some examples to help analysis Dynamic Programming and the specific method to use Dynamic Programming .Key words

3、 : Dynamic Programming , Alsgorithm1.引言 規(guī)劃問(wèn)題的最終目的就是確定各決策變量的取值，以使目標(biāo)函數(shù)達(dá)到極大或極小。在線性規(guī)劃和非線性規(guī)劃中，決策變量都是以集合的形式被一次性處理的；然而，有時(shí)我們也會(huì)面對(duì)決策變量需分期、分批處理的多階段決策問(wèn)題。所謂多階段決策問(wèn)題是指這樣一類活動(dòng)過(guò)程：它可以分解為若干個(gè)互相聯(lián)系的階段，在每一階段分別對(duì)應(yīng)著一組可供選取的決策集合；即構(gòu)成過(guò)程的每個(gè)階段都需要進(jìn)行一次決策的決策問(wèn)題。將各個(gè)階段的決策綜合起來(lái)構(gòu)成一個(gè)決策序列，稱為一個(gè)策略。顯然，由于各個(gè)階段選取的決策不同，對(duì)應(yīng)整個(gè)過(guò)程可以有一系列不同的策略。當(dāng)過(guò)程采取某個(gè)具體策略時(shí)

4、，相應(yīng)可以得到一個(gè)確定的效果，采取不同的策略，就會(huì)得到不同的效果。多階段的決策問(wèn)題，就是要在所有可能采取的策略中選取一個(gè)最優(yōu)的策略，以便得到最佳的效果。動(dòng)態(tài)規(guī)劃是一種求解多階段決策問(wèn)題的系統(tǒng)技術(shù)，可以說(shuō)它橫跨整個(gè)規(guī)劃領(lǐng)域（線性規(guī)劃和非線性規(guī)劃）。在多階段決策問(wèn)題中，有些問(wèn)題對(duì)階段的劃分具有明顯的時(shí)序性，動(dòng)態(tài)規(guī)劃的“動(dòng)態(tài)”二字也由此而得名。動(dòng)態(tài)規(guī)劃的主要?jiǎng)?chuàng)始人是美國(guó)數(shù)學(xué)家貝爾曼（Bellman）。20世紀(jì)40年代末50年代初，當(dāng)時(shí)在蘭德公司（Rand Corporation）從事研究工作的貝爾曼首先提出了動(dòng)態(tài)規(guī)劃的概念。1957年貝爾曼發(fā)表了數(shù)篇研究論文，并出版了他的第一部著作動(dòng)態(tài)規(guī)劃。該著作成

5、為了當(dāng)時(shí)唯一的進(jìn)一步研究和應(yīng)用動(dòng)態(tài)規(guī)劃的理論源泉。在貝爾曼及其助手們致力于發(fā)展和推廣這一技術(shù)的同時(shí)，其他一些學(xué)者也對(duì)動(dòng)態(tài)規(guī)劃的發(fā)展做出了重大的貢獻(xiàn)，其中最值得一提的是愛爾思（Aris）和梅特頓（Mitten）。愛爾思先后于1961年和1964年出版了兩部關(guān)于動(dòng)態(tài)規(guī)劃的著作，并于1964年同尼母霍思爾（Nemhauser）、威爾德（Wild）一道創(chuàng)建了處理分枝、循環(huán)性多階段決策系統(tǒng)的一般性理論。梅特頓提出了許多對(duì)動(dòng)態(tài)規(guī)劃后來(lái)發(fā)展有著重要意義的基礎(chǔ)性觀點(diǎn)，并且對(duì)明晰動(dòng)態(tài)規(guī)劃路徑的數(shù)學(xué)性質(zhì)做出了巨大的貢獻(xiàn)。動(dòng)態(tài)規(guī)劃問(wèn)世以來(lái)，在工程技術(shù)、經(jīng)濟(jì)管理等社會(huì)各個(gè)領(lǐng)域都有著廣泛的應(yīng)用，并且獲得了顯著的效果。在

6、經(jīng)濟(jì)管理方面，動(dòng)態(tài)規(guī)劃可以用來(lái)解決最優(yōu)路徑問(wèn)題、資源分配問(wèn)題、生產(chǎn)調(diào)度問(wèn)題、庫(kù)存管理問(wèn)題、排序問(wèn)題、設(shè)備更新問(wèn)題以及生產(chǎn)過(guò)程最優(yōu)控制問(wèn)題等，是經(jīng)濟(jì)管理中一種重要的決策技術(shù)。許多規(guī)劃問(wèn)題用動(dòng)態(tài)規(guī)劃的方法來(lái)處理，常比線性規(guī)劃或非線性規(guī)劃更有效。特別是對(duì)于離散的問(wèn)題，由于解析數(shù)學(xué)無(wú)法發(fā)揮作用，動(dòng)態(tài)規(guī)劃便成為了一種非常有用的工具。 動(dòng)態(tài)規(guī)劃可以按照決策過(guò)程的演變是否確定分為確定性動(dòng)態(tài)規(guī)劃和隨機(jī)性動(dòng)態(tài)規(guī)劃；也可以按照決策變量的取值是否連續(xù)分為連續(xù)性動(dòng)態(tài)規(guī)劃和離散性動(dòng)態(tài)規(guī)劃。雖然動(dòng)態(tài)規(guī)劃主要用于求解以時(shí)間劃分階段的動(dòng)態(tài)過(guò)程的優(yōu)化問(wèn)題，但是一些與時(shí)間無(wú)關(guān)的靜態(tài)規(guī)劃(如線性規(guī)劃、非線性規(guī)劃)，只要人為地引進(jìn)時(shí)

7、間因素，把它視為多階段決策過(guò)程，也可以用動(dòng)態(tài)規(guī)劃方法方便地求解。2.動(dòng)態(tài)規(guī)劃的基本思想 一般來(lái)說(shuō)，只要問(wèn)題可以劃分成規(guī)模更小的子問(wèn)題，并且原問(wèn)題的最優(yōu)解中包含了子問(wèn)題的最優(yōu)解，則可以考慮用動(dòng)態(tài)規(guī)劃解決。動(dòng)態(tài)規(guī)劃的實(shí)質(zhì)是分治思想和解決冗余，因此，動(dòng)態(tài)規(guī)劃是一種將問(wèn)題實(shí)例分解為更小的、相似的子問(wèn)題，并存儲(chǔ)子問(wèn)題的解而避免計(jì)算重復(fù)的子問(wèn)題，以解決最優(yōu)化問(wèn)題的算法策略。由此可知，動(dòng)態(tài)規(guī)劃法與分治法和貪心法類似，它們都是將問(wèn)題實(shí)例歸納為更小的、相似的子問(wèn)題，并通過(guò)求解子問(wèn)題產(chǎn)生一個(gè)全局最優(yōu)解。其中貪心法的當(dāng)前選擇可能要依賴已經(jīng)作出的所有選擇，但不依賴于有待于做出的選擇和子問(wèn)題。因此貪心法自頂向下，一步一

8、步地作出貪心選擇；而分治法中的各個(gè)子問(wèn)題是獨(dú)立的 (即不包含公共的子子問(wèn)題)，因此一旦遞歸地求出各子問(wèn)題的解后，便可自下而上地將子問(wèn)題的解合并成問(wèn)題的解。但不足的是，如果當(dāng)前選擇可能要依賴子問(wèn)題的解時(shí)，則難以通過(guò)局部的貪心策略達(dá)到全局最優(yōu)解；如果各子問(wèn)題是不獨(dú)立的，則分治法要做許多不必要的工作，重復(fù)地解公共的子問(wèn)題。解決上述問(wèn)題的辦法是利用動(dòng)態(tài)規(guī)劃。該方法主要應(yīng)用于最優(yōu)化問(wèn)題，這類問(wèn)題會(huì)有多種可能的解，每個(gè)解都有一個(gè)值，而動(dòng)態(tài)規(guī)劃找出其中最優(yōu)(最大或最小)值的解。若存在若干個(gè)取最優(yōu)值的解的話，它只取其中的一個(gè)。在求解過(guò)程中，該方法也是通過(guò)求解局部子問(wèn)題的解達(dá)到全局最優(yōu)解，但與分治法和貪心法不同

9、的是，動(dòng)態(tài)規(guī)劃允許這些子問(wèn)題不獨(dú)立，也允許其通過(guò)自身子問(wèn)題的解作出選擇，該方法對(duì)每一個(gè)子問(wèn)題只解一次，并將結(jié)果保存起來(lái)，避免每次碰到時(shí)都要重復(fù)計(jì)算。 因此，動(dòng)態(tài)規(guī)劃法所針對(duì)的問(wèn)題有一個(gè)顯著的特征，即它所對(duì)應(yīng)的子問(wèn)題樹中的子問(wèn)題呈現(xiàn)大量的重復(fù)。動(dòng)態(tài)規(guī)劃法的關(guān)鍵就在于，對(duì)于重復(fù)出現(xiàn)的子問(wèn)題，只在第一次遇到時(shí)加以求解，并把答案保存起來(lái)，讓以后再遇到時(shí)直接引用，不必重新求解。3.動(dòng)態(tài)規(guī)劃的基本概念動(dòng)態(tài)規(guī)劃的數(shù)學(xué)描述離不開它的一些基本概念與符號(hào)，因此有必要在介紹多階段決策過(guò)程的數(shù)學(xué)描述的基礎(chǔ)上，系統(tǒng)地介紹動(dòng)態(tài)規(guī)劃的一些基本概念。3.1多階段決策問(wèn)題如果一類活動(dòng)過(guò)程可以分為若干個(gè)互相聯(lián)系的階段，在每一個(gè)階

10、段都需作出決策，一個(gè)階段的決策確定以后，常常影響到下一個(gè)階段的決策，從而就完全確定了一個(gè)過(guò)程的活動(dòng)路線，則稱它為多階段決策問(wèn)題。各個(gè)階段的決策構(gòu)成一個(gè)決策序列，稱為一個(gè)策略。每一個(gè)階段都有若干個(gè)決策可供選擇，因而就有許多策略供我們選取，對(duì)應(yīng)于一個(gè)策略可以確定活動(dòng)的效果，這個(gè)效果可以用數(shù)量來(lái)確定。策略不同，效果也不同，多階段決策問(wèn)題，就是要在可以選擇的那些策略中間，選取一個(gè)最優(yōu)策略，使在預(yù)定的標(biāo)準(zhǔn)下達(dá)到最好的效果.3.2動(dòng)態(tài)規(guī)劃問(wèn)題中的術(shù)語(yǔ)階段：把所給求解問(wèn)題的過(guò)程恰當(dāng)?shù)胤殖扇舾蓚€(gè)相互聯(lián)系的階段，以便于求解，過(guò)程不同，階段數(shù)就可能不同描述階段的變量稱為階段變量。在多數(shù)情況下，階段變量是離散的，用

11、k表示。此外，也有階段變量是連續(xù)的情形。如果過(guò)程可以在任何時(shí)刻作出決策，且在任意兩個(gè)不同的時(shí)刻之間允許有無(wú)窮多個(gè)決策時(shí)，階段變量就是連續(xù)的。狀態(tài)：狀態(tài)表示每個(gè)階段開始面臨的自然狀況或客觀條件，它不以人們的主觀意志為轉(zhuǎn)移，也稱為不可控因素。在上面的例子中狀態(tài)就是某階段的出發(fā)位置，它既是該階段某路的起點(diǎn)，同時(shí)又是前一階段某支路的終點(diǎn)。過(guò)程的狀態(tài)通?？梢杂靡粋€(gè)或一組數(shù)來(lái)描述，稱為狀態(tài)變量。一般，狀態(tài)是離散的，但有時(shí)為了方便也將狀態(tài)取成連續(xù)的。當(dāng)然，在現(xiàn)實(shí)生活中，由于變量形式的限制，所有的狀態(tài)都是離散的，但從分析的觀點(diǎn)，有時(shí)將狀態(tài)作為連續(xù)的處理將會(huì)有很大的好處。此外，狀態(tài)可以有多個(gè)分量(多維情形)，因

12、而用向量來(lái)代表；而且在每個(gè)階段的狀態(tài)維數(shù)可以不同。無(wú)后效性：我們要求狀態(tài)具有下面的性質(zhì)：如果給定某一階段的狀態(tài)，則在這一階段以后過(guò)程的發(fā)展不受這階段以前各段狀態(tài)的影響，所有各階段都確定時(shí)，整個(gè)過(guò)程也就確定了。換句話說(shuō)，過(guò)程的每一次實(shí)現(xiàn)可以用一個(gè)狀態(tài)序列表示，在前面的例子中每階段的狀態(tài)是該線路的始點(diǎn)，確定了這些點(diǎn)的序列，整個(gè)線路也就完全確定。從某一階段以后的線路開始，當(dāng)這段的始點(diǎn)給定時(shí)，不受以前線路（所通過(guò)的點(diǎn)）的影響。狀態(tài)的這個(gè)性質(zhì)意味著過(guò)程的歷史只能通過(guò)當(dāng)前的狀態(tài)去影響它的未來(lái)的發(fā)展，這個(gè)性質(zhì)稱為無(wú)后效性。決策：一個(gè)階段的狀態(tài)給定以后，從該狀態(tài)演變到下一階段某個(gè)狀態(tài)的一種選擇（行動(dòng)）稱為決策

13、。在最優(yōu)控制中，也稱為控制。在許多間題中，決策可以自然而然地表示為一個(gè)數(shù)或一組數(shù)。不同的決策對(duì)應(yīng)著不同的數(shù)值。描述決策的變量稱決策變量，因狀態(tài)滿足無(wú)后效性，故在每個(gè)階段選擇決策時(shí)只需考慮當(dāng)前的狀態(tài)而無(wú)須考慮過(guò)程的歷史。決策變量的范圍稱為允許決策集合。策略：由每個(gè)階段的決策組成的序列稱為策略。對(duì)于每一個(gè)實(shí)際的多階段決策過(guò)程，可供選取的策略有一定的范圍限制，這個(gè)范圍稱為允許策略集合。允許策略集合中達(dá)到最優(yōu)效果的策略稱為最優(yōu)策略。給定k階段狀態(tài)變量x(k)的值后，如果這一階段的決策變量一經(jīng)確定，第k+1階段的狀態(tài)變量x(k+1)也就完全確定，即x(k+1)的值隨x(k)和第k階段的決策u(k)的值變

14、化而變化，那么可以把這一關(guān)系看成(x(k)，u(k)與x(k+1)確定的對(duì)應(yīng)關(guān)系，用x(k+1)=Tk(x(k),u(k)表示。這是從k階段到k+1階段的狀態(tài)轉(zhuǎn)移規(guī)律，稱為狀態(tài)轉(zhuǎn)移方程。最優(yōu)性原理: 作為整個(gè)過(guò)程的最優(yōu)策略，它滿足：相對(duì)前面決策所形成的狀態(tài)而言，余下的子策略必然構(gòu)成“最優(yōu)子策略”。4.動(dòng)態(tài)規(guī)劃求解的基本步驟動(dòng)態(tài)規(guī)劃所處理的問(wèn)題是一個(gè)多階段決策問(wèn)題，一般由初始狀態(tài)開始，通過(guò)對(duì)中間階段決策的選擇，達(dá)到結(jié)束狀態(tài)。這些決策形成了一個(gè)決策序列，同時(shí)確定了完成整個(gè)過(guò)程的一條活動(dòng)路線(通常是求最優(yōu)的活動(dòng)路線)。如圖所示。動(dòng)態(tài)規(guī)劃的設(shè)計(jì)都有著一定的模式，一般要經(jīng)歷以下幾個(gè)步驟。初始狀態(tài)決策決策

15、決策結(jié)束狀態(tài) 動(dòng)態(tài)規(guī)劃決策過(guò)程示意圖(1)劃分階段：，按照問(wèn)題的時(shí)間或空間特征，把問(wèn)題分為若干個(gè)階段。在劃分階段時(shí)，注意劃分后的階段一定要是有序的或者是可排序的，否則問(wèn)題就無(wú)法求解。 (2)確定狀態(tài)和狀態(tài)變量：將問(wèn)題發(fā)展到各個(gè)階段時(shí)所處于的各種客觀情況用不同的狀態(tài)表示出來(lái)。當(dāng)然，狀態(tài)的選擇要滿足無(wú)后效性。 (3)確定決策并寫出狀態(tài)轉(zhuǎn)移方程：因?yàn)闆Q策和狀態(tài)轉(zhuǎn)移有著天然的聯(lián)系，狀態(tài)轉(zhuǎn)移就是根據(jù)上一階段的狀態(tài)和決策來(lái)導(dǎo)出本階段的狀態(tài)。所以如果確定了決策，狀態(tài)轉(zhuǎn)移方程也就可寫出。但事實(shí)上常常是反過(guò)來(lái)做，根據(jù)相鄰兩段各狀態(tài)之間的關(guān)系來(lái)確定決策。 (4)尋找邊界條件：給出的狀態(tài)轉(zhuǎn)移方程是一個(gè)遞推式，需要一

16、個(gè)遞推的終止條件或邊界條件。 (5)程序設(shè)計(jì)實(shí)現(xiàn)：動(dòng)態(tài)規(guī)劃的主要難點(diǎn)在于理論上的設(shè)計(jì)，一旦設(shè)計(jì)完成，實(shí)現(xiàn)部分就會(huì)非常簡(jiǎn)單。根據(jù)上述動(dòng)態(tài)規(guī)劃設(shè)計(jì)的步驟，可得到大體解題框架如圖所示。 動(dòng)態(tài)規(guī)劃設(shè)計(jì)的一般模式圖 上述提供了動(dòng)態(tài)規(guī)劃方法的一般模式，對(duì)于簡(jiǎn)單的動(dòng)態(tài)規(guī)劃問(wèn)題，可以按部就班地進(jìn)行動(dòng)態(tài)規(guī)劃的設(shè)計(jì)。下面，給出一個(gè)利用動(dòng)態(tài)規(guī)劃方法求解的典型例子。 上圖示出了一個(gè)數(shù)字三角形寶塔。數(shù)字三角形中的數(shù)字為不超過(guò)100的整數(shù)?，F(xiàn)規(guī)定從最頂層走到最底層，每一步可沿左斜線向下或右斜線向下走。 任務(wù)一：假設(shè)三角形行數(shù)10，鍵盤輸入一個(gè)確定的整數(shù)值M，編程確定是否存在一條路徑，使得沿著該路徑所經(jīng)過(guò)的數(shù)字的總和恰為M

17、，若存在則給出所有路徑，若不存在，則輸出“NOAnswer!”字樣。 任務(wù)二：假設(shè)三角形行數(shù)100，編程求解從最頂層走到最底層的一條路徑，使得沿著該路徑所經(jīng)過(guò)的數(shù)字的總和最大，輸出最大值。輸人數(shù)據(jù)：由文件輸入數(shù)據(jù)，任務(wù)一中文件第一行是三角形的行數(shù)N和整數(shù)值M。以后的N行分別是從最頂層到最底層的每一層中的數(shù)字。任務(wù)二中文件數(shù)據(jù)格式同任務(wù)一，只是第一行中沒(méi)有整數(shù)值M。在例子中任務(wù)二的文件數(shù)據(jù)表示如下： 輸入：5 7 輸出： 輸出路徑和最大值 3 8 7 或“No Answer!”字樣。 8 1 0 38 2 7 7 4 810 4 5 2 6 5 2744圖3 數(shù)字三角形 45265【分析】對(duì)于這

18、一問(wèn)題，很容易想到用枚舉的方法去解決，即列舉出所有路徑并記錄每一條路徑所經(jīng)過(guò)的數(shù)字總和。然后判斷數(shù)字總和是否等于給定的整數(shù)值M或?qū)ふ页鲎畲蟮臄?shù)字總和，這一想法很直觀，而且對(duì)于任務(wù)一，由于數(shù)字三角形的行數(shù)不大(10)，因此其枚舉量不是很大，應(yīng)該能夠?qū)崿F(xiàn)。但對(duì)于任務(wù)二，如果用枚舉的方法，當(dāng)三角形的行數(shù)等于100時(shí)，其枚舉量之大是可想而知的，顯然，枚舉法對(duì)于任務(wù)二的求解并不適用。其實(shí)，只要對(duì)對(duì)任務(wù)二稍加分析，就可以得出一個(gè)結(jié)論： 如果得到一條由頂至底的某處的一條最佳路徑，那么對(duì)于該路徑上的每一個(gè)中間點(diǎn)來(lái)說(shuō)，由頂至該中間點(diǎn)的路徑所經(jīng)過(guò)的數(shù)字和也為最大。因此該問(wèn)題是一個(gè)典型的多階段決策最優(yōu)化的問(wèn)題。算法

19、設(shè)計(jì)與分析如下： 對(duì)于任務(wù)一，合理地確認(rèn)枚舉的方法，可以優(yōu)化問(wèn)題的解法。由于從塔頂?shù)降讓用看味贾挥袃煞N走法，即左或右。設(shè)“0”表示左，“1”表示右，對(duì)于層數(shù)為N的數(shù)字塔，從頂?shù)降椎囊环N走法可用一個(gè)N-1位的二進(jìn)制數(shù)表示。如例中二進(jìn)制數(shù)字串1011，其對(duì)應(yīng)的路徑應(yīng)該是：8146。這樣就可以用一個(gè)Nl位的二進(jìn)制數(shù)來(lái)模擬走法和確定解的范圍。窮舉出從0到2n-1個(gè)十進(jìn)制數(shù)所對(duì)應(yīng)的N-1位二進(jìn)制串對(duì)應(yīng)的路徑中的數(shù)字總和，判定其是否等于M而求得問(wèn)題的解。 對(duì)于任務(wù)二，采用動(dòng)態(tài)規(guī)劃中的順推解法。按三角形的行劃分階段，若行數(shù)為n，則可把問(wèn)題看做一個(gè)n-1個(gè)階段的決策問(wèn)題。從始點(diǎn)出發(fā)，依順向求出第一階段、第二階

20、段第n1階段中各決策點(diǎn)至始點(diǎn)的最佳路徑，最終求出始點(diǎn)到終點(diǎn)的最佳路徑。 設(shè)：fk(Uk)為從第k階段中的點(diǎn)Uk至三角形頂點(diǎn)有一條最佳路徑，該路徑所經(jīng)過(guò)的數(shù)字的總和最大，fk(Uk)表示為這個(gè)數(shù)字和；由于每一次決策有兩個(gè)選擇，或沿左斜線向下，或沿右斜線向下，因此設(shè)： Uk1為k-1階段中某點(diǎn)Uk沿左斜線向下的點(diǎn)； Uk2為k-1階段中某點(diǎn)Uk沿右斜線向下的點(diǎn)； dk(Uk1)為k階段中Uk1的數(shù)字；dk(Uk2)為k階段中Uk2的數(shù)字。因而可寫出順推關(guān)系式(狀態(tài)轉(zhuǎn)移方程)為： fk(Uk)=maxfk-1(Uk)+dk(Uk1)，fk-1(Uk)+dk(Uk2)(k=1，2，3，n) f0(U0

21、)0經(jīng)過(guò)一次順推，便可分別求出由頂至底N個(gè)數(shù)的N條路徑，在這N條路徑所經(jīng)過(guò)的N個(gè)數(shù)字和中，最大值即為正確答案。5.動(dòng)態(tài)規(guī)劃的應(yīng)用實(shí)例5.1最短路線問(wèn)題例1 現(xiàn)有一張地圖，各結(jié)點(diǎn)代表城市，兩結(jié)點(diǎn)間連線代表道路，線上數(shù)字表示城市間的距離。如圖1所示，試找出從結(jié)點(diǎn)A到結(jié)點(diǎn)E的最短距離。 我們可以用深度優(yōu)先搜索法來(lái)解決此問(wèn)題，該問(wèn)題的遞歸式為其中是與v相鄰的節(jié)點(diǎn)的集合，w(v,u)表示從v到u的邊的長(zhǎng)度。這個(gè)程序的效率如何呢？我們可以看到，每次除了已經(jīng)訪問(wèn)過(guò)的城市外，其他城市都要訪問(wèn)，所以時(shí)間復(fù)雜度為O(n!)，這是一個(gè)“指數(shù)級(jí)”的算法。 首先，我們來(lái)觀察一下這個(gè)算法。在求從B1到E的最短距離的時(shí)候，

22、先求出從C2到E的最短距離；而在求從B2到E的最短距離的時(shí)候，又求了一遍從C2到E的最短距離。也就是說(shuō)，從C2到E的最短距離我們求了兩遍。同樣可以發(fā)現(xiàn)，在求從C1、C2到E的最短距離的過(guò)程中，從D1到E的最短距離也被求了兩遍。而在整個(gè)程序中，從D1到E的最短距離被求了四遍。如果在求解的過(guò)程中，同時(shí)將求得的最短距離記錄在案，隨時(shí)調(diào)用，就可以避免這種情況。于是，可以改進(jìn)該算法，將每次求出的從v到E的最短距離記錄下來(lái)，在算法中遞歸地求MinDistance(v)時(shí)先檢查以前是否已經(jīng)求過(guò)了MinDistance(v)，如果求過(guò)了則不用重新求一遍，只要查找以前的記錄就可以了。這樣，由于所有的點(diǎn)有n個(gè)，因

23、此不同的狀態(tài)數(shù)目有n個(gè)，該算法的數(shù)量級(jí)為O(n)。更進(jìn)一步，可以將這種遞歸改為遞推，這樣可以減少遞歸調(diào)用的開銷。5.2資源分配問(wèn)題所謂資源分配問(wèn)題，就是將一定數(shù)量的一種或若干種資源（如原材料、機(jī)器設(shè)備、資金、勞動(dòng)力等）恰當(dāng)?shù)胤峙浣o若干個(gè)使用者，以使資源得到最有效地利用。設(shè)有m種資源，總量分別為bi（i = 1,2,m），用于生產(chǎn)n種產(chǎn)品，若用xij代表用于生產(chǎn)第j種產(chǎn)品的第i種資源的數(shù)量（j = 1,2,n），則生產(chǎn)第j種產(chǎn)品的收益是其所獲得的各種資源數(shù)量的函數(shù)，即gj = f（x1j,x2j, xmj）。由于總收益是n種產(chǎn)品收益的和，此問(wèn)題可用如下靜態(tài)模型加以描述： 若是連續(xù)變量，當(dāng) = f

24、（, ）是線性函數(shù)時(shí)，該模型是線性規(guī)劃模型；當(dāng) = f（, ）是非線性函數(shù)時(shí)，該模型是非線性規(guī)劃模型。若是離散變量或（和） = f（, ）是離散函數(shù)時(shí)，此模型用線性規(guī)劃或非線性規(guī)劃來(lái)求解都將是非常麻煩的。然而在此情況下，由于這類問(wèn)題的特殊結(jié)構(gòu)，可以將它看成為一個(gè)多階段決策問(wèn)題，并利用動(dòng)態(tài)規(guī)劃的遞推關(guān)系來(lái)求解。本例只考慮一維資源的分配問(wèn)題，設(shè)狀態(tài)變量表示分配于從第k個(gè)階段至過(guò)程最終（第N個(gè)階段）的資源數(shù)量，即第k個(gè)階段初資源的擁有量；決策變量xk表示第k個(gè)階段資源的分配量。于是有狀態(tài)轉(zhuǎn)移律：允許決策集合：最優(yōu)指標(biāo)函數(shù)（動(dòng)態(tài)規(guī)劃的逆序遞推關(guān)系式）： 利用這一遞推關(guān)系式，最后求得的即為所求問(wèn)題的最大

25、總收益，下面來(lái)看一個(gè)具體的例子。例2 某公司擬將500萬(wàn)元的資本投入所屬的甲、乙、丙三個(gè)工廠進(jìn)行技術(shù)改造，各工廠獲得投資后年利潤(rùn)將有相應(yīng)的增長(zhǎng)，增長(zhǎng)額如表7-1所示。試確定500萬(wàn)元資本的分配方案，以使公司總的年利潤(rùn)增長(zhǎng)額最大。表7-1投資額100萬(wàn)元200萬(wàn)元300萬(wàn)元400萬(wàn)元500萬(wàn)元甲307090120130乙50100110110110丙4060110120120解：將問(wèn)題按工廠分為三個(gè)階段k=1，2，3，設(shè)狀態(tài)變量（）代表從第個(gè)工廠到第3個(gè)工廠的投資額，決策變量代表第k個(gè)工廠的投資額。于是有狀態(tài)轉(zhuǎn)移率、允許決策集合和遞推關(guān)系式： 當(dāng)時(shí)：于是有表7-2，表中表示第三個(gè)階段的最優(yōu)決策。