資源配置中的最短路

1、關(guān)于資源配置中的最短路問題 摘 要：網(wǎng)絡(luò)購物在人們的日常生活中扮演著越來越重要的角色，網(wǎng)購蓬勃發(fā)展的同時刺激了社會物流業(yè)的快速崛起，賣家如何選擇出一條最短物流途徑進(jìn)行商品配送，降低運(yùn)送成本，是十分重要的。本文針對如何求解資源配置中的最短路徑問題,主要介紹了算法和算法以及它們各自的優(yōu)化算法，從而掌握求解最短路徑的這兩種基本方法。最短路問題是對一個賦權(quán)的有向圖 D 中指定的兩點(diǎn) Vs 和 Vt 找到一條從 Vs 到 Vt 的路,使得這條路上所有弧的權(quán)數(shù)和總和最小, 這條路即為從 Vs 到 Vt 的最短路, 這條路上所有弧的權(quán)數(shù)的總和為從 Vs 到 Vt 的距離。在實(shí)際工作中， 最短路問題很常見。求

2、解一般最短路問題， 可用圖和網(wǎng)絡(luò)的方法或動態(tài)規(guī)劃的方法， 但是不同的解法各有其要求及特點(diǎn)。 通過兩個問題的具體解法探討了動態(tài)規(guī)劃方法與圖與網(wǎng)絡(luò)的 Dijkstra 算法各自的特點(diǎn)及適用范圍和要求。 關(guān)鍵詞：資源配置；最短路；算法；算法；優(yōu)化 Abstract: Shopping on the internet is playing a more and more important role in our daily life. This scene stimulates the effective developments of the logistics industry at

3、the same time. So it is very crucial for sellers to pick up a reasonable delivery way to save more delivery costs . The paper mainly introduces the Dijkstra algorithm and the Floyd algorithm, we should learn them well and use them to find the shortest path.Key words: resource; allocation 

4、Dijkstra algorithm; Floyd algorithm ; optimization1 前 言21世紀(jì)是一個社會各行業(yè)獲得飛速發(fā)展的時代，無論是政治，經(jīng)濟(jì)，科技，文化領(lǐng)域都取得了顯著進(jìn)步。我們以科技發(fā)展為例，日新月異的科技進(jìn)步促進(jìn)了網(wǎng)絡(luò)的發(fā)展，高效便捷的網(wǎng)絡(luò)正在潛移默化地改變我們的生活。網(wǎng)絡(luò)走進(jìn)了千家萬戶，豐富的網(wǎng)絡(luò)資源開闊了我們的視野，提高了我們的工作效率。如今，網(wǎng)購也成為一種非常普遍的現(xiàn)象。網(wǎng)購給我們的生活帶來了巨大的便捷，我們足不出戶就可以享受送貨上門的優(yōu)待。網(wǎng)購在被大眾廣泛接受的同時，也帶動了物流業(yè)的快速發(fā)展。賣家在向買家送貨的過程中，需要合理分析多種物流途徑，從中選擇

5、一條最短路徑，從而降低運(yùn)輸成本，節(jié)約配送時間，實(shí)現(xiàn)資源配置的最優(yōu)化。最短路作為圖與網(wǎng)絡(luò)技術(shù)研究中的一個經(jīng)典問題一直在工程規(guī)劃地理信息系統(tǒng)通信和軍事運(yùn)籌學(xué)等領(lǐng)域有著十分廣泛的應(yīng)用，對該問題求解算法的設(shè)計(jì)和改進(jìn)研究有著重要的理論和應(yīng)用價值目前，關(guān)于最短路問題的研究已有較多結(jié)果傳統(tǒng)的最短路算法主要有Floyd算法1和Dijkstra算法2等 其中Floyd算法主要用于計(jì)算所有節(jié)點(diǎn)對之間的最短路；而Dijkstra算法是一種用于計(jì)算從一個源節(jié)點(diǎn)到其所有宿節(jié)點(diǎn)最短路的高效算法本文主要介紹圖論中求最短路徑方法的算法和算法，通過深入分析兩種算法的基本思想，從而掌握求解最短路徑的這兩種經(jīng)典算法。2 問題的提出

