贪婪算法制定船舶物流航线.docx

文档介绍：
贪婪算法制定船舶物流航线

一、总论
所谓贪婪技术就是在每一步操作中，“贪婪”地选择最佳操作，并希望通过一系列局部的最优选择进而对全局问题产生一个最优解。贪婪算法的思想经常在日常生活中左右着我们处理问题时所采取的行为。最简单的例子就是我们在买菜的时候总是想花最少的钱去买最好的菜，在进行选择时如果两家菜的质量一样，我们显然会去选择其中价格最低的那一家来进行购买，这其实就是最为朴素的贪婪算法。在现代社会中物流产业已经成为国民经济发展的动脉，其发展程度可以说是衡量一国现代化程度和综合国力的重要标志之一，被喻为促进经济增长的“加速器”。然而目前我们国内整体物流成本占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个需求点，我们就需要在该无向图中找