動(dòng)態(tài)規(guī)劃精選(九篇)

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

第1篇：動(dòng)態(tài)規(guī)劃范文

關(guān)鍵詞：動(dòng)態(tài)規(guī)劃；模板匹配；特征距離矩陣

DOIDOI：10.11907/rjdk.171142

中圖分類號(hào)：TP312

文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1672-7800（2017）06-0037-03

0 引言

在計(jì)算機(jī)領(lǐng)域，常需要將實(shí)驗(yàn)數(shù)據(jù)與預(yù)先設(shè)定好的模板進(jìn)行匹配。圖像處理領(lǐng)域中的圖像檢索、圖像分割、圖像拼接、圖像檢測(cè)、視頻編碼等，就需要運(yùn)用到模板匹配技術(shù)。模板匹配技術(shù)在圖像處理領(lǐng)域的具體應(yīng)用可以簡(jiǎn)單分為兩大類：基于特征點(diǎn)的匹配技術(shù)、基于像素灰度的匹配?；谔卣鼽c(diǎn)的匹配往往被更高級(jí)的機(jī)器視覺(jué)類任務(wù)采用，而在圖像處理中，基于特征的匹配方法由于抽取的點(diǎn)、線、特征子等特征容易受到視角變換、遮擋等問(wèn)題的干擾，會(huì)影響到最終匹配結(jié)果的質(zhì)量，同時(shí)特征抽取方法的時(shí)間復(fù)雜度較高，對(duì)于實(shí)時(shí)性是一個(gè)挑戰(zhàn)?；谙袼鼗叶鹊哪０迤ヅ浞椒?，只需要設(shè)定好匹配的模板尺寸與遍歷方式，算法簡(jiǎn)潔、穩(wěn)定性高，適合圖像處理與計(jì)算機(jī)視覺(jué)問(wèn)題中的底層預(yù)處理。但其也存在一些缺點(diǎn)，如噪聲、光照引起的灰度變化，且運(yùn)算數(shù)據(jù)量大，基于像素灰度的匹配算法也無(wú)法避免圖像數(shù)據(jù)與模板匹配過(guò)程可能帶來(lái)的高復(fù)雜度問(wèn)題。

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

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

綜上，鑒于動(dòng)態(tài)規(guī)劃方法的自身特性及當(dāng)前圖像處理在解決模板匹配問(wèn)題上的不足，本文提出了一種采用動(dòng)態(tài)規(guī)劃解決模板匹配的方法，首先給出圖像數(shù)據(jù)與模板的匹配問(wèn)題，并對(duì)該問(wèn)題進(jìn)行符號(hào)化和相應(yīng)的理論分析，此后采用動(dòng)態(tài)規(guī)劃的方法解決模板匹配問(wèn)題，并對(duì)傳統(tǒng)動(dòng)態(tài)規(guī)劃解決方法在時(shí)間復(fù)雜度上進(jìn)行改進(jìn)。相較于傳統(tǒng)模板匹配方法，采用本文提出的方法可以將時(shí)間復(fù)雜度減少一個(gè)數(shù)量級(jí)。

1 問(wèn)題分析與解決

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

1.1 問(wèn)題符號(hào)化及分析

為了方便地表達(dá)該問(wèn)題，采用3個(gè)矩陣進(jìn)行存儲(chǔ)和計(jì)算，如圖1所示。一個(gè)是矩陣A，用來(lái)存放原始數(shù)據(jù)；一個(gè)是矩陣B，用來(lái)存放計(jì)算過(guò)程的局部最優(yōu)值；一個(gè)是矩陣R，用來(lái)記錄局部最優(yōu)值所對(duì)應(yīng)的路徑。

1.2 問(wèn)題解決

1.2.1 局部最優(yōu)值計(jì)算

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

其中，k的最大值是第M層葉結(jié)點(diǎn)的個(gè)數(shù)。度為p的樹(shù)中第i層至多有pi-1個(gè)節(jié)點(diǎn)（i>1），該問(wèn)題求解的樹(shù)的度p=3，則第M=15層至多有3M-1=315-1個(gè)結(jié)點(diǎn)，試驗(yàn)中k的最大值為16，通過(guò)分析可以得出該問(wèn)題的時(shí)間復(fù)雜度為O（16*M）。

綜上分析，文中給出的算法在求模板匹配的最優(yōu)解時(shí)，其對(duì)應(yīng)的時(shí)間復(fù)雜度為O（MN）+O（KM），即max（O（MN），O（KM））。若從p叉樹(shù)的生成角度考慮，算法的時(shí)間復(fù)雜度為O（MN）+O（nodes），即max（O（MN），O（nodes））。

3 結(jié)語(yǔ)

針對(duì)傳y模板匹配算法在應(yīng)用圖像處理問(wèn)題時(shí)遇到的時(shí)間復(fù)雜度過(guò)高等問(wèn)題，對(duì)數(shù)據(jù)與模板匹配的過(guò)程進(jìn)行優(yōu)化，提出了一種基于動(dòng)態(tài)規(guī)劃算法加以實(shí)現(xiàn)的方法，算法的時(shí)間復(fù)雜度為max（O（MN），O（KM））。利用本算法，可以將模板匹配過(guò)程的復(fù)雜度大大減小，也不需要對(duì)數(shù)據(jù)進(jìn)行過(guò)多處理，而且程序編寫簡(jiǎn)單，各方面比原算法和目前已有文獻(xiàn)中提到的改進(jìn)算法都有很大提高。

可以看出，未來(lái)無(wú)論是計(jì)算機(jī)處理領(lǐng)域的模板匹配問(wèn)題，還是日常生活生產(chǎn)中經(jīng)常遇到的“試驗(yàn)數(shù)據(jù)和事先存儲(chǔ)好的模板動(dòng)作進(jìn)行匹配”及類似問(wèn)題，本文所提出的算法都具有一定應(yīng)用前景。

參考文獻(xiàn)：

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

[2]李厚軍.快速模板匹配方法及其在眉毛識(shí)別中的應(yīng)用[D].北京：北京工業(yè)大學(xué)，2015.

[3]陳瑩.基于FPGA的微光圖像增強(qiáng)和模板匹配研究[D].北京：中國(guó)科學(xué)院大學(xué)，2014.

[4]王正，陶品，馮立新，溫江濤，楊士強(qiáng).基于模板的調(diào)色板方法[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2016，28（7）：1146-1151.

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

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

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

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

[9]王曉東.計(jì)算機(jī)算法設(shè)計(jì)與分析[M].第2版.北京：電子工業(yè)出版社，2005.

[10]徐孝凱，賀桂英.數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言描述）[M].北京：清華大學(xué)出版社，2004.

[11]唐策善，李龍澍，黃劉生.數(shù)據(jù)結(jié)構(gòu)――用C語(yǔ)言描述[M].北京：高等教育出版社，2003.

第2篇：動(dòng)態(tài)規(guī)劃范文

動(dòng)態(tài)規(guī)范是算法里一種非常重要的方法,是求解決策過(guò)程最優(yōu)化的數(shù)學(xué)方法。動(dòng)態(tài)規(guī)劃自問(wèn)世以來(lái),在經(jīng)濟(jì)管理、生產(chǎn)調(diào)度、工程技術(shù)和最優(yōu)控制等方面得到了廣泛的應(yīng)用。例如最短路線、庫(kù)存管理、資源分配、設(shè)備更新、排序、裝載等問(wèn)題,用動(dòng)態(tài)規(guī)劃方法比用其他方法求解更為方便。

本文通過(guò)對(duì)經(jīng)典的01背包問(wèn)題的求解,從動(dòng)態(tài)規(guī)劃的角度進(jìn)行闡述,通過(guò)案例對(duì)該算法的計(jì)算過(guò)程進(jìn)行了直觀的描述,并對(duì)該算法進(jìn)行了一定的優(yōu)化,最后指出該算法的優(yōu)缺點(diǎn)。

[關(guān)鍵詞]背包 動(dòng)態(tài)規(guī)劃 時(shí)間復(fù)雜度 空間復(fù)雜度

[中圖分類號(hào)]TP31[文獻(xiàn)標(biāo)識(shí)碼]A[文章編號(hào)]1009-5349(2010)05-0121-03

前言

背包問(wèn)題是一個(gè)經(jīng)典的動(dòng)態(tài)規(guī)劃模型,很多關(guān)于算法的教材都把它作為一道例題,該問(wèn)題既簡(jiǎn)單又容易理解,而且在某種程度上還能夠揭示動(dòng)態(tài)規(guī)劃的本質(zhì)。

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

背包問(wèn)題可以擴(kuò)展出很多種問(wèn)題,而01背包問(wèn)題是最常見(jiàn)、最有代表性的背包問(wèn)題。

一、問(wèn)題描述

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

二、基本思路

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

三、利用動(dòng)態(tài)規(guī)劃法求解01背包問(wèn)題

(一)動(dòng)態(tài)規(guī)劃算法的基本思想

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

(二)算法設(shè)計(jì)

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

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

該算法可分為n階段:

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

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

……

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

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

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

(三)存儲(chǔ)結(jié)構(gòu)

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

(四)算法實(shí)現(xiàn)

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

{

initial i,j,value;

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

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

for(i = 0; i

{

optp[i][0] = 0;

x[i] = FALSE;

}

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

for(i = 0; i

{

optp[0][i] = 0;

}

//利用(5)(6)式計(jì)算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.案例分析

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

用optp[i][j]來(lái)存儲(chǔ)這四個(gè)物體在不同載重量的背包下所獲的價(jià)值,計(jì)算過(guò)程如下表所示:

2.時(shí)間空間復(fù)雜度

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

(五)算法優(yōu)化

在上述算法中,時(shí)間復(fù)雜度不能再繼續(xù)優(yōu)化了,但是空間復(fù)雜度是可以繼續(xù)優(yōu)化的。

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

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];

}

}

上述例子中,相應(yīng)的_optp[j]計(jì)算結(jié)果如下表所示:

}

}

