動態(tài)規(guī)劃思想精選(九篇)

前言：一篇好文章的誕生，需要你不斷地搜集資料、整理思路，本站小編為你收集了豐富的動態(tài)規(guī)劃思想主題范文，僅供參考，歡迎閱讀并收藏。

第1篇：動態(tài)規(guī)劃思想范文

Abstract： It is very important for the routing optimization of the apparel chain distribution to raise the service level， reduce the product costs and improve the enterprise benefit of the apparel chain enterprise. According to the basic thought of the dynamic programming， and in combination with the problem of the routing selection and the time-varying factor in the apparel chain distribution logistics process， the impact factor of the unexpected events is introduced and the improved routing optimization algorithm suitable for the apparel chain logistics distribution process. In conjunction with the specific example， the effectiveness and the feasibility of the routing optimization algorithm is validated and the method is too extended to the touting selection of another logistics distribution.

Key words： dynamic programming； apparel chain； distribution； routing optimization

0 引 言

近年來，隨著市場經(jīng)濟(jì)的不斷深入以及人們生活水平的不斷提高，服裝連鎖經(jīng)營在我國有了很大的發(fā)展，品牌服裝的銷售量日益增加，連鎖門店市場的競爭越來越激烈[1]。在電子商務(wù)出現(xiàn)以后，由于電子商務(wù)突破了時空限制、新媒體對服裝全方位的展示、低的交易成本與低庫存、較少的中間環(huán)節(jié)所帶來的交易費用的優(yōu)勢等，給連鎖服裝門店的經(jīng)營帶來了新的挑戰(zhàn)[2-3]。在人們?nèi)找孀非蠓b個性化、高增值服務(wù)的時代，在原材料與人力資源成本挖掘的空間越來越小的情況下，服裝連鎖企業(yè)越來越關(guān)注作為企業(yè)第三利潤源泉的物流的作用[3]，通過降低物流成本、加快配送速度、優(yōu)化配送路徑等措施來提高企業(yè)的競爭力。

在優(yōu)化配送路徑方面，人們做了很多工作。20世紀(jì)50年代，美國數(shù)學(xué)家Bellman等人在研究多階段決策過程的優(yōu)化問題時提出了動態(tài)規(guī)劃法。動態(tài)規(guī)劃法解決了線性規(guī)劃和非線性規(guī)劃無法處理的多階段決策問題[4]。后來，試圖將圖的廣度優(yōu)先搜索算法、蟻群算法與動態(tài)規(guī)劃法結(jié)合求解關(guān)鍵路徑問題[5-9]，或者簡單使用動態(tài)規(guī)劃法研究物流配送的最短路徑[10-11]，但所有這些方法都無法對時變環(huán)境下的路徑進(jìn)行隨機(jī)選擇。

本文根據(jù)動態(tài)規(guī)劃的基本思想，通過對傳統(tǒng)動態(tài)規(guī)劃模型的改進(jìn)，將服裝物流配送過程中因道路、天氣、車輛狀況等引起的突發(fā)事件考慮到模型中，提出了一類高效實用的服裝物流配送路徑優(yōu)化方法。通過該模型的應(yīng)用，服裝連鎖企業(yè)可以得到盡量優(yōu)化的配送路徑，對降低配送成本、提高服務(wù)質(zhì)量、提高企業(yè)經(jīng)濟(jì)效益具有重要的意義。

1 動態(tài)規(guī)劃法簡介

1.1 動態(tài)規(guī)劃法的基本思想[4]

美國數(shù)學(xué)家Bellman等人在研究多階段決策過程的優(yōu)化問題時，通過將多階段過程轉(zhuǎn)化為一系列單階段問題，然后逐一求解，創(chuàng)立了解決多階段過程的動態(tài)規(guī)劃方法，即通常所說的Bellman最優(yōu)性原理。動態(tài)規(guī)劃算法的基本思想是將待求解問題分解為若干子問題，先求解子問題，然后從這些子問題的解得到原問題的解。因此，為了運(yùn)用動態(tài)規(guī)劃法，所考慮的問題：（1）必須能夠分解為相互重疊的子問題；（2）滿足最優(yōu)子結(jié)構(gòu)的特性――子問題的局部最優(yōu)將導(dǎo)致整個問題的全局最優(yōu)；（3）無后效性――當(dāng)前狀態(tài)是此前歷史的總結(jié)，此前的歷史只能通過當(dāng)前的狀態(tài)去影響未來的決策。

1.2 動態(tài)規(guī)劃法的求解過程

各個子問題之間的重疊關(guān)系通過狀態(tài)轉(zhuǎn)移方程（或動態(tài)規(guī)劃函數(shù)）來表現(xiàn)。為了避免重復(fù)計算，將子問題的解填入表中。

動態(tài)規(guī)劃法利用最優(yōu)性原理，采用自底向上的方式，先求出子問題的最優(yōu)解，然后逐步求得整個問題的最優(yōu)解，其求解思路如圖2所示。

因此，使用動態(tài)規(guī)劃法進(jìn)行決策，需要將原問題分解為若干個相互重疊的子問題，進(jìn)行分段決策；然后根據(jù)最優(yōu)性原理，分析問題，建立狀態(tài)轉(zhuǎn)移方程（或動態(tài)規(guī)劃函數(shù)）；最后采用自底向上的求解方法，求出問題的解，從而實現(xiàn)動態(tài)規(guī)劃過程。

為了構(gòu)建簡單實用的服裝運(yùn)輸車輛配送路徑選擇的數(shù)學(xué)模型，假設(shè)：

（1）配送車輛滿足一次配送要求；

（2）配送點是可達(dá)的；

（3）完成一次配送所采用的運(yùn)輸方式相同；

（4）單位成本固定；

（5）配送時間在可接受的范圍內(nèi)。

所以，從服裝物流配送中心S出發(fā)的服裝物流配送最短路徑長度為27，最優(yōu)路徑為SCBADS。

服裝連鎖企業(yè)一般位于人口稠密、交通擁擠的市中心，另外受天氣（如廣東、福建等沿海地區(qū)的臺風(fēng)，北方的霧霾）和道路維護(hù)等的影響，在服裝配送過程中，隨時都會發(fā)生道路擁堵、車輛故障等突發(fā)事件，而且這種突發(fā)事件一旦發(fā)生，毫無疑問會延誤對其他連鎖店的配送時間。因此，在使用動態(tài)規(guī)劃法設(shè)計服裝物流最短路徑時，必須考慮這些因素的影響。假設(shè)突發(fā)事件的影響因子為e，其取值為0？芻e≤10，若e=1表明道路通暢、能見度正常，e？芻1表明道路、天氣等優(yōu)于正常情況，e？酆1表明道理擁堵、能見度低，此值越大，說明情況越糟。

假設(shè)圖3中各邊的權(quán)重是e=1時的情況，CB段和DS段因道路維護(hù)造成擁堵，使得突發(fā)事件影響因子e？酆1，令e=5，則圖3調(diào)整后得到圖4所示。

對圖4使用上述動態(tài)規(guī)劃法，得到表2。

由表2可知，當(dāng)CB段與DS段發(fā)生突發(fā)時間造成擁堵時，有兩條最優(yōu)路徑可選，即SCDBAS或SBDCAS，且最優(yōu)路徑長度均為28。遇到這種多路徑可選的情況，可根據(jù)車輛積載情況、配送的具體情況合理選擇，在此不作詳細(xì)討論。

第2篇：動態(tài)規(guī)劃思想范文

論文關(guān)鍵詞：背包問題,動態(tài)規(guī)劃法,回溯法

 

10/1背包問題

0-1背包問題：給定n種物品和一背包。物品i的重量是Wi，其價值為Vi，背包的容量為C。問應(yīng)如何選擇裝入背包中物品，使得裝入背包中物品的總價值最大？

對于一個實例：物品種類N=4，背包容量C=10，物品重量數(shù)組W={3，5，2，1}，相應(yīng)價值數(shù)組V={9，10，7，4}。找一個n元0-1向量（x1，x2，x3….xn）xi∈{0,1},1≤i≤n.使得，達(dá)到最大。下面分別以動態(tài)規(guī)劃法和回溯法來解決這個實例。

2動態(tài)規(guī)劃法

動態(tài)規(guī)劃法的基本思想是將待求解問題分解成若干個子問題，先求解子問題，然后從這些子問題的解得到原問題的解。用一個表來保存記錄所有已解決的子問題的答案，在需要的時候再找出已求得的答案，避免重復(fù)的計算。

動態(tài)規(guī)劃法適用于解最優(yōu)化問題。通?？砂匆韵?個步驟：

(1)找出最優(yōu)解的性質(zhì)并刻畫其結(jié)構(gòu)特征。

(2)遞歸的定義最優(yōu)解。

(3)以自底向上的方式計算出最優(yōu)值。

(4)根據(jù)計算最優(yōu)值時到得的信息，構(gòu)造最優(yōu)解。

對于所給0-1背包問題的子問題：

，

的最優(yōu)值為m（i，j），即m（i，j）是背包容量為j，可懸著物品為i,i+1,….,n時0-1背包問題的最優(yōu)值。由于0-1背包問題的最優(yōu)子結(jié)構(gòu)性質(zhì)，可以建立計算m（i，j）的如下遞歸式：

（1.1）

（1.2）

從上面算法的執(zhí)行過程中可以看出假設(shè)有Q（n）個子問題,每一個子問題最多需要m次決策,則計算的頻率為nm,回溯的頻率為n，那么整個過程的算法的時間復(fù)雜度為T（n）=nm+n，即為Q（nm）。

3回溯法。

回溯法在包含問題的所有解的解空間樹中,按照深度優(yōu)先的策略,從根結(jié)點出發(fā)搜索解空間樹?；厮菟惴ㄋ阉髦两饪臻g樹的任一結(jié)點時,總是先判斷該結(jié)點是否肯定不包含問題的解。如果肯定不包含,則跳過對以該結(jié)點為根的子樹的系統(tǒng)搜索,逐層向其祖先結(jié)點回溯。否則,進(jìn)入該子樹,繼續(xù)按深度優(yōu)先的策略進(jìn)行搜索?；厮莘ㄔ谟脕砬髥栴}的所有解時,要回溯到根,且根結(jié)點的所有子樹都已被搜索遍才結(jié)束。簡單地說就是確定解空間,建立解空間樹,用深度優(yōu)先搜索算法遞歸搜索解空間樹,并同時注意剪枝。

用回溯法解題的步驟：

(1)針對所給問題定義問題的解空間；

(2)確定易于搜索的解空間結(jié)構(gòu)；

(3)以深度優(yōu)先方式搜索解空間,并在搜索過程中用剪枝函數(shù)避免無效的搜索。

根據(jù)上述0-1背包問題的數(shù)學(xué)描述解向量可以表示成X={X,X,...X|X=0或=1}若X=0,表示第i個物品不裝入背包，X=1，表示將第i個物品裝入背包。

可以用樹的形式將解空間表達(dá)出來。樹中從第i層到第i+1層的邊上的值表示解向量中X的取值，并假定第i層的左子樹描述第i個物品被裝入背包的情況，右子樹描述第i個物品被拒絕的情況。則該0-1背包問題的狀態(tài)空間樹就表示為一棵高度為n的完全二叉樹。若n=3時則此0-1背包問題的解空間的結(jié)構(gòu)如圖1-1所示。從根結(jié)點到葉子結(jié)點的任一路徑就對應(yīng)解空間中的一個解向量

圖1-1n=3時，0-1背包問題的解空間樹

用回溯法求解0-1背包問題時，可以按照物品的單位價值從大到小排序。計算當(dāng)前節(jié)點的上界,搜索左子樹。只有當(dāng)右子樹包含可行解時才搜索右子樹。剪去右子樹的條件是當(dāng)前價值加上剩余物品的總價值小于當(dāng)前的最優(yōu)總價值時,不需搜索右子樹,可將右子樹剪去。回溯法用一定的剪枝進(jìn)行優(yōu)化,算法的時間復(fù)雜度為O(n*2n),n為物品個數(shù)。

4總結(jié)

動態(tài)規(guī)劃算法：動態(tài)規(guī)劃可以把困難得多階段決策變換為一系列相互聯(lián)系比較容易的單階段問題。對于背包問題可以對子過程用枚舉法求解,而且約束條件越多,決策的搜索范圍越小,求解也越容易。但是對于規(guī)模較大的問題它并不是一個理想的算法。最重要的原因就是它的維數(shù)障礙。即計算和存儲量的需要對于狀態(tài)空間和決策空間的維數(shù)的增長呈指數(shù)增長關(guān)系，這樣驚人的增長速度是計算機(jī)難以承受的。這就使得直接的動態(tài)規(guī)劃方法求解規(guī)劃較大的背包問題發(fā)生了困難，且目前尚沒有好的解決辦法。

回溯法：回溯法需要為問題定義一個解空間,這個解空間必須至少包含問題的一個解(可能是最優(yōu)的)。使用遞歸回溯法解決背包問題的優(yōu)點在于它算法思想簡單,而且它能完全遍歷搜索空間,肯定能找到問題的最優(yōu)解。但是由于此問題解的總組合數(shù)有2個,因此,隨著物件數(shù)n的增大,其解的空間將以2級增長,當(dāng)n大到一定程度上,用此算法解決背包問題將是不現(xiàn)實的。

用此兩種方法都能得到問題的最優(yōu)解，從其時間復(fù)雜度來看，兩者的速度都較慢。

參考文獻(xiàn)

1 王曉東.算法設(shè)計與分析[M] .北京 清華大學(xué)出版社 2003.

2 王紅梅.算法設(shè)計與分析[M] .北京 清華大學(xué)出版社 2006.

第3篇：動態(tài)規(guī)劃思想范文

關(guān)鍵詞：樹型動態(tài)規(guī)劃；物流配送；配送中心選址

中圖分類號：F252.14 文獻(xiàn)標(biāo)識碼：A

摘 要：物流配送中心選址問題在物流網(wǎng)絡(luò)規(guī)劃中占有十分重要的地位，選址的合理與否直接影響配送企業(yè)的效益。文章基于樹型動態(tài)規(guī)劃，提出了物流配送中心的最佳選址算法。該算法利用樹型結(jié)構(gòu)簡化配送網(wǎng)絡(luò)，降低了選址的復(fù)雜性，具有較高的穩(wěn)定性。實驗表明，相較于目前較為普遍的算法，如傳統(tǒng)動態(tài)規(guī)劃、層次分析法等，文章所提出的算法在時間上具有明顯的優(yōu)勢。

關(guān)鍵詞：樹型動態(tài)規(guī)劃；物流配送；配送中心選址

中圖分類號：F252.14 文獻(xiàn)標(biāo)識碼：A

Abstract： The problem of logistics distribution center location plays an important role in the logistics network planning. The benefit of enterprises is affected by location selection directly. In this paper， the best location algorithm of logistics distribution center was proposed based on the tree dynamic programming. This algorithm uses the tree structure to simplify the distribution network， and reduces the complexity of location. Moreover， it has higher stability. Experiments show this algorithm has obvious advantage on time， comparing with the convention algorithm， such as traditional dynamic programming and analytic hierarchy process.

Key words： tree dynamic programming； logistics distribution； distribution center location decision

0 引 言

物流企業(yè)普遍需要同時確定多個配送地址。因而在已有的客觀條件下，如何選擇配送中心，使得整個系統(tǒng)費用最低，客戶服務(wù)效果最好，顯得尤為重要。一個良好的物流配送中心的選址方案，不但能有效節(jié)約成本，促進(jìn)生產(chǎn)和消費的協(xié)調(diào)、配合，同時能保證物流系統(tǒng)的高效和平衡發(fā)展，使企業(yè)在激烈的市場競爭中處于有利的地位。

物流配送中心的選址，對其功能的發(fā)揮和整個物流系統(tǒng)的經(jīng)濟(jì)效益影響甚大。因此，該問題也引起不少學(xué)者的關(guān)注。文獻(xiàn)[1]基于傳統(tǒng)動態(tài)規(guī)劃，提出了最優(yōu)化網(wǎng)絡(luò)銷售運(yùn)營方案；文獻(xiàn)[2]采用過濾法求解整數(shù)規(guī)劃數(shù)學(xué)模型，確定了物流配送中心的最佳地；文獻(xiàn)[3]分析了物流中心選址中涉及的眾多因素，運(yùn)用層次分析法進(jìn)行了實現(xiàn)；文獻(xiàn)[4]利用BP神經(jīng)網(wǎng)絡(luò)處理數(shù)據(jù)，建立選址決策的模糊評價矩陣；文獻(xiàn)[5]借助運(yùn)籌學(xué)思想，以距離為考慮因素，提出合理解決配送中心選址問題的方法。文獻(xiàn)[6]結(jié)合聚類蟻群算法與AHP-模糊綜合評價法，得出配送中心選址的最佳方案。