6、如圖1-1，現(xiàn)有賣家從發(fā)貨地（記為節(jié)點(diǎn)0）向買家所在地（記為節(jié)點(diǎn)3）送貨，可選擇的物流途徑中包含中轉(zhuǎn)站（記為節(jié)點(diǎn)1,2,4,5）。圖中已經(jīng)給出了每兩個節(jié)點(diǎn)之間的距離與路徑方向，賣家希望選擇合適的中轉(zhuǎn)站，使從發(fā)貨地到買家收貨地的物流路線最短。即圖1-1中，從節(jié)點(diǎn)0到節(jié)點(diǎn)3的最短路徑。這就是一個典型的最短路問題。3 定義與符號說明（1） 有序積（和是兩個集合）。（2） 無序積，其中（3） 圖-定義為一個偶對，記作，其中 是一個集 合，其中的元素稱為頂點(diǎn)；是無序積中的一個子集合，其元素稱為邊。（4）帶權(quán)有向圖-定義為一個偶對，其中 是一個非空集 合，其元素稱為頂點(diǎn)；是有序積的一個子集,其元素稱為弧。

7、（5）關(guān)聯(lián)-圖中一條邊的端點(diǎn)稱為與這條邊關(guān)聯(lián)。（6）節(jié)點(diǎn)的度-指和該節(jié)點(diǎn)相關(guān)聯(lián)的邊的數(shù)目。（7）弧的權(quán)重-圖中每條邊的長。（8）0-圖的起始點(diǎn)（9）-圖中的各個節(jié)點(diǎn)（10）-連接圖中節(jié)點(diǎn)和節(jié)點(diǎn)之間弧的權(quán)重（11）-圖中節(jié)點(diǎn)的臨時性標(biāo)號（12）-圖中節(jié)點(diǎn)的永久性標(biāo)號（13）-圖中從起始點(diǎn)0到節(jié)點(diǎn)最短路權(quán)的上界（14）-圖中從起始點(diǎn)0到節(jié)點(diǎn)最短路權(quán)（15）-圖1-1中連接節(jié)點(diǎn)與節(jié)點(diǎn)的弧的長度（16）-圖1-1中節(jié)點(diǎn)到節(jié)點(diǎn)的最短距離（17）-連接節(jié)點(diǎn)和節(jié)點(diǎn)的?。?8）-連接節(jié)點(diǎn)和節(jié)點(diǎn)的中間節(jié)點(diǎn)的數(shù)目（19）-圖1-4中入度大于0的節(jié)點(diǎn)集合（20）-圖的頂點(diǎn)數(shù)4 算法介紹4.1 求最短路算法4.1.1

8、 算法思想算法適用于加權(quán)有向圖或無向圖中單源點(diǎn)到其他頂點(diǎn)的最短路徑問題，是按長度遞增的次序來產(chǎn)生最短路徑的算法。我們以帶權(quán)（規(guī)定權(quán)重均為非負(fù)值，即）有向圖為例加以分析。先給帶權(quán)圖的每一個頂點(diǎn)記一個數(shù)（稱為標(biāo)號）-臨時標(biāo)號（簡稱標(biāo)號）或永久性標(biāo)號（簡稱標(biāo)號）。標(biāo)號標(biāo)示從圖起始點(diǎn)0到這一節(jié)點(diǎn)最短道路長的上界，標(biāo)號則是從起始點(diǎn)0到這一點(diǎn)的最短道路長。算法的每一步都把某個點(diǎn)的標(biāo)號改為標(biāo)號。這樣一旦終點(diǎn)得到標(biāo)號，算法停止。如果尋求從圖中的起始點(diǎn)0到某一點(diǎn)的最短路徑，則最多經(jīng)過步算法停止。4.1.2 算法步驟 初始時，起始點(diǎn)0,.其他節(jié)點(diǎn)臨時性標(biāo)號記為+，即 若節(jié)點(diǎn)點(diǎn)是剛得到標(biāo)號的點(diǎn)，考慮圖中與節(jié)點(diǎn)相連的

