|
最短路徑動態(tài)規(guī)劃問題及C語言實現(xiàn)探討
阜寧高等師范學校 王學軍 2013/8/30 12:50:19
摘要: 動態(tài)規(guī)劃算法是一種研究多階段決策問題的算法.用動態(tài)規(guī)劃方法求最短路問題,要求所求問題具有明顯的階段。本文以動態(tài)規(guī)劃理論為指導，研究了動態(tài)規(guī)劃算法求解最短路徑的基本原理及步驟，編寫了基于動態(tài)規(guī)劃算法的C語言程序，輔助完成最短路徑的求解。
關(guān)鍵詞: 最短路徑；動態(tài)規(guī)劃； C 語言編程
1.引言
數(shù)學源于生活，又服務(wù)于生活.它是一門研究現(xiàn)實世界中的數(shù)量關(guān)系與空間形式的學科.當今社會，隨著物質(zhì)水平的不斷提高，生活需求的不斷擴大，自然資源的不斷開發(fā)利用.像天然氣管道鋪設(shè)問題，廠區(qū)布局問題，旅行費用最小問題等都已成為我們平時經(jīng)濟生活中的普遍問題.它們其實都可以化歸為最短路線問題，而最短路問題實質(zhì)上是一個組合優(yōu)化問題[1]。
動態(tài)規(guī)劃方法主要是研究與解決多階段決策過程的最優(yōu)化問題，它將求解分成多階段進行，不但求出了全過程的解，還能求出后部子過程的一組解，在求解一些生活實際問題時，更顯其優(yōu)越性。為了快速、簡單的計算最短路徑，節(jié)約運輸時間與成本，本文利用動態(tài)規(guī)劃的思想編寫了C語言程序，解決物流運輸過程中多地點的最短路徑的選擇問題。
2.最短路徑問題
2.1 最短路徑問題算法的基本思想
在求解網(wǎng)絡(luò)圖上節(jié)點間最短路徑的方法中,目前國內(nèi)外一致公認的較好算法有迪杰斯特拉(Dijkstra)及弗羅伊德(Floyd)算法。這兩種算法中,網(wǎng)絡(luò)被抽象為一個圖論中定義的有向或無向圖,并利用圖的節(jié)點鄰接矩陣記錄點間的關(guān)聯(lián)信息。在進行圖的遍歷以搜索最短路徑時,以該矩陣為基礎(chǔ)不斷進行目標值的最小性判別,直到獲得最后的優(yōu)化路徑[2]。
Dijkstra算法是圖論中確定最短路的基本方法,也是其它算法的基礎(chǔ)。為了求出賦權(quán)圖中任意兩結(jié)點之間的最短路徑,通常采用兩種方法。一種方法是每次以一個結(jié)點為源點,重復執(zhí)行Dijkstra算法n次。另一種方法是由Floyd于1962年提出的Floyd算法,其時間復雜度為 ,雖然與重復執(zhí)行Dijkstra算法n次的時間復雜度相同,但其形式上略為簡單,且實際運算效果要好于前者。
2.2 最短路徑問題算法的基本步驟[3]
(1)Dijkstra算法基本步驟
令： ；
(a)對 ，求 。
(b)求 得 ，使 = 令 。
(c)若 則已找到 到 的最短路距離 ，否則令 從 中刪去 轉(zhuǎn)1
這樣經(jīng)過有限次迭代則可以求出 到 的最短路線。
(2)Floyd算法的基本步驟
如果一個矩陣 其中 表示 與 間的距離,若 與 間無路可通,則 為無窮大。 與 間的最短距離存在經(jīng)過 與 間的 和不經(jīng)過 兩種情況,所以可以令 ,n(n為節(jié)點數(shù))。檢查 與 的值,在此, 與 分別為目前所知的 到 與 到 的最短距離,因此, 就是 到 經(jīng)過 的最短距離。所以,若有 ,就表示從 出發(fā)經(jīng) 再到 的距離要比原來的 到 距離短,自然把 到 的 重寫成 。每當一個 搜索完, 就是目前 到 的最短距離。重復這一過程,最后當查完所有 時, 就為 到 的最短距離。
(3)動態(tài)規(guī)劃算法基本步驟
我們將具有明顯的階段劃分和狀態(tài)轉(zhuǎn)移方程的規(guī)劃稱為動態(tài)規(guī)劃 。在解決多個階段決策問題時采用動態(tài)規(guī)劃法是一個很有效的措施，同時易于實現(xiàn)。
根據(jù)動態(tài)規(guī)劃的基本概念，可以得到動態(tài)規(guī)劃的基本步驟：(1)確定問題的決策對象. (2)對決策過程劃分階段. (3)對各階段確定狀態(tài)變量. (4)根據(jù)狀態(tài)變量確定費用函數(shù)和目標函數(shù).(5)建立各階段狀態(tài)變量的轉(zhuǎn)移過程，確定狀態(tài)轉(zhuǎn)移方程。
根據(jù)動態(tài)規(guī)劃的基本模型，確定用動態(tài)規(guī)劃方法解題的基本思路，是將一個 階段決策問題轉(zhuǎn)化為一次求解 個具有遞推關(guān)系的單階段的決策問題，以此來簡化計算過程.其一般步驟如下:
……
圖1 動態(tài)規(guī)劃步驟
用于衡量所選決策優(yōu)劣的函數(shù)稱為指標函數(shù).指標函數(shù)有有階段的指標函數(shù)和過程的指標函數(shù)之分.階段的指標函數(shù)是對應(yīng)某一階段狀態(tài)和從該狀態(tài)出發(fā)的一個階段的某種效益度量，用 表示.在本文里用 來表示某一階段的決策的最短路徑.過程的指標函數(shù)是指從狀態(tài) 出發(fā)至過程最終，當采取某種子策略時，按預定的標準得到的效益值.這個值既與 本身的狀態(tài)值有關(guān)，又與 以后所選取的策略有關(guān)，它是兩者的函數(shù)值，記作 .過程的指標函數(shù)又是它所包含的各階段指標函數(shù)的函數(shù).本文研究的過程的的指標函數(shù)是其各階段指標函數(shù)的和的形式.當 的值確定后，指標函數(shù)的值就只同k階段起的子策略有關(guān).對應(yīng)于從狀態(tài) 出發(fā)的最優(yōu)子策略的效益值記作 ，于是在最短路問題中，有 。動態(tài)規(guī)劃求解最短路徑程（未完，下一頁）
|