上述例子中,相應(yīng)的_optp[j]計(jì)算結(jié)果如下表所示:

顯然,對(duì)于物體i,_optp[j]的計(jì)算不會(huì)影響到_optp[0,1,……,weight[i]-1],故上述算法可繼續(xù)優(yōu)化為:

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];

}

}

對(duì)于01背包問(wèn)題,常見(jiàn)的要求有兩種:一種是恰好裝滿背包、另一種則沒(méi)有要求,針對(duì)這兩種問(wèn)法,可從初始化上來(lái)區(qū)分。

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

當(dāng)優(yōu)化后,空間復(fù)雜度變?yōu)镺(m),計(jì)算所需時(shí)間為:

當(dāng)weitht[i]較大時(shí),可以節(jié)省很多時(shí)間。

動(dòng)態(tài)規(guī)劃的缺點(diǎn):對(duì)于01背包問(wèn)題,用動(dòng)態(tài)規(guī)劃方法解很容易理解,但是這種方法有一些弊端,從上述算法可以看出:當(dāng)物體的重量較大時(shí),所需的物理空間較大;當(dāng)物體的重量不是整數(shù)時(shí),無(wú)法利用數(shù)組來(lái)存儲(chǔ)該結(jié)構(gòu)。

四、結(jié)束語(yǔ)

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

第3篇：動(dòng)態(tài)規(guī)劃范文

關(guān)鍵詞：動(dòng)態(tài)規(guī)劃；裝載問(wèn)題；JAVA語(yǔ)言

中圖分類號(hào)：TP31 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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

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

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

1 動(dòng)態(tài)規(guī)劃算法簡(jiǎn)介

動(dòng)態(tài)規(guī)劃（dynamic programming）[2]產(chǎn)生于20世紀(jì)50年代，由美國(guó)數(shù)學(xué)家R.E.Bellman等人提出。動(dòng)態(tài)規(guī)劃的思想是把一個(gè)問(wèn)題劃分為具有相關(guān)性的若干子問(wèn)題來(lái)解決，并將各個(gè)子問(wèn)題求解答案和求解方法進(jìn)行保存。如果在之后的處理過(guò)程中還需要用到已解決的子問(wèn)題，則直接調(diào)用答案，從而避免重復(fù)的計(jì)算，節(jié)省了時(shí)間。

在解決實(shí)際問(wèn)題中，我們需要?jiǎng)討B(tài)規(guī)劃出適當(dāng)?shù)募s束條件和遞推關(guān)系，并在各單階段中尋找互相聯(lián)系的因素，依次將每一階段所得的最優(yōu)結(jié)果進(jìn)行存儲(chǔ)。這種階段劃分、自下向上的求解方式需要建立表或數(shù)組才能有效實(shí)施。如圖1所示：

基于動(dòng)態(tài)規(guī)劃法解決的問(wèn)題需要滿足一定的條件，例如：（1）滿足無(wú)后效性，即子問(wèn)題的下一狀態(tài)只與現(xiàn)在狀態(tài)有關(guān)；（2）滿足最優(yōu)性子結(jié)構(gòu)，得出子問(wèn)題的最優(yōu)解；（3）原問(wèn)題可以劃分出多個(gè)擁有關(guān)聯(lián)的子問(wèn)題[3]。

2 模型的建立

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

在0-1背包問(wèn)題中，物品價(jià)值與體積不隨背包容量的變化而變化[4]。舉例說(shuō)明：假設(shè)有N=3個(gè)物品，總?cè)萘繛?0，體積V[i]={2，4，6}分別對(duì)應(yīng)價(jià)值P[i]={3，7，4}，設(shè)數(shù)組B[i][j]，表示在背包容量為j的條件下，放入第i個(gè)物品后的最大價(jià)值。如下表1所示：

動(dòng)態(tài)規(guī)劃算法易于編程的實(shí)現(xiàn)，雖然需要一定的空間存儲(chǔ)其產(chǎn)生的結(jié)果，但是它的高效性能在測(cè)試中體現(xiàn)出來(lái)。

4 測(cè)試數(shù)據(jù)

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

最終得出經(jīng)濟(jì)效益最大值為1904，如圖3所示。

5 結(jié)束語(yǔ)

本文從實(shí)際出發(fā)，給出廠商向校園超市運(yùn)輸商品時(shí)的裝載問(wèn)題，結(jié)合一個(gè)有效的算法――動(dòng)態(tài)規(guī)劃算法，利用JAVA語(yǔ)言得以實(shí)現(xiàn)。動(dòng)態(tài)規(guī)劃法有較好的效率和速度，不僅能用于解決裝箱問(wèn)題，而且能夠運(yùn)用于物流配載中的路徑規(guī)劃、資源分配等實(shí)際問(wèn)題，優(yōu)化了企業(yè)資源管理，提高經(jīng)濟(jì)效益，降低資源成本，能夠應(yīng)用于更多的科學(xué)領(lǐng)域中。

參考文獻(xiàn)：

[1] 謝天保，雷西玲，席文玲.物流配送中心配載車輛調(diào)度問(wèn)題研究[J].計(jì)算機(jī)工程與應(yīng)用，2010，36：237-240.

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

第4篇：動(dòng)態(tài)規(guī)劃范文

關(guān)鍵詞：LINGO；動(dòng)態(tài)規(guī)劃； 最短路問(wèn)題； 生產(chǎn)批量計(jì)劃問(wèn)題

中圖分類號(hào)：G642 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2014）04-0743-04

在交通專業(yè)課程如《交通運(yùn)籌學(xué)》、《交通系統(tǒng)分析方法》等的教學(xué)過(guò)程中，大量涉及到可劃分為多階段的優(yōu)化問(wèn)題求解，這些問(wèn)題的求解一般使用動(dòng)態(tài)規(guī)劃（dynamic programming）方法。動(dòng)態(tài)規(guī)劃將決策問(wèn)題的全過(guò)程劃分為若干個(gè)相互聯(lián)系的子過(guò)程（每個(gè)子過(guò)程為一個(gè)階段），然后按照一定的次序來(lái)求解。當(dāng)劃分的階段個(gè)數(shù)較多時(shí)，手工求解動(dòng)態(tài)規(guī)劃問(wèn)題相當(dāng)麻煩。由于在實(shí)際的交通工程規(guī)劃實(shí)踐中，涉及到的動(dòng)態(tài)規(guī)劃優(yōu)化問(wèn)題規(guī)模往往較大，指導(dǎo)學(xué)生掌握相應(yīng)的優(yōu)化軟件求解動(dòng)態(tài)規(guī)劃問(wèn)題一方面能增進(jìn)學(xué)生對(duì)動(dòng)態(tài)規(guī)劃法的理解掌握，另一方面能鍛煉學(xué)生的編程能力，是一項(xiàng)十分有意義的教學(xué)工作。

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

1 動(dòng)態(tài)規(guī)劃法求解實(shí)例

實(shí)例1 最短路問(wèn)題

在縱橫交錯(cuò)的公路網(wǎng)中（圖1所示），貨車司機(jī)希望找到一條從一個(gè)城市到另一個(gè)城市的最短路。圖中節(jié)點(diǎn)1—8代表貨車可以停靠的城市，弧旁的數(shù)字表示兩個(gè)城市之間的距離（百公里）。若貨車要從城市1出發(fā)到達(dá)城市8，問(wèn)如何選擇行駛路線使所經(jīng)過(guò)的路程最短。

問(wèn)題分析：該最短路問(wèn)題滿足動(dòng)態(tài)規(guī)劃的最優(yōu)性原理，即“從節(jié)點(diǎn)1到節(jié)點(diǎn)8的最短路的子路徑仍然是相應(yīng)節(jié)點(diǎn)間的最短路”，用[D（i，j）]表示從節(jié)點(diǎn)[i]和[j]有弧相連時(shí)相應(yīng)的距離，[L（i）]表示從節(jié)點(diǎn)1到節(jié)點(diǎn)i的最短路程數(shù)。則不難得到以下的動(dòng)態(tài)規(guī)劃由前向后遞推方程：

