李 東，嚴(yán) 義，王丹東，王 強(qiáng)

(杭州電子科技大學(xué)計(jì)算機(jī)學(xué)院，浙江 杭州 310018)

必經(jīng)節(jié)點(diǎn)集約束型無環(huán)最短路徑算法研究

李 東，嚴(yán) 義，王丹東，王 強(qiáng)

(杭州電子科技大學(xué)計(jì)算機(jī)學(xué)院，浙江 杭州 310018)

基于遺傳算法和Dijkstra算法，提出了解決必經(jīng)點(diǎn)集約束型無環(huán)最短路徑問題的方法.將研究問題分解為只含源點(diǎn)、目的節(jié)點(diǎn)和必經(jīng)節(jié)點(diǎn)集的非對稱旅行商問題和消除環(huán)路問題.首先利用遺傳算法求解非對稱旅行商問題得到最優(yōu)必經(jīng)點(diǎn)序列.但求解得到的最優(yōu)必經(jīng)點(diǎn)序列組成的路徑是有環(huán)路徑，為解決環(huán)路問題，設(shè)計(jì)了分段Dijkstra破環(huán)策略.通過實(shí)驗(yàn)分析驗(yàn)證了算法是有效可行的，相對于傳統(tǒng)方法，在時(shí)間效率上有較大的提升.

必經(jīng)節(jié)點(diǎn)集約束；遺傳算法；Dijkstra；最短路徑；消除環(huán)路

0 引 言

隨著電子商務(wù)、網(wǎng)絡(luò)通信等不斷發(fā)展，對約束型路徑規(guī)劃，特別是必經(jīng)節(jié)點(diǎn)集約束型路徑規(guī)劃的需求日益增加.對于最短路徑問題的研究已非常普遍，其中對旅行商問題(Traveling Salesman Problem，TSP)的研究最為廣泛，可采用蟻群算法、遺傳算法、LKH算法等來解決TSP問題[1-3]，但TSP問題只是求解從源點(diǎn)出發(fā)經(jīng)過所有節(jié)點(diǎn)最終回到源點(diǎn)的最短路徑問題.Adam N.L.等[4]提出了用于解決子旅行商問題(Subset Traveling Salesman Problem, STSP)的方法，STSP問題要求路徑需訪問指定節(jié)點(diǎn)集，但目標(biāo)路徑可以存在環(huán)路.馮琳耀等[5]提出通過幾何代數(shù)算法解決經(jīng)過特定節(jié)點(diǎn)且路徑節(jié)點(diǎn)數(shù)最少的問題，該算法關(guān)注點(diǎn)在于經(jīng)過的節(jié)點(diǎn)數(shù)目少而不是經(jīng)過的路徑最短問題，且只適用于無向圖，對于有向圖最短路問題無法適用.黃書力等[6]基于Dijkstra算法提出了求解源點(diǎn)到目的節(jié)點(diǎn)經(jīng)過指定中間節(jié)點(diǎn)集的最短路徑問題，該算法求得的路徑是一條有環(huán)路徑，且只能用于求解無向無權(quán)網(wǎng)絡(luò).在網(wǎng)絡(luò)規(guī)模小且必經(jīng)點(diǎn)數(shù)目極少的情況下，可使用回溯法和動(dòng)態(tài)規(guī)劃等來解決研究問題[7],然而隨著網(wǎng)絡(luò)規(guī)模和必經(jīng)節(jié)點(diǎn)集規(guī)模的增加，回溯法和動(dòng)態(tài)規(guī)劃等精確算法的時(shí)間復(fù)雜度成指數(shù)級增加，在指定時(shí)間內(nèi)根本無法解決此類問題.

針對此類問題，本文將復(fù)雜的問題分解為非對稱旅行商問題(Asymmetric Travelling Salesman Problem,ATSP)和消除環(huán)路問題，通過遺傳算法和Dijkstra分段策略分別求解，并對問題進(jìn)行了數(shù)學(xué)抽象和算法實(shí)現(xiàn).

