導(dǎo)語：貪婪算法制定船舶物流航線一文來源于網(wǎng)友上傳，不代表本站觀點(diǎn)，若需要原創(chuàng)文章可咨詢客服老師，歡迎參考。

一、總論

所謂貪婪技術(shù)就是在每一步操作中，“貪婪”地選擇最佳操作，并希望通過一系列局部的最優(yōu)選擇進(jìn)而對全局問題產(chǎn)生一個(gè)最優(yōu)解。貪婪算法的思想經(jīng)常在日常生活中左右著我們處理問題時(shí)所采取的行為。最簡單的例子就是我們在買菜的時(shí)候總是想花最少的錢去買最好的菜，在進(jìn)行選擇時(shí)如果兩家菜的質(zhì)量一樣，我們顯然會(huì)去選擇其中價(jià)格最低的那一家來進(jìn)行購買，這其實(shí)就是最為樸素的貪婪算法。在現(xiàn)代社會(huì)中物流產(chǎn)業(yè)已經(jīng)成為國民經(jīng)濟(jì)發(fā)展的動(dòng)脈，其發(fā)展程度可以說是衡量一國現(xiàn)代化程度和綜合國力的重要標(biāo)志之一，被喻為促進(jìn)經(jīng)濟(jì)增長的“加速器”。然而目前我們國內(nèi)整體物流成本占GDP的比例比較較高，下降速度也是非常緩慢，這就反映出我國的物流效益整體水平仍然較低。而通過物流網(wǎng)絡(luò)的合理化，可以在很大程度上降低物流成本，提高物流效益。本文就單獨(dú)以船舶物流航線來進(jìn)行討論。我們的整個(gè)航運(yùn)系統(tǒng)可以用聯(lián)節(jié)點(diǎn)（港務(wù)中心、需求點(diǎn)）和航運(yùn)路線構(gòu)成的航運(yùn)網(wǎng)絡(luò)來表示。我們首先需要制定出一個(gè)航運(yùn)網(wǎng)絡(luò)，然后再確定出它的港務(wù)中心，最后以該港務(wù)中心為出發(fā)點(diǎn)制定航線。

二、問題分析

從計(jì)算機(jī)圖論的角度出發(fā)我們可以將某個(gè)物流區(qū)域歸納為一個(gè)圖L=（V，E），其中的Vi為航運(yùn)網(wǎng)絡(luò)圖結(jié)點(diǎn)（港務(wù)中心、需求點(diǎn)），Eij=［Vi，Vj］為連接節(jié)點(diǎn)Vi，Vj的邊并且有一個(gè)非負(fù)權(quán)值Q（Eij）=Qij用來記錄兩個(gè)聯(lián)節(jié)點(diǎn)之間的路徑的損耗，那么我們最后所求得的配送路線即可以看作是一個(gè)小生成樹，并且是圖L的一個(gè)子圖L*=（V*，E*），且V包含V*，E包含E*。如上圖1所示，假設(shè)無向圖L表示一個(gè)航運(yùn)網(wǎng)絡(luò)，而其中的V0，V1，V2，V3，V4，V5，V6，V7，V8，V9，V10，V11，V12，V13分別表示十四個(gè)聯(lián)節(jié)點(diǎn)，E01，E02，E23等分別為各個(gè)聯(lián)結(jié)點(diǎn)之間的路徑。而在路徑上的數(shù)字則表示兩個(gè)結(jié)點(diǎn)之間路徑的權(quán)值。

三、通過Dijkstra算法確定港務(wù)中心

Dijkstra算法的思想是：首先，求出從起點(diǎn)到最接近起點(diǎn)的頂點(diǎn)之間的最短路徑，然后求出第二近的，以此類推。推而廣之，在第i次迭代開始以前，該算法已經(jīng)確定了i-1條連接起點(diǎn)和離起點(diǎn)最近頂點(diǎn)之間的最短路徑。運(yùn)用這種Dijkstra算法的效率取決于圖本身的數(shù)據(jù)結(jié)構(gòu)，以及表示集合V-Vm（Vm是指已經(jīng)加入到子樹中的結(jié)點(diǎn)的集合）的優(yōu)先隊(duì)列的數(shù)據(jù)結(jié)構(gòu)。如果我們采用數(shù)組存儲(chǔ)的方式來進(jìn)行運(yùn)算的話，我們的時(shí)間復(fù)雜度將會(huì)屬于O（|V|2）。假設(shè)我們所參考的圖的權(quán)值足夠準(zhǔn)確，我們就可以將與其他結(jié)點(diǎn)最短路徑之和最小的那個(gè)結(jié)點(diǎn)用來作為我們整個(gè)航運(yùn)網(wǎng)絡(luò)的港務(wù)中心。運(yùn)算結(jié)果如下：1300iid=807，1310iid=629，通過上述計(jì)算結(jié)果我們可以知道結(jié)點(diǎn)V3到其他結(jié)點(diǎn)的最短路徑之和最小，所以在無向圖L之中最適合做其港務(wù)中心的結(jié)點(diǎn)就是V3。而結(jié)點(diǎn)V13到其他結(jié)點(diǎn)的最短路徑之和最大，因此是最不適合選作港務(wù)中心的結(jié)點(diǎn)。

四、用改良后的Prim算法來計(jì)算最佳航路

1．Prim算法介紹Prime算法是圖論中求最小生成樹的一種經(jīng)典算法。它是解決下述問題的一種有效方法：假設(shè)我們在一個(gè)無向圖中需要經(jīng)過n個(gè)需求點(diǎn)，我們就需要在該無向圖中找出n－1條邊使包含該n個(gè)結(jié)點(diǎn)的生成樹在保持連通的同時(shí)還要使權(quán)的總和最小。通過上面的描述我們可以看到，Prim算法也可以用來解決在一個(gè)航運(yùn)網(wǎng)絡(luò)中求最短航運(yùn)線路的問題。其具體步驟如下：令無向圖L=（V，E），其生成樹的頂點(diǎn)集合為Vm。