上述提及的問題，均與物流中心選址有著高度的相似性。但配送點較多時，往往要耗費大量時間進(jìn)行求解。本文基于樹型動態(tài)規(guī)劃算法，通過分層方法和樹型結(jié)構(gòu)，簡化物流配送網(wǎng)絡(luò)，降低選址的復(fù)雜度，在時間上具有明顯的優(yōu)勢。

1 問題分析

配送中心的選址直接影響了配送環(huán)節(jié)中各項活動的成本，同時也關(guān)系到配送中心的正常運(yùn)作與發(fā)展。因此，配送中心的選址和布局須在充分調(diào)查分析的基礎(chǔ)上，結(jié)合企業(yè)自身的經(jīng)營模式、商品特點及交通狀況等綜合考慮。

結(jié)合配送的相關(guān)流程，主要需考慮費用：供貨點到配送中心再到用戶的運(yùn)輸費用、流經(jīng)配送中心的產(chǎn)品的管理費用、配送中心的固定投資費用。

2 模型建立

物流配送中心的選址涉及眾多的因素和數(shù)量關(guān)系，因此，在保證模型基本符合現(xiàn)實情況的基礎(chǔ)上，作如下假設(shè)，以簡化模型：

（1）假設(shè)配送中心所提供的各項服務(wù)收入關(guān)于物流量成線形函數(shù)；

（2）假設(shè)各點間（供貨點、配送中心、用戶）運(yùn)送運(yùn)費為關(guān)于路程的線性函數(shù)，且同一運(yùn)送路線費用相同；

（3）假設(shè)各點需求量及所在地區(qū)的交通情況在一定時間內(nèi)不出現(xiàn)較大波動；

（4）假設(shè)配送中心的固定費用為已知常數(shù)。

基于以上假設(shè)，僅考慮物流配送過程中產(chǎn)生的運(yùn)費，將全國的物流配送網(wǎng)絡(luò)劃分為多個區(qū)域，每個區(qū)域均可確定一個配送中心，且每兩點之間均由雙向邊連接，各邊權(quán)值即為兩端點間的運(yùn)輸成本。分別確定最優(yōu)點以及最優(yōu)路徑，使得該點到其他各點的費用為最小。具體目標(biāo)函數(shù)如下：

minValue=min■cost■1≤j≤n （1）

其中，cost■表示i點至j點的費用。

3 樹型動態(tài)規(guī)劃算法

3.1 符號與定義

3.2 算法求解

普通動態(tài)規(guī)劃均為線性或是建立在圖上的。對于線性情況，有兩種方向：向前和向后，或稱順推與逆推。樹型動態(tài)規(guī)劃以“樹”的數(shù)據(jù)結(jié)構(gòu)為基礎(chǔ)，同樣有兩個方向：

（1）根—葉：該方法在實際問題中應(yīng)用不多，因此無典型實例；

（2）葉—根：根的子節(jié)點向根傳遞有用的信息，再由根通過這些信息求得最優(yōu)解。

本文所選用的樹型動態(tài)規(guī)劃即為后者。由于樹型動態(tài)規(guī)劃屬于動態(tài)規(guī)劃范疇，因此，它同樣具有無后效性、子問題重疊性和最優(yōu)子結(jié)構(gòu)的性質(zhì)[7]。因此，樹型動態(tài)規(guī)劃建立過程中，只需考慮根節(jié)點與子節(jié)點間如何進(jìn)行信息交換即可。

模塊1 預(yù)處理節(jié)點信息

已知：u，v邊的權(quán)值costuv，標(biāo)記數(shù)組mark；

輸入：任意一個點root；

輸出：以x節(jié)點為根節(jié)點的子樹所具有的節(jié)點數(shù)和權(quán)值和分別為childx， value1：n；

Step 1 用mark數(shù)組標(biāo)記root；

Step 2 當(dāng)存在與root節(jié)點相連且未在mark中標(biāo)記的點vi時：

（1）以vi作為進(jìn)行遞歸；

（2）childroot+=childvi+1；

（3）valueroot=childvi+1*childrootvi+valuevi。

任意選取一個點作為樹的根節(jié)點root開始進(jìn)行第一次樹型動態(tài)規(guī)劃掃描，并計算樹中每個節(jié)點的孩子個數(shù)，以及以每個子節(jié)點到根的權(quán)值和，即求出dpi和childi值。相應(yīng)目標(biāo)函數(shù)如下：

dpi=dpi+childj*cost■ （2）

childi=childi+childj （3）

其中，j∈Son■，初始值dpi=0，childi=1。

模塊2 確定中心點

已知：以x節(jié)點為根節(jié)點的子樹所具有的節(jié)點數(shù)和權(quán)值分別為childx，value1：n，清空mark數(shù)組，圖中點的個數(shù)n；

輸入：任意節(jié)點root；

輸出：以x為根節(jié)點的樹的總權(quán)值和rvaluex；

Step1 用mark數(shù)組標(biāo)記root；

Step2 當(dāng)存在于root節(jié)點相連且未在mark中標(biāo)記的點vi時：

（1）計算rvaluevi=rvalueroot-childvi+1*costrootvi+n-childvi-1*costrootvi；

（2）以vi作為輸入進(jìn)行遞歸。

從根節(jié)點root出發(fā)，利用第一次樹型動規(guī)中所求得的dpi和childi數(shù)組，進(jìn)行第二次樹型動規(guī)。此時需采用從根到葉的方式，通過根已有的信息來更新子節(jié)點的信息，從而達(dá)到求出解的目的。相應(yīng)目標(biāo)函數(shù)如下：

total_valj=■ （4）

3.3 時間復(fù)雜度分析

模塊1為處理階段，對每個節(jié)點i求dpi和childi時，其子節(jié)點僅在i的轉(zhuǎn)移方程中出現(xiàn)，且只出現(xiàn)一次，因此復(fù)雜度為ON。

模塊2為決策階段，通過遍歷整棵樹，求解每個點到其他點的費用和。由于求當(dāng)前節(jié)點時，只需知道其父親節(jié)點的信息（即父親節(jié)點total_val值），因此復(fù)雜度亦為ON。

綜合上述分析，總的算法復(fù)雜度即為ON。

4 實驗結(jié)果與分析

為了更好地檢驗樹型動規(guī)算法的效率，隨機(jī)產(chǎn)生了8組數(shù)據(jù)，同時，通過加權(quán)取模的方法，對數(shù)據(jù)范圍作了限定，使其更貼近實際。通過對比，檢驗樹型動態(tài)規(guī)劃的正確性和高效性。本文用于對比的傳統(tǒng)算法，采用枚舉中心點，求其到其他點的距離和。在所有距離和中，取最小值對應(yīng)的中心點。

最終得到選址中心確定所需的時間分別為：

對比兩種算法可發(fā)現(xiàn)：當(dāng)備選點個數(shù)超過一定數(shù)量后，樹型動態(tài)規(guī)劃的時間效率要遠(yuǎn)勝于傳統(tǒng)算法。且樹型動態(tài)規(guī)劃的時間及空間復(fù)雜度只和待處理的作業(yè)的數(shù)量有關(guān)。在內(nèi)存受限，計算時間要求較高的物流配送中心選址問題中，是一種相對理想的算法。

5 總 結(jié)

本文以O(shè)N的時間復(fù)雜度確定了每一區(qū)域的最優(yōu)中心點，大幅度優(yōu)化了選址效率。但由于配送中心的選址問題還涉及到經(jīng)濟(jì)、城市規(guī)劃等因素，因此算法只能為該問題提供相對較優(yōu)的參考方案。

本文算法建立在區(qū)域劃分的基礎(chǔ)上，后續(xù)將進(jìn)一步研究區(qū)域劃分和該算法的結(jié)合，并加入影響選址中心的其他因素，提高算法的實用性，使之適用于不同情況，為物流配送中心選址提供更為準(zhǔn)確的方案。

參考文獻(xiàn)：

[1] 謝云. 基于動態(tài)規(guī)劃的最優(yōu)運(yùn)輸費用問題探析[J]. 財會通訊，2011（1）：138-139.

[2] 劉曉惠. 物流配送中心選址規(guī)劃方法研究[J]. 綜合運(yùn)輸，2012（3）：30-32.

[3] 李海洋，劉冬敏，張曉磊. 基于AHP層次分析法的物流中心選址研究[J]. 中州大學(xué)學(xué)報，2012（2）：115-118.

[4] 韓慶蘭，梅運(yùn)先. 基于BP人工神經(jīng)網(wǎng)絡(luò)的物流配送中心選址決策[J]. 中國軟科學(xué)，2004（6）：140-143.

[5] 田昌奇. 物流配送中心合理選址問題的研究[J]. 物流工程與管理，2009（10）：99-100.

第4篇：動態(tài)規(guī)劃思想范文

中圖分類號：C935 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-914X（2014）36-0043-01

1、最優(yōu)控制問題基本介紹

最優(yōu)控制是使控制系統(tǒng)的性能指標(biāo)實現(xiàn)最優(yōu)化的基本條件和綜合方法，是現(xiàn)代控制理論的核心之一，是從大量實際問題中提煉出來的。它所研究的問題可以概括為：對一個受控的動力學(xué)系統(tǒng)或運(yùn)動過程，從一類允許的控制方案中找出一個最優(yōu)的控制方案，使系統(tǒng)的運(yùn)動在由某個初始狀態(tài)轉(zhuǎn)移到指定的目標(biāo)狀態(tài)的同時，其性能指標(biāo)最優(yōu)。最優(yōu)控制是最優(yōu)化方法的一個應(yīng)用。從數(shù)學(xué)意義上說，最優(yōu)化方法是一種求極值的方法，即在一組約束為等式或不等式的條件下，使系統(tǒng)的目標(biāo)函數(shù)達(dá)到極值，即最大值或最小值。從經(jīng)濟(jì)意義上說，是在一定的人力、物力和財力資源條件下，是經(jīng)濟(jì)效果達(dá)到最大（如產(chǎn)值、利潤），或者在完成規(guī)定的生產(chǎn)或經(jīng)濟(jì)任務(wù)下，使投入的人力、物力和財力等資源為最少。

控制理論發(fā)展到今天，經(jīng)歷了古典控制理論和現(xiàn)代控制理論兩個重要發(fā)展階段，現(xiàn)已進(jìn)入了以大系統(tǒng)理論和智能控制理論為核心的第三個階段。對于確定性系統(tǒng)的最優(yōu)控制理論，實際是從20世紀(jì)50年代才開始真正發(fā)展起來的，它以1956年原蘇聯(lián)數(shù)學(xué)家龐特里亞金（Pontryagin）提出的極大值原理和1957年貝爾曼提出的動態(tài)規(guī)劃法為標(biāo)志。時至今日，隨著數(shù)字技術(shù)和電子計算機(jī)的快速發(fā)展，最優(yōu)控制的應(yīng)用已不僅僅局限于高端的航空航天領(lǐng)域，而更加滲入到生產(chǎn)過程、軍事行動、經(jīng)濟(jì)活動以及人類的其他有目的的活動中，對于國民經(jīng)濟(jì)和國防事業(yè)起著非常重要的作用。

對于靜態(tài)優(yōu)化的方法，解決的主要是如何求解函數(shù)的極值問題；變分法則被用來求解泛函的極值問題；極小值原理的方法，適用于類似最短時間控制、最少燃料控制的問題。另外，還有線性系統(tǒng)二次型指標(biāo)的最優(yōu)控制，即線性二次型問題。與解析法相比，用最優(yōu)控制理論設(shè)計系統(tǒng)有如下的特點：

（1）適用于多變量、非線性、時變系統(tǒng)的設(shè)計。

（2）初始條件可以任意。

（3）可以滿足多個目標(biāo)函數(shù)的要求，并可用于多個約束的情況。

2、最優(yōu)控制的求解方法

2.1 變分法

變分法是求解泛函極值的一種經(jīng)典方法，可以確定容許控制為開集的最優(yōu)控制函數(shù)，也是研究最優(yōu)控制問題的一種重要工具。掌握變分法的基本原理，還有助于理解以最小值原理和動態(tài)規(guī)劃等最優(yōu)控制理論的思想和內(nèi)容。

但是，變分法作為一種古典的求解最優(yōu)控制的方法，只有當(dāng)控制向量u（t）不受任何約束，其容許控制集合充滿整個m維控制空間，用古典變分法來處理等式約束條件下的最優(yōu)控制問題才是行之有效的。在許多實際控制問題中，控制函數(shù)的取值常常受到封閉性的邊界限制，如方向舵只能在兩個極限值范圍內(nèi)轉(zhuǎn)動，電動機(jī)的力矩只能在正負(fù)的最大值范圍內(nèi)產(chǎn)生等。因此，古典變分法不適于解決許多重要的實際最優(yōu)控制問題。

2.2 最小值原理

極小值原理是對經(jīng)典變分法的擴(kuò)展，可以解決經(jīng)典變分法無法解決的最優(yōu)控制問題。也就是當(dāng)控制有約束，哈密頓函數(shù)H對U不可微時，要用極小值原理。所得出的最優(yōu)控制必要條件與變分法所得的條件的差別，僅在于用哈密頓函數(shù)在最優(yōu)控制上取值的條件代替，可以看出，后者可以作為前者的特殊情況。其他條件包括正則方程，橫截條件，邊界條件等都一樣。需要注意的是，極小值原理解決最短時間控制問題時，最短時間的控制量只能取約束的邊界值+1或-1；而最少燃料控制的控制量可取邊界值+1、-1、0。

用極小值原理解非線性系統(tǒng)的最優(yōu)控制將導(dǎo)致非線性兩點邊值問題，這類問題求解是很困難的。即使系統(tǒng)是線性的，但當(dāng)指標(biāo)函數(shù)是最短時間、最少燃料這種形式，要求得到最優(yōu)控制的解析表達(dá)式，并構(gòu)成反饋控制（即把U（t）表示為X（t）的函數(shù)）也是非常困難的。

2.3 動態(tài)規(guī)劃

動態(tài)規(guī)劃又稱為多級決策理論，是貝爾曼提出的一種非線性規(guī)劃方法。它將一個多級決策問題化為一系列單極決策問題，從最后一級狀態(tài)開始到初始狀態(tài)為止，逆向遞推求解最優(yōu)決策。動態(tài)規(guī)劃法原理簡明，適用于計算機(jī)求解，在許多理論問題的研究中，都應(yīng)用到動態(tài)規(guī)劃的思路。

動態(tài)規(guī)劃是求解最優(yōu)化問題的重要方法，在應(yīng)用動態(tài)規(guī)劃時，有一個前提條件是系統(tǒng)的狀態(tài)變量必須滿足“無后效性”。所謂無后效性的概念是：在任一時刻，系統(tǒng)狀態(tài)為x（），以后的狀態(tài)僅決定于x（）以及x（）到達(dá)終點時刻的狀態(tài)x（）的控制策略，而與以前的狀態(tài)和以前的控制策略無關(guān)。因此，在應(yīng)用動態(tài)規(guī)劃方法時，要注意狀態(tài)變量的選取，使之滿足“無后效性”的條件。例如，討論物體在空間運(yùn)動時，不僅選用物體的空間位置座位狀態(tài)變量，而且要將速度變量也包括在狀態(tài)變量之內(nèi)，以便滿足“無后效性”的條件。動態(tài)規(guī)劃法的局限性還表現(xiàn)在所謂的“維數(shù)災(zāi)難”問題：當(dāng)狀態(tài)變量的維數(shù)增加，要求計算機(jī)內(nèi)存成指數(shù)倍增長，計算工作量也大大增加。此外，求解連續(xù)決策過程采用的動態(tài)規(guī)劃法得到的哈密頓-雅克比方程是偏微分方程，求解x（）也是相當(dāng)困難的。動態(tài)規(guī)劃雖然提供的是充分條件，但是，由于連續(xù)型系統(tǒng)的哈密頓-雅克比方程難于求解而不能滿足實際需要。

2.4 線性二次型最優(yōu)控制

線性二次型問題的實用意義在于：把它所得到的最優(yōu)反饋控制與非線性系統(tǒng)的開環(huán)最優(yōu)控制結(jié)合起來，可減少開環(huán)控制的誤差，達(dá)到更精確的控制的目的。