圖1 必經(jīng)點(diǎn)集約束型無環(huán)最短路徑問題示例圖

1 問題描述與定義

1.1 問題描述

本文研究的問題是在帶權(quán)有向網(wǎng)絡(luò)中，求解從源節(jié)點(diǎn)經(jīng)過指定節(jié)點(diǎn)集到目的節(jié)點(diǎn)的最短路徑，且路徑中無環(huán)路，問題的實(shí)例網(wǎng)絡(luò)如圖1所示.源點(diǎn)V0到目的節(jié)點(diǎn)V1的最短路徑是V0-V1,權(quán)值和為1，經(jīng)過必經(jīng)節(jié)點(diǎn)集{V2,V3}且無環(huán)的最短路徑為V0-V2-V3-V1，權(quán)值和為5.V0-V3-V2-V3-V1這條路徑權(quán)值和雖然較小(權(quán)值和為4)，但這條路徑存在回路，不滿足問題要求.

1.2 問題定義

給定一個(gè)帶權(quán)有向圖G(V,E)，V={v1,v2,…,vn}為頂點(diǎn)集，E={e1,e2,…,en}為有向邊集，每條有向邊的權(quán)重為wij.對于給定源點(diǎn)s和目的節(jié)點(diǎn)t，以及必經(jīng)節(jié)點(diǎn)集V′?V-{s，t}，找出從s到t的無環(huán)最短路徑P，使得P通過V′中所有節(jié)點(diǎn)，簡稱為(s-V′-t)最短路問題.設(shè)x∈(0,1)，若弧(i,j)在路徑P中，xij=1，否則xij=0，則問題的數(shù)學(xué)模型是：

求解

(1)

(2)

(3)

(4)

Vp∩V′=V′

(5)

其中，約束(2)和(3)定義了一條源點(diǎn)到目的節(jié)點(diǎn)t的路徑；約束(4)是避免路徑P中出現(xiàn)環(huán)路；約束(5)要求路徑P經(jīng)過必經(jīng)節(jié)點(diǎn)集V′中的每一個(gè)節(jié)點(diǎn).

2 算法設(shè)計(jì)與實(shí)現(xiàn)

2.1 算法總體設(shè)計(jì)

首先將原網(wǎng)絡(luò)轉(zhuǎn)換為只含源點(diǎn)、目的節(jié)點(diǎn)和必經(jīng)節(jié)點(diǎn)集的子網(wǎng)絡(luò)，子網(wǎng)絡(luò)中節(jié)點(diǎn)間的權(quán)重為原網(wǎng)絡(luò)中節(jié)點(diǎn)間的最短路徑長度，然后將(s-V′-t)最短路問題分解為從源點(diǎn)經(jīng)過所有子網(wǎng)絡(luò)節(jié)點(diǎn)到達(dá)目的節(jié)點(diǎn)的最短路徑問題，這其實(shí)是一個(gè)特殊的ATSP問題，可以利用改進(jìn)的遺傳算法求解此類ATSP問題得到最優(yōu)必經(jīng)點(diǎn)序列，最后利用Dijkstra分段破環(huán)策略求對最優(yōu)必經(jīng)點(diǎn)序列路徑進(jìn)行破環(huán)操作.

2.2 簡化網(wǎng)絡(luò)結(jié)構(gòu)

定義1在一個(gè)網(wǎng)絡(luò)中，若一個(gè)節(jié)點(diǎn)的出度之和為0或者入度之和為0，那么該節(jié)點(diǎn)稱為邊緣節(jié)點(diǎn).

定義2在一個(gè)網(wǎng)絡(luò)中，若一個(gè)節(jié)點(diǎn)的出度之和及入度之和均為0，那么該節(jié)點(diǎn)稱為孤立節(jié)點(diǎn).

