一種快速尋找最短路徑的算法

朱世宇 張洪明

摘要：最短路徑算法是計算機科學(xué)與地理信息科學(xué)等領(lǐng)域的研究熱點。從工業(yè)機械運動到城市道路網(wǎng)絡(luò)，最短路徑算法是其中不可或缺的一部分。最短路徑問題是圖論研究中的一個經(jīng)典算法問題，旨在尋找由結(jié)點和路徑組成的圖中兩結(jié)點之間的最短路徑。主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。本文介紹了一種以最鄰算法為基礎(chǔ)進(jìn)行改進(jìn)的算法。

關(guān)鍵詞：最短路徑 算法 圖論

中圖分類號：TP301 文獻(xiàn)標(biāo)識碼：A 文章編號：1007-9416（2016）07-0115-02

1 引言

最短路徑算法是計算機科學(xué)與地理信息科學(xué)等領(lǐng)域的研究熱點。從工業(yè)機械運動到城市道路網(wǎng)絡(luò)，最短路徑算法是其中不可或缺的一部分。本文以試驗坐標(biāo)點為例子討論了采用最短路徑算法的優(yōu)勢，并提出了一種快速尋找最短路徑的算法。在很多文獻(xiàn)中，研究人員已提出過多種關(guān)于路徑優(yōu)化的問題的求解算法[1～4]。本文在綜合最優(yōu)路徑的算法研究上主要提出了1種基于最鄰算法的改進(jìn)算法。

2 區(qū)域最鄰算法

以表1所示的坐標(biāo)進(jìn)行試驗，在未進(jìn)行優(yōu)化的時候，按其原有的排列順序進(jìn)行移動，其運動軌跡如圖1所示，以試驗坐標(biāo)點為單位，從第一個點到最后一個點運動路程共7252.39。

從圖1可以看出，未對坐標(biāo)進(jìn)行優(yōu)化之前，運動軌跡非常的混亂。使用最鄰算法對表1坐標(biāo)進(jìn)行排序后，得到表2，按其排列順序進(jìn)行移動，其運動軌跡如圖2所示，以坐標(biāo)為單位，從第一個點到最后一個點運動路程共3642.559。

圖2的移動的路徑較之前的運行軌跡更加合理[5]，但是經(jīng)過研究其實還有提升的空間。本文在最近鄰方法上，進(jìn)行了改進(jìn)，使用了一種區(qū)域劃分的方式將整個打坐標(biāo)分布的區(qū)域劃分別劃分為橫縱的5行。如果是以縱向的寬度劃分區(qū)域的話，那么從第一行起，坐標(biāo)的排列順序為橫向從小到大排列，而第二行則是從大到小，第三行再從小到大，以此類推。而如果是以橫向劃分區(qū)域，則是以縱向進(jìn)行大小排列。以縱向劃分方式對表1中的坐標(biāo)排序后，得到表3，按其排列順序進(jìn)行移動，其運動軌跡如圖3所示，以坐標(biāo)為單位，從第一個點到最后一個點運動路程共4004.745。

3 結(jié)語

以試驗坐標(biāo)為例，優(yōu)化后的機械手移動路徑比未經(jīng)優(yōu)化的路徑節(jié)約路程7252.39-2324.798=4927.59，節(jié)省了約原來一半多的的路程。

參考文獻(xiàn)

[1]Wu C G， Liang Y C ， Lee H P ， et al. Generalized chromosome genetic algorithm for generalized traveling salesman problems and its applications for machining[J]. Physical Review E ， 2004 ， 70（1）：1～13.

[2]Dimitrijevic V ， Saric Z. Efficient transformation of the generalized traveling salesman problem into the traveling salesman.problem on digraphs[J].Information Sciences，1997，102（1～4）：105～110.

[3]Lien Y N ， Ma E ， Wah Benjamin W S. Transformation of the generalized trav-eling-salesman an problem into the standard trav2eling2salesman problem[J].Information Sciences，1993，74（1～2）：177～189.

[4]Tsai I C F ， Tsai C W， Tseng C C. A new hybrid heuristic approach for solving large traveling salesman problem[J].Infor2 mation Sciences，2004，166（1～4）：67～81.

[5]趙赫，杜端甫.TSP的鄰域搜索算法的分析和改進(jìn)[J].中國管理科，1997，5（1）：35～39.