與經(jīng)典控制問題相比，線性二次型問題有兩個顯著的特點：第一，它研究的是多輸入多輸出動態(tài)系統(tǒng)的控制問題，其中包括了作為特例的單輸入單輸出情形；第二，它的性能指標(biāo)是綜合性的，既包含有誤差的成分，又包含有控制能量的成分。根據(jù)線性的最優(yōu)反饋控制律，即控制量正比與狀態(tài)變量，可寫成或。把這種線性二次型問題的最優(yōu)控制與非線性系統(tǒng)的開環(huán)控制結(jié)合起來，還可減少開環(huán)控制的誤差。線性二次型問題的最優(yōu)控制一般可分狀態(tài)調(diào)節(jié)器問題和伺服跟蹤問題兩大類。

對于終端時刻tf有限的連續(xù)系統(tǒng)狀態(tài)調(diào)節(jié)器問題，要求加權(quán)陣P、Q為對稱半正定，R為對稱正定，但并不要求系統(tǒng)完全可控。

3、三種方法之間的相互關(guān)系

動態(tài)規(guī)劃法、極小值原理和變分法，都是求解最優(yōu)控制問題的重要方法。由動態(tài)規(guī)劃的哈密頓-雅克比方程，可以推得變分法中的歐拉方程和橫截條件：也可以推得極小值原理的必要條件。

變分法對解決開集約束的最優(yōu)控制問題十分有效，但對于處理閉集性約束就無能為力了。變分法與極小值原理都可以解微分方程所描述的變分問題作為目標(biāo)，結(jié)果得出了一組常微分方程所表示的必要條件。這三種方法要求的條件不同，其中屬動態(tài)規(guī)劃要求最高。在所要求的條件都滿足的情況下，使用這三種方法所得結(jié)論相同。

參考文獻(xiàn)

[1] 胡壽松-最優(yōu)控制理論與系統(tǒng)[M].（第二版）北京：科學(xué)出版社，2005.

[2] 張蓮-現(xiàn)代控制理論.北京：清華大學(xué)出版社，2008.1.

[3] 于長官-現(xiàn)代控制理論及應(yīng)用.哈爾冰工業(yè)大學(xué)出版社，2005.1.

第5篇：動態(tài)規(guī)劃思想范文

關(guān)鍵詞：背包問題；貪婪法；動態(tài)規(guī)劃法；時間復(fù)雜度

中圖分類號：TP311文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044(2008)25-1534-02

Study on Algorithm Design and Analysis of Knapsack Problem

SUN Hong-li

(Computer Science Department, Shangqiu Normal University, Shangqiu 476000, China)

Abstract: The knapsack problem is a classical question in the area of algorithm design and analysis, in this paper greedy method, the dynamic programming method and the recursion method are used separately to solve the knapsack problem, 0-1 knapsack problem and the simple 0-1 knapsack problem, and to design the algorithm, to discuss the time complexity. Algorithm design and realization process is given, and with example algorithm basic thought to describe different solution is introduced, and the conclusion is gotten by summarizing the goods and shortcoming of three methods.

Key words: knapsack problem; greedy method; dynamic programming method; time complexity

1 引言

算法是計算機(jī)科學(xué)的核心，也是程序設(shè)計的關(guān)鍵，對算法的研究是通過程序來實踐的，算法+數(shù)據(jù)結(jié)構(gòu)=程序，此經(jīng)典公式表明有了算法，加上合適的數(shù)據(jù)結(jié)構(gòu)，用高級語言進(jìn)行實現(xiàn)就可以得到程序。那么要解決背包問題，首要的前提就是設(shè)計出好的算法，想求得背包問題的解，就要先設(shè)計出算法。本文采用三種方法來對背包問題進(jìn)行算法設(shè)計，并分析其時間復(fù)雜度，進(jìn)而得出結(jié)論。

2 背包問題描述

背包問題是整數(shù)規(guī)劃中的一類特殊問題，在現(xiàn)實生活中具有廣泛應(yīng)用，如能提出求解此問題的有效算法，則具有很好的經(jīng)濟(jì)價值和決策價值，如物流公司的貨物發(fā)配問題，集裝箱的運(yùn)載問題，如何才能獲得最大利潤。

問題的一般描述是：旅行者背包登山，背包的最大承重為M，現(xiàn)有n個物品可供選擇裝入背包，第i個物品重量為wi，價值為pi，假定物品i的一部分xi（0≤xi≤1）放入背包，獲得價值為xipi，由于背包最大承重為M，要求裝入物品總質(zhì)量不過超過M，問旅行者應(yīng)該如何選擇物品裝入背包，使得裝入物品的價值總和達(dá)到最大值。

背包問題的數(shù)學(xué)描述如下：要求找到一個n元向量(x1,x2,…xn)，在滿足約束條件：■情況下，使得目標(biāo)函數(shù)max∑xipi，其中，1≤i≤n;M>0;wi>0;pi>0。滿足約束條件的任何向量都是一個可行解，而使得目標(biāo)函數(shù)達(dá)到最大的那個可行解則為最優(yōu)解。

3 局部優(yōu)先策略的貪婪法求解背包問題

采用貪婪法求解問題的最優(yōu)解核心是選擇合適的優(yōu)化測度，下面以一個背包問題的具體實例來說明求解思想。已知：n=3，w=(10,25,30)，p=(60,50,90)，M=30，求如何裝包可得到最大價值。

分析：如果從剩余的物品中每次都選取當(dāng)前價值最大的來裝入的話，利用價值優(yōu)先測度，不能保證獲得最優(yōu)解，也就是說如果優(yōu)化側(cè)度的選取只考慮價值是不行的；如果每次都選擇背包耗費最小的物品裝入的話，利用質(zhì)量最小作為優(yōu)化測度，同樣也不能保證得到最優(yōu)解，只考慮質(zhì)量同樣無法得到最優(yōu)解；最后我們同時考慮價值和質(zhì)量，以單位質(zhì)量價值大的物品首先裝入，以此作為優(yōu)化測度，就可以保證背包問題獲得最優(yōu)解。上面的例子求解結(jié)果如下：最大價值為120，解向量為（1，0，2/3）。其求解過程可以簡單概括如下，首先對所有物品的單位質(zhì)量價值按非升序排列，然后一個個考慮物品，裝入物品后要修正背包的當(dāng)前承重及已獲得價值，如果背包的當(dāng)前承重不足以裝入整個物品時，可以裝入物品的一部分保證背包裝滿而獲得最大價值。由此利用局部最優(yōu)策略求解背包問題得到的局部最優(yōu)解肯定是全局最優(yōu)解。

采用貪婪法局部優(yōu)先策略算法時間復(fù)雜度是T(n)=O(n2)。首先我們對物品單位質(zhì)量的價值非升序排列，采用冒泡法實現(xiàn)，執(zhí)行時間為T1(n)=(n-1)+(n-2)+…+1=n(n+1)/2；從排好序的物品中選取加入解向量，最大執(zhí)行n次T2(n)=O(n)，故貪婪法總的時間耗費為：T(n)=T1(n)+T2(n)=O(n2)。

如果對背包問題進(jìn)行擴(kuò)展，再裝入物品時只允許全裝或者不裝，不允許裝入物品的部分，也就是xi=1或者xi=0。此時成為0-1背包問題。那么對0-1背包問題，貪婪法可以求得最優(yōu)解嗎？

答案是否定的，還以上面的實例說明，采用貪婪法求的解向量為（1，0，0），最大價值為60，很明顯，（0，0，1）優(yōu)于前者，最大價值為90。要求0-1背包問題的最優(yōu)解就需要采用全新的算法思想，下面具體說明。

4 最優(yōu)化原理的動態(tài)規(guī)劃法求解0-1背包問題

動態(tài)規(guī)劃法的核心基礎(chǔ)是最優(yōu)化原理，它把已知問題分為很多子問題，按順序求解子問題，在每一種情況下，列出各種情況的局部解，按條件從中選取那些最有可能產(chǎn)生最佳的結(jié)果舍棄其余。前一子問題為后面子問題提供信息，而減少計算量，最后一個子問題的解即為問題解。采用此方法求解0-1背包問題的主要步驟如下：

①分析最優(yōu)解的結(jié)構(gòu)：最有子結(jié)構(gòu)性質(zhì)；

②建立遞歸方程；

③計算最優(yōu)值；

④構(gòu)造最優(yōu)解。

下面用動態(tài)規(guī)劃法求解0-1背包問題。首先此問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。簡單說明如下：設(shè)(y1,y2,…,yn)是最優(yōu)解，則(y2, …,yn)是對應(yīng)子問題的一個最優(yōu)解：max■ pixi，■

采用反證法說明：假設(shè)(y2, …,yn)不是對應(yīng)子問題的最優(yōu)解，那么必定存在最優(yōu)解，令 (z2,…,zn)是對應(yīng)子問題的一個最優(yōu)解。由上述假設(shè)得到， ■zipi> ■yipi，并且w1y1+ ■ziwi≤M在■zipi> ■yipi兩邊同時加上p1y1，得到 ■zipi+p1y1> ■yipi+p1y1，合并w1y1+ ■ziwi≤M，可得出(y1,z2,…,zn)優(yōu)于(y1,y2,…,yn)，推出矛盾，也即假設(shè)不成立。符合最優(yōu)子結(jié)構(gòu)性質(zhì)。

根據(jù)最優(yōu)子結(jié)構(gòu)性質(zhì)可以推出遞歸方程。引入符號v(i,j)表示i個物品當(dāng)前背包承重為j時可以獲得的最大價值，要求得i個物品可以獲得最大價值要考慮第i個物品質(zhì)量和當(dāng)前背包承重大小關(guān)系，背包可以容納第i個物品的話，有裝入和不裝兩種情況，表示為v(i-1,j-wi)和v(i-1,j)，如果第i個物品質(zhì)量大于背包當(dāng)前承重，則只有不裝，即v(i-1,j)。由此可以得出關(guān)于解的遞歸方程如下：

■

根據(jù)遞歸方程，可以求得0-1背包問題的最大價值和解向量，還以上面的實例說明求解過程。

■

故得到：v(1,30)=60;v(2,30)=60;v(3,30)=90；X=（0，0，1），從這個求解過程可得動態(tài)規(guī)劃法肯定可以得到0-1背包問題的最優(yōu)解。

動態(tài)規(guī)劃法算法執(zhí)行時間為n*a*b次循環(huán)，每次循環(huán)都要執(zhí)行比較運(yùn)算，算法完成所需總是件為cn2，故時間復(fù)雜度為

T(n)=O(n3)。

如果對0-1背包問題的求解目標(biāo)進(jìn)行限制，求如何裝包可以使得裝入物品的重量總和恰好是M。那么問題就不再是最優(yōu)化問題，稱為簡單的0-1背包問題。顯然，用貪婪法或動態(tài)規(guī)劃法都無法求得此問題的解向量，這時需要用到遞歸法來求解。

5 遞歸法求解簡單0-1背包問題

簡單0-1背包問題可以描述為：現(xiàn)有n個物品，第i個物品質(zhì)量為wi，有一個可容物品最大質(zhì)量為M的背包，如何從n件物品中選取出若干件裝入使得放入背包的質(zhì)量之和正好為M。

由于0-1背包問題對第i件物品要么裝入，要么不裝，故問題可能有解，也可能無解。采用布爾函數(shù)表示問題。Knap(i,j)其中i表示物品個數(shù)，j表示背包當(dāng)前容量。如果問題有解函數(shù)值為true，否則為false。

先取第n個物品裝入，如果wn=M,knap(n,M)=true；

如果wn1,knap(n,M)= knap(n-1,M-wn)有解可行，否則轉(zhuǎn)化為knap(n,M)= knap(n-1,M)；

如果wn1,knap(n,M)= knap(n-1,M)。

遞歸算法的執(zhí)行時間是那n2次調(diào)用，每次調(diào)用完成一次比較和一次棧運(yùn)算，算法完成總時間是2n2，時間復(fù)雜度為T(n)O(n2)。

6 結(jié)論

這三種算法都在c語言環(huán)境下得到驗證，運(yùn)行結(jié)果證明了算法設(shè)計是可行的，正確的。通過對背包問題、0-1背包問題與簡單0-1背包問題的算法設(shè)計及時間復(fù)雜度分析可以看出，無論采用貪婪法還是動態(tài)規(guī)劃法，都是在已知約束條件下求解最大值建立數(shù)學(xué)模型算法實現(xiàn)的過程；但算法具體實現(xiàn)和數(shù)據(jù)結(jié)構(gòu)的建立要用到遞歸和棧操作。比較貪婪法和動態(tài)規(guī)劃法，前者的時間復(fù)雜度低于后者，從耗費上而言優(yōu)于后者，但后者的實現(xiàn)算法可讀性要優(yōu)于前者。

參考文獻(xiàn)：

[1] M.H.Alsuwaiyel.算法設(shè)計技巧與分析[M].北京:電子工業(yè)出版社，2004.

第6篇：動態(tài)規(guī)劃思想范文

關(guān)鍵詞：算法設(shè)計與分析 實例驅(qū)動教學(xué) 背包問題 教學(xué)改革

中圖分類號：G642 文獻(xiàn)標(biāo)識碼：A 文章編號：1673-9795（2013）06（a）-0070-01

1 問題的提出

《算法設(shè)計與分析》[1]是實踐性較強(qiáng)的一門課程。這門課程的主要目的，通過對計算機(jī)算法系統(tǒng)的學(xué)習(xí)與研究，掌握算法設(shè)計算法策略和技巧，培養(yǎng)學(xué)生對算法的計算復(fù)雜性正確分析的能力，對不同的實際問題設(shè)計出清晰高效的算法，為獨立設(shè)計算法和對算法進(jìn)行復(fù)雜性分析奠定堅實的理論基礎(chǔ)。軟件的效率和穩(wěn)定性取決于軟件中所采用的算法，學(xué)習(xí)《算法設(shè)計與分析》課程，可以開闊編程思路，有助于編寫出高效程序。因此，提高《算法設(shè)計與分析》課程教學(xué)水平有著極其深遠(yuǎn)的意義和重要的作用。

《算法設(shè)計與分析》內(nèi)容的比較抽象與復(fù)雜，從學(xué)生的普遍反映來看，這是一門比較難的課程?！端惴ㄔO(shè)計與分析》課程的教學(xué)內(nèi)容按算法分類組織。在教科書中[2]，每一章對應(yīng)一種算法，主要內(nèi)容涵蓋了動態(tài)規(guī)劃、貪心法、回溯法和分支限界法經(jīng)典的算法。本文針對該課程，對典型實例驅(qū)動教學(xué)在《算法設(shè)計與分析》教學(xué)中的應(yīng)用做了一些探索。通過典型的實例教學(xué)，一個抽象的算法使其更具體化、形象化，學(xué)生能快速理解各種算法的原理及算法之間的區(qū)別，因此，在《算法設(shè)計與分析》教學(xué)中合理利用典型實例，激發(fā)學(xué)生學(xué)習(xí)興趣和熱情，從而提高教學(xué)效果。

2 0-1背包問題實例

0-1背包問題是經(jīng)典組合優(yōu)化問題[3]，有著廣泛的實際應(yīng)用背景，0-1背包問題比較簡單，把抽象的，復(fù)雜的算法應(yīng)用到該問題便于同學(xué)理解和掌握。0-1背包問題描述為：給定n種物品和一背包。物品i的重量是wi，其價值為vi，背包的容量為C。問應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價值最大。

3 動態(tài)規(guī)劃算法

動態(tài)規(guī)劃是解決多階段決策過程最優(yōu)化的一種方法，該方法是由美國數(shù)學(xué)家貝爾曼等人提出的。用于解決生產(chǎn)管理、工程技術(shù)等方面的許多問題，并建立了運(yùn)籌學(xué)的一個新的分支，即動態(tài)規(guī)劃。動態(tài)規(guī)劃算法與分治法類似，其基本思想也是將待求解問題分解成若干個子問題。但是經(jīng)分解得到的子問題往往不是互相獨立的。不同子問題的數(shù)目常常只有多項式量級。在用分治法求解時，有些子問題被重復(fù)計算了許多次。如果能夠保存已解決的子問題的答案，而在需要時再找出已求得的答案，就可以避免大量重復(fù)計算，從而得到多項式時間算法。動態(tài)規(guī)劃方法能夠把復(fù)雜問題的算法從指數(shù)階的計算量減少到多項式階。

4 貪心算法