簡化網(wǎng)絡(luò)結(jié)構(gòu)就是從原網(wǎng)絡(luò)中刪除目標(biāo)路徑中必然不包含的節(jié)點(diǎn).若某必經(jīng)節(jié)點(diǎn)為孤立或邊緣節(jié)點(diǎn)，那么目標(biāo)路徑是不存在的.若一個(gè)節(jié)點(diǎn)為孤立節(jié)點(diǎn)或者邊緣節(jié)點(diǎn)，該節(jié)點(diǎn)必然不會出現(xiàn)在目標(biāo)路徑中，則可以刪除此類節(jié)點(diǎn)以及以此類節(jié)點(diǎn)為起點(diǎn)或終點(diǎn)的弧.通過刪除孤立節(jié)點(diǎn)和邊緣節(jié)點(diǎn)，降低網(wǎng)絡(luò)規(guī)模，提高算法的執(zhí)行效率.

2.3 改進(jìn)遺傳算法求解最優(yōu)必經(jīng)點(diǎn)序列

最優(yōu)必經(jīng)點(diǎn)序列是特殊的ATSP問題，遺傳算法是基于“適者生存”的一種高度并行、隨機(jī)和自適應(yīng)的優(yōu)化算法，具備較好的全局搜索能力，能夠快速搜索出解空間中的全體解，而不會陷入局部極值[8]，故可以用來求解ATSP問題.在實(shí)際應(yīng)用中，遺傳算法的局部搜索能力較差，以致于單純的遺傳算法十分費(fèi)時(shí)，在迭代后期搜索效率較低，為此本文通過改進(jìn)遺傳算法的選擇和變異操作，大大提高了遺傳算法的收斂速度和求值能力.

遺傳算法求解實(shí)際問題主要步驟是：問題的描述和編碼、產(chǎn)生初始種群、構(gòu)造適應(yīng)度函數(shù)、選擇、交叉、變異算子的選取等.下面將根據(jù)(s-V′-t)最短路問題進(jìn)行逐一討論.

2.3.1 問題的描述和編碼

遺傳算法求解TSP問題常見的編碼方式有順序編碼、近鄰編碼、矩陣編碼、路徑編碼等[9]，由于路徑編碼是最符合本文問題邏輯的編碼方式，經(jīng)過每一個(gè)必經(jīng)點(diǎn)且不會產(chǎn)生回路，所以本文采用路徑編碼，源點(diǎn)為起始編碼，目的節(jié)點(diǎn)為終止編碼，中間編碼為必經(jīng)點(diǎn)序列.如編碼0231表示圖1中V0節(jié)點(diǎn)依次經(jīng)過V2，V3到達(dá)V1的一條路徑.

2.3.2 初始種群的產(chǎn)生

由于起始編碼和終止編碼是確定的，所以初始種群的產(chǎn)生只關(guān)注必經(jīng)節(jié)點(diǎn)集的排列順序.必經(jīng)節(jié)點(diǎn)序列的編碼方式采用隨機(jī)方式和啟發(fā)式方式，其中90%的初始種群通過隨機(jī)產(chǎn)生，10%通過啟發(fā)式產(chǎn)生，結(jié)合A*算法[10]，啟發(fā)式方式是從源點(diǎn)開始，距離上一編碼和終止編碼之和最近的點(diǎn)作為該條染色體當(dāng)前位編碼.混合產(chǎn)生方法能加快算法的收斂速度.

2.3.3 適應(yīng)度函數(shù)的構(gòu)造

適應(yīng)度函數(shù)的構(gòu)造是遺傳算法的重要組成部分，直接影響遺傳算法的收斂速度和成敗.最優(yōu)必經(jīng)點(diǎn)序列不僅要求路徑長度短而且要求序列中的環(huán)路數(shù)量少，為此本文在設(shè)計(jì)適應(yīng)度函數(shù)時(shí)，充分考慮了這兩方面的需求.設(shè)染色體路徑長度為Rd，路徑中出現(xiàn)的環(huán)路數(shù)量為n，每個(gè)環(huán)路懲罰權(quán)值為a，經(jīng)過反復(fù)驗(yàn)證，a取網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)量與網(wǎng)絡(luò)中邊的最大權(quán)重的乘積效果最優(yōu).當(dāng)n越小，路徑長度Rd越小，越容易遺傳到下一代，所以適應(yīng)度函數(shù)取路徑長度和環(huán)路懲罰值之和的倒數(shù)，即：