根據(jù)式（1），再進(jìn)一步定義當(dāng)節(jié)點(diǎn)[i]在從節(jié)點(diǎn)1到節(jié)點(diǎn)[j]的最短路徑上時(shí)，[P（i，j）=1]，否則[P（i，j）=0]，編寫如下LINGO求解代碼：

運(yùn)行LINGO得到如圖1所示的最優(yōu)解報(bào)告。

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

實(shí)例2（生產(chǎn)批量計(jì)劃問(wèn)題）

某企業(yè)生產(chǎn)某種產(chǎn)品用以滿足市場(chǎng)需求。通過(guò)統(tǒng)計(jì)，該產(chǎn)品今后[T]4周的外部需求（訂貨量）分別是[d1]千件、[d2]千件、[d3]千件和[d4]千件。如果第[t]周要開(kāi)工生產(chǎn)，則第[t]周開(kāi)工所需的生產(chǎn)準(zhǔn)備費(fèi)為[st]千元（與生產(chǎn)的數(shù)量無(wú)關(guān)），每件產(chǎn)品的生產(chǎn)費(fèi)為[ct]千元。如果在滿足需求后周末有產(chǎn)品剩余，每千件產(chǎn)品的存儲(chǔ)費(fèi)為[ht]千元。設(shè)第[t]周末的庫(kù)存量為[It]，假設(shè)開(kāi)始沒(méi)有庫(kù)存，記為[I0=0]且不考慮生產(chǎn)能力限制，問(wèn)工廠應(yīng)如何安排生產(chǎn)，在按時(shí)滿足需求的條件下，使總費(fèi)用最??？

問(wèn)題分析：對(duì)于生產(chǎn)批量計(jì)劃問(wèn)題，分析可知有如下兩條性質(zhì)成立：

由于以上兩個(gè)性質(zhì)，只有當(dāng)上一時(shí)段庫(kù)存[It-1=0]時(shí)，本時(shí)段才考慮進(jìn)行生產(chǎn)，且一旦生產(chǎn)，其生產(chǎn)量一定為某些后續(xù)時(shí)段需求量的總和，即[xt∈{dt，dt+dt+1，…，dt+dt+1+…+dT}]。這樣如用[ft]表示當(dāng)[t]時(shí)段初始庫(kù)存為0時(shí)，從[t]時(shí)段到[T]時(shí)段的子問(wèn)題的最優(yōu)費(fèi)用值，可以建立如下的遞推關(guān)系：

運(yùn)行LINGO得到如下最優(yōu)解報(bào)告：

從報(bào)告可以看到，[F（1）=561]，即從第1周到第4周末的最優(yōu)費(fèi)用為561（千元），分析其它[F]值得到，最優(yōu)的生產(chǎn)批量計(jì)劃為第1周生產(chǎn)2（千件），第2周生產(chǎn)5（千件），第3周不生產(chǎn)，第4周生產(chǎn)4（千件）。

2 結(jié)束語(yǔ)

本文針對(duì)用動(dòng)態(tài)規(guī)劃方法手工求解多階段優(yōu)化決策問(wèn)題十分繁瑣的特點(diǎn)，利用LINGO軟件將各個(gè)動(dòng)態(tài)規(guī)劃遞推方程簡(jiǎn)潔明確地編程實(shí)現(xiàn)，幫助學(xué)生更好的理解了各階段決策變量之間相互遞進(jìn)的關(guān)系，同時(shí)更重要的是交通專業(yè)學(xué)生熟練地掌握了軟件的使用，才能解決實(shí)際工程規(guī)劃中的大規(guī)模復(fù)雜優(yōu)化問(wèn)題，LINGO軟件的教學(xué)實(shí)踐促進(jìn)了《交通運(yùn)籌學(xué)》、《交通系統(tǒng)分析方法》與《交通規(guī)劃》等課程的融合。

參考文獻(xiàn)：

[1] 李曉川，朱曉敏，趙乃東. 基于Lingo的運(yùn)輸優(yōu)化系統(tǒng)設(shè)計(jì)與開(kāi)發(fā)[J]. 物流技術(shù)，2010（Z1）.

第5篇：動(dòng)態(tài)規(guī)劃范文

關(guān)鍵詞：最短路徑；動(dòng)態(tài)規(guī)劃；C 語(yǔ)言編程

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2013）09-2191-03

1 概述

數(shù)學(xué)源于生活，又服務(wù)于生活.它是一門研究現(xiàn)實(shí)世界中的數(shù)量關(guān)系與空間形式的學(xué)科.當(dāng)今社會(huì)，隨著物質(zhì)水平的不斷提高，生活需求的不斷擴(kuò)大，自然資源的不斷開(kāi)發(fā)利用.像天然氣管道鋪設(shè)問(wèn)題，廠區(qū)布局問(wèn)題，旅行費(fèi)用最小問(wèn)題等都已成為我們平時(shí)經(jīng)濟(jì)生活中的普遍問(wèn)題.它們其實(shí)都可以化歸為最短路線問(wèn)題，而最短路問(wèn)題實(shí)質(zhì)上是一個(gè)組合優(yōu)化問(wèn)題[1]。

動(dòng)態(tài)規(guī)劃方法主要是研究與解決多階段決策過(guò)程的最優(yōu)化問(wèn)題，它將求解分成多階段進(jìn)行，不但求出了全過(guò)程的解，還能求出后部子過(guò)程的一組解，在求解一些生活實(shí)際問(wèn)題時(shí)，更顯其優(yōu)越性。為了快速、簡(jiǎn)單的計(jì)算最短路徑，節(jié)約運(yùn)輸時(shí)間與成本，該文利用動(dòng)態(tài)規(guī)劃的思想編寫了C語(yǔ)言程序，解決物流運(yùn)輸過(guò)程中多地點(diǎn)的最短路徑的選擇問(wèn)題。

2 最短路徑問(wèn)題

2.1 最短路徑問(wèn)題算法的基本思想

在求解網(wǎng)絡(luò)圖上節(jié)點(diǎn)間最短路徑的方法中，目前國(guó)內(nèi)外一致公認(rèn)的較好算法有迪杰斯特拉（Dijkstra）及弗羅伊德（Floyd）算法。這兩種算法中，網(wǎng)絡(luò)被抽象為一個(gè)圖論中定義的有向或無(wú)向圖，并利用圖的節(jié)點(diǎn)鄰接矩陣記錄點(diǎn)間的關(guān)聯(lián)信息。在進(jìn)行圖的遍歷以搜索最短路徑時(shí)，以該矩陣為基礎(chǔ)不斷進(jìn)行目標(biāo)值的最小性判別，直到獲得最后的優(yōu)化路徑[2]。

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

2.2 最短路徑問(wèn)題算法的基本步驟[3]

這樣經(jīng)過(guò)有限次迭代則可以求出[v1]到[vn]的最短路線。

（2）Floyd算法的基本步驟

（3）動(dòng)態(tài)規(guī)劃算法基本步驟

我們將具有明顯的階段劃分和狀態(tài)轉(zhuǎn)移方程的規(guī)劃稱為動(dòng)態(tài)規(guī)劃[1]。在解決多個(gè)階段決策問(wèn)題時(shí)采用動(dòng)態(tài)規(guī)劃法是一個(gè)很有效的措施，同時(shí)易于實(shí)現(xiàn)。

根據(jù)動(dòng)態(tài)規(guī)劃的基本概念，可以得到動(dòng)態(tài)規(guī)劃的基本步驟：1）確定問(wèn)題的決策對(duì)象。2）對(duì)決策過(guò)程劃分階段。3）對(duì)各階段確定狀態(tài)變量。4）根據(jù)狀態(tài)變量確定費(fèi)用函數(shù)和目標(biāo)函數(shù)。5）建立各階段狀態(tài)變量的轉(zhuǎn)移過(guò)程，確定狀態(tài)轉(zhuǎn)移方程。

根據(jù)動(dòng)態(tài)規(guī)劃的基本模型，確定用動(dòng)態(tài)規(guī)劃方法解題的基本思路，是將一個(gè)[n]階段決策問(wèn)題轉(zhuǎn)化為一次求解[n]個(gè)具有遞推關(guān)系的單階段的決策問(wèn)題，以此來(lái)簡(jiǎn)化計(jì)算過(guò)程.其一般步驟如下：

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

3 最短路徑態(tài)規(guī)劃實(shí)際應(yīng)用舉例

設(shè)某物流配送網(wǎng)絡(luò)圖由12個(gè)配送點(diǎn)組成，點(diǎn)1為配送中心起點(diǎn)，12為終點(diǎn)，試求自終點(diǎn)到圖中任何配送點(diǎn)的最短距離。圖中相鄰兩點(diǎn)的連線上標(biāo)有兩點(diǎn)間的距離[4]。

首先用動(dòng)態(tài)規(guī)劃法來(lái)討論圖3的最短路徑，由圖可知：

1）集合[ξ4]中有點(diǎn)9、10、11，它們?cè)谝徊街畠?nèi)可到達(dá)點(diǎn)12；

