動態規劃精選(九篇)

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

第1篇：動態規劃范文

關鍵詞：動態規劃；模板匹配；特征距離矩陣

DOIDOI：10.11907/rjdk.171142

中圖分類號：TP312

文獻標識碼：A 文章編號：1672-7800（2017）06-0037-03

0 引言

在計算機領域，常需要將實驗數據與預先設定好的模板進行匹配。圖像處理領域中的圖像檢索、圖像分割、圖像拼接、圖像檢測、視頻編碼等，就需要運用到模板匹配技術。模板匹配技術在圖像處理領域的具體應用可以簡單分為兩大類：基于特征點的匹配技術、基于像素灰度的匹配。基于特征點的匹配往往被更高級的機器視覺類任務采用，而在圖像處理中，基于特征的匹配方法由于抽取的點、線、特征子等特征容易受到視角變換、遮擋等問題的干擾，會影響到最終匹配結果的質量，同時特征抽取方法的時間復雜度較高，對于實時性是一個挑戰。基于像素灰度的模板匹配方法，只需要設定好匹配的模板尺寸與遍歷方式，算法簡潔、穩定性高，適合圖像處理與計算機視覺問題中的底層預處理。但其也存在一些缺點，如噪聲、光照引起的灰度變化，且運算數據量大，基于像素灰度的匹配算法也無法避免圖像數據與模板匹配過程可能帶來的高復雜度問題。

迄今為止，模板匹配技術已經被廣泛應用到圖像處理的實際問題中，并取得了一系列成果。例如，王倩倩[1]將模板匹配問題應用到藻類圖像的識別問題中，李厚軍[2]將模板匹配問題應用到眉毛的識別問題中，陳瑩[3]將模板匹配方法用于增強微光圖像，王正等[4]將模板匹配引入到圖像編碼中的調色板更正上，提高了圖像編碼效率，王志衡，郭超等[5]將模板匹配方法應用到了新聞圖像字母行切分之中，張盼盼[6]等將模板匹配方法應用到了數字識別過程中，陳寧等[7]將該方法應用到集裝箱識別與匹配的問題中。然而，采用上述方法在面臨大數據量的數據時，也存在復雜度較高的問題。因此，如何進一步優化模板匹配問題有待進一步研究解決。

動態劃方法（Dynamic Programming）早期誕生于運籌學，是一種迭代求解最優的方法。近年來，動態規劃方法作為算法設計策略中求解最優子結構的一種重要思想，被廣泛引入到計算機問題求解之中。動態規劃求解計算機問題的基本思想是，將待求解問題分解成若干個結構相同的子問題，在求解過程中保存已求解子問題的答案并在后續求解過程中，有效利用之前求解的答案協助當前問題求解。由于后續問題在求解過程中已經遇到了需要之前已經求過的子問題，因此大大提高了求解效率[8-11]。可以簡單地將動態規劃算法分為基于線性的動態規劃算法、基于樹形的動態規劃算法、基于區域的動態規劃算法、基于背包的動態規劃算法。具體采用何種動態規劃方法應針對具體問題作具體分析，例如，有學者[12-13]在語音識別與動作識別等具體領域嘗試采用動態規劃算法嘗試優化求解。但往往只是將動態規劃算法應用到某一具體問題，尚未對圖像處理中的模板匹配問題進行動態規劃算法實現。

綜上，鑒于動態規劃方法的自身特性及當前圖像處理在解決模板匹配問題上的不足，本文提出了一種采用動態規劃解決模板匹配的方法，首先給出圖像數據與模板的匹配問題，并對該問題進行符號化和相應的理論分析，此后采用動態規劃的方法解決模板匹配問題，并對傳統動態規劃解決方法在時間復雜度上進行改進。相較于傳統模板匹配方法，采用本文提出的方法可以將時間復雜度減少一個數量級。

1 問題分析與解決

圖像模板匹配算法的過程可以簡單歸納為：首先采用某一尺度的模板遍歷所有數據（例如整幅圖像），此后計算模板與模板在整個圖像中所對應區域的匹配程度，最后在數據中找到與模板匹配程度最高的區域。對于一幅圖像數據S而言，若圖像的尺寸大小為H*W，模板T的尺寸為P*P，模板匹配算法需要在圖像數據上進行遍歷，并計算模板與模板覆蓋區域的匹配程度，將模板覆蓋到一個圖像區域并計算匹配度的過程約定為一個動作。設有一組試驗動作序列：V=（V0，V1，…，VM） 和一組模板動作序列T=（T0，T1，…，TN），（M>N），兩組序列都滿足動作的時間順序，這里試驗動作數據中的每個動作都必須出現在匹配路徑中，而模板動作序列不做此要求。計算模板與圖像對應位置的匹配程度，可以根據需求采取不同的度量方式，如歐式距離、光度距離與幾何距離等。模板的移動可以采用Zigzag的方式實現。則上述模板匹配可以得到有效的距離矩陣，可以在該距離矩陣的基礎上設計動態規劃優化解決方案。這里，假設試驗動作數為M=15，模板動作數為N=10。

1.1 問題符號化及分析

為了方便地表達該問題，采用3個矩陣進行存儲和計算，如圖1所示。一個是矩陣A，用來存放原始數據；一個是矩陣B，用來存放計算過程的局部最優值；一個是矩陣R，用來記錄局部最優值所對應的路徑。

1.2 問題解決

1.2.1 局部最優值計算

對于上述問題，采用動態規劃思想進行解決，其基本思路如下：首先，試驗動作從V0開始，由于它是第一個試驗動作，前面沒有其它動作，因而無論它選擇哪一個模板，都可看成是當前的最優值；然后，考查第二個試驗動作V1，如果V1選擇的模板動作是T0，那么試驗動作V0選擇的模板只能是T0，這時它的最小值為a0，0+a1，0，同時在矩陣R中r0，0位置記錄該局部最優值所對應的模板序號；如果V1選擇的模板動作為T1，那么試驗動作V0可以選擇的模板是T0或T1，顯然，只有取a0，0和a0，1中的最小值，與a1，1相加后可得V1在選擇模板動作T1時的最優值，同時在矩陣R中r0，1位置記錄該局部最優值所對應的模板序號；如果V1選擇的模板動作為T2，那么試驗動作V0可以選擇的模板就可以是T0、T1或T2，這時，需要取a0，0、a0，1、a0，2中的最小值，與a1，2相加后可得V1在選擇模板動作T2時的最優值，同時在矩陣R中r0，2位置記錄該局部最優值所對應的模板序號；如果V1選擇的模板動作為Tj，j=3，…9，則依次類推。

其中，k的最大值是第M層葉結點的個數。度為p的樹中第i層至多有pi-1個節點（i>1），該問題求解的樹的度p=3，則第M=15層至多有3M-1=315-1個結點，試驗中k的最大值為16，通過分析可以得出該問題的時間復雜度為O（16*M）。

綜上分析，文中給出的算法在求模板匹配的最優解時，其對應的時間復雜度為O（MN）+O（KM），即max（O（MN），O（KM））。若從p叉樹的生成角度考慮，算法的時間復雜度為O（MN）+O（nodes），即max（O（MN），O（nodes））。

3 結語

針對傳y模板匹配算法在應用圖像處理問題時遇到的時間復雜度過高等問題，對數據與模板匹配的過程進行優化，提出了一種基于動態規劃算法加以實現的方法，算法的時間復雜度為max（O（MN），O（KM））。利用本算法，可以將模板匹配過程的復雜度大大減小，也不需要對數據進行過多處理，而且程序編寫簡單，各方面比原算法和目前已有文獻中提到的改進算法都有很大提高。

可以看出，未來無論是計算機處理領域的模板匹配問題，還是日常生活生產中經常遇到的“試驗數據和事先存儲好的模板動作進行匹配”及類似問題，本文所提出的算法都具有一定應用前景。

參考文獻：

[1]王倩倩.基于聚類的模板匹配顯微細胞圖像分割算法的研究[D].重慶：重慶大學，2015.

[2]李厚軍.快速模板匹配方法及其在眉毛識別中的應用[D].北京：北京工業大學，2015.

[3]陳瑩.基于FPGA的微光圖像增強和模板匹配研究[D].北京：中國科學院大學，2014.

[4]王正，陶品，馮立新，溫江濤，楊士強.基于模板的調色板方法[J].計算機輔助設計與圖形學學報，2016，28（7）：1146-1151.

[5]王志衡，郭超.基于模板匹配的新聞圖像字幕行切分算法[J].北京郵電大學學報，2016，39（3）：49-53.

[6]張盼盼，張穎穎.模板匹配與八鄰域分析法在數字細化預處理中的應用及比較[J].軟件導刊，2016，15（5）：210-211.

[7]陳寧，王勝，黃正文.基于特征匹配的集裝箱識別與定位技術研究[J].圖學學報，2016，37（4）：530-536.

[8]THOMAS H CORMEN，CHARLES E LEISERSON.Introduction to algorithms[M].Second Edition.Massachusetts：The MIT Press，2001.