(6)

(7)

適應(yīng)度函數(shù)的設(shè)計(jì)加入了環(huán)路懲罰機(jī)制，降低必經(jīng)點(diǎn)優(yōu)秀序列中存在環(huán)的可能性，可以大大降低破環(huán)的難度，提升了算法的效率和準(zhǔn)確性.

2.3.4 選擇操作

選擇操作是從種群中選擇優(yōu)勝染色體，常用策略有輪盤賭選擇和錦標(biāo)賽選擇等[11].本文為了加快遺傳算法的收斂速度，選用輪盤賭選擇和錦標(biāo)賽選擇混合的策略，對適應(yīng)度值進(jìn)行排序得到一定比例的前N個(gè)最優(yōu)染色體直接進(jìn)入下一代，剩余染色體通過輪盤賭方式選擇.

2.3.5 交叉策略

本文采用交叉策略是最常見的路徑交叉策略，把一對父代部分染色體片段進(jìn)行交換重組生成一對新的染色體過程，這種交叉策略理論已經(jīng)十分成熟，本文不作詳細(xì)論述.

2.3.6 變異策略

互換變異是常用的路徑變異策略，將一條染色體中的兩個(gè)基因片段互換.反轉(zhuǎn)變異是另一種常用的路徑變異策略，將染色體片段進(jìn)行反轉(zhuǎn).但是這兩種變異策略的搜索鄰域范圍都比較小，為克服遺傳算法局部搜索能力差的缺點(diǎn)，本文構(gòu)造了大鄰域搜索變異策略(Bigger Neighborhood Search Mutation Strategy, BNSMS).BNSMS策略的主要思想如下：

BNSMS策略主要結(jié)合反轉(zhuǎn)變異和交換變異，遺傳算法進(jìn)行第一次迭代時(shí)采用變鄰域反轉(zhuǎn)變異策略，可以選擇出接近最優(yōu)值的一條路徑，之后各代均采用交換變異策略，這樣可以有效的跳出局部最優(yōu).變鄰域反轉(zhuǎn)變異策略步驟如下：

1)獲取交叉后的當(dāng)前最優(yōu)解P′(s-b1-…-bi-…-bj-…-bn-t)；

2)因?yàn)槭怯邢蚓W(wǎng)絡(luò)，故通過染色體片段反轉(zhuǎn)，擴(kuò)大變異的搜索鄰域，保持種群的多樣性，基于這個(gè)思路，提出了循環(huán)反轉(zhuǎn)方案進(jìn)一步擴(kuò)大搜索鄰域，偽代碼如下：

BNSMS變異策略不僅可以防止早熟，跳出局部最優(yōu)，還具備較強(qiáng)的局部搜索能力，同時(shí)可以擴(kuò)大搜索鄰域，從而加快收斂速度.

2.4 解決環(huán)路問題

通過改進(jìn)遺傳算法求得優(yōu)秀必經(jīng)點(diǎn)序列，雖然在遺傳算法中加入了降低環(huán)路數(shù)量處理，但依然不能保證路徑中沒有環(huán)路，若存在環(huán)路，需要進(jìn)一步破環(huán)處理.基于Dijkstra算法，本文提出了一重Dijkstra破環(huán)策略和二重Dijkstra破環(huán)策略.一重Dijkstra破環(huán)策略如下：

1)對路徑P′(s-b1-…-bi-…-bj-…-bn-t)進(jìn)行分段破環(huán)求出當(dāng)前段最優(yōu)路徑，保存到P中，并將這段路徑中的節(jié)點(diǎn)禁忌，不允許出現(xiàn)在之后的路徑中.如通過分段Dijkstra算法依次求(s-b1)、(b1-b2)…(bn-t)之間的最短路徑，若(s-b1)中求得的路徑為(s-v1-v2-b1)，則節(jié)點(diǎn){s,v1,v2}需要禁忌，再分段Dijkstra求(b1-b2)時(shí)，{s,v1,v2}不會出現(xiàn)在此時(shí)(b1-b2)的最短路徑中.