貪心算法通過一系列的選擇來得到問題的最優(yōu)解，它所做的每一個選擇都是當(dāng)前狀態(tài)最好的選擇，即貪心選擇。雖然貪心算法不能對所有問題都得到整體最優(yōu)解，但對許多問題它能產(chǎn)生整體最優(yōu)解。在一些情況下，即使貪心算法不能得到整體最優(yōu)解，其最終結(jié)果卻是最優(yōu)解的很好近似。用貪心算法不能求解0-1背包問題，但能解決背包問題，背包問題與0-1背包問題類似，所不同的是在選擇物品i裝入背包時，可以選擇物品i的一部分，而不一定要全部裝入背包，即xi∈[0，1]。

5 回溯算法

回溯法在問題的解空間樹中，按深度優(yōu)先策略，從根結(jié)點出發(fā)系統(tǒng)地搜索一個問題的所有解或任一解。算法搜索至解空間樹的任意一點時，先判斷該結(jié)點是否包含問題的解：如果肯定不包含，則跳過對該結(jié)點為根的子樹的搜索，逐層向其祖先結(jié)點回溯；否則，進(jìn)入該子樹，繼續(xù)按深度優(yōu)先策略搜索。

如果采用回溯法解決0-1背包問題，如一個結(jié)點的左兒子結(jié)點是一個可行結(jié)點就搜索其左子樹。而對于右子樹，需要用貪心算法構(gòu)造一個上界函數(shù)，上界函數(shù)是通過講將0-1背包問題松弛為背包問題利用貪心算法求得的，這個函數(shù)表明這個結(jié)點的子樹所能達(dá)到的可能的最優(yōu)值，只在這個上界函數(shù)的值超過當(dāng)前最優(yōu)解時才進(jìn)入搜索。隨著搜索進(jìn)程的推進(jìn)，最優(yōu)解不斷得到加強(qiáng)，對搜索的限制就越來越嚴(yán)格。如果這個上界小于當(dāng)前值Bestf，說明該子樹不可能包含最優(yōu)解，即可以被“剪枝”。

6 分支限界法

分支限界法類似于回溯法，也是一種在問題的解空間樹上搜索問題解的算法。分支限界法則以廣度優(yōu)先或以最小耗費優(yōu)先的方式搜索解空間樹。采用分支限界法解決0-1背包問題，同樣需要用到貪心算法構(gòu)造的上界函數(shù)。所不同的是，這個上界函數(shù)的作用不在于判斷是否進(jìn)入一個結(jié)點的子樹繼續(xù)搜索，因為在搜索到達(dá)葉節(jié)點之前，大家也無法知道已經(jīng)得到的最優(yōu)解是什么。在這里，可用一個最大堆來實現(xiàn)活結(jié)點的優(yōu)先隊列，上界函數(shù)的值將作為優(yōu)先級，這樣一旦有一個葉結(jié)點成為擴(kuò)展結(jié)點，就表明已經(jīng)找到了最優(yōu)解。

7 結(jié)語

通過典型0-1背包問題實例，學(xué)生可以快速理解各種算法的基本思想、特點及算法之間區(qū)別，便于理解與掌握。筆者在這門課程的教學(xué)過程中深刻地體會到，要上好這門課，教師要注意觀察學(xué)生的課堂反應(yīng)及接受能力，采用適當(dāng)?shù)慕虒W(xué)方法。實踐證明，《算法設(shè)計與分析》實例教學(xué)方法是一種將抽象算法理論與實際典型實例相結(jié)合，讓學(xué)生帶著感興趣的問題進(jìn)入課程的學(xué)習(xí)，其探究能力和創(chuàng)新意識得到了較好的培養(yǎng)，同時培養(yǎng)學(xué)生分析問題及解決問題的能力。

參考文獻(xiàn)

[1] 阿霍.計算機(jī)算法設(shè)計與分析：英文版，[M].北京：機(jī)械工業(yè)出版社，2006.

第7篇：動態(tài)規(guī)劃思想范文

關(guān)鍵詞：水庫；優(yōu)化調(diào)度決策；動態(tài)規(guī)劃模型；新方法

在我國，水庫優(yōu)化調(diào)度決策研究相對起步較晚，大多都是通過建立優(yōu)化模型來求解其優(yōu)化的目標(biāo)函數(shù)也主要有兩類：一是以庫群多年電能或供水量最大為目標(biāo)，二是以系統(tǒng)年費用最小為目標(biāo)，模型既有確定性的，也有隨機(jī)型的隨著研究的不斷深入，研究的目標(biāo)逐漸由單目標(biāo)擴(kuò)展到了多目標(biāo)，研究對象由單庫擴(kuò)大到了多庫乃至整個流域或系統(tǒng)的庫群，其模型也由單一模型發(fā)展到了組合模型近年來，又把系統(tǒng)辯識思想運(yùn)用到了水庫調(diào)度決策研究中，將隨機(jī)動態(tài)規(guī)劃與常規(guī)調(diào)度決策方法有機(jī)結(jié)合，為水庫調(diào)度決策研究提供了一個新的理論框架。隨著社會經(jīng)濟(jì)的快速發(fā)展，社會用水量也急劇增加，水資源供需矛盾日趨尖銳如何合理調(diào)配有限的水資源已成為水資源管理中現(xiàn)實而緊迫的任務(wù)水庫優(yōu)化調(diào)度決策是水資源系統(tǒng)優(yōu)化配置的重要手段，因此做好水庫優(yōu)化調(diào)度決策方案及管理對解決這一嚴(yán)重的問題無疑具有非常重要的意義。

一、當(dāng)前水庫調(diào)度決策存在的問題

目前，國內(nèi)外水水庫優(yōu)化調(diào)度決策研究成果較多，常規(guī)調(diào)度決策方法以水位或入庫流量確定水庫的操作方法，雖然簡明直觀，但在對新技術(shù)的應(yīng)用客觀條件變化對調(diào)度決策結(jié)果的影響分析等諸方面存在明顯不足優(yōu)化調(diào)度決策決策方法方案存在的主要問題有：

（1）調(diào)度決策方案只是一個合理的方案，而不是最優(yōu)的方案；

（2）無論哪種模型，應(yīng)用哪種數(shù)學(xué)方法，仍不能回避未來入庫徑流無法確知的問題，從而大大降低實際應(yīng)用效果；

（3）應(yīng)用比較多的動態(tài)規(guī)劃模型受到數(shù)學(xué)維數(shù)的限制，即維數(shù)災(zāi)問題需借助其它方法，如逐步優(yōu)化法對模型進(jìn)行降維處理；

（4）在建立模型求解的過程中計算量大如各項指標(biāo)的分析優(yōu)選校核

（5）所建立的模型難以反映復(fù)雜系統(tǒng)的真實情況；

（6）模型可操作性較低由于優(yōu)化調(diào)度決策所用的方法和理論比較復(fù)雜，使用者因缺少相應(yīng)的知識，實際操作比較困難，從而影響了模型的應(yīng)用和推廣。

二、水庫調(diào)度決策的優(yōu)化應(yīng)用分析

我國對水庫優(yōu)化調(diào)度決策優(yōu)化研究和應(yīng)用相對起步較晚，基本上都是通過建立有效的優(yōu)化模型來進(jìn)行解答，其優(yōu)化的目標(biāo)函數(shù)也主要分為兩個方面，一種目標(biāo)是在庫群用水量最大或發(fā)電量最大時，另一種目標(biāo)是消耗費用最少時。隨著對水庫優(yōu)化調(diào)度決策研究的不斷深入，研究目標(biāo)變得多元，研究對象也在向多元化發(fā)展，研究模型變得更加復(fù)雜多變。近些年，系統(tǒng)辯識思想也運(yùn)用到了水庫調(diào)度決策研究中，隨機(jī)態(tài)規(guī)劃與常規(guī)調(diào)度決策方法互相有機(jī)結(jié)合，為水庫調(diào)度決策研究提供了一個新的理論框架。為了發(fā)揮水庫的最大經(jīng)濟(jì)效益，包括防洪、發(fā)電、灌溉、供水及航運(yùn)等效益最佳，我國進(jìn)行了大量的研究與實踐。

1、水庫調(diào)度決策的優(yōu)化應(yīng)用實例

我國大約從20 世紀(jì)60 年代開始水庫優(yōu)化調(diào)度決策的研究。1960 年吳滄浦最先提出了每年調(diào)節(jié)水庫的最優(yōu)動用動態(tài)規(guī)劃模型。1963 年譚維信、黃守信等通過學(xué)習(xí)了解動態(tài)規(guī)劃與Markov 過程理論，順利完成了一個長期調(diào)節(jié)水電站水庫的優(yōu)化馬爾柯夫過程理論模型，并在獅子灘水電站的優(yōu)化調(diào)度決策中得到成功嘗試。1979 年張勇傳、熊斯毅等在研究拓溪水電站水庫優(yōu)化調(diào)度決策模型時，采用可變方向探索法，雖然優(yōu)化調(diào)度決策圖依然用Bellman 最優(yōu)化原理， 由于引進(jìn)了懲罰項從而使調(diào)度決策圖的可靠性提高。同樣是在1979 年，在劉家峽水電站水庫優(yōu)化調(diào)度決策研究時， 董子敖等人提出了對國民經(jīng)濟(jì)有最大效益的目標(biāo)函數(shù)。張玉新、馮尚友在八十年代末研究了多目標(biāo)動態(tài)規(guī)劃的迭代法求解方法，建立了一個多維決策的多目標(biāo)動態(tài)規(guī)劃模型。由于模糊里路的不斷發(fā)展，吳倍益提出應(yīng)用模糊數(shù)學(xué)進(jìn)行水庫群優(yōu)化調(diào)度決策；張勇傳、邴鳳山等把相關(guān)的模糊理論引入水庫優(yōu)化調(diào)度決策的研究中。陳守煜于1988 年把動態(tài)規(guī)劃和模糊優(yōu)選有機(jī)結(jié)合起來提出了優(yōu)選模糊原理模型，此后又提出了系統(tǒng)層次模糊優(yōu)選模型，這些理論不斷完善了模糊理論。20 世紀(jì)末以來，人們開始不斷尋求水庫優(yōu)化功能來進(jìn)行模擬。2000 年李會安建立了可以水量隨時自己優(yōu)化的模型。2000年暢建霞等人為西安市水庫群建立了神經(jīng)網(wǎng)絡(luò)優(yōu)化調(diào)度決策模型，并在2001年改進(jìn)遺傳算法的水電站基礎(chǔ)上再次進(jìn)行水庫優(yōu)化調(diào)度決策。2005年邱林等人把混沌優(yōu)化理論應(yīng)用到水庫優(yōu)化調(diào)度決策中，徐剛、馬光文等人也在同一年研究了蟻群優(yōu)化在水庫優(yōu)化中的作用，并在在單庫、多庫優(yōu)化調(diào)度決策中的成功試用。

2、水庫調(diào)度決策的優(yōu)化應(yīng)用方案

比如水庫的調(diào)度決策來說，將以天堂山水利樞紐工程為例子，全面的分析水庫調(diào)度決策的優(yōu)化應(yīng)用方案。天堂山水利樞紐工程位于龍門縣城西北約14 km的增江上游天堂山峽谷處，集雨面積461 km2（占增江全流域面積15%，總庫容2.43億m3，是一宗以防洪為主，兼顧灌溉、發(fā)電、養(yǎng)殖、旅游等綜合效益的大型水利樞紐工程。

天堂山水利樞紐工程以防洪為主，兼有灌溉、發(fā)電、旅游、養(yǎng)殖等綜合利用的大（2）型水利工程，電站安裝有3臺單機(jī)容量6500kW的混流立式水輪發(fā)電機(jī)組。根據(jù)原設(shè)計標(biāo)準(zhǔn)劃分，本工程為Ⅱ等大（2）型工程，大壩與隧洞進(jìn)水口工程等別為Ⅱ等，建筑物級別為2級，設(shè)計洪水標(biāo)準(zhǔn)為100年一遇，校核洪水標(biāo)準(zhǔn)為1000年一遇；引水隧洞（不包括進(jìn)水口）、高壓管道、調(diào)壓井和電站工程等別為Ⅲ等，建筑物級別為3級，設(shè)計洪水標(biāo)準(zhǔn)為50年一遇，校核洪水標(biāo)準(zhǔn)為500年一遇。同時將從水文、氣象、徑流、設(shè)計洪水標(biāo)準(zhǔn)、生態(tài)環(huán)境等等因素考慮，本文將從徑流的調(diào)度優(yōu)化與應(yīng)用來進(jìn)行分析。

由于廣東省暫未頒布最新的降雨徑流等值線圖，本階段按《廣東省水文圖集》（1991年版）資料進(jìn)行初步分析。從圖集中查得天堂山水電站多年平均降雨量為2200mm（查Cv=0.25），多年平均徑流深為1300mm（查算Cv=0.35），計算天堂山水電站降雨徑流系數(shù)為0.59。與天堂山還原后多年平均徑流深1216mm相比，兩者誤差6%?？梢哉J(rèn)為設(shè)計年徑流深符合地區(qū)規(guī)律，徑流設(shè)計成果基本合理。

降雨、徑流各參數(shù)見表3.4-3。

表3.4-3 天堂山水電站多年平均年降雨量、徑流深比較表

三、水庫調(diào)度決策發(fā)展優(yōu)化應(yīng)用分析的展望

為了解決理論研究方面存在的問題， 應(yīng)采用系統(tǒng)的調(diào)度決策理論， 從全局出發(fā)， 不斷完善調(diào)度決策理論， 注重理論與生產(chǎn)實際相結(jié)合， 注重研究成果向生產(chǎn)的轉(zhuǎn)化， 把理論研究與實際應(yīng)用的差距較好的縮短； 必須結(jié)合生產(chǎn)需要和具體問題， 研究探討適合某一具體河流或區(qū)域、簡便實用并為生產(chǎn)管理者所接受的水庫調(diào)度決策模型及應(yīng)用方法。隨著計算機(jī)及人工智能技術(shù)的發(fā)展， 與計算機(jī)及人工智能技術(shù)相結(jié)合， 并引入新的理論， 成為水庫優(yōu)化調(diào)度決策研究的一個熱點和發(fā)展趨勢：

1） 充分應(yīng)用計算機(jī)的快速運(yùn)算及大容量存儲能力， 研究快速、準(zhǔn)確求解水庫優(yōu)化調(diào)度決策模型的方法及算法， 以提高水庫優(yōu)化調(diào)度決策模型效率。

2） 充分利用計算機(jī)技術(shù)， 結(jié)合人工智能開發(fā)出人機(jī)界面友好的具有智能化、敏捷化的決策支持系統(tǒng)是水庫調(diào)度決策決策技術(shù)今后的發(fā)展趨勢。此外， 全球定位系統(tǒng)、地理信息系統(tǒng)、遙感技術(shù)以及虛擬現(xiàn)實技術(shù)等高新技術(shù)， 在水利行業(yè)也具有廣闊的應(yīng)用前景。

四、結(jié)束語

總之， 在水庫調(diào)度決策方面更廣泛的、高質(zhì)量的應(yīng)用高新技術(shù)， 可以使得調(diào)度決策決策變得更科學(xué)化、更智能化、更敏捷化， 進(jìn)一步提升調(diào)度決策決策的技術(shù)水平， 使水庫調(diào)度決策向著可視化、交互化、智能化、集成化的方向前進(jìn)。

參考文獻(xiàn)：

[1]梅亞東. 水庫調(diào)度決策研究的若干進(jìn)展[J]. 湖北水力發(fā)電. 2008（01）

[2]羅強(qiáng)，宋朝紅，雷聲隆. 水庫調(diào)度決策自優(yōu)化模擬技術(shù)的最優(yōu)域[J]. 水電能源科學(xué). 2002（03）

第8篇：動態(tài)規(guī)劃思想范文

單個機(jī)器人的路徑規(guī)劃是找出從起始點至終點的一條最短無碰路徑。多個機(jī)器人的路徑規(guī)劃側(cè)重考慮整個系統(tǒng)的最優(yōu)路徑，如系統(tǒng)的總耗時間最少路徑或是系統(tǒng)總路徑最短等。從目前國內(nèi)外的研究來看，在規(guī)劃多機(jī)器人路徑時，更多考慮的是多機(jī)器人之間的協(xié)調(diào)和合作式的路徑規(guī)劃。