9、弧且節(jié)點(diǎn)是標(biāo)號。對節(jié)點(diǎn)的標(biāo)號進(jìn)行如下更改：比較所有具有標(biāo)號的點(diǎn)，把最小者改為標(biāo)號。當(dāng)存在兩個以上最小者時，可同時改為標(biāo)號； 重復(fù)上述過程，直到得出終點(diǎn)的標(biāo)號； 將上面得到標(biāo)號節(jié)點(diǎn)的次序反向，就是圖中從起始點(diǎn)0到終點(diǎn)的最短路徑。 算法的正確性是顯然的。因?yàn)樵谌我徊?，設(shè)中每一點(diǎn)的標(biāo)號是從圖的起始點(diǎn)0到該節(jié)點(diǎn)的最短道路長（開始，這個假設(shè)顯然是對的），下面只要說明是從起點(diǎn)0到節(jié)點(diǎn)的最短路徑。實(shí)際上，任一條從起點(diǎn)0到節(jié)點(diǎn)的道路，若通過標(biāo)號的第一個節(jié)點(diǎn)是，而的話，由于所有邊長為非負(fù)，則這種道路長不會比小，所以算法成立。4.2 求最短路算法算法主要解決單源點(diǎn)物流最短路徑問題。那么如何求出圖中任意節(jié)點(diǎn)之間的最

10、短路徑。如果使用算法，可以將每一個節(jié)點(diǎn)當(dāng)作起始點(diǎn)分別求其到各節(jié)點(diǎn)的最短路徑。操作中我們可以發(fā)現(xiàn)這個過程較為繁瑣，耗時長。針對這個問題，我們引出算法，該算法適用于無向圖和有向圖，能夠一次性求得圖中任意節(jié)點(diǎn)間的最短路徑，下面我們主要探討它在帶權(quán)有向圖的應(yīng)用情況。4.2.1 算法思想對于圖中任意節(jié)點(diǎn)間的最短路徑問題，我們思考從節(jié)點(diǎn)到節(jié)點(diǎn)的最短距離路徑只有兩種可能，即節(jié)點(diǎn)與直接相連和節(jié)點(diǎn)與通過中間節(jié)點(diǎn)相連?？梢钥闯鏊惴ㄊ茄芯抗?jié)點(diǎn)與之間插入節(jié)點(diǎn)的情況的算法，故又形象地稱其為插點(diǎn)法。4.2.2 算法步驟 令圖中（是圖中節(jié)點(diǎn)與之外剩余節(jié)點(diǎn)的數(shù)目），比較與的值； 若有，表示從節(jié)點(diǎn)出發(fā)經(jīng)過中間節(jié)點(diǎn)再到節(jié)點(diǎn)的距離

11、要比原來的節(jié)點(diǎn)直接到的距離短，所以把改為， 重復(fù)上述過程，當(dāng)所有的都查完了，就是目前節(jié)點(diǎn)到的最短距離。5 算法的應(yīng)用5.1 算法應(yīng)用 例1 用算法求解圖1-1中的最短路問題。解 首先記，該問題中各條弧的權(quán)重即為圖1-1中所標(biāo)出的兩節(jié)點(diǎn)間線段的長度。 ：圖1-1中與節(jié)點(diǎn)0相連的弧是（0,2）和（0,3），且節(jié)點(diǎn)2， 3 均為標(biāo)號。修改這兩個節(jié)點(diǎn)的標(biāo)號： ：在所有標(biāo)號中（），因?yàn)樽钚。?所以，令 ：圖1-1中與節(jié)點(diǎn)2相連的弧是（2,1）和（2,5），且節(jié)點(diǎn)1，5均為標(biāo)號。修改這兩個節(jié)點(diǎn)的標(biāo)號： ：在當(dāng)前所有標(biāo)號中，最小，所以，令 ：圖1-1中與節(jié)點(diǎn)5相連的弧是（5,3）和（5,4），且節(jié)點(diǎn)3,4均

12、為標(biāo)號。修改這兩個節(jié)點(diǎn)的標(biāo)號： ：在所有標(biāo)號中（即）,因?yàn)樽钚?，所以，令到目前為止，我們從圖1-1中起始點(diǎn)0出發(fā)得出終點(diǎn)3的標(biāo)號。將以上得到標(biāo)號節(jié)點(diǎn)的次序反向就可以得到從起始點(diǎn)0到終點(diǎn)3的最短路徑。具體如下：因?yàn)楣?jié)點(diǎn)3與節(jié)點(diǎn)5永久性標(biāo)號的差是10恰等于?。?,3）的長度。所以，退回到節(jié)點(diǎn)5.而節(jié)點(diǎn)5與節(jié)點(diǎn)2的永久性標(biāo)號差是7恰等于弧（2，5）的長度。所以，退回到節(jié)點(diǎn)2.最后退回到起點(diǎn)0.故得到從起點(diǎn)0到節(jié)點(diǎn)3的最短路徑是：0253，長度為22. 5.2 算法應(yīng)用例2 用算法求解圖1-1中節(jié)點(diǎn)1到節(jié)點(diǎn)3的最短路徑。 解 判斷從節(jié)點(diǎn)1出發(fā)是否可以不通過其他節(jié)點(diǎn)直接到達(dá)節(jié)點(diǎn)3.由圖1-1可以看出節(jié)點(diǎn)