2)若某段優(yōu)秀序列(bi-bi+1)中進(jìn)行分段破環(huán)時(shí)無法求出通路，說明(bi-bi+1)中的必走節(jié)點(diǎn)被前面求出的最短路徑序列占用，需要分段打開之前的禁忌路徑節(jié)點(diǎn)，再對當(dāng)前序列對和打開序列對這兩組序列對進(jìn)行先后分段破環(huán)，若兩段同時(shí)能夠連通，說明這兩組序列對之間的路徑均為較好路徑.若不能夠同時(shí)連通，則說明當(dāng)前序列對被占用的必走節(jié)點(diǎn)集不在被打開序列中，再依次向前打開釋放禁忌節(jié)點(diǎn).

二重破環(huán)是在一重破環(huán)失敗的前提下使用的，說明兩個(gè)不能連通的必經(jīng)點(diǎn)之間的路徑必走節(jié)點(diǎn)集被前面的兩個(gè)或兩個(gè)以上的必經(jīng)點(diǎn)序列對占用.主要思想和一重破環(huán)類似，最大的區(qū)別是一重破環(huán)每次打開一組必經(jīng)點(diǎn)序列對，而兩重破環(huán)是同時(shí)打開兩組必經(jīng)點(diǎn)序列對.若一重破環(huán)和二重破環(huán)都無法成功破環(huán)，說明遺傳算法求得的優(yōu)秀必經(jīng)點(diǎn)序列不是最優(yōu)序列，此時(shí)將本次的優(yōu)秀序列作為初始種群中的一條染色體繼續(xù)尋優(yōu).根據(jù)算法的特點(diǎn)，無論是遺傳算法求解必經(jīng)點(diǎn)最優(yōu)序列還是環(huán)路破環(huán)策略，其時(shí)間復(fù)雜度主要與必經(jīng)點(diǎn)集規(guī)模有關(guān)，算法的總體流程如圖2所示.

圖2 算法流程

3 實(shí)驗(yàn)結(jié)果及分析

本文的實(shí)驗(yàn)環(huán)境是Ubuntu系統(tǒng)，2.2 GHz i3 CPU，算法采用C++語言實(shí)現(xiàn).網(wǎng)絡(luò)實(shí)例和必經(jīng)節(jié)點(diǎn)集均是隨機(jī)生成.網(wǎng)絡(luò)實(shí)例的源點(diǎn)為1，目的節(jié)點(diǎn)為節(jié)點(diǎn)數(shù)目|V|.

3.1 驗(yàn)證算法的正確性

網(wǎng)絡(luò)實(shí)例如圖3所示，具有36個(gè)節(jié)點(diǎn)，弧段數(shù)為108，必經(jīng)節(jié)點(diǎn)集規(guī)模為6，記為G(36,6).求解從源點(diǎn)1經(jīng)必經(jīng)節(jié)點(diǎn)集{18,19,24,28,29,35}到達(dá)目的節(jié)點(diǎn)36的最短路徑.根據(jù)2.2節(jié)描述的簡化網(wǎng)絡(luò)方法刪除邊緣節(jié)點(diǎn)17,6,8,25以及刪除以源節(jié)點(diǎn)1為終點(diǎn)的弧和以目的節(jié)點(diǎn)36為起點(diǎn)的弧，簡化網(wǎng)絡(luò)如圖4所示.

圖3 G(36,6)實(shí)例網(wǎng)絡(luò)

圖4 G(36,6)簡化網(wǎng)絡(luò)