2）集合[ξ3]中有點(diǎn)6，7，8，它們不超過(guò)兩步就可達(dá)到點(diǎn)12；

3）集合[ξ2]中包括點(diǎn) 2、3、4、5，不超過(guò)三步就可到達(dá)點(diǎn)12；

4）集合[ξ1]中包括點(diǎn)1，不超過(guò)四步可到達(dá)點(diǎn)12；

按照動(dòng)態(tài)規(guī)劃法類推，得到最優(yōu)路徑長(zhǎng)為16，徑路通過(guò)點(diǎn)為1，2，7，10，12和1，3，6，10，12。

根據(jù)動(dòng)態(tài)規(guī)劃算法編寫C語(yǔ)言計(jì)算程序[5] [6]，計(jì)算得到實(shí)驗(yàn)結(jié)果如下圖4所示：

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

4 結(jié)束語(yǔ)

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

參考文獻(xiàn)：

[1] 杜彥娟.利用動(dòng)態(tài)規(guī)劃數(shù)學(xué)模型求解最短路徑[J].煤炭技術(shù)，2005（1）：94-95.

第6篇：動(dòng)態(tài)規(guī)劃范文

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

 

10/1背包問(wèn)題

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

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

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

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

動(dòng)態(tài)規(guī)劃法適用于解最優(yōu)化問(wèn)題。通常可按以下4個(gè)步驟：

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

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

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

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

對(duì)于所給0-1背包問(wèn)題的子問(wèn)題：

，

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

（1.1）

（1.2）

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

3回溯法。

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

用回溯法解題的步驟：

(1)針對(duì)所給問(wèn)題定義問(wèn)題的解空間；

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

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

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

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

圖1-1n=3時(shí)，0-1背包問(wèn)題的解空間樹(shù)

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

4總結(jié)

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

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

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

參考文獻(xiàn)

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

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

第7篇：動(dòng)態(tài)規(guī)劃范文

關(guān)鍵詞：人才培養(yǎng)模式；工業(yè)工程；動(dòng)態(tài)規(guī)劃

中圖分類號(hào)：G640 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1002-4107（2013）02-0058-02

一、動(dòng)態(tài)規(guī)劃與人才培養(yǎng)

（一）動(dòng)態(tài)規(guī)劃

動(dòng)態(tài)規(guī)劃是運(yùn)籌學(xué)的一個(gè)分支，是求解決策過(guò)程最優(yōu)化的數(shù)學(xué)方法。在現(xiàn)實(shí)生活中，有一類活動(dòng)的過(guò)程，由于它的特殊性，可將過(guò)程分成若干個(gè)互相聯(lián)系的階段，在它的每一階段都需要做出決策，從而使整個(gè)過(guò)程達(dá)到最好的活動(dòng)效果。當(dāng)然，各個(gè)階段決策的選取不是任意確定的，它依賴于當(dāng)前面臨的狀態(tài)，又影響以后的發(fā)展，當(dāng)各個(gè)階段決策確定后，就組成一個(gè)決策序列，因而也就確定了整個(gè)過(guò)程的一條活動(dòng)路線。

這種把一個(gè)問(wèn)題看作是一個(gè)前后關(guān)聯(lián)具有鏈狀結(jié)構(gòu)的多階段過(guò)程就稱為多階段決策過(guò)程。在多階段決策過(guò)程中，動(dòng)態(tài)規(guī)劃法的基本思路是從終點(diǎn)逐段向始點(diǎn)方向?qū)ふ易疃搪肪€，既把當(dāng)前一段和未來(lái)各段分開(kāi)，又把當(dāng)前效益和未來(lái)效益結(jié)合起來(lái)考慮，從而得到整個(gè)問(wèn)題的最優(yōu)解[1]。

（二）動(dòng)態(tài)規(guī)劃思想融入工業(yè)工程專業(yè)人才培養(yǎng)

動(dòng)態(tài)規(guī)劃法的基本思想告訴我們，每段決策的選取是從全局來(lái)考慮的，與該段選擇的最優(yōu)答案一般是不同的，這對(duì)專業(yè)人才培養(yǎng)有很大的啟發(fā)。如果把人的整個(gè)成長(zhǎng)過(guò)程看成全局問(wèn)題，在學(xué)校階段取得最好成績(jī)只是該段決策最優(yōu)，能否在學(xué)生今后的就業(yè)及成長(zhǎng)過(guò)程中發(fā)揮最大作用，實(shí)現(xiàn)成才的最終目標(biāo)即達(dá)到全局最優(yōu)，還取決于學(xué)生未來(lái)從事崗位和工作領(lǐng)域的選擇。這對(duì)工業(yè)工程人才培養(yǎng)格外重要。

現(xiàn)代工業(yè)工程是技術(shù)與管理相結(jié)合的交叉學(xué)科，它既有鮮明的工程屬性，也有明顯的管理特征[2]。由于這門學(xué)科技術(shù)與管理交叉的特點(diǎn)，使得工業(yè)工程專業(yè)人才的就業(yè)方向非常廣泛，既可以進(jìn)行技術(shù)類的工程設(shè)計(jì)，也可以從事管理類的企業(yè)管理與決策，還可以繼續(xù)深造進(jìn)行科研攻關(guān)，每個(gè)方向的工作崗位對(duì)人才素質(zhì)的要求各不相同[3-5]。多元化的選擇使得學(xué)生畢業(yè)求職時(shí)看似什么崗位都適合，但事實(shí)上什么技能也不完全具備，只能臨時(shí)抱佛腳或者遭到社會(huì)的淘汰。因此，要想較好地完成個(gè)人成長(zhǎng)及成才，依據(jù)動(dòng)態(tài)規(guī)劃法的基本思想應(yīng)從終點(diǎn)逐段向始點(diǎn)方向?qū)ふ易疃搪肪€，在進(jìn)行人才培養(yǎng)時(shí)也應(yīng)該進(jìn)行逆序求解，首先幫助學(xué)生確立成才目標(biāo)及個(gè)人定位，然后自后向前尋找，從而幫助每個(gè)學(xué)生對(duì)當(dāng)前大學(xué)階段的努力方向和培養(yǎng)過(guò)程進(jìn)行決策。

二、啟發(fā)式的人才培養(yǎng)模式

基于上述理念，南京工業(yè)大學(xué)工業(yè)工程專業(yè)結(jié)合自身辦學(xué)條件和課程設(shè)置提出了開(kāi)放性、啟發(fā)式的人才培養(yǎng)新思路。在引導(dǎo)學(xué)生對(duì)未來(lái)職業(yè)定位和自身特點(diǎn)進(jìn)行分析思考的基礎(chǔ)上明確就業(yè)目標(biāo)，利用課堂教學(xué)和課余時(shí)間對(duì)學(xué)生進(jìn)行專項(xiàng)能力培訓(xùn)，最后集中進(jìn)行學(xué)業(yè)成果展示，如圖1所示。

（一）啟發(fā)式的人才測(cè)評(píng)和職業(yè)傾向測(cè)試

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

圖1 工業(yè)工程人才培養(yǎng)模式

（二）針對(duì)不同類型職業(yè)傾向的學(xué)生進(jìn)行專項(xiàng)能力培訓(xùn)

在對(duì)學(xué)生進(jìn)行人才測(cè)評(píng)和職業(yè)傾向測(cè)試的基礎(chǔ)上，在大三大四專業(yè)課學(xué)習(xí)階段針對(duì)不同類型職業(yè)傾向的學(xué)生進(jìn)行專項(xiàng)能力培訓(xùn)與強(qiáng)化，設(shè)立成長(zhǎng)性、開(kāi)放性的課程體系，使每個(gè)學(xué)生都可以自主選擇參與其中一種或幾種培養(yǎng)計(jì)劃。

1.對(duì)工程設(shè)計(jì)能力相對(duì)突出的學(xué)生，進(jìn)行工業(yè)工程設(shè)計(jì)能力強(qiáng)化培訓(xùn)。在學(xué)生已掌握的工業(yè)工程領(lǐng)域先進(jìn)工程設(shè)計(jì)軟件的基礎(chǔ)上，進(jìn)行企業(yè)實(shí)地調(diào)研，綜合運(yùn)用Flexsim、Proplanner、AutoCAD、Matlab、動(dòng)作分析軟件、流水線等軟硬件進(jìn)行工程設(shè)計(jì)與改善，并在培訓(xùn)結(jié)束后對(duì)設(shè)計(jì)作品和數(shù)據(jù)資料進(jìn)行匯總刻盤，最終得到可以向用人單位展示的設(shè)計(jì)成果。

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

2.對(duì)管理能力相對(duì)突出的學(xué)生，進(jìn)行管理實(shí)踐能力強(qiáng)化培訓(xùn)。每年全國(guó)都會(huì)召開(kāi)工業(yè)工程應(yīng)用案例大賽及現(xiàn)代物流技能大賽，利用此契機(jī)讓每個(gè)學(xué)生都參與其中，綜合課程所學(xué)的相關(guān)知識(shí)，對(duì)大賽中提出的案例進(jìn)行分析解決，讓每個(gè)學(xué)生都撰寫相應(yīng)的案例解決報(bào)告。這樣每個(gè)同學(xué)都有可以參與全國(guó)大賽的機(jī)會(huì)，報(bào)告也可以作為學(xué)生就業(yè)時(shí)的獨(dú)特成果向用人單位展示。