[9]王曉東.計算機算法設計與分析[M].第2版.北京：電子工業出版社，2005.

[10]徐孝凱，賀桂英.數據結構（C語言描述）[M].北京：清華大學出版社，2004.

[11]唐策善，李龍澍，黃劉生.數據結構――用C語言描述[M].北京：高等教育出版社，2003.

第2篇：動態規劃范文

動態規范是算法里一種非常重要的方法,是求解決策過程最優化的數學方法。動態規劃自問世以來,在經濟管理、生產調度、工程技術和最優控制等方面得到了廣泛的應用。例如最短路線、庫存管理、資源分配、設備更新、排序、裝載等問題,用動態規劃方法比用其他方法求解更為方便。

本文通過對經典的01背包問題的求解,從動態規劃的角度進行闡述,通過案例對該算法的計算過程進行了直觀的描述,并對該算法進行了一定的優化,最后指出該算法的優缺點。

[關鍵詞]背包 動態規劃 時間復雜度 空間復雜度

[中圖分類號]TP31[文獻標識碼]A[文章編號]1009-5349(2010)05-0121-03

前言

背包問題是一個經典的動態規劃模型,很多關于算法的教材都把它作為一道例題,該問題既簡單又容易理解,而且在某種程度上還能夠揭示動態規劃的本質。

將具有不同重量和價值的物體裝入一個有固定載重量的背包,以獲取最大價值,這類問題被稱為背包問題。

背包問題可以擴展出很多種問題,而01背包問題是最常見、最有代表性的背包問題。

一、問題描述

給定一個載重量為M的背包及n個物體,物體i的重量為wi、價值為pi,1≤i≤n,要求把這些物體裝入背包,使背包內的物體價值總量最大。此處我們討論的物體是不可分割的,通常稱這種物體不可分割的背包問題為01背包問題。

二、基本思路

01背包問題的特點是:每種物體只有一件,可以選擇放或者不放。假設:xi表示物體i被裝入背包的情況,xi=0,1。當xi=0時,表示物體沒有被裝入背包;當xi=1時,表示物體被裝入背包。根據問題的要求,有如下的約束方程(1)和目標函數(2):

三、利用動態規劃法求解01背包問題

(一)動態規劃算法的基本思想

動態規劃算法通常用于求解具有某種最優性質的問題。在這類問題中,可能會有許多可行解。每一個解都對應于一個值,我們希望找到具有最優值的解。動態規劃算法與分治法類似,其基本思想也是將待求解問題分解成若干個子問題,先求解子問題,然后從這些子問題的解得到原問題的解。與分治法不同的是,適合于用動態規劃求解的問題,經分解得到子問題往往不是互相獨立的。若用分治法來解這類問題,則分解得到的子問題數目太多,有些子問題被重復計算很多次。如果我們能夠保存已解決的子問題的答案,而在需要時再找出已求得的答案,這樣就可以避免大量的重復計算,節省時間。我們可以用一個表來記錄所有已解的子問題的答案。不管該子問題以后是否被用到,只要它被計算過,就將其結果填入表中,這就是動態規劃法的基本思路。具體的動態規劃算法多種多樣,但它們具有相同的填表格式。

(二)算法設計

假定背包的載重量范圍為0～m。類似于資源分配那樣,令optpi(j)表示在前i個物體中,能夠裝入載重量為j的背包所得的最大價值,j=1,2,……,m。顯然,此時在前i個物體中,有些物體可以裝入背包,有些物體不能裝入背包。于是,可以得到下面的動態規劃函數:

(4)式表明:把前面i個物體裝入載重量為0的背包,或者把0個物體裝入載重量為j的背包,得到的價值都為0。(5)式表明:當第i個物體的重量大于背包的載重量時,裝入前i個物體得到的最大價值,與裝入前i-1個物體得到的最大價值一樣,即第i個物體沒有裝入背包。(6)式表明:當第i個物體的重量小于背包的載重量時,如果第i個物體裝入背包,背包中物體的價值,等于把前i-1個物體裝入載重量為j-wi的背包所得到的價值與第i個物體的價值pi之和;如果第i個物體沒有裝入背包,則背包中物體的價值,等于把前i-1個物體裝入載重量為j的背包,卻不裝入第i個物體所取得的價值。顯然,這兩種裝入方法,在背包中所取得的價值不一定相同,因此,取這兩者中的最大值,作為把前面i個物體裝入載重量為j的背包所取得的最優價值。

該算法可分為n階段:

第一階段,只裝入一個物體,計算在不同載重量的背包情況下,所取得的最大價值;

第二階段,裝入前兩個物體,按(5)式和(6)式計算在不同載重量的背包情況下,取得的最大價值;

……

第n階段,裝入前n個物體,按(5)式和(6)式計算在不同載重量的背包情況下,取得的最大價值,而在背包載重量為M時,所得結果就是我們想要的結果。

為了確定具體哪個物體裝入背包,從optpn(m)的值向前倒推。有如下遞推關系式:

(7)式表明:如果optpi(j)大于optpi-1(j),則物體i被裝入背包;如果optpi(j)等于optpi-1(j),表明i物體未被裝入背包。按照該關系式,i從n到1依次類推,直到確定第一個物體是否被裝入背包為止,就能確定裝入背包的具體物體。

(三)存儲結構

該算法需要將每一個物體的重量和價值分別存儲起來,并針對不同載重量的背包對物體分別計算,故考慮使用數組來實現。對于物體i,用weight[i]來表示重量、用p[i]表示價值,解向量用x[i]表示物體i是否被放入,上面提到的optpi(j)則用二維數組相應的optp[i][j]來表示,物體個數n,背包載重量為m。

(四)算法實現

initial knapsack_dynamic(initial optp[][],weight[],p[],x[],n,m)