（1）首先我們將把港務(wù)中心結(jié)點(diǎn)V3加入到Vm中。

（2）在所有的Vm與V－Vm結(jié)點(diǎn)之間尋找在其中權(quán)值最小的邊e∈E并將這一條邊加入到該生成樹之中。

（3）把步驟二中所找到的邊e所對應(yīng)的屬于V－Vm之中的結(jié)點(diǎn)V*加入Vt集合。這時(shí)進(jìn)行檢測如果發(fā)現(xiàn)Vm集合之中已經(jīng)包含有所需要的n個(gè)元素，則算法結(jié)束；否則繼續(xù)執(zhí)行步驟二。

2．并行Prim算法當(dāng)然在實(shí)際情況中，在同一個(gè)航運(yùn)網(wǎng)絡(luò)之中往往同時(shí)運(yùn)行有兩條或兩條以上的航運(yùn)線路。而用傳統(tǒng)的Prim算法就無法解決這種問題，而需要對其進(jìn)行改進(jìn)。首先我們需要確定港務(wù)中心所需要派出的船舶組數(shù)，如果是需要兩組運(yùn)輸船舶那么我們最后所得出的結(jié)果應(yīng)為兩個(gè)子樹L1（V*1，E*1），L2（V*2，E*2）其分別對應(yīng)兩組航運(yùn)線路。下面是以無向圖L為例子的算法分析。第一步：首先在我們之前計(jì)算出來各個(gè)結(jié)點(diǎn)到其他結(jié)點(diǎn)的所有最短路徑之和中找出數(shù)值最大的那個(gè)結(jié)點(diǎn)，在無向圖L中為V13.第二步：然后再找出V13的所有鄰邊之中權(quán)值最小的一條邊E11-13并將此邊加入到結(jié)果子樹L1的邊集E*1中，并將V13，V11加入到子樹L1的點(diǎn)集V*1中。接著再用Prim算法找出結(jié)點(diǎn)V11，V13到港務(wù)中心V3的最短路徑V3-V5-V10-V11-V13并將該路徑上的所有結(jié)點(diǎn)和邊均加入子樹L1中。第三步：根據(jù)圖三選擇除港務(wù)中心結(jié)點(diǎn)外到其他結(jié)點(diǎn)所有最短路徑之和最小的結(jié)點(diǎn)，判斷該結(jié)點(diǎn)是否在V*1中，若在，則接著去找次小值的結(jié)點(diǎn)繼續(xù)判斷。直到發(fā)現(xiàn)滿足條件的結(jié)點(diǎn)并將此結(jié)點(diǎn)的鄰邊中權(quán)值最小的一條邊加入到結(jié)果子樹L2邊集E*2中。然后用Prim算法找出該結(jié)點(diǎn)到物流中心的最短路徑，并將該路徑上的所有結(jié)點(diǎn)和邊均加入子樹L2中。無向圖L中除了港務(wù)中心結(jié)點(diǎn)外到其他結(jié)點(diǎn)所有最短路徑之和最小的結(jié)點(diǎn)是V5，但是V5已經(jīng)存在于V*1中了，因此我們需要找次小值V4繼續(xù)判斷，發(fā)現(xiàn)V4不在V*1中，因此，我們就將V4的最小臨邊E47加入到L2的邊集E*2中，將V4，V7加入到L2的點(diǎn)集V*2中。然后找出V4，V7到港務(wù)中心V3的最短路徑V3–V4–V7并將其加入到子樹L2中。第四步：對于剩余的孤立結(jié)點(diǎn)，我們可以先計(jì)算出他們分別連接到兩個(gè)子樹所產(chǎn)生的路徑長度，取其中較小者將其加入。假如該結(jié)點(diǎn)到兩條子樹的路徑增加值均相同，則我們需要考慮子樹總路徑的長度，選擇子樹總路徑長度最小的那一條將其并入。在本例中還有V0，V1，V2，V6，V8，V9，V12，七個(gè)結(jié)點(diǎn)，分別判斷其加入到L1或L2后路徑長度的增加值。V6離子樹L2近加入子樹L2后其長度增加值為5，V8離子樹L2近加入子樹L2后其長度增加值為11，V9離子樹L2近加入子樹L2后其長度增加值為15，V12離子樹L1近加入子樹L1后其長度增加值為10，V2離子樹L2近加入子樹L2后其長度增加值為20，V1離子樹L1近加入子樹L1后其長度增加值為25，V0離子樹L2近加入子樹L2后其長度增加值為23。因此這里選擇先將V1，V12加入到子樹L1中，而將V0，V2，V6，V8，V9這五個(gè)結(jié)點(diǎn)加入到子樹L2中。通過上述運(yùn)算，我們在無向圖L中求出了兩個(gè)子樹L1、L2也就是得到了兩條航運(yùn)線路。他們最終生成子圖如下。

五、總結(jié)

本文首先運(yùn)用貪婪算法在一個(gè)航運(yùn)網(wǎng)絡(luò)的各個(gè)結(jié)點(diǎn)之中，找出適合作為港務(wù)中心的結(jié)點(diǎn)。然后本文又利用一種改進(jìn)的Prim算法，在整個(gè)航運(yùn)網(wǎng)絡(luò)中找出兩條航運(yùn)線路來提高整個(gè)物流網(wǎng)絡(luò)的工作效率，并盡可能的降低物流損耗。然而要真正制定出符合實(shí)際的物流線路，其關(guān)鍵還是在于無向圖中的“權(quán)”值的制定，這也是本人今后工作的研究方向之一。