13、1與節(jié)點(diǎn)3不直接相連，必須通過圖中其他節(jié)點(diǎn)將它們連接起來。 判斷從節(jié)點(diǎn)1出發(fā)是否可以只通過一個節(jié)點(diǎn)然后到達(dá)節(jié)點(diǎn)3.觀察圖1-1得到符合條件的分別是中間節(jié)點(diǎn)0和節(jié)點(diǎn)4. 路徑一：103. 路徑二：143. 判斷從節(jié)點(diǎn)1出發(fā)是否可以中途經(jīng)過兩個節(jié)點(diǎn)最終到達(dá)節(jié)點(diǎn)3.觀察圖1-1得到?jīng)]有符合條件的中間節(jié)點(diǎn)。 判斷從節(jié)點(diǎn)1出發(fā)是否可以中途經(jīng)過三個節(jié)點(diǎn)最終到達(dá)節(jié)點(diǎn)3.觀察圖1-1得到符合條件的一組中途節(jié)點(diǎn)0，節(jié)點(diǎn)2，節(jié)點(diǎn)5.路徑三：10253. 判斷從節(jié)點(diǎn)1出發(fā)是否可以途中通過四個節(jié)點(diǎn)最終到達(dá)節(jié)點(diǎn)3.觀察圖1-1得到符合條件的一組中途節(jié)點(diǎn)0，節(jié)點(diǎn)2，節(jié)點(diǎn)5，節(jié)點(diǎn)4.路徑四：102543. 目前為止，所有節(jié)

14、點(diǎn)全部討論完畢。比較路徑一，路徑二，路徑三，路徑四，得到節(jié)點(diǎn)1到節(jié)點(diǎn)3的最短路徑為路徑二：143. 6 算法優(yōu)化6.1 優(yōu)化算法算法是典型最短路算法之一，主要特點(diǎn)是以帶權(quán)有向圖起始點(diǎn)為中心向外層層擴(kuò)展，直到擴(kuò)展到終點(diǎn)為止。要求圖中每條弧權(quán)值均為非負(fù)。算法雖然能夠得出最短路徑的最優(yōu)解，但由于隨著帶權(quán)有向圖中頂點(diǎn)數(shù)量的增加，計(jì)算步驟也會逐漸增多，大大降低計(jì)算效率。針對算法的不足之處，這里提出一種的優(yōu)化算法。6.1.1 優(yōu)化算法思想我們在網(wǎng)購過程中注意到賣家是按收貨地分區(qū)域配送貨物的，并不是按照唯一的路徑送貨。這一現(xiàn)象啟發(fā)我們在用算法求最短路徑的過程中，也許并不需要把每個點(diǎn)都討論一遍，而只需要討論某

15、些關(guān)鍵點(diǎn)。我們知道幾何意義上兩點(diǎn)之間線段最短。因此，起始點(diǎn)0到指定節(jié)點(diǎn)的最短路徑一定在直接連接起始點(diǎn)與終點(diǎn)的弧的附近。我們以這條弧為界來劃分圖，分別計(jì)算出每個子圖的最短路徑，最后加以比較分析得出結(jié)論。6.1.2 優(yōu)化算法的應(yīng)用例3 我們在圖1-1中使用優(yōu)化算法求起點(diǎn)0到終點(diǎn)3的最短路徑。解 將圖1-1進(jìn)行劃分。在圖1-1中可以看到起始0與終點(diǎn)3由?。?,3）直接相連。故它們之間的最短路徑一定在這條弧附近。所以以這條弧為界將圖1-1劃分成三個子圖，分別為圖1-2、圖1-3和圖1-4.841423030 圖 1-2304403183510710552圖 1-4圖 1-3由這三個子圖，可以馬上確定出