{

initial i,j,value;

//根據(4)式初始化第0列及解向量X

//解向量初始值設置為false,表示起初所有物體均未放入背包

for(i = 0; i

{

optp[i][0] = 0;

x[i] = FALSE;

}

//根據(4)式初始化第0行

for(i = 0; i

{

optp[0][i] = 0;

}

//利用(5)(6)式計算optp[i][j]

for(i = 1; i

{

for(j = 1; j

{

optp[i][j] = optp[i-1][j];

if((j >= weight[i]) && (optp[i-1][j - weight[i]]+p[i]) > optp[i-1][j])

optp[i][j] = optp[i-1][j-weight[i]] + p[i];

}

}

//確定裝入背包的具體物體

j = m;

for(i = n; i > 0; i--)

{

if(optp[i][j] > optp[i-1][j])

{

x[i] = TRUE;

j = j - weight[i];

}

}

//value就是所要求的值

value = optp[n][m];

return value;

}

1.案例分析

現有載重量為10的背包,有四個物體A、B、C、D,其重量分別為4、2、5、3,價值分別為4、3、5、8,要求放入物體使背包所獲價值最大。

用optp[i][j]來存儲這四個物體在不同載重量的背包下所獲的價值,計算過程如下表所示:

2.時間空間復雜度

該算法中,矩陣optp的大小為(m+1)×(n+1),物體的重量、價值和解向量大小都等于物體個數n,故該算法的空間復雜度為O(nm)。對物體重量、價值的初始化(算法實現略)所需時間都為n,解向量和矩陣第0行初始化時間為n,矩陣第0列初始化時間為m,對矩陣optp的計算所需時間為n×m,解向量X的確定時間為n,故整個算法的時間復雜度為O(nm)。

(五)算法優化

在上述算法中,時間復雜度不能再繼續優化了,但是空間復雜度是可以繼續優化的。

上述算法中,存儲optp使用的是二維數組,其大小為(m+1)×(n+1),但是仔細觀察發現,optp[i][j]只與optp[i-1][j]和optp[i-1][j - weight[i]]有關,與optp[k][l](k=1,2,……,i-2,i+1,……n,j=1,2,……,m)無關,故可考慮只用一維數組_optp來存儲,_optp[j]相當于optp[i][j]。而考慮到optp[i][j]是由optp[i][j]和optp[i-1][j - weight[i]]共同計算得到的,故該算法中的j循環要從后往前計算,_optp[]的計算算法設計如下所示:

for(i = 1; i

{

for(j = m; j >= 1; j--)

{

if((j >= weight[i]) && (_optp[j - weight[i]]+p[i]) > _optp[j])

_optp[j] = optp[j-weight[i]] + p[i];

}

}

上述例子中,相應的_optp[j]計算結果如下表所示:

}

}

上述例子中,相應的_optp[j]計算結果如下表所示:

顯然,對于物體i,_optp[j]的計算不會影響到_optp[0,1,……,weight[i]-1],故上述算法可繼續優化為:

for(i = 1; i

{

for(j = m; j >= weitht[i]; j--)

{

if((_optp[j - weight[i]]+p[i]) > _optp[j])

_optp[j] = optp[j-weight[i]] + p[i];

}

}

對于01背包問題,常見的要求有兩種:一種是恰好裝滿背包、另一種則沒有要求,針對這兩種問法,可從初始化上來區分。

當要求恰好裝滿背包時,初始化時將_optp[0]設為0,其他_optp[1,2,……,m]全部設為-∞,這樣就可保證最終得到的_optp[n]是一種恰好裝滿的最優解,此時可以把初始化理解成沒有任何物體可放時,只有容量為0的背包能被價值為0的nothing“恰好裝滿”;當沒有這個限制時,初始化時應將_optp[0,1,……,m]都設為0,此時可以理解為任何一個背包都有一個合法的解“什么都不裝”,這個解的價值為0。

當優化后,空間復雜度變為O(m),計算所需時間為:

當weitht[i]較大時,可以節省很多時間。

動態規劃的缺點:對于01背包問題,用動態規劃方法解很容易理解,但是這種方法有一些弊端,從上述算法可以看出:當物體的重量較大時,所需的物理空間較大;當物體的重量不是整數時,無法利用數組來存儲該結構。

四、結束語

在日常生活中,01背包問題有很多應用,比如如何利用有限空間的手提包,裝入外出旅行的各種必需品。

第3篇：動態規劃范文

關鍵詞：動態規劃；裝載問題；JAVA語言

中圖分類號：TP31 文獻標識碼：A 文章編號：1009-3044（2014）10-2401-03

Abstract： How to load goods to get maximum economic benefits by manufacturers is a sub-problem divided from logistics distribution.In this paper，the sub-problem is abstracted a 0-1 knapsack problem.We create a mathematical model based on dynamic programming algorithm，and analyze the advantages of the algorithm.Then we use JAVA language to solve the problem.After setting some test datum， the final results show that the dynamic programming method has efficiency，and can be applied widely.

Key words： Dynamic programming； Loading problems； JAVA language

隨著經濟的不斷發展，各廠商在滿足客戶需求的條件下，利用物流技術，從備貨、裝箱、配送、存儲等物流配載技術網中尋求省時省力的方法，使得資源使用效率得到提高，同時降低了廠商的成本[1]。

問題提出：某廠商每周向校園超市運輸一次商品，在小型貨車容量不變且不能超載的約束下，如何裝載商品，使產生的經濟效益最大化？該問題是廠家所關心的，也是本文的關注點。運用動態規劃方法解決此問題，能夠較好地控制企業的人力資源成本和運輸成本，從而提高商業的競爭力。

1 動態規劃算法簡介

動態規劃（dynamic programming）[2]產生于20世紀50年代，由美國數學家R.E.Bellman等人提出。動態規劃的思想是把一個問題劃分為具有相關性的若干子問題來解決，并將各個子問題求解答案和求解方法進行保存。如果在之后的處理過程中還需要用到已解決的子問題，則直接調用答案，從而避免重復的計算，節省了時間。

在解決實際問題中，我們需要動態規劃出適當的約束條件和遞推關系，并在各單階段中尋找互相聯系的因素，依次將每一階段所得的最優結果進行存儲。這種階段劃分、自下向上的求解方式需要建立表或數組才能有效實施。如圖1所示：

基于動態規劃法解決的問題需要滿足一定的條件，例如：（1）滿足無后效性，即子問題的下一狀態只與現在狀態有關；（2）滿足最優性子結構，得出子問題的最優解；（3）原問題可以劃分出多個擁有關聯的子問題[3]。

2 模型的建立

廠商向校園超市運輸商品的問題：已知廠商共有N件商品，每件商品擁有固定的Id號，Id=i的商品重量為Wi，產生的經濟效益為Vi，貨車的最大載重量為N。現假設一個n維向量Xi=（X1，X2，...Xn）∈{0，1}n，當Xi=1時表明相應Id的商品裝入車中；當Xi=0時表明商品未裝入車中。最終得出的結果為[maxi=1nViXi]，即最大效益值，約束條件為[maxi=1nWiXi]≤N。貨車的載重量是有限的，在這個上限內盡可能裝下商品使經濟效益越高越好。通過以上分析，此問題恰好可以抽象為一個重量集合、經濟效益集合與貨車載重量分別是Wi={W1，W2，...Wn}，Vi={V1，V2，...Vn}和N的0-1KP問題。

在0-1背包問題中，物品價值與體積不隨背包容量的變化而變化[4]。舉例說明：假設有N=3個物品，總容量為10，體積V[i]={2，4，6}分別對應價值P[i]={3，7，4}，設數組B[i][j]，表示在背包容量為j的條件下，放入第i個物品后的最大價值。如下表1所示：

動態規劃算法易于編程的實現，雖然需要一定的空間存儲其產生的結果，但是它的高效性能在測試中體現出來。

4 測試數據

假設廠商貨車載重量為上述的1534，他們所建Commodity表中總共有50件商品，其Id、weight、value的數據分別如下所示：

最終得出經濟效益最大值為1904，如圖3所示。

5 結束語

本文從實際出發，給出廠商向校園超市運輸商品時的裝載問題，結合一個有效的算法――動態規劃算法，利用JAVA語言得以實現。動態規劃法有較好的效率和速度，不僅能用于解決裝箱問題，而且能夠運用于物流配載中的路徑規劃、資源分配等實際問題，優化了企業資源管理，提高經濟效益，降低資源成本，能夠應用于更多的科學領域中。

參考文獻：

[1] 謝天保，雷西玲，席文玲.物流配送中心配載車輛調度問題研究[J].計算機工程與應用，2010，36：237-240.

[2] 陳大偉，孫瑞志，向勇，史銀雪.基于流程模式的工作流靜態規劃方法[J].計算機工程與設計，2011（1）：129-132，137.

第4篇：動態規劃范文

關鍵詞：LINGO；動態規劃； 最短路問題； 生產批量計劃問題

中圖分類號：G642 文獻標識碼：A 文章編號：1009-3044（2014）04-0743-04

在交通專業課程如《交通運籌學》、《交通系統分析方法》等的教學過程中，大量涉及到可劃分為多階段的優化問題求解，這些問題的求解一般使用動態規劃（dynamic programming）方法。動態規劃將決策問題的全過程劃分為若干個相互聯系的子過程（每個子過程為一個階段），然后按照一定的次序來求解。當劃分的階段個數較多時，手工求解動態規劃問題相當麻煩。由于在實際的交通工程規劃實踐中，涉及到的動態規劃優化問題規模往往較大，指導學生掌握相應的優化軟件求解動態規劃問題一方面能增進學生對動態規劃法的理解掌握，另一方面能鍛煉學生的編程能力，是一項十分有意義的教學工作。

美國LINDO系統公司開發的LINGO由其求解問題的高效性和穩定性，成為目前廣泛使用的優化軟件。LINGO是一套專門用于求解最優化問題的軟件包，其內置了一種建立最優化模型的的語言，可以簡便表達出問題，同時利用LINGO高效的求解器可快速求解并分析結果。LINGO在處理含有大量變量和約束條件的優化問題時，一般使用數組和矩陣的輸入方法：LINGO程序首先定義集合段，確定需要的集合及其屬性，然后定義數據段，用于輸入已知原始數據，最后使用函數對集合進行操作。在通常介紹LINGO使用的文獻中[1][2]，一般著重于敘述其如何求解線性規劃和非線性規劃等具有明確目標函數的優化問題，很少關注如何用LINGO求解復雜的動態規劃問題，該文通過分析交通運輸中常見的最短路問題和生產批量計劃問題，給出用動態規劃方法求解的LINGO代碼，指出LINGO可以在不需要目標函數的情況同樣很好地求解多階段優化問題。

1 動態規劃法求解實例

實例1 最短路問題

在縱橫交錯的公路網中（圖1所示），貨車司機希望找到一條從一個城市到另一個城市的最短路。圖中節點1—8代表貨車可以停靠的城市，弧旁的數字表示兩個城市之間的距離（百公里）。若貨車要從城市1出發到達城市8，問如何選擇行駛路線使所經過的路程最短。

問題分析：該最短路問題滿足動態規劃的最優性原理，即“從節點1到節點8的最短路的子路徑仍然是相應節點間的最短路”，用[D（i，j）]表示從節點[i]和[j]有弧相連時相應的距離，[L（i）]表示從節點1到節點i的最短路程數。則不難得到以下的動態規劃由前向后遞推方程：

根據式（1），再進一步定義當節點[i]在從節點1到節點[j]的最短路徑上時，[P（i，j）=1]，否則[P（i，j）=0]，編寫如下LINGO求解代碼：

運行LINGO得到如圖1所示的最優解報告。

從報告中可以看到，最短路徑找到，由[L（8）]的值可以得出，從城市1到城市8的最短路程數為14，由各個[P（i，j）]的值分析可知，從城市1到城市8的最短路線為[1258]。

實例2（生產批量計劃問題）

某企業生產某種產品用以滿足市場需求。通過統計，該產品今后[T]4周的外部需求（訂貨量）分別是[d1]千件、[d2]千件、[d3]千件和[d4]千件。如果第[t]周要開工生產，則第[t]周開工所需的生產準備費為[st]千元（與生產的數量無關），每件產品的生產費為[ct]千元。如果在滿足需求后周末有產品剩余，每千件產品的存儲費為[ht]千元。設第[t]周末的庫存量為[It]，假設開始沒有庫存，記為[I0=0]且不考慮生產能力限制，問工廠應如何安排生產，在按時滿足需求的條件下，使總費用最小？

問題分析：對于生產批量計劃問題，分析可知有如下兩條性質成立：

由于以上兩個性質，只有當上一時段庫存[It-1=0]時，本時段才考慮進行生產，且一旦生產，其生產量一定為某些后續時段需求量的總和，即[xt∈{dt，dt+dt+1，…，dt+dt+1+…+dT}]。這樣如用[ft]表示當[t]時段初始庫存為0時，從[t]時段到[T]時段的子問題的最優費用值，可以建立如下的遞推關系：

運行LINGO得到如下最優解報告：

從報告可以看到，[F（1）=561]，即從第1周到第4周末的最優費用為561（千元），分析其它[F]值得到，最優的生產批量計劃為第1周生產2（千件），第2周生產5（千件），第3周不生產，第4周生產4（千件）。

2 結束語

本文針對用動態規劃方法手工求解多階段優化決策問題十分繁瑣的特點，利用LINGO軟件將各個動態規劃遞推方程簡潔明確地編程實現，幫助學生更好的理解了各階段決策變量之間相互遞進的關系，同時更重要的是交通專業學生熟練地掌握了軟件的使用，才能解決實際工程規劃中的大規模復雜優化問題，LINGO軟件的教學實踐促進了《交通運籌學》、《交通系統分析方法》與《交通規劃》等課程的融合。

參考文獻：

[1] 李曉川，朱曉敏，趙乃東. 基于Lingo的運輸優化系統設計與開發[J]. 物流技術，2010（Z1）.

第5篇：動態規劃范文

關鍵詞：最短路徑；動態規劃；C 語言編程

中圖分類號：TP311 文獻標識碼：A 文章編號：1009-3044（2013）09-2191-03

1 概述

數學源于生活，又服務于生活.它是一門研究現實世界中的數量關系與空間形式的學科.當今社會，隨著物質水平的不斷提高，生活需求的不斷擴大，自然資源的不斷開發利用.像天然氣管道鋪設問題，廠區布局問題，旅行費用最小問題等都已成為我們平時經濟生活中的普遍問題.它們其實都可以化歸為最短路線問題，而最短路問題實質上是一個組合優化問題[1]。

動態規劃方法主要是研究與解決多階段決策過程的最優化問題，它將求解分成多階段進行，不但求出了全過程的解，還能求出后部子過程的一組解，在求解一些生活實際問題時，更顯其優越性。為了快速、簡單的計算最短路徑，節約運輸時間與成本，該文利用動態規劃的思想編寫了C語言程序，解決物流運輸過程中多地點的最短路徑的選擇問題。

2 最短路徑問題

2.1 最短路徑問題算法的基本思想

在求解網絡圖上節點間最短路徑的方法中，目前國內外一致公認的較好算法有迪杰斯特拉（Dijkstra）及弗羅伊德（Floyd）算法。這兩種算法中，網絡被抽象為一個圖論中定義的有向或無向圖，并利用圖的節點鄰接矩陣記錄點間的關聯信息。在進行圖的遍歷以搜索最短路徑時，以該矩陣為基礎不斷進行目標值的最小性判別，直到獲得最后的優化路徑[2]。

Dijkstra算法是圖論中確定最短路的基本方法，也是其它算法的基礎。為了求出賦權圖中任意兩結點之間的最短路徑，通常采用兩種方法。一種方法是每次以一個結點為源點，重復執行Dijkstra算法n次。另一種方法是由Floyd于1962年提出的Floyd算法，其時間復雜度為[On3]，雖然與重復執行Dijkstra算法n次的時間復雜度相同，但其形式上略為簡單，且實際運算效果要好于前者。

2.2 最短路徑問題算法的基本步驟[3]

這樣經過有限次迭代則可以求出[v1]到[vn]的最短路線。

（2）Floyd算法的基本步驟

（3）動態規劃算法基本步驟

我們將具有明顯的階段劃分和狀態轉移方程的規劃稱為動態規劃[1]。在解決多個階段決策問題時采用動態規劃法是一個很有效的措施，同時易于實現。

根據動態規劃的基本概念，可以得到動態規劃的基本步驟：1）確定問題的決策對象。2）對決策過程劃分階段。3）對各階段確定狀態變量。4）根據狀態變量確定費用函數和目標函數。5）建立各階段狀態變量的轉移過程，確定狀態轉移方程。

根據動態規劃的基本模型，確定用動態規劃方法解題的基本思路，是將一個[n]階段決策問題轉化為一次求解[n]個具有遞推關系的單階段的決策問題，以此來簡化計算過程.其一般步驟如下：

用于衡量所選決策優劣的函數稱為指標函數.指標函數有有階段的指標函數和過程的指標函數之分.階段的指標函數是對應某一階段狀態和從該狀態出發的一個階段的某種效益度量，用[vkxk，uk]表示。在本文里用[dkxk，uk]來表示某一階段的決策的最短路徑。過程的指標函數是指從狀態[xn（k=1，2，...，n）]出發至過程最終，當采取某種子策略時，按預定的標準得到的效益值。這個值既與[xk]本身的狀態值有關，又與[xk]以后所選取的策略有關，它是兩者的函數值，記作[dk，nxk，uk，xk+1，uk+1，…xn，un]。過程的指標函數又是它所包含的各階段指標函數的函數。本文研究的過程的的指標函數是其各階段指標函數的和的形式.當[xk]的值確定后，指標函數的值就只同k階段起的子策略有關。對應于從狀態[xk]出發的最優子策略的效益值記作[fkxk]，于是在最短路問題中，有[fkxk=mindk，n]。動態規劃求解最短路徑程序流程圖如圖2所示。

3 最短路徑態規劃實際應用舉例

設某物流配送網絡圖由12個配送點組成，點1為配送中心起點，12為終點，試求自終點到圖中任何配送點的最短距離。圖中相鄰兩點的連線上標有兩點間的距離[4]。

首先用動態規劃法來討論圖3的最短路徑，由圖可知：

1）集合[ξ4]中有點9、10、11，它們在一步之內可到達點12；

2）集合[ξ3]中有點6，7，8，它們不超過兩步就可達到點12；

3）集合[ξ2]中包括點 2、3、4、5，不超過三步就可到達點12；

4）集合[ξ1]中包括點1，不超過四步可到達點12；

按照動態規劃法類推，得到最優路徑長為16，徑路通過點為1，2，7，10，12和1，3，6，10，12。

根據動態規劃算法編寫C語言計算程序[5] [6]，計算得到實驗結果如下圖4所示：

由圖4可以看出程序得到的結果與本文推出的結果一樣。證明了本文編寫的C語言程序是正確的。

4 結束語

綜上所述，用動態規劃解決多階段決策問題效率高，而且思路清晰簡便，同時易于實現.我們可以看到，動態規劃方法的應用很廣泛，已成功解決了許多實際問題，具有一定的實用性。此種算法我們用動態規劃思想來編程，并解決相應的問題，其在 VC 環境下實現，能方便快速的計算出到達目的地的最短距離及路徑，節省更多的運輸時間與成本。不過，該文只考慮了動態規劃算法在生活中的簡單運用，在實際生活中可能存在多個目的地或者更復雜的情況.因此我們可以考慮將其進行改進或者結合啟發式算法，使之更好的運用在實際生活中，這有待于以后的繼續研究。

參考文獻：

[1] 杜彥娟.利用動態規劃數學模型求解最短路徑[J].煤炭技術，2005（1）：94-95.

第6篇：動態規劃范文

論文關鍵詞：背包問題,動態規劃法,回溯法

 

10/1背包問題

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

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

2動態規劃法

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

動態規劃法適用于解最優化問題。通常可按以下4個步驟：

(1)找出最優解的性質并刻畫其結構特征。

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

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

(4)根據計算最優值時到得的信息，構造最優解。

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

，

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

（1.1）

（1.2）

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

3回溯法。

回溯法在包含問題的所有解的解空間樹中,按照深度優先的策略,從根結點出發搜索解空間樹。回溯算法搜索至解空間樹的任一結點時,總是先判斷該結點是否肯定不包含問題的解。如果肯定不包含,則跳過對以該結點為根的子樹的系統搜索,逐層向其祖先結點回溯。否則,進入該子樹,繼續按深度優先的策略進行搜索。回溯法在用來求問題的所有解時,要回溯到根,且根結點的所有子樹都已被搜索遍才結束。簡單地說就是確定解空間,建立解空間樹,用深度優先搜索算法遞歸搜索解空間樹,并同時注意剪枝。

用回溯法解題的步驟：

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

(2)確定易于搜索的解空間結構；

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

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

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

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

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

4總結

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

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

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

參考文獻

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

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

第7篇：動態規劃范文

關鍵詞：人才培養模式；工業工程；動態規劃

中圖分類號：G640 文獻標識碼：A 文章編號：1002-4107（2013）02-0058-02

一、動態規劃與人才培養

（一）動態規劃

動態規劃是運籌學的一個分支，是求解決策過程最優化的數學方法。在現實生活中，有一類活動的過程，由于它的特殊性，可將過程分成若干個互相聯系的階段，在它的每一階段都需要做出決策，從而使整個過程達到最好的活動效果。當然，各個階段決策的選取不是任意確定的，它依賴于當前面臨的狀態，又影響以后的發展，當各個階段決策確定后，就組成一個決策序列，因而也就確定了整個過程的一條活動路線。

這種把一個問題看作是一個前后關聯具有鏈狀結構的多階段過程就稱為多階段決策過程。在多階段決策過程中，動態規劃法的基本思路是從終點逐段向始點方向尋找最短路線，既把當前一段和未來各段分開，又把當前效益和未來效益結合起來考慮，從而得到整個問題的最優解[1]。

（二）動態規劃思想融入工業工程專業人才培養

動態規劃法的基本思想告訴我們，每段決策的選取是從全局來考慮的，與該段選擇的最優答案一般是不同的，這對專業人才培養有很大的啟發。如果把人的整個成長過程看成全局問題，在學校階段取得最好成績只是該段決策最優，能否在學生今后的就業及成長過程中發揮最大作用，實現成才的最終目標即達到全局最優，還取決于學生未來從事崗位和工作領域的選擇。這對工業工程人才培養格外重要。

現代工業工程是技術與管理相結合的交叉學科，它既有鮮明的工程屬性，也有明顯的管理特征[2]。由于這門學科技術與管理交叉的特點，使得工業工程專業人才的就業方向非常廣泛，既可以進行技術類的工程設計，也可以從事管理類的企業管理與決策，還可以繼續深造進行科研攻關，每個方向的工作崗位對人才素質的要求各不相同[3-5]。多元化的選擇使得學生畢業求職時看似什么崗位都適合，但事實上什么技能也不完全具備，只能臨時抱佛腳或者遭到社會的淘汰。因此，要想較好地完成個人成長及成才，依據動態規劃法的基本思想應從終點逐段向始點方向尋找最短路線，在進行人才培養時也應該進行逆序求解，首先幫助學生確立成才目標及個人定位，然后自后向前尋找，從而幫助每個學生對當前大學階段的努力方向和培養過程進行決策。

二、啟發式的人才培養模式

基于上述理念，南京工業大學工業工程專業結合自身辦學條件和課程設置提出了開放性、啟發式的人才培養新思路。在引導學生對未來職業定位和自身特點進行分析思考的基礎上明確就業目標，利用課堂教學和課余時間對學生進行專項能力培訓，最后集中進行學業成果展示，如圖1所示。

（一）啟發式的人才測評和職業傾向測試

首先，在入學時的專業介紹中讓學生明確工業工程目前的發展狀況以及未來發展趨勢，有意識地引導學生思考自身目標，進行自我認知。在大二階段設置的組織行為學課程實驗中，運用斯坦福―比納量表對學生進行智商測試，該量表不僅測試成人智商水平，而且顯示被測試者在語言、數學、空間、理解等方面的智商特點，幫助他們了解自己的智商水平與智力特點。運用卡特爾16相人格測試量表和明尼蘇達多相人格測試對學生進行人格特征測試，幫助他們了解自己的人格、能力特質。在智商、人格測試的基礎上，運用霍蘭德職業傾向測試，幫助學生了解自己的職業興趣以及適合從事的職業類型。對有創業愿望的大學生運用南加州大學創造力測驗，幫助學生了解自己是否適合創業，啟發學生對未來職業定位、自身特點和興趣進行思考。

圖1 工業工程人才培養模式

（二）針對不同類型職業傾向的學生進行專項能力培訓

在對學生進行人才測評和職業傾向測試的基礎上，在大三大四專業課學習階段針對不同類型職業傾向的學生進行專項能力培訓與強化，設立成長性、開放性的課程體系，使每個學生都可以自主選擇參與其中一種或幾種培養計劃。

1.對工程設計能力相對突出的學生，進行工業工程設計能力強化培訓。在學生已掌握的工業工程領域先進工程設計軟件的基礎上，進行企業實地調研，綜合運用Flexsim、Proplanner、AutoCAD、Matlab、動作分析軟件、流水線等軟硬件進行工程設計與改善，并在培訓結束后對設計作品和數據資料進行匯總刻盤，最終得到可以向用人單位展示的設計成果。

針對此類學生的培養，在大三大四每學期期末開設為期3周的課程設計進行強化培訓，開放性實驗也可為學生提供設計與實驗的平臺。此外，加強校企聯合，嘗試在畢業設計過程中組成團隊深入企業（如沙鋼集團）生產第一線進行團隊畢業設計。在進行實地調研兩個月的基礎上，每個學生針對企業實際存在的問題進行分析解決，最后形成畢業設計。這樣較長時間的讓學生深入企業進行課題研究，讓學生能夠持續性地、效果可檢驗地深入企業第一線進行畢業設計，并聯合各個教師的研究特長對學生進行全程指導，能夠切實提高學生的工程設計能力，加強團隊合作精神，打造適應市場需求的高素質人才，最終的團隊設計成果以總報告的方式提交給企業，深受企業贊許，多名團隊成員畢業后直接進入該企業工作。

2.對管理能力相對突出的學生，進行管理實踐能力強化培訓。每年全國都會召開工業工程應用案例大賽及現代物流技能大賽，利用此契機讓每個學生都參與其中，綜合課程所學的相關知識，對大賽中提出的案例進行分析解決，讓每個學生都撰寫相應的案例解決報告。這樣每個同學都有可以參與全國大賽的機會，報告也可以作為學生就業時的獨特成果向用人單位展示。

對自主創業意識和能力相對突出的學生，進行創業實戰能力培訓。通過參加學院每年舉辦的企業生產運營BOSS大獎賽和商道管理決策競賽，組織參與聽取學校創業講座，增強其創業意識和決策能力，并結合市場情況指導其撰寫詳細的創業計劃書。

在該模式的引導下，南京工業大學在校生多次獲得全國商科院校技能大賽、大學生管理決策模擬大賽、IE亮劍等國內競賽獎項，畢業生中也有多個創業團隊出現。

3.對科研能力突出的同學，在課程中引入研究型教學[6]。教師以課程內容和學生的學識積累為基礎，引導學生創造性地運用知識和能力，自主地觀察問題、提出問題、分析問題和解決問題，在研討中積累知識、培養能力和鍛煉思維。

目前，我們選取“質量管理與可靠性”課程進行研究型教學試點，教師提出問題，引起學生思考，并牽頭成立該課題的研究小組，引導他們在課后開展科研活動。目前課題組已經產生了豐碩的研究成果，以這些科研成果為基礎，教師與本科生合作在《工業工程與管理》等核心期刊上發表了學術論文4篇。

三、開放性的學業成果全過程立體化展示

在以上培訓的基礎上，每個學生都具備了可以向用人單位展示的各種成果。我們建設開放性的“工業工程學生學業成果展示”網站，將每個學生本科四年期間的各種學業成果進行集中展示，包括工程設計作品、創新創業作品、案例設計成果、各類競賽成績等，以學生個人為標簽，為全系學生建立個人網頁，全過程、立體化地反映學生本科四年的學習成果。

成果主要將以各種可視化的方式進行有效展示，包括：個性化自我介紹（視頻）、發表的論文成果、各種獎勵證書、工業工程三大實習（認識實習、金工實習與生產實習）的現場多媒體展示、專業主干課程實驗及課程設計作品、參與競賽獲獎、創新設計作品等，可以讓學生親自參與到網頁內容編輯及頁面設計中，充分利用各種多媒體工具和網絡平臺，將每個學生的比較優勢展現出來。這種方式不僅能夠提高學生的學習積極性、實踐能力、創新能力，而且能夠使企業快速、全面、立體地了解本專業每一個學生的獨特能力，而不是僅靠一紙簡歷來平面地了解學生的情況。這種信息溝通方式既能有效促進本專業學生的就業，又加強了學校與用人單位的聯系，雙方可充分利用網絡這個平臺進行實時的動態交互。不僅企業通過這個平臺了解到學生的能力，我們也可以通過這個平臺隨時了解用人單位的需求，進而調整改進教學活動和實踐安排。

實踐表明，自該方法實行以來，學校培養了一批特點突出、素質高的優秀畢業生，獲得了學生及用人單位的一致好評。可以說，啟發式、開放性、因材施教的培養方式無論在提高人才培養質量方面，還是在高等教育教學理論應用和人才培養方法方面都取得了一定成果，邁開了教學改革堅實的一步。

參考文獻：

[1]吳祈宗.運籌學：第2版[M].北京：機械工業出版社，

2006.

[2]馬如宏.工業工程專業課程設置探討[J].教育與職業，

2006，（35）.

[3]郭絢霞.提高我國高校大學生就業力的途徑[J].改革與

開放，2009，（7）.

[4]張忠，楊蕾.基于當前就業形勢的工業工程專業教學改

革探析[J].裝備制造技術，2009，（3）.

[5]楊振剛，陳建國.基于港式思路的IE專業人才培養新模

式[J].工業工程，2010，（6）.

第8篇：動態規劃范文

關鍵詞：可重構制造系統；柔性測度；動態規劃；柔性值

一、引言

可重構制造系統（Reconfigurable Manufacturing System，RMS）是一種能夠根據產品功能和生產能力的需求及市場需求變化做出快速響應，以應對不可預測的全球性市場激烈競爭的制造系統。在當今全球經濟一體化的時代背景下，制造企業面臨著提高產品質量、降低產品成本及對市場需求做出快速響應的多重壓力。在這一嚴峻形勢下，提升制造系統的柔性對企業提高競爭優勢有著非常重要的意義。RMS是一種可重新構形的現代制造系統，它不僅具有剛性制造系統較高的生產制造效率，還具有柔性制造系統自動化程度高的優勢，從而它是滿足大批定制要求的最佳制造系統。制造企業在構建可重構制造系統時，需要綜合考慮柔性與成本兩個因素，合理地確定RMS柔性的大小才能使企業獲得最大化的利益。因此，準確地測度RMS的柔性具有重要的實踐意義。

針對生產制造系統的柔性研究，早期學者的研究側重于針對柔性制造系統的柔性進行評價。楊思遠、劉細兵在討論柔性制造系統柔性衡量標準的基礎上建立了柔性的凈現值指標評價模型；李巖、張曉坤和徐躍飛等在針對影響柔性制造系統的柔性因素進行深入分析的基礎上提出了用模糊評價方法對制造系統柔性進行評價。隨后，學者們逐漸將柔性作為制造系統的一個特征，研究柔性的概念并針對影響制造系統柔性的各種因素進行分析，并且給出了具體的柔性評價的方法。近年來，梁福軍、寧汝新及姜曉鵬、王潤孝、庫祥臣分別對RMS的柔性進行了定義并系統闡述了柔性的分類，但是都沒有針對RMS柔性的測度方面進行研究。

在已有的制造系統柔性測度研究中，學者們從不同的角度對制造系統柔性的測度進行了研究。Mandalbaum用制造系統的柔性在環境變化發生時造成的損失或者帶來的收益來對柔性進行測度；Gustavsson認為制造系統的柔性可以用制造系統的投資剩余值與投資原值之比來表示；Kumar則根據生產制造系統處理不確定性環境的能力以反映該系統的柔性，建立了基于信息理論的柔性測度方法；Slack認為制造系統的柔性應該在由狀態范圍維度、狀態轉移費用維度和狀態轉移時間維度構成的三維空間中進行度量；Barad認為制造系統運行柔性可以用系統適應變化所需的時間來度量并采用時間Petri網描述柔性。以上為學者從四個不同的角度對柔性的主要特征進行了描述并提出了相應的柔性測度方法。

綜上所述，目前對于制造系統柔性的測度主要是基于經濟效果、信息論、Petri網和多維度的柔性度量方法，但這些柔性度量方法存在著不同程度的缺陷。雖然目前制造系統柔性度量研究存在一定程度的缺陷，但是針對制造系統“柔性”這一特征的研究已經十分豐富。但是，目前針對可重構制造系統柔性的研究還很貧乏，還僅限于柔性的概念和分類。針對現有研究的不足，本文選用隨機動態規劃的方法，針對制造系統的一個生產制造周期構造了RMS中柔性的隨機動態規劃定量評價模型，通過求解模型得到最優收益值，本文用RMS和剛性制造系統最優收益值之差來定義柔性，既可避免由于運行環境、制造系統自身等因素的變化對制造系統柔性測度的準確性的影響，又可以直觀地反映出可重構制造系統對顧客需求發生變化的響應程度。

二、RMS的柔性及測度原理

（一）RMS的柔性

RMS的柔性是指RMS整體通過系統本身的構件之間的重新構形從而實現的對加工任務或加工工作的適應性。RMS由七個柔性因素構成，即設備柔性、產品柔性、工藝柔性、工序柔性、運行柔性、批量柔性和重構柔性。RMS具有柔性決定了其在生產制造過程中的優勢：RMS具有剛性制造系統和柔性制造系統的特性，其生產能力和生產功能介于剛性制造系統和柔性制造系統之間；RMS是基于多個工件族來進行設計的，對工件族中的所有工件提供定制柔性；另外，其構形能夠根據產品生產的變化而進行調整，在一定程度上適應了以多品種、中小批量、短的產品生命周期等為特征的以顧客需求為導向的生產模式。因此，可重構制造系統的柔性對企業適應快速變化的市場需求具有重要的意義。

（二）RMS柔性測度原理

本文設定了一個生產制造周期，即從上一種產品生產制造完成時刻開始到因顧客需求改變而轉入下一種能夠滿足顧客需求的產品的生產制造完成時刻為止。針對這一生產制造周期建立隨機動態規劃模型，求解出該條件下的最優收益值，即可重構制造在面臨需求改變的情況下對自身進行調整以適應這種變化這一過程中的獲得的最優收益。由于剛性制造系統不具有柔性，在相同的假設條件下求得的剛性制造系統的最優收益值即制造系統不具備柔性值時的最優收益。RMS的最優收益值和剛性制造系統的最優收益值之差為可重構制造系統僅考慮柔性作用下制造系統的最優收益即可表示RMS的柔性值。

三、RMS柔性測度模型

RMS因其內在的柔性使得企業能夠更好地適應外界環境的變化，對各種不確定性因素做出相應的反應，從而增強企業自身的市場競爭力。與此同時，可重構制造系統要素隨時間變化的特征使得系統的定量評價更加困難，因此必須建立能夠反映其內涵的動態隨機模型。由于影響系統的不確定性因素很多，本文主要討論由于顧客需求發生變化對RMS造成的不確定性，而這里所指的顧客需求變化指的是顧客對產品組合、需求數量及對新產品的需求等。

（一）可重構制造系統柔性定量評價的假設條件

1.假設該機械制造企業一個生產周期為上一批工件加工完畢的時刻開始至下一批工件加工完畢的時刻為止，且生產制造的兩種產品種類不同。

2.假設制造系統在第一種產品生產完成至第二種產品開始生產之前自身已完成調整可以進行轉產，因為本文主要研究可重構制造系統對顧客需求變化的響應程度。

3.制造系統在整個生產周期內不受到除顧客需求發生變化之外的其他外界因素影響。

（二）評價RMS柔性的隨機動態規劃模型

1.確定階段

在此階段企業將要進行個階段的生產加工。

2.狀態變量和決策變量的設定

在t階段末，第t階段的生產制造過程結束并開始第t+1階段的生產制造。若在第t階段末，已知顧客需求第i種產品的產量為di（t），即Ni（t）=di（t）；假設生產制造完第j種產品的產量為xj（t），則有：狀態變量St=（xi（t），di（t）），可達到的狀態集合St={xj（t），dt（t）}，其中i，j=1，2，...，n，xj（t）=1，2，...，Mj，di（t）=1，2，...，Dj。

第t階段末需要對第t+1階段的生產進行決策，允許集合為：Dt（St）={xi（t+1）}，其中，i=1，2，...，n，xi=1，2，...，D。

若決策變量Ut（St）=xi（t+1），則有所做的決策為：第t+1階段生產制造第種產品的產量為xi（t+1）。其中，Mi為每個階段各種工件的產量上限數，Mi取整數；Di為每個階段對各種產品的需求上限，Di取整數，且Di≤Mi；xi（t）為第i種工件的產量；dj（t）為顧客對第j種產品的需求產量；Nj（t）為第t階段末顧客對第i種產品的需求量，Nj（t）=1，2，...，Di；di（t）∈[1，Di]，di（t）取整數，i=1，2，...，n。

（三）決策過程

由于上文中構建的模型假定初始狀態已給定，因此選用逆序解法求得結果：F（0，xi（0），dj（0））={EF（1，xi（1），dj（1））}。此時，F值為該可重構制造系統在整個加工階段的最優收益值。

通過利用上文構建的隨機動態規劃模型并對其求解，可以得到RMS在需求等外界條件處于經常性變動的情況下整個加工階段的最優收益值F。同時，也可以計算出該制造系統的剛性最優收益值F，即假設顧客需求等外界條件不變的情況下制造系統生產制造同一種產品的最優收益值Vf。最后，計算兩者之差即可定義為RMS的柔性值，即

Vf=F-F′

以Vf，即可重構制造系統與剛性制造系統最優收益值之差來定義可重構制造系統的柔性值更具有準確性和客觀性

四、結論

本文在可重構制造系統柔性的相關理論研究的基礎上，通過隨機動態規劃的方法建立模型并通過模型求解分別得到可重構制造系統與剛性制造系統的最優收益值，最后可重構制造系與剛性制造系統的最優收益值之差即可重構制造系統的柔性值。

本文尚存在如下不足：一是只考慮顧客需求發生變化時RMS對這一外界變化的反應能力，而沒有考慮其他外界因素發生變化對RMS柔性的影響；二是建立模型時假設了一個理想狀態即設備處于無故障狀態、原材料供應充足等條件完全具備，但在實際生產制造過程中這種理想狀態并不總是存在。因此，今后需要針對以上不足之處進行系統和深入研究。

參考文獻：

[1]楊思遠，劉細兵.柔性制造系統的經濟評價[J].上海交通大學學報，1994（02）.

[2]李言，張曉坤，徐躍飛等.FMS柔性的評價[J].機械科學與技術，1994（02）.

[3]梁福軍，寧汝新.可重構制造系統系統理論研究[J].機械工程學報，2003（39）.

[4]姜曉鵬，王潤孝，庫祥臣.可重構制造系統研究進展[J].機床與液壓，2007（35）.

[5]Mandalbaum M. Flexibility in Decision Making： an Exploration and Unification[D].Univ. of Toronto，1978.

[6]Kumar Vinod. Entropic measures of manufacturing flexibility [J].International Journal of Production Research，1987（07）.

[7]Slack N. The Flexibility of Manufacturing Systems. Int. J. of Oper.&Prod.mauagement，1978（04）.

第9篇：動態規劃范文

關鍵詞： 動態三角網格； AD*算法； 路徑規劃； 模擬仿真

中圖分類號： TN911.1?34； TM417 文獻標識碼： A 文章編號： 1004?373X（2017）11?0103?04

Research on path planning based on dynamic triangular mesh

and heuristic search algorithm

WANG Wenxia

（Department of Computer Science and Technology， Yuncheng University， Yuncheng 044000， China）

Abstract： The dynamic triangular network map algorithm was designed and implemented on the basis of static triangular mesh to change the grid node cost value in the obstacle changing process of the triangular mesh map. The related algorithm was designed to acquire the updata information of the generated grid map in real time to realize the dynamic change effect. The search algorithm Anytime Replanning A*（ARA*） and D* Lite are combined to realize the path planning method A*（AD*） in dynamic environmet. The extended information in grid map is saved， and the expansion factor is reduced constantly in the finite time to find the node with minimum cost value in the grid map， and obtain the optimul path of dynamic planning. The dynamic scene graph is simulated in dynamic environment. The dynamic planning method is used to establish the corresponding data search structure and method to analyze and contrast the simulation results.

Keywords： dynamic triangular mesh； AD* algorithm； path planning； analog simulation

隨著社會經濟的發展，找到合適、優化而且適用于各種額外條件如動態環境、大規模人群、任意寬度路徑等一系列需求成為路徑規劃算法的研究方向[1]。本文研究在動態地圖網格中通過動態搜索算法，實時更新地圖信息的同時采用更加高效的搜索算法記錄當前群體信息并反饋出動態環境中的環境變化情況，如人群規模、路徑寬度等相關信息，以便在較短時間內避免碰撞和到達目的地。

1 動態環境地圖網格構建及生成

1.1 動態三角網格設計實現

在構建動態網格（Dynamic Local Clearance Triangulation，DLCT）[2]的過程中需要保持原有的LCT三角網格[3]中對路徑寬度的要求，在動態化的過程中添加和刪除障礙物時通過多邊形障礙物ID進行操作，在添加算法中把所有障礙物的限制條件遍歷直至找到需要添加障礙物的ID；在之后的刪除算法中會把與找到的障礙物ID相關的限制條件同時刪除。由于在地圖中障礙物之間可以相互覆蓋，因此每個ID可能關聯相互覆蓋的限制條件。

1.1.1 障礙物插入模塊

該模塊在原有LCT（S）的存儲單元中插入新的多邊形障礙物，在插入過程中，給障礙物設置新的ID。S設置為現在LCT（S）已存在的限制規劃，O是將插入的新多邊形障礙物。插入過程如下：

（1） 將多邊形障礙物O中的k條線段插入CDT中，對于需要修改的頂點和限制邊界分別存儲在兩個List中。List V中存儲所有已修改邊的鄰接頂點（其中包括因CDT交換的邊）；List C中存υ誆迦胝習物過程中受限制的邊界。

（2） 對于List C中的限制邊界，通過搜索算法判斷S是否被阻塞。對于每個被阻塞的遍歷找到后，相關聯頂點加入List V。如圖1所示，通過搜索加入頂點兩邊可能因S引起阻隔。對每次遍歷來說，相關聯的阻隔頂點v被加入到List V中。

圖1 尋找被阻斷過程

（3） 在遍歷過程所有被List V中頂點影響的頂點將重新測試其屬性，判斷在當前情況是否需要被限制， Local_Ref函數定義和遍歷了在變化過程中與V相鄰的頂點。對于每一個所有與相鄰的三角形都要被訪問。設為當前與臨近被訪問的三角形，此時需要調用函數檢測是否有遍歷過的節點需要重新定義；函數查看的后繼節點是否被影響，當找到被影響的路徑時，頂點和若不在List V中則系統自動進行添加，然后重新測試所有在V中的頂點。

1.1.2 障礙物刪除模塊

該模塊將把現有地圖中的多邊形障礙物移除，移除過程中通過在插入中設置的ID找到該障礙物。由于障礙物之間可以發生覆蓋，故對于每一個障礙物來說可能同時具有多個ID。刪除過程如下：

（1） 將已存儲的障礙物O從CDT中刪除，并把所有已修改與邊相關的頂c信息存儲在List V1中；

（2） 將與List V1被限制頂點的周圍臨近頂點找到后存入List V2；

（3） 把List V1中相關的頂點信息從CDT中刪除；

（4） 對于所有在執行過程中需要限制的頂點，通過調用Local_Ref函數再次遍歷與其臨近的頂點信息，并對發生變化的進行改變。

1.1.3 動態三角網格構建過程

基于動態三角網格地圖的動態環境構建步驟如下：

（1） 獲取三角網格發生變化后的地圖信息。

（2） 獲取地圖中障礙物變化信息。

（3） 地圖網格中障礙物節點信息發生改變時，若有新節點加入，則添加后更新相鄰節點；若有節點刪除，則刪除后更新相鄰節點信息。

（4） 反復執行步驟（3），直至所有的更新信息都處理完畢。

（5） 更新地圖中三角網格節點信息。

1.2 動態地圖構建實現

動態三角網格地圖構建過程如圖2所示，其中第一幅圖展示了在原始地圖中通過添加障礙物實現了地圖中存在若干個障礙物的情況，然后通過改變地圖網格中障礙物的個數、重新劃分三角網格以及移動障礙物和刪除算法等方法，實現了仿真過程中對真實地圖情況的模擬和地圖網格的構建過程。

圖2 動態地圖實現效果

2 啟發式搜索動態路徑規劃方法

2.1 啟發式動態路徑規劃方法（AD*）

Anytime Dynamic A*（AD*）算法是在原有的動態環境下將D* Lite和ARA*結合，解決了在動態環境下高效率的路徑規劃問題[4]。在AD*算法中利用ARA*中膨脹因子不斷遞減的過程進行一系列路徑搜索。當三角網格地圖環境發生改變并影響到邊的代價值時，在D*算法的OPEN表中對應節點的Key值發生相應改變。AD*算法具體執行過程如下：

（1） 程序初始化。將OPEN，CLOSED和INCONS表清空，膨脹因子初始值為

（2） 計算最短路徑。計算最短路徑的過程中節點的擴展順序為從目標點goal到起始點start進行擴展，尋找出從源點到目標點的最短路徑。

（3） 個體從start開始沿路徑向goal前進。

（4） 在擴展過程中，將已擴展過的節點存儲在INCONS表中。

（5） 判斷前進過程中網格代價值是否發生變化，如果發生變化，則以當前節點為新的起始點，并減小膨脹因子的值。

（6） 在下一次擴展過程中，用作為啟發函數，在擴展OPEN表中剩余的點之前，把上一輪INCONS表中的點插入OPEN表中，在原來OPEN表的基礎上修改所有與變化節點相關的rhs，key的值，清空CLOSE表。

（7） 以新的start點為起始點，goal為目標點，運行步驟（3）直至到達目標點。

2.2 地圖網格密度計算

基于三角網格密度的改進方法[5]，模擬人群仿真的過程在不同時間內每個三角網格參數值因agents數量的不同而發生變化，因此把密度信息添加到Key值的計算中，可以估算每一個OPEN表中節點的優先權從而得到最優路徑。density（n）表示第個節點所在三角網格的密度值；是通過節點和距離信息來估算到目標點的路徑長度[6]。此時OPEN中擴展節點的優先權的計算公式如下：

（1）

式中：膨脹因子要滿足條件

將agents標記在不同三角形網格中，通過計算當前三角網格的密度信息決定不同節點在OPEN表中的優先權，此時Key的值計算公式（2）如下所示：

（2）

通過不斷減小在搜索路徑過程中膨脹因子的值找到最優路徑。

3 動態路徑規劃算法設計與實現

3.1 搜索節點數據結構

在動態環境中，以DLCT三角網格[7]作為地圖的劃分方法，將地圖網格中的動態變化信息和移動個體動態搜索路徑方法相關聯，構造如下數據結構，在Map_Node中存儲動態網格中障礙物發生變化后節點的構建網格信息；Agent_Node中記錄移動個體在尋路過程所擴展的三角網格邊。規劃路徑時根據當前Open_Node節點中存放的信息計算最優路徑。

3.2 動態搜索算法實現

在動態搜索算法中，當動態環境發生變化時更新三角網格地圖信息，通過在OPEN表中擴展邊，更新變化的頂點信息與其鄰接節點，判斷當前移動個體路徑是否受到影響，未受影響的個體按原路徑移動；由于網格變化需要重新尋路時，計算節點代價值如下所示：

（3）

通過計算新添加節點（添加障礙物）或位置變更節點（移動障礙物）的代價值得到當前三角網格地圖的節點序列，在OPEN中節點進行擴展時根據代價值的排序重新規劃路徑，通過執行RecomputeShortestPath（）得到從當前位置為起始點到目標點的路徑規劃方法[8]。例如，個體Agent移動到節點所連接的邊edge時，移動障礙物模塊至三角網格edge邊移動方向的前方，此時動態規劃域與個體移動域有交集，在此區域里由于頂點變化三角網格地圖重新劃分，若劃分后節點不存在，通過不斷執行Pred（s）找到前驅節點至此節點在更新后的網格地圖中存在，同理，后繼節點通過執行Succ（s）不斷向后查找直至找到的后繼節點與新生成的網格地圖中匹配的節點（未找到則重新規劃此區域的路徑），在前驅節點和后繼節點之間的區域D中根據式（3）計算得到網格地圖變化后Agent個體從當前位置到目標點移動的規劃路徑。

4 基于動態環境的動態規劃仿真與實現

4.1 地圖規模變化策略

為了驗證動態搜索算法在不同規模三角網格地圖上的適用性和模擬仿真場景中復雜逼真程度，同時證明DLCT網格劃分方法對不同地圖的劃分結果的差異。本實驗應用動態搜索算法AD*實現在不同規模地圖上個體規劃路徑過程。如圖3所示，圖中地圖網格的復雜程度由簡到繁分別采用5×5，10×10，20×20，40×40的網格拓撲結構，通過不斷增大迷宮場景圖的復雜程度，在地圖中選擇起始點和目標點后通過啟發式動態路徑搜索算法，AD*在不斷變化的三角網格中進行路徑規劃，最終找到當前狀態下的最優路徑。

通過采用不同規模地圖對單一移動個體規劃路徑，不同的搜索算法尋路過程與地圖的復雜程度正相關，隨著地圖復雜程度的增加，搜索路徑的過程在地圖網格中與擴展的三角邊總數呈正相關的趨勢增長。因此，在復雜多變的環境中模擬真實場景時，采用高效的地圖網格剖分方法能夠使路徑規劃效率得到提高。

4.2 群w移動策略

4.2.1 碰撞檢測方法

采用的規避方法是隨機處理方式和球體處理方法相結合，在Agents碰撞發生后進行處理，設置兩個移動個體之間距離的最小值，若小于最小值時則認為碰撞發生。在碰撞發生后，若個體所在三角網格密度信息較大，則重新規劃路徑進行移動直至目標點；若個體所在三角網格在密度范圍內則個體延時等待一段時間后，通過避讓的方法繞過障礙物繼續前行到達目標點。

4.2.2 個體規避策略方法實現

在動態三角網格地圖環境中，當障礙物發生移動時，移動個體會根據當前規劃路徑是否受到影響決定移動策略，根據對方向進行判斷，若在移動過程中碰撞發生，記錄當前位置信息CurPosition，判斷當前三角網格密度值density，在密度滿足閾值條件時應用規避方法重新規劃路徑繼續移動；其他情況下，需改變移動方向，密度滿足要求時進行重新規劃。

模擬仿真過程截圖如圖4～圖7所示，在圖4和圖5中，障礙物的移動沒有對個體移動的路徑產生影響，仍按照原規劃路徑前行；在圖6中，當動態地圖網格中障礙物變化導致網格布局發生改變，從而對個體原路徑產生影響時，個體重新規劃路徑；在圖7中，當地圖網格發生動態改變時，若同時存在的若干移動個體發生碰撞，此時應用個體移動的規避策略對路徑進行重新規劃。

4.3 群體動態路徑規劃方法

4.3.1 群體動態路徑方法

群體路徑規劃方法是在單獨個體基礎上對每個移動物體進行路徑規劃的過程。為了模擬大規模人群仿真技術提出群行為模擬方法，移動個體對不同的Agent的影響有很大差異，主要問題有如下幾個方面：

（1） 如在此移動個體之前有另一個體相向而行，則其中一個物體應該改變速度方向避免碰撞發生。

（2） 若兩個移動個體同向時，其中較慢的個體應在人群密度較小的情況下改變速度方向超過前方遮擋個體；而在人群密度較大時，跟在前方物體之后行走。

綜合以上問題描述，本文通過碰撞類型分類對優先級進行劃分。按照優先級原則對仿真環境中的Agents個體進行優先級排序（模擬真實場景中的出場順序或根據重要程度排序等），根據優先級遞減劃分成不同的組別，對于中的每個Agent個體，保存其start，goal，position，DesSpeed，velDir變量信息。

在規劃群體路徑過程中，根據Agents的優先級大小對速度方向進行修改，若在中Agents和中的移動個體移動方向相同則需要在判斷優先級的條件下重新規劃其余組別的路徑方向。在采用以上方法避免碰撞發生的條件下，若碰撞發生，記錄當前碰撞發生時移動個體的位置信息position，計算當前三角網格的密度density和相鄰節點構造網格密度值，根據Agents的優先級以及已得到的密度信息進行重新排序，若此時的移動個體滿足優先級條件，則重新計算地圖網格的代價值并重新規劃由當前位置position到目標點的路徑；若此時碰撞個體優先級較低，則處于等待狀態至下一次重新規劃。

4.3.2 群體規劃路徑實現

為了驗證本文的群體動態路徑規劃方法，對在地圖網格中可能發生碰撞的Agents個體采用碰撞規避策略對每個Agents個體進行路徑規劃，在仿真的過程中不斷增加Agents規模，分別對Agents=50，Agents=100，Agents=150，Agents=200在不同時刻的尋路情況仿真模擬，實現結果截圖如圖8所示，圖中不同顏色的小方格分別代表不同的Agents移動個體，每個移動個體從初始點出發到目標點規劃出各自的路徑，當有Agents個體之間發生相互碰撞時（此時原規劃路徑移動方向被阻擋），則Agent個體根據本文中采用的碰撞規避原則，采用AD*算法繞過對方后重新規劃路徑。

圖8 群體規劃路徑實現

由仿真效果可知，隨著網格地圖中Agents個體數的不斷增加，發生碰撞的幾率明顯增大，因此在動態環境中，在采用高效的動態路徑搜索算法的同時，需要針對群體中發生碰撞的規避策略來避免碰撞發生。

4.4 仿真實驗結果分析

通過對動態環境中的動態網格效果、動態路徑規劃算法進行驗證，將二者結合實現本文關于動態環境中的路徑規劃方法的研究。在動態網格地圖中分別移動和增添障礙物后，實現了地圖網格發生變化情況的模擬。在動態搜索算法中，通過將D*Lite和ARA*算法結合實現了動態路徑規劃方法的優化AD*算法，通過將二者結合，定義新的數據結構存儲移動個體移動過程中的變量值，對群體路徑規劃和碰撞規避策略的應用計算達到了動態環境路徑規劃的模擬仿真效果。

5 結 論

本文的主要研究內容包括基于動態環境的網格地圖方法和動態路徑規劃方法的研究，在此基礎上實現動態環境中的路徑規劃。在動態路徑規劃的過程中需要對網格構建和搜索算法進行研究，對地圖網格劃分方法在LCT靜態三角網格的基礎上，通過障礙物的移動、添加和刪除實現了動態網格規劃方法（DLCT）；在路徑搜索算法方面，將基于A*算法實現的ARA*算法和動態搜索算法D*Lite相結合，實現了在動態環境中的路徑規劃算法AD*。

參考文獻

[1] 孫俊，戴國駿，張懷相.裁剪優化的Anytime算法[J].杭州電子科技大學學報，2010，30（2）：41?44.

[2] 張勝.一種基于狀態空間的啟發式搜索算法及其實現[J].現代電子技術，2008，31（16）：79?80.

[3] 孫蘭會，成鋒，陸愈實.基于GIS的路徑規劃算法研究與實現[J].現代電子技術，2016，39（5）：101?104.

[4] 思磊.距離網格地圖動態更新及基于距離網格地圖路徑規劃的研究[D].西安：西安電子科技大學，2013.

[5] 朱大奇，顏明重.移動機器人路徑規劃技術綜述[J].控制與決策，2010，25（7）：961?967.

[6] 席裕庚，張純剛.一類動態不確定環境下機器人的滾動路徑規劃[J].自動化學報，2002，28（2）：161?175.