通過改進(jìn)遺傳算法求得的必經(jīng)點(diǎn)最優(yōu)序列為1-35-19-29-24-28-18-36，但這條最優(yōu)序列組成的路徑是有環(huán)路徑，如表1所示，必經(jīng)點(diǎn)29到必經(jīng)點(diǎn)24之間的路徑必須要經(jīng)過節(jié)點(diǎn)16，而節(jié)點(diǎn)16已經(jīng)出現(xiàn)在必經(jīng)點(diǎn)19到必經(jīng)點(diǎn)29的路徑中，這樣就形成環(huán)路，導(dǎo)致節(jié)點(diǎn)29與節(jié)點(diǎn)24之間在無環(huán)情況下無法連通，這時(shí)需要將節(jié)點(diǎn)19，16從禁忌節(jié)點(diǎn)集中刪除，先后通過分段破環(huán)策略計(jì)算節(jié)點(diǎn)29到節(jié)點(diǎn)24和節(jié)點(diǎn)19到節(jié)點(diǎn)29之間的最短路徑，使得兩段路徑能夠同時(shí)連通.

表1 小規(guī)模網(wǎng)絡(luò)有環(huán)路徑

小規(guī)模網(wǎng)絡(luò)破環(huán)過程如表2所示，最優(yōu)不成環(huán)路徑序列為1-5-32-35-31-19-14-20-27-26-29-15-13-23-24-28-18-36，路徑權(quán)值和32，是網(wǎng)絡(luò)G(36,6)中從源點(diǎn)1經(jīng)過必經(jīng)節(jié)點(diǎn)集到節(jié)點(diǎn)25的最短路徑耗時(shí)10 ms，實(shí)驗(yàn)結(jié)果表明本文提出的算法是有效可行的.

表2 小規(guī)模網(wǎng)絡(luò)破環(huán)過程

3.2 算法效率分析

圖5展示的是必經(jīng)點(diǎn)集規(guī)模大小為48的情況下，隨著網(wǎng)絡(luò)規(guī)模的增大，算法執(zhí)行時(shí)間的變化情況，圖6展示的是網(wǎng)絡(luò)規(guī)模為2 000時(shí)，隨著必經(jīng)點(diǎn)集規(guī)模的增大，算法的執(zhí)行時(shí)間變化情況.可以發(fā)現(xiàn)，在必經(jīng)點(diǎn)集規(guī)模一定的情況下，算法執(zhí)行時(shí)間變化較為平緩，但在網(wǎng)絡(luò)規(guī)模一定的情況下，當(dāng)必經(jīng)節(jié)點(diǎn)集規(guī)模超出98時(shí)，隨著必經(jīng)節(jié)點(diǎn)集規(guī)模的增大，算法執(zhí)行時(shí)間急劇增加，充分體現(xiàn)了本文算法的時(shí)間復(fù)雜度主要與必經(jīng)節(jié)點(diǎn)集規(guī)模有關(guān)，對于大規(guī)模網(wǎng)絡(luò)而必經(jīng)點(diǎn)相對少的情況下，本文算法是十分高效可行的.

圖5 指定必經(jīng)節(jié)點(diǎn)集規(guī)模算法時(shí)間

圖6 指定網(wǎng)絡(luò)規(guī)模算法時(shí)間

表3展示的是當(dāng)必經(jīng)點(diǎn)集規(guī)模為10時(shí)，網(wǎng)絡(luò)節(jié)點(diǎn)規(guī)模分別為25,50,100條件下，加入減枝的回溯法和本文算法的平均運(yùn)行時(shí)間與最短路徑長度.

表3 2種算法在必經(jīng)節(jié)點(diǎn)集規(guī)模為10條件下的實(shí)驗(yàn)結(jié)果

從表3中可以看出，本文算法和減枝優(yōu)化的回溯法求解的最短路徑權(quán)值相近.由于回溯法是確定型算法，可以求解出解空間里的所有解，本文算法的時(shí)間消耗相對于減枝優(yōu)化的回溯法有了量級上的縮減，特別是隨著網(wǎng)絡(luò)規(guī)模的增加，回溯法的時(shí)間消耗成指數(shù)級增長，回溯法只適合求解小規(guī)模網(wǎng)絡(luò)的必經(jīng)節(jié)點(diǎn)集約束型無環(huán)最短路問題，所以本文算法的整體性能優(yōu)于回溯法等確定型算法.

4 結(jié)束語