對(duì)自主創(chuàng)業(yè)意識(shí)和能力相對(duì)突出的學(xué)生，進(jìn)行創(chuàng)業(yè)實(shí)戰(zhàn)能力培訓(xùn)。通過(guò)參加學(xué)院每年舉辦的企業(yè)生產(chǎn)運(yùn)營(yíng)BOSS大獎(jiǎng)賽和商道管理決策競(jìng)賽，組織參與聽(tīng)取學(xué)校創(chuàng)業(yè)講座，增強(qiáng)其創(chuàng)業(yè)意識(shí)和決策能力，并結(jié)合市場(chǎng)情況指導(dǎo)其撰寫詳細(xì)的創(chuàng)業(yè)計(jì)劃書。

在該模式的引導(dǎo)下，南京工業(yè)大學(xué)在校生多次獲得全國(guó)商科院校技能大賽、大學(xué)生管理決策模擬大賽、IE亮劍等國(guó)內(nèi)競(jìng)賽獎(jiǎng)項(xiàng)，畢業(yè)生中也有多個(gè)創(chuàng)業(yè)團(tuán)隊(duì)出現(xiàn)。

3.對(duì)科研能力突出的同學(xué)，在課程中引入研究型教學(xué)[6]。教師以課程內(nèi)容和學(xué)生的學(xué)識(shí)積累為基礎(chǔ)，引導(dǎo)學(xué)生創(chuàng)造性地運(yùn)用知識(shí)和能力，自主地觀察問(wèn)題、提出問(wèn)題、分析問(wèn)題和解決問(wèn)題，在研討中積累知識(shí)、培養(yǎng)能力和鍛煉思維。

目前，我們選取“質(zhì)量管理與可靠性”課程進(jìn)行研究型教學(xué)試點(diǎn)，教師提出問(wèn)題，引起學(xué)生思考，并牽頭成立該課題的研究小組，引導(dǎo)他們?cè)谡n后開(kāi)展科研活動(dòng)。目前課題組已經(jīng)產(chǎn)生了豐碩的研究成果，以這些科研成果為基礎(chǔ)，教師與本科生合作在《工業(yè)工程與管理》等核心期刊上發(fā)表了學(xué)術(shù)論文4篇。

三、開(kāi)放性的學(xué)業(yè)成果全過(guò)程立體化展示

在以上培訓(xùn)的基礎(chǔ)上，每個(gè)學(xué)生都具備了可以向用人單位展示的各種成果。我們建設(shè)開(kāi)放性的“工業(yè)工程學(xué)生學(xué)業(yè)成果展示”網(wǎng)站，將每個(gè)學(xué)生本科四年期間的各種學(xué)業(yè)成果進(jìn)行集中展示，包括工程設(shè)計(jì)作品、創(chuàng)新創(chuàng)業(yè)作品、案例設(shè)計(jì)成果、各類競(jìng)賽成績(jī)等，以學(xué)生個(gè)人為標(biāo)簽，為全系學(xué)生建立個(gè)人網(wǎng)頁(yè)，全過(guò)程、立體化地反映學(xué)生本科四年的學(xué)習(xí)成果。

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

實(shí)踐表明，自該方法實(shí)行以來(lái)，學(xué)校培養(yǎng)了一批特點(diǎn)突出、素質(zhì)高的優(yōu)秀畢業(yè)生，獲得了學(xué)生及用人單位的一致好評(píng)?？梢哉f(shuō)，啟發(fā)式、開(kāi)放性、因材施教的培養(yǎng)方式無(wú)論在提高人才培養(yǎng)質(zhì)量方面，還是在高等教育教學(xué)理論應(yīng)用和人才培養(yǎng)方法方面都取得了一定成果，邁開(kāi)了教學(xué)改革堅(jiān)實(shí)的一步。

參考文獻(xiàn)：

[1]吳祈宗.運(yùn)籌學(xué)：第2版[M].北京：機(jī)械工業(yè)出版社，

2006.

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

2006，（35）.

[3]郭絢霞.提高我國(guó)高校大學(xué)生就業(yè)力的途徑[J].改革與

開(kāi)放，2009，（7）.

[4]張忠，楊蕾.基于當(dāng)前就業(yè)形勢(shì)的工業(yè)工程專業(yè)教學(xué)改

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

[5]楊振剛，陳建國(guó).基于港式思路的IE專業(yè)人才培養(yǎng)新模

式[J].工業(yè)工程，2010，（6）.

第8篇：動(dòng)態(tài)規(guī)劃范文

關(guān)鍵詞：可重構(gòu)制造系統(tǒng)；柔性測(cè)度；動(dòng)態(tài)規(guī)劃；柔性值

一、引言

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

針對(duì)生產(chǎn)制造系統(tǒng)的柔性研究，早期學(xué)者的研究側(cè)重于針對(duì)柔性制造系統(tǒng)的柔性進(jìn)行評(píng)價(jià)。楊思遠(yuǎn)、劉細(xì)兵在討論柔性制造系統(tǒng)柔性衡量標(biāo)準(zhǔn)的基礎(chǔ)上建立了柔性的凈現(xiàn)值指標(biāo)評(píng)價(jià)模型；李巖、張曉坤和徐躍飛等在針對(duì)影響柔性制造系統(tǒng)的柔性因素進(jìn)行深入分析的基礎(chǔ)上提出了用模糊評(píng)價(jià)方法對(duì)制造系統(tǒng)柔性進(jìn)行評(píng)價(jià)。隨后，學(xué)者們逐漸將柔性作為制造系統(tǒng)的一個(gè)特征，研究柔性的概念并針對(duì)影響制造系統(tǒng)柔性的各種因素進(jìn)行分析，并且給出了具體的柔性評(píng)價(jià)的方法。近年來(lái)，梁福軍、寧汝新及姜曉鵬、王潤(rùn)孝、庫(kù)祥臣分別對(duì)RMS的柔性進(jìn)行了定義并系統(tǒng)闡述了柔性的分類，但是都沒(méi)有針對(duì)RMS柔性的測(cè)度方面進(jìn)行研究。

在已有的制造系統(tǒng)柔性測(cè)度研究中，學(xué)者們從不同的角度對(duì)制造系統(tǒng)柔性的測(cè)度進(jìn)行了研究。Mandalbaum用制造系統(tǒng)的柔性在環(huán)境變化發(fā)生時(shí)造成的損失或者帶來(lái)的收益來(lái)對(duì)柔性進(jìn)行測(cè)度；Gustavsson認(rèn)為制造系統(tǒng)的柔性可以用制造系統(tǒng)的投資剩余值與投資原值之比來(lái)表示；Kumar則根據(jù)生產(chǎn)制造系統(tǒng)處理不確定性環(huán)境的能力以反映該系統(tǒng)的柔性，建立了基于信息理論的柔性測(cè)度方法；Slack認(rèn)為制造系統(tǒng)的柔性應(yīng)該在由狀態(tài)范圍維度、狀態(tài)轉(zhuǎn)移費(fèi)用維度和狀態(tài)轉(zhuǎn)移時(shí)間維度構(gòu)成的三維空間中進(jìn)行度量；Barad認(rèn)為制造系統(tǒng)運(yùn)行柔性可以用系統(tǒng)適應(yīng)變化所需的時(shí)間來(lái)度量并采用時(shí)間Petri網(wǎng)描述柔性。以上為學(xué)者從四個(gè)不同的角度對(duì)柔性的主要特征進(jìn)行了描述并提出了相應(yīng)的柔性測(cè)度方法。

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

二、RMS的柔性及測(cè)度原理

（一）RMS的柔性

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

（二）RMS柔性測(cè)度原理

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

三、RMS柔性測(cè)度模型

RMS因其內(nèi)在的柔性使得企業(yè)能夠更好地適應(yīng)外界環(huán)境的變化，對(duì)各種不確定性因素做出相應(yīng)的反應(yīng)，從而增強(qiáng)企業(yè)自身的市場(chǎng)競(jìng)爭(zhēng)力。與此同時(shí)，可重構(gòu)制造系統(tǒng)要素隨時(shí)間變化的特征使得系統(tǒng)的定量評(píng)價(jià)更加困難，因此必須建立能夠反映其內(nèi)涵的動(dòng)態(tài)隨機(jī)模型。由于影響系統(tǒng)的不確定性因素很多，本文主要討論由于顧客需求發(fā)生變化對(duì)RMS造成的不確定性，而這里所指的顧客需求變化指的是顧客對(duì)產(chǎn)品組合、需求數(shù)量及對(duì)新產(chǎn)品的需求等。

（一）可重構(gòu)制造系統(tǒng)柔性定量評(píng)價(jià)的假設(shè)條件