目前國內(nèi)外多機(jī)器人路徑規(guī)劃研究方法分為傳統(tǒng)方法、智能優(yōu)化方法和其他方法三大類。其中傳統(tǒng)方法主要有基于圖論的方法（如可視圖法、自由空間法、柵格法、Voronoi圖法以及人工勢場方法等）；智能優(yōu)化方法主要有遺傳算法、蟻群算法、免疫算法、神經(jīng)網(wǎng)絡(luò)、強(qiáng)化學(xué)習(xí)等；其他方法主要有動態(tài)規(guī)劃、最優(yōu)控制算法、模糊控制等。它們中的大部分都是從單個機(jī)器人路徑規(guī)劃方法擴(kuò)展而來的。

1）傳統(tǒng)方法多機(jī)器人路徑規(guī)劃傳統(tǒng)方法的特點主要體現(xiàn)在基于圖論的基礎(chǔ)上。方法一般都是先將環(huán)境構(gòu)建成一個圖，然后再從圖中尋找最優(yōu)的路徑。其優(yōu)點是比較簡單，比較容易實現(xiàn)；缺點是得到的路徑有可能不是最優(yōu)路徑，而是次優(yōu)路徑。薄喜柱等人[4]提出的一種新路徑規(guī)劃方法的基本思想就是基于柵格類的環(huán)境表示和障礙地圖的。而人工勢場方法的基本思想是將移動機(jī)器人在環(huán)境中的運(yùn)動視為一種虛擬人工受力場中的運(yùn)動。障礙物對移動機(jī)器人產(chǎn)生斥力，目標(biāo)點產(chǎn)生引力，引力和斥力周圍由一定的算法產(chǎn)生相應(yīng)的勢，機(jī)器人在勢場中受到抽象力作用,抽象力使得機(jī)器人繞過障礙物。其優(yōu)點是適合未知環(huán)境下的規(guī)劃，不會出現(xiàn)維數(shù)爆炸問題；但是人工勢場法也容易陷入局部最小，并且存在丟失解的部分有用信息的可能。顧國昌等人[5]提出了引用總體勢減小的動態(tài)調(diào)度技術(shù)的多機(jī)器人路徑規(guī)劃，較好地解決了這個問題。

2）智能優(yōu)化方法多機(jī)器人路徑規(guī)劃的智能優(yōu)化方（算）法是隨著近年來智能計算發(fā)展而產(chǎn)生的一些新方法。其相對于傳統(tǒng)方法更加智能化，且日益成為國內(nèi)外研究的重點。

遺傳算法是近年來計算智能研究的熱點，作為一種基于群體進(jìn)化的概率優(yōu)化方法，適用于處理傳統(tǒng)搜索算法難以解決的復(fù)雜和非線性問題，如多機(jī)器的路徑規(guī)劃問題。在路徑規(guī)劃中，其基本思想是先用鏈接圖法把環(huán)境地圖構(gòu)建成一個路徑節(jié)點鏈接網(wǎng)，將路徑個體表達(dá)為路徑中一系列中途節(jié)點，并轉(zhuǎn)換為二進(jìn)制串；然后進(jìn)行遺傳操作（如選擇、交叉、復(fù)制、變異），經(jīng)過N次進(jìn)化，輸出當(dāng)前的最優(yōu)個體即機(jī)器人的最優(yōu)路徑。遺傳算法的缺點是運(yùn)算速度不快，進(jìn)化眾多的規(guī)劃要占據(jù)很大的存儲空間和運(yùn)算時間；優(yōu)點是有效避免了局部極小值問題，且計算量較小。

孫樹棟等人[6，7]在這方面較早地展開了研究，提出的基于集中協(xié)調(diào)思想的一種混合遺傳算法來規(guī)劃多機(jī)器人路徑方法較好地解決了避障問題。但不足的是該方法必須建立環(huán)境地圖，在環(huán)境未知情況下的規(guī)劃沒有得到很好的解決；且規(guī)劃只能保證找到一個比較滿意的解，在求解全局最優(yōu)解時仍有局限。

文獻(xiàn)[8]中提出的一種基于定長十進(jìn)編碼方法有效降低了遺傳算法的編碼難度，克服了已有的變長編碼機(jī)制及定長二進(jìn)制編碼機(jī)制需特殊遺傳操作算子和特殊解碼的缺陷,使得算法更加簡單有效。

智能計算的另一種常見的方法——蟻群算法屬于隨機(jī)搜索的仿生算法。其基本思想是模擬螞蟻群體的覓食運(yùn)動過程來實現(xiàn)尋優(yōu)，通過螞蟻群體中各個體之間的相互作用，分布、并行地解決組合優(yōu)化問題。該算法同樣比較適合解決多機(jī)器人的路徑規(guī)劃問題。

朱慶保[9]提出了在全局未知環(huán)境下多機(jī)器人運(yùn)動螞蟻導(dǎo)航算法。該方法將全局目標(biāo)點映射到機(jī)器人視野域邊界附近作為局部導(dǎo)航子目標(biāo)，再由兩組螞蟻相互協(xié)作完成機(jī)器人視野域內(nèi)局部最優(yōu)路徑的搜索，然后在此基礎(chǔ)上進(jìn)行與其他機(jī)器人的碰撞預(yù)測與避碰規(guī)劃。因此，機(jī)器人的前進(jìn)路徑不斷被動態(tài)修改，從而在每條局部優(yōu)化路徑引導(dǎo)下，使機(jī)器人沿一條全局優(yōu)化的路徑到達(dá)目標(biāo)點。但其不足是在動態(tài)不確定的環(huán)境中路徑規(guī)劃時間開銷劇增，而且機(jī)器人缺乏必要的學(xué)習(xí)，以至于整個機(jī)器人系統(tǒng)路徑難以是最優(yōu)路徑。

強(qiáng)化學(xué)習(xí)[10，11](又稱再激勵學(xué)習(xí))是一種重要的機(jī)器學(xué)習(xí)方法。它是一種智能體從環(huán)境狀態(tài)到行為映射的學(xué)習(xí)，使得行為從環(huán)境中獲得積累獎賞值最大。其原理如圖1所示。

強(qiáng)化學(xué)習(xí)算法一般包含了兩個步驟：a）從當(dāng)前學(xué)習(xí)循環(huán)的值函數(shù)確定新的行為策略；b）在新的行為策略指導(dǎo)下，通過所獲得的瞬時獎懲值對該策略進(jìn)行評估。學(xué)習(xí)循環(huán)過程如下所示，直到值函數(shù)和策略收斂:

v0π1v1π2…v*π*v*

目前比較常見的強(qiáng)化學(xué)習(xí)方法有：MonteCarlo方法、動態(tài)規(guī)劃方法、TD（時間差分）方法。其中TD算法包含Sarsa算法、Q學(xué)習(xí)算法以及Dyna-Q算法等。其Q值函數(shù)迭代公式分別為

TD（0）策略：V(si)V(si)+α[γi+1+γV(si+1)-V(si)]

Sarsa算法：Q(st,at)Q(st,at)+α[γt+1+γQ(st+1,at.+1)-Q(st,at)]Qs′學(xué)習(xí)算法：Qπ(s,a)=∑Pαss′[Rass′+γVπ(s′)]

近年來，基于強(qiáng)化學(xué)習(xí)的路徑規(guī)劃日益成為國內(nèi)外學(xué)者研究的熱點。M.J.Mataric[12]首次把強(qiáng)化學(xué)習(xí)引入到多機(jī)器人環(huán)境中。而基于強(qiáng)化學(xué)習(xí)的多機(jī)器人路徑規(guī)劃的優(yōu)點主要體現(xiàn)在：無須建立精確的環(huán)境模型，簡化了智能體的編程；無須構(gòu)建環(huán)境地圖；強(qiáng)化學(xué)習(xí)可以把路徑規(guī)劃、避碰、避障、協(xié)作等問題統(tǒng)一解決。

張芳等人[13]提出了基于再激勵協(xié)調(diào)避障路徑規(guī)劃方法，把再勵函數(shù)設(shè)計為基于行為分解的無模型非均勻結(jié)構(gòu)，新的再勵函數(shù)結(jié)構(gòu)使得學(xué)習(xí)速度得以提高且有較好的魯棒性。同時，證明了在路徑規(guī)劃中，機(jī)器人的趨向目標(biāo)和避障行為密切相關(guān)，對反映各基本行為的再勵函數(shù)取加權(quán)和來表示總的再勵函數(shù)要優(yōu)于取直接和的表示方式，也反映了再勵函數(shù)設(shè)計得合理與否及其確切程度將影響再勵學(xué)習(xí)的收斂速度。王醒策等人[14]在動態(tài)編隊的強(qiáng)化學(xué)習(xí)算法方面展開了研究。宋一然[15]則提出了分段再勵函數(shù)的強(qiáng)化學(xué)習(xí)方法進(jìn)行路徑規(guī)劃。其缺點是學(xué)習(xí)次數(shù)較多、效率不高，當(dāng)機(jī)器人數(shù)目增加時，它有可能面臨維數(shù)災(zāi)難的困難。所以，基于強(qiáng)化學(xué)習(xí)的路徑規(guī)劃在多機(jī)器人環(huán)境下的學(xué)習(xí)將變得比較困難，需要對傳統(tǒng)的強(qiáng)化學(xué)習(xí)加以優(yōu)化，如基于人工神經(jīng)網(wǎng)絡(luò)的強(qiáng)化學(xué)習(xí)[16]等。

3)其他方法除了以上國內(nèi)外幾種比較常見且研究較多的方法外，還有唐振民等人[17]提出的基于動態(tài)規(guī)劃思想的多機(jī)器人路徑規(guī)劃，把運(yùn)籌學(xué)中的動態(tài)規(guī)劃思想與Dijkstra算法引入到多機(jī)器人的路徑規(guī)劃中，用動態(tài)規(guī)劃的基本思想來解決圖論中的費用流問題和路徑規(guī)劃中的層級動態(tài)聯(lián)盟問題。其選擇距離鄰近法作為聯(lián)盟參考依據(jù)。一個機(jī)器人的鄰居是指在地理位置上分布在這個機(jī)器人周圍的其他機(jī)器人；與該機(jī)器人最近鄰的機(jī)器人為第一層鄰居,第一層鄰居的鄰居為該機(jī)器人的第二層鄰居,依此類推。那么層級越高（即越近)的鄰居,它滿足協(xié)作要求的可能性越大。動態(tài)規(guī)劃算法實質(zhì)上是一種以空間換時間的技術(shù)，它在實現(xiàn)的過程中，必須存儲產(chǎn)生過程中的各種狀態(tài)，其空間復(fù)雜度要大于其他算法，故動態(tài)規(guī)劃方法比較適合多機(jī)器人的全局路徑規(guī)劃。

孫茂相等人[18]提出了最優(yōu)控制與智能決策相結(jié)合的多移動機(jī)器人路徑規(guī)劃方法。其首先構(gòu)造一個以各機(jī)器人最優(yōu)運(yùn)動狀態(tài)數(shù)據(jù)庫為核心的實時專家系統(tǒng),在離線狀態(tài)下完成;然后各機(jī)器人在此專家系統(tǒng)的支持下,以最優(yōu)規(guī)劃策略為基礎(chǔ),采用速度遷移算法,自主決定其控制。該方法擁有較好的穩(wěn)定性與復(fù)雜度。焦立男等人[19]提出的基于局部傳感和通信的多機(jī)器人運(yùn)動規(guī)劃框架較好地解決了多機(jī)器人路徑規(guī)劃在局部在線規(guī)劃的系統(tǒng)框架問題。沈捷等人[20]提出了保持隊形的多移動機(jī)器人路徑規(guī)劃。以基于行為的導(dǎo)航算法為基礎(chǔ),把機(jī)器人隊列的運(yùn)動過程劃分為正常運(yùn)動、避障和恢復(fù)隊形三個階段。在避障階段,引入虛擬機(jī)器人使隊形保持部分完整;當(dāng)隊形被嚴(yán)重打亂時,規(guī)劃機(jī)器人的局部目標(biāo)位姿使隊列快速恢復(fù)隊形。其算法重點為避障機(jī)器人進(jìn)入避障狀態(tài),暫時脫離隊列,并以虛擬機(jī)器人代替避障機(jī)器人。

2多機(jī)器人避碰和避障

避障和避碰是多機(jī)器人路徑規(guī)劃研究中需要考慮的重點問題之一。避障和避碰主要討論的內(nèi)容有防止碰撞；沖突消解、避免擁塞；如何避免死鎖。在路徑規(guī)劃中常見的多機(jī)器人避障方法[21]有主從控制法、動態(tài)優(yōu)先法（建立在機(jī)器人之間的通信協(xié)商上）、交通規(guī)則法、速率調(diào)整法，以及障礙物膨脹法、基于人工勢場的方法等。

目前國內(nèi)外對于多機(jī)器人避障展開的研究還不是很多，比較典型的有徐潼等人[22]以Th.Fraichard的思想為基礎(chǔ)，擴(kuò)充并完善了路徑/速度分解方案來協(xié)調(diào)多機(jī)器人,設(shè)立集中管理agent進(jìn)行整體規(guī)劃，為每個機(jī)器人規(guī)劃路徑；并根據(jù)優(yōu)先級規(guī)則對運(yùn)動特征進(jìn)行分布式規(guī)劃以避免機(jī)器人間的沖突。周明等人[23]提出分布式智能避撞規(guī)劃系統(tǒng)，將原來比較復(fù)雜的大系統(tǒng)轉(zhuǎn)換為相對簡單的子系統(tǒng)問題,由各智能機(jī)器人依據(jù)任務(wù)要求和環(huán)境變化,獨立調(diào)整自身運(yùn)動狀態(tài),完成任務(wù)的分布式智能決策體系結(jié)構(gòu)。任炏等人[24]提出了基于過程獎賞和優(yōu)先掃除的強(qiáng)化學(xué)習(xí)多機(jī)器人系統(tǒng)的沖突消解方法。該算法能夠顯著減少沖突,避免死鎖,提高了系統(tǒng)整體性能。歐錦軍等人[25]提出了通過調(diào)整機(jī)器人的運(yùn)動速度實現(xiàn)多機(jī)器人避碰，將避碰問題轉(zhuǎn)換為高維線性空間的優(yōu)化問題,并進(jìn)一步將其轉(zhuǎn)換為線性方程的求解。該方法的缺點是系統(tǒng)的復(fù)雜度較高、計算量太大。

人工勢場方法的特點是計算簡潔、實時性強(qiáng)、便于數(shù)學(xué)描述，且適合于多自由度機(jī)器人環(huán)境，但容易產(chǎn)生抖動和陷入局部極小。為了克服其缺點，景興建等人[26]提出了人工協(xié)調(diào)場的方法，在傳統(tǒng)排斥力場中增加一個協(xié)調(diào)力,并將吸引力、排斥力和協(xié)調(diào)力與局部環(huán)境下機(jī)器人的運(yùn)動狀態(tài)和運(yùn)動要求結(jié)合起來，有效地保證機(jī)器人的安全性，提高機(jī)器人在復(fù)雜動態(tài)環(huán)境下行為決策的準(zhǔn)確性和魯棒性。

3多機(jī)器人協(xié)作和協(xié)調(diào)機(jī)制

多機(jī)器人間的運(yùn)動協(xié)調(diào)[27~31]是多機(jī)器人路徑規(guī)劃的關(guān)鍵，也是多機(jī)器人與單機(jī)器人路徑規(guī)劃相區(qū)別的根本所在。多機(jī)器人系統(tǒng)在復(fù)雜動態(tài)實時環(huán)境下，由于受到時間、資源及任務(wù)要求的約束，需要在有限時間、資源的情況下進(jìn)行資源分配、任務(wù)調(diào)配、沖突解決等協(xié)調(diào)合作問題，而機(jī)器人間的協(xié)調(diào)與協(xié)作，能夠大大地提高整個系統(tǒng)的效率和魯棒性，成為系統(tǒng)完成控制或解決任務(wù)的關(guān)鍵。

目前已有的協(xié)調(diào)方式分為集中式、分布式和混合式三種。在集中式協(xié)調(diào)中，集中規(guī)劃器詳細(xì)地規(guī)劃出每個機(jī)器人的動作，通常的做法是將多個機(jī)器人看做一個多自由度的機(jī)器人進(jìn)行規(guī)劃；而分布式協(xié)調(diào)規(guī)劃中，機(jī)器人之間進(jìn)行合作，將一個任務(wù)分成多個子任務(wù)，根據(jù)各自的特點完成不同的子任務(wù)，從而共同完成總?cè)蝿?wù)；混合式協(xié)調(diào)是集中式和分布式混合在一起的形式。

