• 
    

    
    

      99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看

      ?

      最短路徑動態(tài)規(guī)劃問題及C語言實現(xiàn)探討

      2013-04-29 05:25:03王學(xué)軍
      電腦知識與技術(shù) 2013年9期
      關(guān)鍵詞:最短路徑動態(tài)規(guī)劃

      王學(xué)軍

      摘要:動態(tài)規(guī)劃算法是一種研究多階段決策問題的算法.用動態(tài)規(guī)劃方法求最短路問題,要求所求問題具有明顯的階段。該文以動態(tài)規(guī)劃理論為指導(dǎo),研究了動態(tài)規(guī)劃算法求解最短路徑的基本原理及步驟,編寫了基于動態(tài)規(guī)劃算法的C語言程序,輔助完成最短路徑的求解。

      關(guān)鍵詞:最短路徑;動態(tài)規(guī)劃;C 語言編程

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

      1 概述

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

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

      2 最短路徑問題

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

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

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

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

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

      (2)Floyd算法的基本步驟

      (3)動態(tài)規(guī)劃算法基本步驟

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

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

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

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

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

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

      首先用動態(tài)規(guī)劃法來討論圖3的最短路徑,由圖可知:

      1)集合[ξ4]中有點9、10、11,它們在一步之內(nèi)可到達(dá)點12;

      2)集合[ξ3]中有點6,7,8,它們不超過兩步就可達(dá)到點12;

      3)集合[ξ2]中包括點 2、3、4、5,不超過三步就可到達(dá)點12;

      4)集合[ξ1]中包括點1,不超過四步可到達(dá)點12;

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

      根據(jù)動態(tài)規(guī)劃算法編寫C語言計算程序[5] [6],計算得到實驗結(jié)果如下圖4所示:

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

      4 結(jié)束語

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

      參考文獻(xiàn):

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

      [2] 蔣琦瑋,陳治亞.物流配送最短徑路的動態(tài)規(guī)劃方法研究[J].系統(tǒng)工程,2007(25):27-29.

      [3] 朱建民.運籌學(xué)——典型例題與解法[EB/OL].http://www.zytxs.com/,2003.

      猜你喜歡
      最短路徑動態(tài)規(guī)劃
      Dijkstra算法設(shè)計與實現(xiàn)
      基于Dijkstra算法的優(yōu)化研究
      圖論最短路徑算法的圖形化演示及系統(tǒng)設(shè)計
      ACM—ICPC競賽趣味學(xué)習(xí)系統(tǒng)設(shè)計
      大學(xué)生經(jīng)濟旅游優(yōu)化設(shè)計模型研究
      中國市場(2016年33期)2016-10-18 14:23:52
      動態(tài)規(guī)劃最優(yōu)控制在非線性系統(tǒng)中的應(yīng)用
      不確定條件下物流車最優(yōu)路徑選擇研究
      中國市場(2016年10期)2016-03-24 10:17:44
      動態(tài)規(guī)劃案例教學(xué)設(shè)計
      基于NFC的博物館智能導(dǎo)航系統(tǒng)設(shè)計
      產(chǎn)品最優(yōu)求解問題中運籌學(xué)方法的應(yīng)用
      蕉岭县| 石家庄市| 八宿县| 辉县市| 原平市| 革吉县| 普兰县| 澎湖县| 湛江市| 五指山市| 藁城市| 淄博市| 德阳市| 衡阳县| 通江县| 新安县| 迁西县| 永康市| 阿图什市| 二连浩特市| 湘潭市| 麻栗坡县| 怀柔区| 芦山县| 泗洪县| 许昌县| 中江县| 宿松县| 思茅市| 赣州市| 普安县| 武清区| 永春县| 从江县| 临朐县| 宁德市| 平果县| 温宿县| 葵青区| 台前县| 淄博市|