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

一、總論

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

二、問題分析

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

三、通過Dijkstra算法確定港務中心

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

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

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

（1）首先我們將把港務中心結點V3加入到Vm中。

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

（3）把步驟二中所找到的邊e所對應的屬于V－Vm之中的結點V*加入Vt集合。這時進行檢測如果發現Vm集合之中已經包含有所需要的n個元素，則算法結束；否則繼續執行步驟二。

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

五、總結

本文首先運用貪婪算法在一個航運網絡的各個結點之中，找出適合作為港務中心的結點。然后本文又利用一種改進的Prim算法，在整個航運網絡中找出兩條航運線路來提高整個物流網絡的工作效率，并盡可能的降低物流損耗。然而要真正制定出符合實際的物流線路，其關鍵還是在于無向圖中的“權”值的制定，這也是本人今后工作的研究方向之一。