1.假設(shè)該機(jī)械制造企業(yè)一個(gè)生產(chǎn)周期為上一批工件加工完畢的時(shí)刻開(kāi)始至下一批工件加工完畢的時(shí)刻為止，且生產(chǎn)制造的兩種產(chǎn)品種類不同。

2.假設(shè)制造系統(tǒng)在第一種產(chǎn)品生產(chǎn)完成至第二種產(chǎn)品開(kāi)始生產(chǎn)之前自身已完成調(diào)整可以進(jìn)行轉(zhuǎn)產(chǎn)，因?yàn)楸疚闹饕芯靠芍貥?gòu)制造系統(tǒng)對(duì)顧客需求變化的響應(yīng)程度。

3.制造系統(tǒng)在整個(gè)生產(chǎn)周期內(nèi)不受到除顧客需求發(fā)生變化之外的其他外界因素影響。

（二）評(píng)價(jià)RMS柔性的隨機(jī)動(dòng)態(tài)規(guī)劃模型

1.確定階段

在此階段企業(yè)將要進(jìn)行個(gè)階段的生產(chǎn)加工。

2.狀態(tài)變量和決策變量的設(shè)定

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

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

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

（三）決策過(guò)程

由于上文中構(gòu)建的模型假定初始狀態(tài)已給定，因此選用逆序解法求得結(jié)果：F（0，xi（0），dj（0））={EF（1，xi（1），dj（1））}。此時(shí)，F(xiàn)值為該可重構(gòu)制造系統(tǒng)在整個(gè)加工階段的最優(yōu)收益值。

通過(guò)利用上文構(gòu)建的隨機(jī)動(dòng)態(tài)規(guī)劃模型并對(duì)其求解，可以得到RMS在需求等外界條件處于經(jīng)常性變動(dòng)的情況下整個(gè)加工階段的最優(yōu)收益值F。同時(shí)，也可以計(jì)算出該制造系統(tǒng)的剛性最優(yōu)收益值F，即假設(shè)顧客需求等外界條件不變的情況下制造系統(tǒng)生產(chǎn)制造同一種產(chǎn)品的最優(yōu)收益值Vf。最后，計(jì)算兩者之差即可定義為RMS的柔性值，即

Vf=F-F′

以Vf，即可重構(gòu)制造系統(tǒng)與剛性制造系統(tǒng)最優(yōu)收益值之差來(lái)定義可重構(gòu)制造系統(tǒng)的柔性值更具有準(zhǔn)確性和客觀性

四、結(jié)論

本文在可重構(gòu)制造系統(tǒng)柔性的相關(guān)理論研究的基礎(chǔ)上，通過(guò)隨機(jī)動(dòng)態(tài)規(guī)劃的方法建立模型并通過(guò)模型求解分別得到可重構(gòu)制造系統(tǒng)與剛性制造系統(tǒng)的最優(yōu)收益值，最后可重構(gòu)制造系與剛性制造系統(tǒng)的最優(yōu)收益值之差即可重構(gòu)制造系統(tǒng)的柔性值。

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

參考文獻(xiàn)：

[1]楊思遠(yuǎn)，劉細(xì)兵.柔性制造系統(tǒng)的經(jīng)濟(jì)評(píng)價(jià)[J].上海交通大學(xué)學(xué)報(bào)，1994（02）.

[2]李言，張曉坤，徐躍飛等.FMS柔性的評(píng)價(jià)[J].機(jī)械科學(xué)與技術(shù)，1994（02）.

[3]梁福軍，寧汝新.可重構(gòu)制造系統(tǒng)系統(tǒng)理論研究[J].機(jī)械工程學(xué)報(bào)，2003（39）.

[4]姜曉鵬，王潤(rùn)孝，庫(kù)祥臣.可重構(gòu)制造系統(tǒng)研究進(jìn)展[J].機(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篇：動(dòng)態(tài)規(guī)劃范文

關(guān)鍵詞： 動(dòng)態(tài)三角網(wǎng)格； AD*算法； 路徑規(guī)劃； 模擬仿真

中圖分類號(hào)： TN911.1?34； TM417 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 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

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

1 動(dòng)態(tài)環(huán)境地圖網(wǎng)格構(gòu)建及生成

1.1 動(dòng)態(tài)三角網(wǎng)格設(shè)計(jì)實(shí)現(xiàn)

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

1.1.1 障礙物插入模塊

該模塊在原有LCT（S）的存儲(chǔ)單元中插入新的多邊形障礙物，在插入過(guò)程中，給障礙物設(shè)置新的ID。S設(shè)置為現(xiàn)在LCT（S）已存在的限制規(guī)劃，O是將插入的新多邊形障礙物。插入過(guò)程如下：

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

（2） 對(duì)于List C中的限制邊界，通過(guò)搜索算法判斷S是否被阻塞。對(duì)于每個(gè)被阻塞的遍歷找到后，相關(guān)聯(lián)頂點(diǎn)加入List V。如圖1所示，通過(guò)搜索加入頂點(diǎn)兩邊可能因S引起阻隔。對(duì)每次遍歷來(lái)說(shuō)，相關(guān)聯(lián)的阻隔頂點(diǎn)v被加入到List V中。

圖1 尋找被阻斷過(guò)程

（3） 在遍歷過(guò)程所有被List V中頂點(diǎn)影響的頂點(diǎn)將重新測(cè)試其屬性，判斷在當(dāng)前情況是否需要被限制， Local_Ref函數(shù)定義和遍歷了在變化過(guò)程中與V相鄰的頂點(diǎn)。對(duì)于每一個(gè)所有與相鄰的三角形都要被訪問(wèn)。設(shè)為當(dāng)前與臨近被訪問(wèn)的三角形，此時(shí)需要調(diào)用函數(shù)檢測(cè)是否有遍歷過(guò)的節(jié)點(diǎn)需要重新定義；函數(shù)查看的后繼節(jié)點(diǎn)是否被影響，當(dāng)找到被影響的路徑時(shí)，頂點(diǎn)和若不在List V中則系統(tǒng)自動(dòng)進(jìn)行添加，然后重新測(cè)試所有在V中的頂點(diǎn)。

1.1.2 障礙物刪除模塊

該模塊將把現(xiàn)有地圖中的多邊形障礙物移除，移除過(guò)程中通過(guò)在插入中設(shè)置的ID找到該障礙物。由于障礙物之間可以發(fā)生覆蓋，故對(duì)于每一個(gè)障礙物來(lái)說(shuō)可能同時(shí)具有多個(gè)ID。刪除過(guò)程如下：

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

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

（3） 把List V1中相關(guān)的頂點(diǎn)信息從CDT中刪除；

（4） 對(duì)于所有在執(zhí)行過(guò)程中需要限制的頂點(diǎn)，通過(guò)調(diào)用Local_Ref函數(shù)再次遍歷與其臨近的頂點(diǎn)信息，并對(duì)發(fā)生變化的進(jìn)行改變。

1.1.3 動(dòng)態(tài)三角網(wǎng)格構(gòu)建過(guò)程

基于動(dòng)態(tài)三角網(wǎng)格地圖的動(dòng)態(tài)環(huán)境構(gòu)建步驟如下：

（1） 獲取三角網(wǎng)格發(fā)生變化后的地圖信息。

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

（3） 地圖網(wǎng)格中障礙物節(jié)點(diǎn)信息發(fā)生改變時(shí)，若有新節(jié)點(diǎn)加入，則添加后更新相鄰節(jié)點(diǎn)；若有節(jié)點(diǎn)刪除，則刪除后更新相鄰節(jié)點(diǎn)信息。

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

（5） 更新地圖中三角網(wǎng)格節(jié)點(diǎn)信息。

1.2 動(dòng)態(tài)地圖構(gòu)建實(shí)現(xiàn)

動(dòng)態(tài)三角網(wǎng)格地圖構(gòu)建過(guò)程如圖2所示，其中第一幅圖展示了在原始地圖中通過(guò)添加障礙物實(shí)現(xiàn)了地圖中存在若干個(gè)障礙物的情況，然后通過(guò)改變地圖網(wǎng)格中障礙物的個(gè)數(shù)、重新劃分三角網(wǎng)格以及移動(dòng)障礙物和刪除算法等方法，實(shí)現(xiàn)了仿真過(guò)程中對(duì)真實(shí)地圖情況的模擬和地圖網(wǎng)格的構(gòu)建過(guò)程。

圖2 動(dòng)態(tài)地圖實(shí)現(xiàn)效果

2 啟發(fā)式搜索動(dòng)態(tài)路徑規(guī)劃方法

2.1 啟發(fā)式動(dòng)態(tài)路徑規(guī)劃方法（AD*）

Anytime Dynamic A*（AD*）算法是在原有的動(dòng)態(tài)環(huán)境下將D* Lite和ARA*結(jié)合，解決了在動(dòng)態(tài)環(huán)境下高效率的路徑規(guī)劃問(wèn)題[4]。在AD*算法中利用ARA*中膨脹因子不斷遞減的過(guò)程進(jìn)行一系列路徑搜索。當(dāng)三角網(wǎng)格地圖環(huán)境發(fā)生改變并影響到邊的代價(jià)值時(shí)，在D*算法的OPEN表中對(duì)應(yīng)節(jié)點(diǎn)的Key值發(fā)生相應(yīng)改變。AD*算法具體執(zhí)行過(guò)程如下：

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

（2） 計(jì)算最短路徑。計(jì)算最短路徑的過(guò)程中節(jié)點(diǎn)的擴(kuò)展順序?yàn)閺哪繕?biāo)點(diǎn)goal到起始點(diǎn)start進(jìn)行擴(kuò)展，尋找出從源點(diǎn)到目標(biāo)點(diǎn)的最短路徑。