16、源點(diǎn)0到終點(diǎn)3之間的最短路徑在圖1-3中，是路徑0253，權(quán)為22.可以看出優(yōu)化后的算法中劃分子圖的過程直觀易懂，算法步驟也更為簡單，確實(shí)有效提高了算法效率。6.2 優(yōu)化算法算法過程容易理解，可以求出圖中任意兩個節(jié)點(diǎn)之間的最短路徑。但是每次討論圖中任意兩個節(jié)點(diǎn)間的最短路徑都要將其余所有節(jié)點(diǎn)考慮一遍（插點(diǎn)法），這樣會耗費(fèi)大量運(yùn)算時間，因此我們介紹一種的優(yōu)化算法。6.2.1 優(yōu)化算法思想在使用算法進(jìn)行插點(diǎn)之前，我們先規(guī)定一個集合，它表示所有入度不為0的節(jié)點(diǎn)集合。然后后續(xù)的插點(diǎn)過程就只在集合中選點(diǎn)，直到成為空集，求得題目中要求的兩節(jié)點(diǎn)間的最短路徑。這樣就要求每次經(jīng)過的中間點(diǎn)入度必須大于0，裁剪掉了不

17、可能經(jīng)過的中間節(jié)點(diǎn)，避免了無謂的計(jì)算，節(jié)省了運(yùn)算時間。6.2.2 優(yōu)化算法的應(yīng)用2378 1251003614圖 1-4例4 用優(yōu)化算法求圖1-4中節(jié)點(diǎn)0到節(jié)點(diǎn)4的最短路徑。解 ：節(jié)點(diǎn)0與節(jié)點(diǎn)4之間沒有直接的弧相連，考慮插入剩余節(jié)點(diǎn)（節(jié)點(diǎn)1、節(jié)點(diǎn)2和節(jié)點(diǎn)3）。 ：節(jié)點(diǎn)1,節(jié)點(diǎn)2，節(jié)點(diǎn)3中入度大于0的節(jié)點(diǎn)集合=（節(jié)點(diǎn)1,節(jié)點(diǎn)2）。 ：在節(jié)點(diǎn)0與節(jié)點(diǎn)4之間只插入節(jié)點(diǎn)1，路徑一：014. ：在節(jié)點(diǎn)0與節(jié)點(diǎn)4之間插入節(jié)點(diǎn)1和節(jié)點(diǎn)2，路徑二：0124. 故得到節(jié)點(diǎn)0與節(jié)點(diǎn)4之間最短路徑為 路徑一：014. 在上述求解過程中可以看出優(yōu)化算法相比未優(yōu)化前的方法減少了中間入度為0的節(jié)點(diǎn)3的討論。對于節(jié)點(diǎn)數(shù)比較

18、多的帶權(quán)有向圖，在求解圖中任意節(jié)點(diǎn)間的最短路徑時，優(yōu)化算法能夠更加顯示出它的算法優(yōu)越性，提高計(jì)算效率。7 結(jié)束語以上我們主要討論了針對求節(jié)點(diǎn)間最短路徑的算法和算法，通過介紹兩種算法，了解了它們各自的算法核心思想，也探討了在實(shí)際問題中兩種算法存在的不足之處，并加以簡單優(yōu)化思維。這次研究不僅讓我們深入了解了算法和算法，體會這兩種經(jīng)典算法的巨大魅力，也拓展了我們的思維，優(yōu)化處理環(huán)節(jié)確實(shí)能夠讓我們感受到數(shù)學(xué)學(xué)科的強(qiáng)大生命力與價值，這是我們每一個數(shù)學(xué)研究者都引以為傲的地方。數(shù)學(xué)來源于生活，服務(wù)于生活。生活中處處體現(xiàn)著數(shù)學(xué)思想，數(shù)學(xué)讓我們享受更加智慧的生活。最短路徑問題涉及到我們生活的方方面，算法和算法為我們提供了有利的解決途徑。特別是物流業(yè)要理解兩種算法的基本思想并能夠簡靈活應(yīng)用于實(shí)際操作中，進(jìn)而實(shí)現(xiàn)資源的高效配置?，F(xiàn)代社會中充滿了討論最優(yōu)化的思想理念，無論是企業(yè)市場還是事業(yè)單位都在不斷地追求如何使用最少的投資達(dá)到最大的收益。可見，研究最優(yōu)問題是十分有意義與價值的。最優(yōu)化理念不僅可以節(jié)約資源，降低成本，實(shí)現(xiàn)最大限度的收益；進(jìn)而達(dá)到資源的最大限度利用，有利于建成資源節(jié)約型，環(huán)境友好型的和諧社會。參考文獻(xiàn)：1 阮潔,鐘寶榮.算法在物流配送運(yùn)輸中的最短路徑優(yōu)化研究J.計(jì)算機(jī)光盤