摘要：在查閱大量文獻(xiàn)的基礎(chǔ)上對多機(jī)器人路徑規(guī)劃的主要研究內(nèi)容和研究現(xiàn)狀進(jìn)行了分析和總結(jié)，討論了多機(jī)器人路徑規(guī)劃方法的評判標(biāo)準(zhǔn)，并闡述了研究遇到的瓶頸問題，展望了多機(jī)器人路徑規(guī)劃方法的發(fā)展趨勢。

關(guān)鍵詞：多機(jī)器人；路徑規(guī)劃；強(qiáng)化學(xué)習(xí)；評判準(zhǔn)則

Abstract:Thispaperanalyzedandconcludedthemainmethodandcurrentresearchofthepathplanningresearchformultirobot.Thendiscussedthecriterionofpathplanningresearchformultirobotbasedlargeofliterature.Meanwhile,itexpoundedthebottleneckofthepathplanningresearchformultirobot，forecastedthefuturedevelopmentofmultirobotpathplanning.

Keywords:multirobot；pathplanning;reinforcementlearning;evaluatingcriteria

近年來，分布式人工智能(DAI)成為人工智能研究的一個重要分支。DAI研究大致可以分為DPS（distributedproblemsolving）和MAS（multiagentsystem）兩個方面。一些從事機(jī)器人學(xué)的研究人員受多智能體系統(tǒng)研究的啟發(fā)，將智能體概念應(yīng)用于多機(jī)器人系統(tǒng)的研究中，將單個機(jī)器人視做一個能獨立執(zhí)行特定任務(wù)的智能體，并把這種多機(jī)器人系統(tǒng)稱為多智能體機(jī)器人系統(tǒng)（MARS）。因此，本文中多機(jī)器人系統(tǒng)等同于多智能體機(jī)器人系統(tǒng)。目前，多機(jī)器人系統(tǒng)已經(jīng)成為學(xué)術(shù)界研究的熱點,而路徑規(guī)劃研究又是其核心部分。

機(jī)器人路徑規(guī)劃問題可以建模為一個帶約束的優(yōu)化問題，其包括地理環(huán)境信息建模、路徑規(guī)劃、定位和避障等任務(wù)，它是移動機(jī)器人導(dǎo)航與控制的基礎(chǔ)。單個移動機(jī)器人路徑規(guī)劃研究一直是機(jī)器人研究的重點，且已經(jīng)有許多成果[1~3]，例如在靜態(tài)環(huán)境中常見的有連接圖法、可視圖法、切線圖法、Voronoi圖法、自由空間法、柵格法、拓?fù)浞?、鏈接圖法、DempsterShafer證據(jù)理論建圖等；動態(tài)環(huán)境中常見的有粒子群算法、免疫算法、遺傳算法、神經(jīng)網(wǎng)絡(luò)、蟻群算法、模擬退火算法、人工勢場法等。然而，多機(jī)器人路徑規(guī)劃研究比單個機(jī)器人路徑規(guī)劃要復(fù)雜得多，必須考慮多機(jī)器人系統(tǒng)中機(jī)器人之間的避碰機(jī)制、機(jī)器人之間的相互協(xié)作機(jī)制、通信機(jī)制等問題。

1多機(jī)器人路徑規(guī)劃方法

單個機(jī)器人的路徑規(guī)劃是找出從起始點至終點的一條最短無碰路徑。多個機(jī)器人的路徑規(guī)劃側(cè)重考慮整個系統(tǒng)的最優(yōu)路徑，如系統(tǒng)的總耗時間最少路徑或是系統(tǒng)總路徑最短等。從目前國內(nèi)外的研究來看，在規(guī)劃多機(jī)器人路徑時，更多考慮的是多機(jī)器人之間的協(xié)調(diào)和合作式的路徑規(guī)劃。

目前國內(nèi)外多機(jī)器人路徑規(guī)劃研究方法分為傳統(tǒng)方法、智能優(yōu)化方法和其他方法三大類。其中傳統(tǒng)方法主要有基于圖論的方法（如可視圖法、自由空間法、柵格法、Voronoi圖法以及人工勢場方法等）；智能優(yōu)化方法主要有遺傳算法、蟻群算法、免疫算法、神經(jīng)網(wǎng)絡(luò)、強(qiáng)化學(xué)習(xí)等；其他方法主要有動態(tài)規(guī)劃、最優(yōu)控制算法、模糊控制等。它們中的大部分都是從單個機(jī)器人路徑規(guī)劃方法擴(kuò)展而來的。

1）傳統(tǒng)方法多機(jī)器人路徑規(guī)劃傳統(tǒng)方法的特點主要體現(xiàn)在基于圖論的基礎(chǔ)上。方法一般都是先將環(huán)境構(gòu)建成一個圖，然后再從圖中尋找最優(yōu)的路徑。其優(yōu)點是比較簡單，比較容易實現(xiàn)；缺點是得到的路徑有可能不是最優(yōu)路徑，而是次優(yōu)路徑。薄喜柱等人[4]提出的一種新路徑規(guī)劃方法的基本思想就是基于柵格類的環(huán)境表示和障礙地圖的。而人工勢場方法的基本思想是將移動機(jī)器人在環(huán)境中的運(yùn)動視為一種虛擬人工受力場中的運(yùn)動。障礙物對移動機(jī)器人產(chǎn)生斥力，目標(biāo)點產(chǎn)生引力，引力和斥力周圍由一定的算法產(chǎn)生相應(yīng)的勢，機(jī)器人在勢場中受到抽象力作用,抽象力使得機(jī)器人繞過障礙物。其優(yōu)點是適合未知環(huán)境下的規(guī)劃，不會出現(xiàn)維數(shù)爆炸問題；但是人工勢場法也容易陷入局部最小，并且存在丟失解的部分有用信息的可能。顧國昌等人[5]提出了引用總體勢減小的動態(tài)調(diào)度技術(shù)的多機(jī)器人路徑規(guī)劃，較好地解決了這個問題。

2）智能優(yōu)化方法多機(jī)器人路徑規(guī)劃的智能優(yōu)化方（算）法是隨著近年來智能計算發(fā)展而產(chǎn)生的一些新方法。其相對于傳統(tǒng)方法更加智能化，且日益成為國內(nèi)外研究的重點。

遺傳算法是近年來計算智能研究的熱點，作為一種基于群體進(jìn)化的概率優(yōu)化方法，適用于處理傳統(tǒng)搜索算法難以解決的復(fù)雜和非線性問題，如多機(jī)器的路徑規(guī)劃問題。在路徑規(guī)劃中，其基本思想是先用鏈接圖法把環(huán)境地圖構(gòu)建成一個路徑節(jié)點鏈接網(wǎng)，將路徑個體表達(dá)為路徑中一系列中途節(jié)點，并轉(zhuǎn)換為二進(jìn)制串；然后進(jìn)行遺傳操作（如選擇、交叉、復(fù)制、變異），經(jīng)過N次進(jìn)化，輸出當(dāng)前的最優(yōu)個體即機(jī)器人的最優(yōu)路徑。遺傳算法的缺點是運(yùn)算速度不快，進(jìn)化眾多的規(guī)劃要占據(jù)很大的存儲空間和運(yùn)算時間；優(yōu)點是有效避免了局部極小值問題，且計算量較小。

孫樹棟等人[6，7]在這方面較早地展開了研究，提出的基于集中協(xié)調(diào)思想的一種混合遺傳算法來規(guī)劃多機(jī)器人路徑方法較好地解決了避障問題。但不足的是該方法必須建立環(huán)境地圖，在環(huán)境未知情況下的規(guī)劃沒有得到很好的解決；且規(guī)劃只能保證找到一個比較滿意的解，在求解全局最優(yōu)解時仍有局限。

文獻(xiàn)[8]中提出的一種基于定長十進(jìn)編碼方法有效降低了遺傳算法的編碼難度，克服了已有的變長編碼機(jī)制及定長二進(jìn)制編碼機(jī)制需特殊遺傳操作算子和特殊解碼的缺陷,使得算法更加簡單有效。

智能計算的另一種常見的方法——蟻群算法屬于隨機(jī)搜索的仿生算法。其基本思想是模擬螞蟻群體的覓食運(yùn)動過程來實現(xiàn)尋優(yōu)，通過螞蟻群體中各個體之間的相互作用，分布、并行地解決組合優(yōu)化問題。該算法同樣比較適合解決多機(jī)器人的路徑規(guī)劃問題。

朱慶保[9]提出了在全局未知環(huán)境下多機(jī)器人運(yùn)動螞蟻導(dǎo)航算法。該方法將全局目標(biāo)點映射到機(jī)器人視野域邊界附近作為局部導(dǎo)航子目標(biāo)，再由兩組螞蟻相互協(xié)作完成機(jī)器人視野域內(nèi)局部最優(yōu)路徑的搜索，然后在此基礎(chǔ)上進(jìn)行與其他機(jī)器人的碰撞預(yù)測與避碰規(guī)劃。因此，機(jī)器人的前進(jìn)路徑不斷被動態(tài)修改，從而在每條局部優(yōu)化路徑引導(dǎo)下，使機(jī)器人沿一條全局優(yōu)化的路徑到達(dá)目標(biāo)點。但其不足是在動態(tài)不確定的環(huán)境中路徑規(guī)劃時間開銷劇增，而且機(jī)器人缺乏必要的學(xué)習(xí)，以至于整個機(jī)器人系統(tǒng)路徑難以是最優(yōu)路徑。

強(qiáng)化學(xué)習(xí)[10，11](又稱再激勵學(xué)習(xí))是一種重要的機(jī)器學(xué)習(xí)方法。它是一種智能體從環(huán)境狀態(tài)到行為映射的學(xué)習(xí)，使得行為從環(huán)境中獲得積累獎賞值最大。其原理如圖1所示。

強(qiáng)化學(xué)習(xí)算法一般包含了兩個步驟：a）從當(dāng)前學(xué)習(xí)循環(huán)的值函數(shù)確定新的行為策略；b）在新的行為策略指導(dǎo)下，通過所獲得的瞬時獎懲值對該策略進(jìn)行評估。學(xué)習(xí)循環(huán)過程如下所示，直到值函數(shù)和策略收斂:

v0π1v1π2…v*π*v*

目前比較常見的強(qiáng)化學(xué)習(xí)方法有：MonteCarlo方法、動態(tài)規(guī)劃方法、TD（時間差分）方法。其中TD算法包含Sarsa算法、Q學(xué)習(xí)算法以及Dyna-Q算法等。其Q值函數(shù)迭代公式分別為

TD（0）策略：V(si)V(si)+α[γi+1+γV(si+1)-V(si)]

Sarsa算法：Q(st,at)Q(st,at)+α[γt+1+γQ(st+1,at.+1)-Q(st,at)]Qs′學(xué)習(xí)算法：Qπ(s,a)=∑Pαss′[Rass′+γVπ(s′)]

近年來，基于強(qiáng)化學(xué)習(xí)的路徑規(guī)劃日益成為國內(nèi)外學(xué)者研究的熱點。M.J.Mataric[12]首次把強(qiáng)化學(xué)習(xí)引入到多機(jī)器人環(huán)境中。而基于強(qiáng)化學(xué)習(xí)的多機(jī)器人路徑規(guī)劃的優(yōu)點主要體現(xiàn)在：無須建立精確的環(huán)境模型，簡化了智能體的編程；無須構(gòu)建環(huán)境地圖；強(qiáng)化學(xué)習(xí)可以把路徑規(guī)劃、避碰、避障、協(xié)作等問題統(tǒng)一解決。

張芳等人[13]提出了基于再激勵協(xié)調(diào)避障路徑規(guī)劃方法，把再勵函數(shù)設(shè)計為基于行為分解的無模型非均勻結(jié)構(gòu)，新的再勵函數(shù)結(jié)構(gòu)使得學(xué)習(xí)速度得以提高且有較好的魯棒性。同時，證明了在路徑規(guī)劃中，機(jī)器人的趨向目標(biāo)和避障行為密切相關(guān)，對反映各基本行為的再勵函數(shù)取加權(quán)和來表示總的再勵函數(shù)要優(yōu)于取直接和的表示方式，也反映了再勵函數(shù)設(shè)計得合理與否及其確切程度將影響再勵學(xué)習(xí)的收斂速度。王醒策等人[14]在動態(tài)編隊的強(qiáng)化學(xué)習(xí)算法方面展開了研究。宋一然[15]則提出了分段再勵函數(shù)的強(qiáng)化學(xué)習(xí)方法進(jìn)行路徑規(guī)劃。其缺點是學(xué)習(xí)次數(shù)較多、效率不高，當(dāng)機(jī)器人數(shù)目增加時，它有可能面臨維數(shù)災(zāi)難的困難。所以，基于強(qiáng)化學(xué)習(xí)的路徑規(guī)劃在多機(jī)器人環(huán)境下的學(xué)習(xí)將變得比較困難，需要對傳統(tǒng)的強(qiáng)化學(xué)習(xí)加以優(yōu)化，如基于人工神經(jīng)網(wǎng)絡(luò)的強(qiáng)化學(xué)習(xí)[16]等。

3)其他方法除了以上國內(nèi)外幾種比較常見且研究較多的方法外，還有唐振民等人[17]提出的基于動態(tài)規(guī)劃思想的多機(jī)器人路徑規(guī)劃，把運(yùn)籌學(xué)中的動態(tài)規(guī)劃思想與Dijkstra算法引入到多機(jī)器人的路徑規(guī)劃中，用動態(tài)規(guī)劃的基本思想來解決圖論中的費用流問題和路徑規(guī)劃中的層級動態(tài)聯(lián)盟問題。其選擇距離鄰近法作為聯(lián)盟參考依據(jù)。一個機(jī)器人的鄰居是指在地理位置上分布在這個機(jī)器人周圍的其他機(jī)器人；與該機(jī)器人最近鄰的機(jī)器人為第一層鄰居,第一層鄰居的鄰居為該機(jī)器人的第二層鄰居,依此類推。那么層級越高（即越近)的鄰居,它滿足協(xié)作要求的可能性越大。動態(tài)規(guī)劃算法實質(zhì)上是一種以空間換時間的技術(shù)，它在實現(xiàn)的過程中，必須存儲產(chǎn)生過程中的各種狀態(tài)，其空間復(fù)雜度要大于其他算法，故動態(tài)規(guī)劃方法比較適合多機(jī)器人的全局路徑規(guī)劃。

孫茂相等人[18]提出了最優(yōu)控制與智能決策相結(jié)合的多移動機(jī)器人路徑規(guī)劃方法。其首先構(gòu)造一個以各機(jī)器人最優(yōu)運(yùn)動狀態(tài)數(shù)據(jù)庫為核心的實時專家系統(tǒng),在離線狀態(tài)下完成;然后各機(jī)器人在此專家系統(tǒng)的支持下,以最優(yōu)規(guī)劃策略為基礎(chǔ),采用速度遷移算法,自主決定其控制。該方法擁有較好的穩(wěn)定性與復(fù)雜度。焦立男等人[19]提出的基于局部傳感和通信的多機(jī)器人運(yùn)動規(guī)劃框架較好地解決了多機(jī)器人路徑規(guī)劃在局部在線規(guī)劃的系統(tǒng)框架問題。沈捷等人[20]提出了保持隊形的多移動機(jī)器人路徑規(guī)劃。以基于行為的導(dǎo)航算法為基礎(chǔ),把機(jī)器人隊列的運(yùn)動過程劃分為正常運(yùn)動、避障和恢復(fù)隊形三個階段。在避障階段,引入虛擬機(jī)器人使隊形保持部分完整;當(dāng)隊形被嚴(yán)重打亂時,規(guī)劃機(jī)器人的局部目標(biāo)位姿使隊列快速恢復(fù)隊形。其算法重點為避障機(jī)器人進(jìn)入避障狀態(tài),暫時脫離隊列,并以虛擬機(jī)器人代替避障機(jī)器人。

2多機(jī)器人避碰和避障

避障和避碰是多機(jī)器人路徑規(guī)劃研究中需要考慮的重點問題之一。避障和避碰主要討論的內(nèi)容有防止碰撞；沖突消解、避免擁塞；如何避免死鎖。在路徑規(guī)劃中常見的多機(jī)器人避障方法[21]有主從控制法、動態(tài)優(yōu)先法（建立在機(jī)器人之間的通信協(xié)商上）、交通規(guī)則法、速率調(diào)整法，以及障礙物膨脹法、基于人工勢場的方法等。