（3） 個(gè)體從start開(kāi)始沿路徑向goal前進(jìn)。

（4） 在擴(kuò)展過(guò)程中，將已擴(kuò)展過(guò)的節(jié)點(diǎn)存儲(chǔ)在INCONS表中。

（5） 判斷前進(jìn)過(guò)程中網(wǎng)格代價(jià)值是否發(fā)生變化，如果發(fā)生變化，則以當(dāng)前節(jié)點(diǎn)為新的起始點(diǎn)，并減小膨脹因子的值。

（6） 在下一次擴(kuò)展過(guò)程中，用作為啟發(fā)函數(shù)，在擴(kuò)展OPEN表中剩余的點(diǎn)之前，把上一輪INCONS表中的點(diǎn)插入OPEN表中，在原來(lái)OPEN表的基礎(chǔ)上修改所有與變化節(jié)點(diǎn)相關(guān)的rhs，key的值，清空CLOSE表。

（7） 以新的start點(diǎn)為起始點(diǎn)，goal為目標(biāo)點(diǎn)，運(yùn)行步驟（3）直至到達(dá)目標(biāo)點(diǎn)。

2.2 地圖網(wǎng)格密度計(jì)算

基于三角網(wǎng)格密度的改進(jìn)方法[5]，模擬人群仿真的過(guò)程在不同時(shí)間內(nèi)每個(gè)三角網(wǎng)格參數(shù)值因agents數(shù)量的不同而發(fā)生變化，因此把密度信息添加到Key值的計(jì)算中，可以估算每一個(gè)OPEN表中節(jié)點(diǎn)的優(yōu)先權(quán)從而得到最優(yōu)路徑。density（n）表示第個(gè)節(jié)點(diǎn)所在三角網(wǎng)格的密度值；是通過(guò)節(jié)點(diǎn)和距離信息來(lái)估算到目標(biāo)點(diǎn)的路徑長(zhǎng)度[6]。此時(shí)OPEN中擴(kuò)展節(jié)點(diǎn)的優(yōu)先權(quán)的計(jì)算公式如下：

（1）

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

將agents標(biāo)記在不同三角形網(wǎng)格中，通過(guò)計(jì)算當(dāng)前三角網(wǎng)格的密度信息決定不同節(jié)點(diǎn)在OPEN表中的優(yōu)先權(quán)，此時(shí)Key的值計(jì)算公式（2）如下所示：

（2）

通過(guò)不斷減小在搜索路徑過(guò)程中膨脹因子的值找到最優(yōu)路徑。

3 動(dòng)態(tài)路徑規(guī)劃算法設(shè)計(jì)與實(shí)現(xiàn)

3.1 搜索節(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)

在動(dòng)態(tài)環(huán)境中，以DLCT三角網(wǎng)格[7]作為地圖的劃分方法，將地圖網(wǎng)格中的動(dòng)態(tài)變化信息和移動(dòng)個(gè)體動(dòng)態(tài)搜索路徑方法相關(guān)聯(lián)，構(gòu)造如下數(shù)據(jù)結(jié)構(gòu)，在Map_Node中存儲(chǔ)動(dòng)態(tài)網(wǎng)格中障礙物發(fā)生變化后節(jié)點(diǎn)的構(gòu)建網(wǎng)格信息；Agent_Node中記錄移動(dòng)個(gè)體在尋路過(guò)程所擴(kuò)展的三角網(wǎng)格邊。規(guī)劃路徑時(shí)根據(jù)當(dāng)前Open_Node節(jié)點(diǎn)中存放的信息計(jì)算最優(yōu)路徑。

3.2 動(dòng)態(tài)搜索算法實(shí)現(xiàn)

在動(dòng)態(tài)搜索算法中，當(dāng)動(dòng)態(tài)環(huán)境發(fā)生變化時(shí)更新三角網(wǎng)格地圖信息，通過(guò)在OPEN表中擴(kuò)展邊，更新變化的頂點(diǎn)信息與其鄰接節(jié)點(diǎn)，判斷當(dāng)前移動(dòng)個(gè)體路徑是否受到影響，未受影響的個(gè)體按原路徑移動(dòng)；由于網(wǎng)格變化需要重新尋路時(shí)，計(jì)算節(jié)點(diǎn)代價(jià)值如下所示：

（3）

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

4 基于動(dòng)態(tài)環(huán)境的動(dòng)態(tài)規(guī)劃仿真與實(shí)現(xiàn)

4.1 地圖規(guī)模變化策略

為了驗(yàn)證動(dòng)態(tài)搜索算法在不同規(guī)模三角網(wǎng)格地圖上的適用性和模擬仿真場(chǎng)景中復(fù)雜逼真程度，同時(shí)證明DLCT網(wǎng)格劃分方法對(duì)不同地圖的劃分結(jié)果的差異。本實(shí)驗(yàn)應(yīng)用動(dòng)態(tài)搜索算法AD*實(shí)現(xiàn)在不同規(guī)模地圖上個(gè)體規(guī)劃路徑過(guò)程。如圖3所示，圖中地圖網(wǎng)格的復(fù)雜程度由簡(jiǎn)到繁分別采用5×5，10×10，20×20，40×40的網(wǎng)格拓?fù)浣Y(jié)構(gòu)，通過(guò)不斷增大迷宮場(chǎng)景圖的復(fù)雜程度，在地圖中選擇起始點(diǎn)和目標(biāo)點(diǎn)后通過(guò)啟發(fā)式動(dòng)態(tài)路徑搜索算法，AD*在不斷變化的三角網(wǎng)格中進(jìn)行路徑規(guī)劃，最終找到當(dāng)前狀態(tài)下的最優(yōu)路徑。

通過(guò)采用不同規(guī)模地圖對(duì)單一移動(dòng)個(gè)體規(guī)劃路徑，不同的搜索算法尋路過(guò)程與地圖的復(fù)雜程度正相關(guān)，隨著地圖復(fù)雜程度的增加，搜索路徑的過(guò)程在地圖網(wǎng)格中與擴(kuò)展的三角邊總數(shù)呈正相關(guān)的趨勢(shì)增長(zhǎng)。因此，在復(fù)雜多變的環(huán)境中模擬真實(shí)場(chǎng)景時(shí)，采用高效的地圖網(wǎng)格剖分方法能夠使路徑規(guī)劃效率得到提高。

4.2 群w移動(dòng)策略

4.2.1 碰撞檢測(cè)方法

采用的規(guī)避方法是隨機(jī)處理方式和球體處理方法相結(jié)合，在Agents碰撞發(fā)生后進(jìn)行處理，設(shè)置兩個(gè)移動(dòng)個(gè)體之間距離的最小值，若小于最小值時(shí)則認(rèn)為碰撞發(fā)生。在碰撞發(fā)生后，若個(gè)體所在三角網(wǎng)格密度信息較大，則重新規(guī)劃路徑進(jìn)行移動(dòng)直至目標(biāo)點(diǎn)；若個(gè)體所在三角網(wǎng)格在密度范圍內(nèi)則個(gè)體延時(shí)等待一段時(shí)間后，通過(guò)避讓的方法繞過(guò)障礙物繼續(xù)前行到達(dá)目標(biāo)點(diǎn)。

4.2.2 個(gè)體規(guī)避策略方法實(shí)現(xiàn)

在動(dòng)態(tài)三角網(wǎng)格地圖環(huán)境中，當(dāng)障礙物發(fā)生移動(dòng)時(shí)，移動(dòng)個(gè)體會(huì)根據(jù)當(dāng)前規(guī)劃路徑是否受到影響決定移動(dòng)策略，根據(jù)對(duì)方向進(jìn)行判斷，若在移動(dòng)過(guò)程中碰撞發(fā)生，記錄當(dāng)前位置信息CurPosition，判斷當(dāng)前三角網(wǎng)格密度值density，在密度滿足閾值條件時(shí)應(yīng)用規(guī)避方法重新規(guī)劃路徑繼續(xù)移動(dòng)；其他情況下，需改變移動(dòng)方向，密度滿足要求時(shí)進(jìn)行重新規(guī)劃。

