朱世宇 張洪明

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

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

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

1 引言

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

2 區(qū)域最鄰算法

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

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

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

3 結(jié)語(yǔ)

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

參考文獻(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].中國(guó)管理科，1997，5（1）：35～39.