目前國內(nèi)外對于多機(jī)器人避障展開的研究還不是很多，比較典型的有徐潼等人[22]以Th.Fraichard的思想為基礎(chǔ)，擴(kuò)充并完善了路徑/速度分解方案來協(xié)調(diào)多機(jī)器人,設(shè)立集中管理agent進(jìn)行整體規(guī)劃，為每個機(jī)器人規(guī)劃路徑；并根據(jù)優(yōu)先級規(guī)則對運(yùn)動特征進(jìn)行分布式規(guī)劃以避免機(jī)器人間的沖突。周明等人[23]提出分布式智能避撞規(guī)劃系統(tǒng)，將原來比較復(fù)雜的大系統(tǒng)轉(zhuǎn)換為相對簡單的子系統(tǒng)問題,由各智能機(jī)器人依據(jù)任務(wù)要求和環(huán)境變化,獨立調(diào)整自身運(yùn)動狀態(tài),完成任務(wù)的分布式智能決策體系結(jié)構(gòu)。任炏等人[24]提出了基于過程獎賞和優(yōu)先掃除的強(qiáng)化學(xué)習(xí)多機(jī)器人系統(tǒng)的沖突消解方法。該算法能夠顯著減少沖突,避免死鎖,提高了系統(tǒng)整體性能。歐錦軍等人[25]提出了通過調(diào)整機(jī)器人的運(yùn)動速度實現(xiàn)多機(jī)器人避碰，將避碰問題轉(zhuǎn)換為高維線性空間的優(yōu)化問題,并進(jìn)一步將其轉(zhuǎn)換為線性方程的求解。該方法的缺點是系統(tǒng)的復(fù)雜度較高、計算量太大。

人工勢場方法的特點是計算簡潔、實時性強(qiáng)、便于數(shù)學(xué)描述，且適合于多自由度機(jī)器人環(huán)境，但容易產(chǎn)生抖動和陷入局部極小。為了克服其缺點，景興建等人[26]提出了人工協(xié)調(diào)場的方法，在傳統(tǒng)排斥力場中增加一個協(xié)調(diào)力,并將吸引力、排斥力和協(xié)調(diào)力與局部環(huán)境下機(jī)器人的運(yùn)動狀態(tài)和運(yùn)動要求結(jié)合起來，有效地保證機(jī)器人的安全性，提高機(jī)器人在復(fù)雜動態(tài)環(huán)境下行為決策的準(zhǔn)確性和魯棒性。

3多機(jī)器人協(xié)作和協(xié)調(diào)機(jī)制

多機(jī)器人間的運(yùn)動協(xié)調(diào)[27~31]是多機(jī)器人路徑規(guī)劃的關(guān)鍵，也是多機(jī)器人與單機(jī)器人路徑規(guī)劃相區(qū)別的根本所在。多機(jī)器人系統(tǒng)在復(fù)雜動態(tài)實時環(huán)境下，由于受到時間、資源及任務(wù)要求的約束，需要在有限時間、資源的情況下進(jìn)行資源分配、任務(wù)調(diào)配、沖突解決等協(xié)調(diào)合作問題，而機(jī)器人間的協(xié)調(diào)與協(xié)作，能夠大大地提高整個系統(tǒng)的效率和魯棒性，成為系統(tǒng)完成控制或解決任務(wù)的關(guān)鍵。

目前已有的協(xié)調(diào)方式分為集中式、分布式和混合式三種。在集中式協(xié)調(diào)中，集中規(guī)劃器詳細(xì)地規(guī)劃出每個機(jī)器人的動作，通常的做法是將多個機(jī)器人看做一個多自由度的機(jī)器人進(jìn)行規(guī)劃；而分布式協(xié)調(diào)規(guī)劃中，機(jī)器人之間進(jìn)行合作，將一個任務(wù)分成多個子任務(wù)，根據(jù)各自的特點完成不同的子任務(wù)，從而共同完成總?cè)蝿?wù)；混合式協(xié)調(diào)是集中式和分布式混合在一起的形式。

多機(jī)器人間典型的協(xié)調(diào)方法[32]有合同網(wǎng)協(xié)議[33]、黑板模型、結(jié)果共享的協(xié)同方法、市場機(jī)制。近年來強(qiáng)化學(xué)習(xí)在多機(jī)器人協(xié)作方面也得到很好的應(yīng)用，陳雪江[32]在基于強(qiáng)化學(xué)習(xí)的多機(jī)器人協(xié)作方面展開了研究，提出了多智能體協(xié)作的兩層強(qiáng)化學(xué)習(xí)方法來求解在多智能體完全協(xié)作、有通信情況下的協(xié)作問題。其主要通過在單個智能體中構(gòu)筑兩層強(qiáng)化學(xué)習(xí)單元來實現(xiàn)：第一層強(qiáng)化學(xué)習(xí)單元負(fù)責(zé)學(xué)習(xí)智能體的聯(lián)合任務(wù)協(xié)作策略；第二層強(qiáng)化學(xué)習(xí)單元負(fù)責(zé)學(xué)習(xí)在本智能體看來是最有效的行動策略。陳偉等人[34]提出基于多目標(biāo)決策理論的多機(jī)器人協(xié)調(diào)方法；通過對環(huán)境的拓?fù)浣?從基于行為的機(jī)器人學(xué)角度出發(fā),對任務(wù)進(jìn)行分解并設(shè)計目標(biāo)行為,以多目標(biāo)行為決策理論作為決策支持,從而達(dá)到多機(jī)器人運(yùn)動協(xié)調(diào)的目的。

4多機(jī)器人路徑規(guī)劃方(算)法的判優(yōu)準(zhǔn)則

通常評價機(jī)器人路徑規(guī)劃方(算)法的標(biāo)準(zhǔn)文獻(xiàn)[35]有正確性、時間/空間復(fù)雜度、并行性、可靠性、擴(kuò)展性、魯棒性和學(xué)習(xí)。而多機(jī)器人的路徑規(guī)劃除了以上一些衡量標(biāo)準(zhǔn)之外，還需要考慮整個系統(tǒng)的最優(yōu)化以及機(jī)器人間的協(xié)調(diào)性。

1)正確性是分析算法的最基本的原則之一。一般來說算法的正確性是指:在給定有效的輸入數(shù)據(jù)后，算法經(jīng)過有窮時間的計算能給出正確的答案。但在多機(jī)器人路徑規(guī)劃算法中，正確性主要指:路徑規(guī)劃算法要生成多個機(jī)器人協(xié)調(diào)運(yùn)動的無碰安全路徑;這條路徑是優(yōu)化的。

2)安全性一般指多機(jī)器人所生成的各路徑中節(jié)點與障礙物有一定的距離。但在實際的應(yīng)用背景下，有人認(rèn)為安全性可以從兩個方面來理解：a）狹義地講，它就是機(jī)器人在行走過程中所做的功。在一定的條件下，它與路徑長度準(zhǔn)則是一致的。b）廣義地講，它是各種優(yōu)化條件加權(quán)綜合而得到的結(jié)果。

3)復(fù)雜度一個算法的復(fù)雜性高低體現(xiàn)在該算法所需要的計算機(jī)資源的多少上面。所需要的資源越多，該算法的復(fù)雜性越高；反之，所需要的資源越少，該算法的復(fù)雜性就越低。算法的復(fù)雜性包括時間復(fù)雜度和空間復(fù)雜度。

在多機(jī)器人的路徑規(guī)劃算法中，算法的復(fù)雜度分析顯得尤為重要。一般地，單機(jī)器人路徑規(guī)劃算法的時空復(fù)雜度已經(jīng)頗高，它們的數(shù)量級至少是O(n2)；多機(jī)器人的路徑規(guī)劃算法不僅是m-O(n2)(即m個機(jī)器人路徑規(guī)劃簡單地疊加)，它們之間還存在著對運(yùn)動空間競爭的沖突，面對不斷變化的沖突的協(xié)調(diào)需要花費大量的時間和空間。通常多機(jī)器人的路徑規(guī)劃算法與機(jī)器人的個數(shù)呈指數(shù)關(guān)系O(km×n2)（k為常數(shù)）。這對多機(jī)器人路徑規(guī)劃算法的時間/空間復(fù)雜度控制是一個很嚴(yán)峻的考驗。

4)并行性算法的并行性從算法設(shè)計、編寫程序、編譯和運(yùn)行等多個不同的層次來體現(xiàn)。路徑規(guī)劃過程需要大量的計算，當(dāng)處理的環(huán)境比較復(fù)雜，機(jī)器人工作的環(huán)境過于緊湊，尤其是機(jī)器人數(shù)量很多時，算法的時間/空間復(fù)雜度勢必會成為算法效率的關(guān)鍵。因此，在算法設(shè)計和運(yùn)行上的并行性是通常考慮的方法。對多個機(jī)器人的路徑規(guī)劃盡量采用分布式多進(jìn)程的規(guī)劃機(jī)制，以實現(xiàn)每個機(jī)器人路徑規(guī)劃的并行性。

5)可靠性把多個機(jī)器人及其工作環(huán)境看成是一個系統(tǒng)，多機(jī)器人處于它們各自的起始點時，稱該系統(tǒng)處于初始狀態(tài)；當(dāng)它們處于各自的目標(biāo)點時，稱該系統(tǒng)處于目標(biāo)狀態(tài)。多機(jī)器人的路徑規(guī)劃就是在該系統(tǒng)的這兩個狀態(tài)間建立一串合理的狀態(tài)變遷。這一狀態(tài)變遷過程可能會歷經(jīng)許多狀態(tài)，如果在狀態(tài)變遷過程中，路徑規(guī)劃算法控制不好各狀態(tài)間的轉(zhuǎn)移關(guān)系，就會導(dǎo)致系統(tǒng)紊亂，出現(xiàn)機(jī)器人間的碰撞、找不到路徑等惡性后果，使任務(wù)失敗。所以這就對算法的可靠性和完備性提出了挑戰(zhàn)。為了很好地克服這一困難，需要對系統(tǒng)的各種可能狀態(tài)建模，分析它們相互間的關(guān)系，建立有限狀態(tài)自動機(jī)模型或Petri網(wǎng)模型，并以此為指導(dǎo)，按照軟件工程的思想，構(gòu)造恰當(dāng)?shù)乃惴ㄝ斎雭韺λ惴ǖ目煽啃赃M(jìn)行檢驗。

6)可擴(kuò)展性在多機(jī)器人的路徑規(guī)劃算法中，可擴(kuò)展性主要是指一種路徑規(guī)劃算法在邏輯上，或者說在實現(xiàn)上能否容易地從2D空間擴(kuò)展到3D空間，從低自由度擴(kuò)展到高自由度，從較少的機(jī)器人數(shù)到更多的機(jī)器人數(shù)。可擴(kuò)展性在各種路徑規(guī)劃算法之間沒有一種量的比較標(biāo)準(zhǔn)，只能從實際的具體情況出發(fā)、從對環(huán)境描述的適宜程度出發(fā)、從算法解決這一問題的復(fù)雜度出發(fā)、從算法本身的自適應(yīng)出發(fā)等來考慮。

7)魯棒性和學(xué)習(xí)魯棒性對于多機(jī)器人系統(tǒng)非常重要。因為許多應(yīng)用，如路徑規(guī)劃要求連續(xù)的作業(yè)、系統(tǒng)中的單個機(jī)器人出現(xiàn)故障或被破壞，要求機(jī)器人利用剩余的資源仍然能夠完成任務(wù)。學(xué)習(xí)是在線適應(yīng)特定的任務(wù)。雖然通用的系統(tǒng)非常有用，但將它用于特定應(yīng)用上時，通常需要調(diào)整一些參數(shù)。具有在線調(diào)整相關(guān)參數(shù)的能力是非常吸引人的，這在將體系結(jié)構(gòu)轉(zhuǎn)移到其他應(yīng)用時可以節(jié)省許多工作。尤其是多機(jī)器人系統(tǒng)中機(jī)器人的自身學(xué)習(xí)和相互間的學(xué)習(xí)能夠大大提高整個系統(tǒng)的效率和系統(tǒng)的穩(wěn)定性。

8）最優(yōu)化對動態(tài)環(huán)境有優(yōu)化反應(yīng)。由于有些應(yīng)用領(lǐng)域涉及的是動態(tài)的環(huán)境條件，具有根據(jù)條件優(yōu)化系統(tǒng)的反應(yīng)能力成為能否成功的關(guān)鍵。

5結(jié)束語

綜上所述，國內(nèi)外研究者在多機(jī)器人路徑規(guī)劃取得了一些成果，但是在協(xié)作、學(xué)習(xí)、通信機(jī)制等方面仍面臨很大的困難和不足。如何進(jìn)一步提高機(jī)器人間的協(xié)調(diào)性，增強(qiáng)機(jī)器人自身以及相互間的學(xué)習(xí)以提高多機(jī)器人系統(tǒng)的效率和魯棒性都有待深入研究。近年來無線通信技術(shù)得到長足發(fā)展,但在目前的技術(shù)條件下，在多機(jī)器人系統(tǒng)中實現(xiàn)所有機(jī)器人之間的點對點實時通信還有較大困難，這也是大多數(shù)多機(jī)器人系統(tǒng)仍然采用集中通信方式的主要原因。因此，如何降低多機(jī)器人系統(tǒng)對通信速度的依賴程度也是一個非常重要的問題。

總之,多機(jī)器人路徑規(guī)劃設(shè)計和實現(xiàn)是一項極其復(fù)雜的系統(tǒng)工程,展望其能在結(jié)合計算智能方法，如差分進(jìn)化、遺傳算法、粒子群算法、免疫算法、模糊邏輯算法、BP網(wǎng)絡(luò)、人工勢場的改進(jìn)、模擬退火和環(huán)境建模方法等方面取得新的突破。

參考文獻(xiàn)：

［1］WEISSG.Multiagentsystems:amodernapproachtodistributedmodernapproachtoartificialintelligence[M].Cambridge,Massachusetts：MITPress，1999：121-161.

[2]蔡自興，徐光祐.人工智能及其應(yīng)用:研究生用書[M].3版.北京：清華大學(xué)出版社，2004：124-198.

[3]譚民,王碩,曹志強(qiáng).多機(jī)器人系統(tǒng)[M].北京：清華大學(xué)出版社，2005：6-81.

[4]薄喜柱,洪炳熔.動態(tài)環(huán)境下多移動機(jī)器人路徑規(guī)劃的一種新方法[J].機(jī)器人，2001,23（5）：407-410.

[5]顧國昌,李亞波.基于總體勢減小的動態(tài)調(diào)度技術(shù)解決多機(jī)器人的路徑規(guī)劃[J].機(jī)器人，2001,23（2）：171-174.

[6]孫樹棟,林茂.基于遺傳算法的多移動機(jī)器人協(xié)調(diào)路徑規(guī)劃[J].自動化學(xué)報，2000,26（5）：672-676.

[7]周明,孫樹棟,彭炎午.基于遺傳算法的多機(jī)器人系統(tǒng)集中協(xié)調(diào)式路徑規(guī)劃[J].航空學(xué)報，2000,21（2）：146-149.

[8]CAIZixing,PENGZhihong.Cooperativecoevolutionaryadaptivegeneticalgorithminpathplanningofcooperativemultimobilerobotsystems[J].JournalofIntelligentandRoboticSystems:TheoryandApplications,2002,33(1):61-71.

[9]朱慶保.全局未知環(huán)境下多機(jī)器人運(yùn)動螞蟻導(dǎo)航算法[J].軟件學(xué)報，2006,17（9）：1890-1898.

[10]SANDHOLMTW，CRITESRH.Multiagentreinforcementlearningintheiteratedprisoner’sdilemma[J].BioSystems，1996，37(1):147-166.

[11]高陽，陳世福，陸鑫.強(qiáng)化學(xué)習(xí)研究綜述[J].自動化學(xué)報，2004,30（1）：

86-100.

[12]MATARICMJ.Interactionandintelligentbehavior[D].Massachusetls:DepartmentofElectricalEngineeringandComputerScience,MIT,1994.

[13]張芳,顏國正,林良明.基于再勵學(xué)習(xí)的多移動機(jī)器人協(xié)調(diào)避障路徑規(guī)劃方法[J].計算機(jī)工程與應(yīng)用，2003，39（3）：80-83.

[14]王醒策,張汝波,顧國昌.多機(jī)器人動態(tài)編隊的強(qiáng)化學(xué)習(xí)算法研究[J].計算機(jī)研究與發(fā)展，2003,40（10）：1444-1450.

[15]宋一然.基于強(qiáng)化學(xué)習(xí)的多機(jī)器人路徑規(guī)劃方法[J].莆田學(xué)院學(xué)報，2006,13（2）：38-41.