模擬仿真過(guò)程截圖如圖4～圖7所示，在圖4和圖5中，障礙物的移動(dòng)沒(méi)有對(duì)個(gè)體移動(dòng)的路徑產(chǎn)生影響，仍按照原規(guī)劃路徑前行；在圖6中，當(dāng)動(dòng)態(tài)地圖網(wǎng)格中障礙物變化導(dǎo)致網(wǎng)格布局發(fā)生改變，從而對(duì)個(gè)體原路徑產(chǎn)生影響時(shí)，個(gè)體重新規(guī)劃路徑；在圖7中，當(dāng)?shù)貓D網(wǎng)格發(fā)生動(dòng)態(tài)改變時(shí)，若同時(shí)存在的若干移動(dòng)個(gè)體發(fā)生碰撞，此時(shí)應(yīng)用個(gè)體移動(dòng)的規(guī)避策略對(duì)路徑進(jìn)行重新規(guī)劃。

4.3 群體動(dòng)態(tài)路徑規(guī)劃方法

4.3.1 群體動(dòng)態(tài)路徑方法

群體路徑規(guī)劃方法是在單獨(dú)個(gè)體基礎(chǔ)上對(duì)每個(gè)移動(dòng)物體進(jìn)行路徑規(guī)劃的過(guò)程。為了模擬大規(guī)模人群仿真技術(shù)提出群行為模擬方法，移動(dòng)個(gè)體對(duì)不同的Agent的影響有很大差異，主要問(wèn)題有如下幾個(gè)方面：

（1） 如在此移動(dòng)個(gè)體之前有另一個(gè)體相向而行，則其中一個(gè)物體應(yīng)該改變速度方向避免碰撞發(fā)生。

（2） 若兩個(gè)移動(dòng)個(gè)體同向時(shí)，其中較慢的個(gè)體應(yīng)在人群密度較小的情況下改變速度方向超過(guò)前方遮擋個(gè)體；而在人群密度較大時(shí)，跟在前方物體之后行走。

綜合以上問(wèn)題描述，本文通過(guò)碰撞類型分類對(duì)優(yōu)先級(jí)進(jìn)行劃分。按照優(yōu)先級(jí)原則對(duì)仿真環(huán)境中的Agents個(gè)體進(jìn)行優(yōu)先級(jí)排序（模擬真實(shí)場(chǎng)景中的出場(chǎng)順序或根據(jù)重要程度排序等），根據(jù)優(yōu)先級(jí)遞減劃分成不同的組別，對(duì)于中的每個(gè)Agent個(gè)體，保存其start，goal，position，DesSpeed，velDir變量信息。

在規(guī)劃群體路徑過(guò)程中，根據(jù)Agents的優(yōu)先級(jí)大小對(duì)速度方向進(jìn)行修改，若在中Agents和中的移動(dòng)個(gè)體移動(dòng)方向相同則需要在判斷優(yōu)先級(jí)的條件下重新規(guī)劃其余組別的路徑方向。在采用以上方法避免碰撞發(fā)生的條件下，若碰撞發(fā)生，記錄當(dāng)前碰撞發(fā)生時(shí)移動(dòng)個(gè)體的位置信息position，計(jì)算當(dāng)前三角網(wǎng)格的密度density和相鄰節(jié)點(diǎn)構(gòu)造網(wǎng)格密度值，根據(jù)Agents的優(yōu)先級(jí)以及已得到的密度信息進(jìn)行重新排序，若此時(shí)的移動(dòng)個(gè)體滿足優(yōu)先級(jí)條件，則重新計(jì)算地圖網(wǎng)格的代價(jià)值并重新規(guī)劃由當(dāng)前位置position到目標(biāo)點(diǎn)的路徑；若此時(shí)碰撞個(gè)體優(yōu)先級(jí)較低，則處于等待狀態(tài)至下一次重新規(guī)劃。

4.3.2 群體規(guī)劃路徑實(shí)現(xiàn)

為了驗(yàn)證本文的群體動(dòng)態(tài)路徑規(guī)劃方法，對(duì)在地圖網(wǎng)格中可能發(fā)生碰撞的Agents個(gè)體采用碰撞規(guī)避策略對(duì)每個(gè)Agents個(gè)體進(jìn)行路徑規(guī)劃，在仿真的過(guò)程中不斷增加Agents規(guī)模，分別對(duì)Agents=50，Agents=100，Agents=150，Agents=200在不同時(shí)刻的尋路情況仿真模擬，實(shí)現(xiàn)結(jié)果截圖如圖8所示，圖中不同顏色的小方格分別代表不同的Agents移動(dòng)個(gè)體，每個(gè)移動(dòng)個(gè)體從初始點(diǎn)出發(fā)到目標(biāo)點(diǎn)規(guī)劃出各自的路徑，當(dāng)有Agents個(gè)體之間發(fā)生相互碰撞時(shí)（此時(shí)原規(guī)劃路徑移動(dòng)方向被阻擋），則Agent個(gè)體根據(jù)本文中采用的碰撞規(guī)避原則，采用AD*算法繞過(guò)對(duì)方后重新規(guī)劃路徑。

圖8 群體規(guī)劃路徑實(shí)現(xiàn)

由仿真效果可知，隨著網(wǎng)格地圖中Agents個(gè)體數(shù)的不斷增加，發(fā)生碰撞的幾率明顯增大，因此在動(dòng)態(tài)環(huán)境中，在采用高效的動(dòng)態(tài)路徑搜索算法的同時(shí)，需要針對(duì)群體中發(fā)生碰撞的規(guī)避策略來(lái)避免碰撞發(fā)生。

4.4 仿真實(shí)驗(yàn)結(jié)果分析

通過(guò)對(duì)動(dòng)態(tài)環(huán)境中的動(dòng)態(tài)網(wǎng)格效果、動(dòng)態(tài)路徑規(guī)劃算法進(jìn)行驗(yàn)證，將二者結(jié)合實(shí)現(xiàn)本文關(guān)于動(dòng)態(tài)環(huán)境中的路徑規(guī)劃方法的研究。在動(dòng)態(tài)網(wǎng)格地圖中分別移動(dòng)和增添障礙物后，實(shí)現(xiàn)了地圖網(wǎng)格發(fā)生變化情況的模擬。在動(dòng)態(tài)搜索算法中，通過(guò)將D*Lite和ARA*算法結(jié)合實(shí)現(xiàn)了動(dòng)態(tài)路徑規(guī)劃方法的優(yōu)化AD*算法，通過(guò)將二者結(jié)合，定義新的數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)移動(dòng)個(gè)體移動(dòng)過(guò)程中的變量值，對(duì)群體路徑規(guī)劃和碰撞規(guī)避策略的應(yīng)用計(jì)算達(dá)到了動(dòng)態(tài)環(huán)境路徑規(guī)劃的模擬仿真效果。

5 結(jié) 論

本文的主要研究?jī)?nèi)容包括基于動(dòng)態(tài)環(huán)境的網(wǎng)格地圖方法和動(dòng)態(tài)路徑規(guī)劃方法的研究，在此基礎(chǔ)上實(shí)現(xiàn)動(dòng)態(tài)環(huán)境中的路徑規(guī)劃。在動(dòng)態(tài)路徑規(guī)劃的過(guò)程中需要對(duì)網(wǎng)格構(gòu)建和搜索算法進(jìn)行研究，對(duì)地圖網(wǎng)格劃分方法在LCT靜態(tài)三角網(wǎng)格的基礎(chǔ)上，通過(guò)障礙物的移動(dòng)、添加和刪除實(shí)現(xiàn)了動(dòng)態(tài)網(wǎng)格規(guī)劃方法（DLCT）；在路徑搜索算法方面，將基于A*算法實(shí)現(xiàn)的ARA*算法和動(dòng)態(tài)搜索算法D*Lite相結(jié)合，實(shí)現(xiàn)了在動(dòng)態(tài)環(huán)境中的路徑規(guī)劃算法AD*。

參考文獻(xiàn)

[1] 孫俊，戴國(guó)駿，張懷相.裁剪優(yōu)化的Anytime算法[J].杭州電子科技大學(xué)學(xué)報(bào)，2010，30（2）：41?44.

[2] 張勝.一種基于狀態(tài)空間的啟發(fā)式搜索算法及其實(shí)現(xiàn)[J].現(xiàn)代電子技術(shù)，2008，31（16）：79?80.

[3] 孫蘭會(huì)，成鋒，陸愈實(shí).基于GIS的路徑規(guī)劃算法研究與實(shí)現(xiàn)[J].現(xiàn)代電子技術(shù)，2016，39（5）：101?104.

[4] 思磊.距離網(wǎng)格地圖動(dòng)態(tài)更新及基于距離網(wǎng)格地圖路徑規(guī)劃的研究[D].西安：西安電子科技大學(xué)，2013.

[5] 朱大奇，顏明重.移動(dòng)機(jī)器人路徑規(guī)劃技術(shù)綜述[J].控制與決策，2010，25（7）：961?967.

[6] 席裕庚，張純剛.一類動(dòng)態(tài)不確定環(huán)境下機(jī)器人的滾動(dòng)路徑規(guī)劃[J].自動(dòng)化學(xué)報(bào)，2002，28（2）：161?175.