本文基于改進(jìn)遺傳算法和Dijkstra破環(huán)策略提出了解決必經(jīng)點(diǎn)集約束型無環(huán)最短路問題的算法，通過加入BNSMS變異策略，提高了遺傳算法的收斂速度，擴(kuò)大了遺傳算法的局部搜索能力.對于節(jié)點(diǎn)規(guī)模大而必經(jīng)節(jié)點(diǎn)集規(guī)模小(100以內(nèi))的網(wǎng)絡(luò)有較高的效率，但隨著必經(jīng)節(jié)點(diǎn)集的增加，算法的時(shí)空效率逐漸減弱，該問題有待進(jìn)一步研究和探討.

[1] 張泓,李愛平,劉雪梅.面向TSP求解的混合蟻群算法[J].計(jì)算機(jī)工程,2009,35(8):34-37.

[2] 蔡光躍,董恩清.遺傳算法和蟻群算法在求解TSP問題上的對比分析[J].計(jì)算機(jī)工程與應(yīng)用,2007,43(10):96-98.

[3] LIN Z W, FU J Z, SHEN H Y. Tool path generation for multi-axis freeform surface finishing with the LKH TSP solver[J]. Computer-Aided Design, 2015,69:51-61.

[4] LETCHFORD A N, Nasiri S D, Theis D O. Compact formulations of the Steiner Traveling Salesman Problem and related problems[J]. European Journal of Operational Research, 2013,228(1):83-92.

[5] 馮琳耀,袁林旺,羅文,等.節(jié)點(diǎn)約束型最短路徑的幾何代數(shù)算法[J].電子學(xué)報(bào),2014,42(5):846-851.

[6] 黃書力,胡大裟,蔣玉明.經(jīng)過指定的中間節(jié)點(diǎn)集的最短路徑算法[J].計(jì)算機(jī)工程與應(yīng)用,2015,51(11):41-46.

[7] IBARAKI T. Algorithms for Obtaining Shortest Paths Visiting Specified Nodes[J]. Siam Review, 1973,15(2):309-317.

[8] 曾文飛,張英杰,顏玲.遺傳算法的基本原理及其應(yīng)用研究[J].軟件導(dǎo)刊,2009(9):54-56.

[9] 孫年芳.遺傳算法求解TSP問題[J].長春理工大學(xué)學(xué)報(bào)(高教版),2009(2):123-124.

[10] 吳宏超,劉檢華,唐承統(tǒng),等.基于改進(jìn)A*算法的管路自動(dòng)布局設(shè)計(jì)與優(yōu)化方法[J].計(jì)算機(jī)集成制造系統(tǒng),2016,22(4):945-954.

[11] 王小平,曹立明.遺傳算法理論、應(yīng)用與軟件實(shí)現(xiàn)[M].西安:西安交通大學(xué)出版社，2002:10-12.

ResearchontheLoop-freeShortestPathAlgorithmwithNecessaryNodesConstraint

LI Dong, YAN Yi, WANG Dandong, WANG Qiang

(SchoolofComputer,HangzhouDianziUniversity,HangzhouZhejiang, 310018,China)

Based on the genetic algorithm and the Dijkstra algorithm, a method to solve the problem of the loop-free shortest path with necessary nodes constraint is proposed. The problem is decomposed into a special asymmetric ATSP problem and eliminates the loop path problem. Firstly, this paper uses genetic algorithm to solve the problem of special asymmetric ATSP and then obtains the optimal sequence of necessary nodes set. But the path composed of the optimal sequence consists of loop. In order to solve the problem of loop path, a segmented Dijkstra destruction strategy is designed. Finally, it is proved that the algorithm is effective and feasible through the experiments. And compared with the traditional method, the efficiency of time has been greatly improved.

necessary nodes constraint; genetic algorithm; Dijkstra; shortest path; eliminate the loop path

TP301.6

A

1001-9146(2017)05-0044-07

2016-00-00

李東(1989-)，男，安徽臨泉人，碩士研究生，嵌入式與智能控制.通信作者：嚴(yán)義教授，E-mail：yybjyyj@163.com.

10.13954/j.cnki.hdu.2017.05.009