[16]韓學(xué)東,洪炳熔.基于人工神經(jīng)網(wǎng)絡(luò)的多機(jī)器人協(xié)作學(xué)習(xí)研究[J].計算機(jī)工程與設(shè)計，2002,23（6）：1-3.

[17]唐振民,趙春霞,楊靜宇，等.基于動態(tài)規(guī)劃思想的多機(jī)器人路徑規(guī)劃[J].南京理工大學(xué)學(xué)報，2003,27（5）：610-615.

[18]孫茂相,周明,王艷紅,等.多移動機(jī)器人實時最優(yōu)運(yùn)動規(guī)劃[J].控制與決策，1998,

13（2）：125-130.

[19]焦立男,唐振民.基于局部傳感和通訊的多機(jī)器人運(yùn)動規(guī)劃框架[J].計算機(jī)工程與應(yīng)用，2007,43(17)：89-93.

[20]沈捷,費樹岷，鄭波.多移動機(jī)器人保持隊形路徑規(guī)劃[J].東南大學(xué)學(xué)報，2005,35(3):391-395.

[21]MANSORMA，MORRISAS.Pathplanninginunknownenvironmentwithobstaclesusingvirtualwindow[J].JournalofIntelligentandRoboticSystems，1999，24(3):235-251.

[22]徐潼，唐振民.多機(jī)器人系統(tǒng)中的動態(tài)避碰規(guī)劃[J].計算機(jī)工程，2003,29(17):

79-81,104.

[23]周明,孫茂相,尹朝萬，等.多移動機(jī)器人分布式智能避撞規(guī)劃系統(tǒng)[J].機(jī)器人，1999,21（2）：139-143.

[24]任炏,陳宗海.基于強(qiáng)化學(xué)習(xí)算法的多機(jī)器人系統(tǒng)的沖突消解的方法[J].控制與決策，2006,21(4):430-434,439.

[25]歐錦軍,朱楓.一種多移動機(jī)器人避碰規(guī)劃方法[J].機(jī)器人，2000,22(6):474-481.

[26]景興建,王越超,談大龍.基于人工協(xié)調(diào)場的多移動機(jī)器人實時協(xié)調(diào)避碰規(guī)劃[J].控制理論與應(yīng)用，2004,21(5):757-764.

[27]PANAITL,LUKES.Cooperativemultiagentlearning:thestateoftheart[J].AutonomousAgentsandMultiAgentSystems,2005,11(3):387-434.

[28]TZAFESTASCS,PROKOPIOUPA,TZAFESTASSG.Pathplanningandcontrolofacooperativethreerobotsystemmanipulatinglargeobjects[J].JournalofIntelligentandRoboticSystems，1998,22(2):99-116.

[29]薛宏濤,葉媛媛,沈林成，等.多智能體系統(tǒng)體系結(jié)構(gòu)及協(xié)調(diào)機(jī)制研究綜述[J].機(jī)器人，2001,23（1）：85-90.

[30]周風(fēng)余,李貽斌,宋銳，等.基于混合式多智能體系統(tǒng)的協(xié)作多機(jī)器人系統(tǒng)研究[J].山東大學(xué)學(xué)報:工學(xué)版，2005,35(1):82-87.

[31]夏冰,張佐,張毅,等.基于多智能體系統(tǒng)的動態(tài)路徑選擇算法研究[J].公路交通科技，2003,20（1）：93-96.

[32]陳雪江.基于強(qiáng)化學(xué)習(xí)的多機(jī)器人協(xié)作機(jī)制研究[D].杭州：浙江工業(yè)大學(xué)，2004.

[33]SMITHR.Thecontractnetprotocol:highlevelcommunicationandcontrolinadistributedproblemsolver[J].IEEETransonComputer,1980，C-29(12):1104-1113.

[34]陳偉,張銘鈞,孟憲松.基于多目標(biāo)決策理論的多機(jī)器人協(xié)調(diào)方法[J].哈爾濱工程大學(xué)學(xué)報，2003,24（3）：308-312.

[35]李亞波.多機(jī)器人的路徑規(guī)劃與協(xié)調(diào)[D].哈爾濱：哈爾濱工程大學(xué)，2000.

摘要：在查閱大量文獻(xiàn)的基礎(chǔ)上對多機(jī)器人路徑規(guī)劃的主要研究內(nèi)容和研究現(xiàn)狀進(jìn)行了分析和總結(jié)，討論了多機(jī)器人路徑規(guī)劃方法的評判標(biāo)準(zhǔn)，并闡述了研究遇到的瓶頸問題，展望了多機(jī)器人路徑規(guī)劃方法的發(fā)展趨勢。

第9篇：動態(tài)規(guī)劃思想范文

Abstract： Through the introduction of the interesting questions of programming contest， which can help to stimulate the students' interest in learning and to raise the students' practical ability. This paper solves a classic competition topic named energy necklace problem by using a typical example named matrix multiply problem of the dynamic programming method， analyzes the similarity and difference of this two problems， and obtains the solving method of energy necklace problem.

關(guān)鍵詞： 動態(tài)規(guī)劃；矩陣連乘問題；能量項鏈問題

Key words： dynamic programming；matrix multiply problem；energy necklace problem

中圖分類號：G42；TP39 文獻(xiàn)標(biāo)識碼：A 文章編號：1006-4311（2012）35-0170-02

0 引言

在軟件工程專業(yè)的算法分析與設(shè)計課程中，筆者進(jìn)行了相關(guān)的教學(xué)改革，其中最突出的一點就是在講每種算法設(shè)計方法時，都從ACM競賽或NOI競賽中挑選有趣的且適合的競賽題目來引入要講的這個例子。例如，在講動態(tài)規(guī)劃算法時，通過賽題“能量項鏈問題”來引入矩陣連乘問題，通過賽題“回文詞的構(gòu)造”來引入最長公共子序列問題等。通過這些競賽題目的引入，極大地激發(fā)了學(xué)生的學(xué)習(xí)興趣。本文要討論的就是如何利用所學(xué)的矩陣連乘問題來解決經(jīng)典的競賽題目“能量項鏈問題”。

1 問題描述

1.1 矩陣連乘問題 幾乎在任何一本關(guān)于算法分析與設(shè)計課程的教材中，在介紹動態(tài)規(guī)劃算法時，都無一例外的會講授矩陣連乘問題，該問題是能用利用動態(tài)規(guī)劃方法解決的典型問題。該問題是說：給定n個矩陣A1，A2，…，An，其中矩陣Ai（1≤i≤n）的維數(shù)為pi×pi+1，于是相鄰的兩個矩陣就是可以相乘的?？紤]這n個矩陣的連乘積A1A2…An，由于矩陣乘法滿足結(jié)合律，所以求解這個矩陣連乘積時可以有許多不同的計算次序，每種計算次序都對應(yīng)一個乘法次數(shù)。那么矩陣連乘問題就是要確定一個矩陣連乘積的一種最優(yōu)計算次序，使得計算一個矩陣連乘積時，所需要的乘法次數(shù)最少。

假設(shè)用二維數(shù)組m來保存問題的最優(yōu)值，數(shù)組元素m[i][j]保存的是求解矩陣連乘積AiAi+1…Aj-1Aj時所需的最少乘法次數(shù)。則根據(jù)最優(yōu)子結(jié)構(gòu)性質(zhì)，容易建立m[i][j]所滿足的遞推關(guān)系式如下。

（1）i=j m[i][j]=0

（2）i

根據(jù)遞推關(guān)系式容易給出求解最小乘法次數(shù)的動態(tài)規(guī)劃算法，如下所示。

int p[100]，m[100][100]；

void matrix_min（int n）

{ for（int i=1；i

m[i][i]=0；

for（int r=2；r

for（int i=1；i

{ int j=i+r-1；

m[i][j]=m[i+1][j]+p[i]*p[i+1]*p[j+1]；

for（int k=i+1；k

{ int min=m[i][k]+m[k+1][j]+p[i]*p[k+1]*p[j+1]；

if （minm[i][j]）

m[i][j]=min；

}

}

}

調(diào)用該算法可求出n個矩陣相乘時所需的最少乘法次數(shù)，若要求n個矩陣相乘時所需的最大乘法次數(shù)則只需將matrix_min算法中if語句條件中的“”即可，為了便于描述，將求n個矩陣相乘時所需的最大乘法次數(shù)的算法命名為matrix_max算法。

1.2 能量項鏈問題 在NOIP2006提高組復(fù)賽試題中有一道題目，叫做“能量項鏈問題”，題目的大致含義是：在一串能量項鏈上有N顆能量珠。能量珠是一顆有頭標(biāo)記與尾標(biāo)記的珠子，這些標(biāo)記對應(yīng)著某個正整數(shù)。對于相鄰的兩顆珠子，前一顆珠子的尾標(biāo)記一定等于后一顆珠子的頭標(biāo)記。因為只有這樣，這兩顆珠子才能聚合成一顆珠子，同時釋放出能量。如果前一顆能量珠的頭標(biāo)記為m，尾標(biāo)記為r，后一顆能量珠的頭標(biāo)記為r，尾標(biāo)記為n，則這兩顆能量珠聚合后釋放的能量為m×r×n，新產(chǎn)生的珠子的頭標(biāo)記為m，尾標(biāo)記為n。

顯然，N顆珠子聚合成一顆珠子時會有許多不同的聚合次序，不同的聚合順序得到的總能量是不同的，能量項鏈問題就是要確定N顆珠子聚合時的一種最優(yōu)聚合次序，使得按照這種次序?qū)顆珠子聚合成一顆珠子時，釋放出的總能量最大。

例如：設(shè)N=4，4顆珠子的頭標(biāo)記與尾標(biāo)記依次為（2，3），（3，5），（5，10），（10，2）。則這4顆珠子的一種最優(yōu)聚合次序及釋放出的最大能量值如下。

（（4？茌1）？茌2）？茌3）=10×2×3+10×3×5+10×5×10=710。

符號？茌表示聚合操作。

2 矩陣連乘問題與能量項鏈問題的相似性與相異性

由以上兩個問題的描述可知，它們之間有許多相似之處，其相似性可歸納為以下五點。

①矩陣和珠子非常相似，每個矩陣都有行數(shù)和列數(shù)，每個珠子都有頭標(biāo)記和尾標(biāo)記；②對于相鄰的兩個矩陣來說，前一個矩陣的列等于后一個矩陣的行，對于相鄰的兩個珠子來說，前一個珠子的尾標(biāo)記等于后一個珠子的頭標(biāo)記；③相鄰的兩個矩陣相乘時所需的乘法次數(shù)為這兩個矩陣的三個維數(shù)的乘積，相鄰的兩個珠子聚合時所產(chǎn)生的能量為這兩個珠子的三個標(biāo)記的乘積；④兩個矩陣相乘后得到一個矩陣，這個矩陣的行數(shù)為第一個矩陣的行，這個矩陣的列數(shù)為第二個矩陣的列，中間相同的維數(shù)抵消了。兩個珠子聚合后得到一個珠子，這個珠子的頭標(biāo)記為第一個珠子的頭標(biāo)記，這個珠子的尾標(biāo)記為第二個珠子的尾標(biāo)記，中間相同的標(biāo)記抵消了；⑤n個矩陣相乘時，一種計算次序所對應(yīng)的乘法次數(shù)是每一次相乘時所需的乘法次數(shù)之和，n個珠子聚合時，一種聚合次序所對應(yīng)的能量值是每一次聚合時所產(chǎn)生的能量之和。

當(dāng)然，兩個問題之間也有區(qū)別，主要有兩點。①在矩陣連乘問題中，第n個矩陣和第1個矩陣是不相鄰的，而在能量項鏈問題中，第n個珠子和第1個珠子是相鄰的，第n個珠子的尾標(biāo)記一定要等于第1個珠子的頭標(biāo)記，這兩個珠子是可以進(jìn)行聚合操作的；②在矩陣連乘問題中，是要確定n個矩陣相乘的一種最優(yōu)計算次序，使得所需要的乘法次數(shù)最少。而在能量項鏈問題中，是要確定n個珠子聚合時的一種最優(yōu)聚合次序，使得釋放的總能量值最大。

3 能量項鏈問題的解法探討

鑒于以上分析，能量項鏈問題其實就是一個特殊的矩陣連乘問題，可將一個珠子看成是一個矩陣，將n個珠子構(gòu)成的能量項鏈看成是由n個矩陣構(gòu)成的環(huán)形矩陣連乘積，只不過在這個環(huán)形矩陣連乘積中，第n個矩陣的列數(shù)一定要等于第1個矩陣的行數(shù)。兩個珠子聚合后產(chǎn)生的能量值就是它們對應(yīng)的兩個矩陣相乘時所需的乘法次數(shù)，n個珠子聚合成一個珠子時產(chǎn)生的總能量值就是這n個矩陣相乘后得到一個矩陣時所需的總的乘法次數(shù)，要確定n個珠子聚合時的一種最優(yōu)聚合次序，使得釋放的總能量值最大。也就是要確定這n個矩陣構(gòu)成的環(huán)形矩陣連乘問題的一種最優(yōu)計算次序，使得所需的乘法次數(shù)達(dá)到最大。

在n個矩陣直線相乘時，第n個矩陣和第1個矩陣是不相鄰的，即這兩個矩陣是不能相乘的。而當(dāng)這n個矩陣環(huán)形相乘時，第n個矩陣和第1個矩陣是相鄰的，這兩個矩陣是可以相乘的，這種相鄰性的改變使問題變得復(fù)雜了。在n個矩陣直線相乘時，長度為n的矩陣連乘積只有一種，就是A1A2…An，而當(dāng)n個矩陣環(huán)形相乘時，長度為n的矩陣連乘積就有n種，分別是：A1A2…An-1An，A2A3…AnA1，依此類推，最后一種是AnA1…An-2An-1。其實要表示出這n種情況，可將n個矩陣構(gòu)成的圓環(huán)在矩陣An和A1之間斷開，拉成一條直線，然后在矩陣An的后面添加上n-1個矩陣，也就是添加上A1A2…An-2An-1，這樣就形成了一個長度為2n-1的直線矩陣鏈，顯然在這個長度為2n-1的直線矩陣鏈中，上述n種情況都可以表示出來。

若用An+i來表示新添加的第i個矩陣，這里1≤i≤n-1，則有An+i=Ai。對于這個長度為2n-1的直線矩陣連乘問題來說，上述n種直線相乘的情況就是這個問題的n個子問題，因此，只需要利用matrix_max算法求長度為2n-1的直線矩陣連乘問題的最大乘法次數(shù)即可，在以自底向上方式計算它的最大乘法次數(shù)時，所有長度為n的子矩陣連乘積所需的最大乘法次數(shù)都已經(jīng)求完了，共有n個，由matrix_max算法的思想可知，長度為n的子矩陣連乘積所需的最大乘法次數(shù)可表示為m[i][i+n-1]，這里1≤i≤n，最終這n個m[i][i+n-1]中的最大者就是n個矩陣環(huán)形相乘時所需的最大乘法次數(shù)。

根據(jù)上述方法求解環(huán)形矩陣連乘問題最優(yōu)值的步驟可歸納為三步。

①擴(kuò)充操作，添加n-1個矩陣，從而將長度為n的環(huán)形矩陣連乘問題轉(zhuǎn)化為長度為2n-1的直線矩陣連乘問題；②調(diào)用matrix_max算法求長度為2n-1的直線矩陣連乘問題的最優(yōu)值；③求n個m[i][i+n-1]中的最大者。

根據(jù)上述思想，其求解算法如下所示。

int circlematrix（int n）

{ int i， max=0；

for（i=2；i

p[n+i]=p[i]；

matrix_max（2*n-1）；

for（i=1；i

if（m[i][i+n-1]>max）

max=m[i][i+n-1]；

return max；

}

4 結(jié)論

本文利用“矩陣連乘問題”解決了一道經(jīng)典的競賽題目“能量項鏈問題”，在授課程過程中，筆者曾以一個學(xué)生為例引入了這道競賽題目，課堂效果非常好。通過競賽題目的引入和講解，有利于激發(fā)學(xué)生的學(xué)習(xí)興趣，對算法分析與設(shè)計課程不再有畏難心理，提高學(xué)生的算法設(shè)計能力，并有利于開展素質(zhì)教育活動，積極指導(dǎo)學(xué)生參加學(xué)科競賽。

參考文獻(xiàn)：

[1]潘金貴，顧鐵成等譯.算法導(dǎo)論[M].北京：機(jī)械工業(yè)出版社，2007：197-202.