過必經(jīng)點(diǎn)集且具有額外硬約束的最短路徑算法

郭展羽，張志明，賀蘭山，鄭家齊，趙師兵，康 琦

同濟(jì)大學(xué) 電子與信息工程學(xué)院，上海200092

最短路徑問題一直是運(yùn)籌學(xué)、計(jì)算機(jī)科學(xué)、地理信息科學(xué)、交通運(yùn)輸?shù)阮I(lǐng)域的研究熱點(diǎn)，并廣泛應(yīng)用到公共交通運(yùn)輸網(wǎng)絡(luò)規(guī)劃、無人自動(dòng)駕駛、機(jī)器人自主導(dǎo)航等的實(shí)際問題中[1-6]。現(xiàn)實(shí)生活里有許多問題都可以抽象轉(zhuǎn)化為最短路徑問題，路徑規(guī)劃要求根據(jù)某種優(yōu)化準(zhǔn)則，在給定的真實(shí)環(huán)境中尋找到一條從起始位置到目標(biāo)位置可行并且代價(jià)最小的路徑。研究如何有效地計(jì)算和求解最短路徑問題，其面臨的難點(diǎn)是如何在較短的時(shí)間內(nèi)找到較為完備的解。根據(jù)對(duì)環(huán)境信息的掌握程度不同，路徑規(guī)劃可分為全局路徑規(guī)劃和局部路徑規(guī)劃，兩者沒有本質(zhì)上的區(qū)別。經(jīng)典的全局路徑規(guī)劃算法有Dijkstra算法[7]和A*算法[8]等，可以靜態(tài)地規(guī)劃出最優(yōu)或次優(yōu)路線。近年來，國內(nèi)外學(xué)者在此基礎(chǔ)上，引入啟發(fā)式算法和仿生算法等，提出多種最短路徑改進(jìn)算法[9-16]，如模擬退火法、蟻群算法、遺傳算法、粒子群算法、深度優(yōu)先算法和廣度優(yōu)先算法等，并在解決過必經(jīng)點(diǎn)集的最短路徑問題上已經(jīng)取得很好的成效，康文雄等人[9]通過分層回溯的Dijkstra 算法，有效地減少問題求解的計(jì)算時(shí)間；Daniele 等人[10]對(duì)約束最短路徑漫游問題（constrained shortest path tour problem，CSPTP）提出新的數(shù)學(xué)模型和高效的分支定界方法；王磊等人[14]使用改進(jìn)的A*算法，對(duì)最短路徑段進(jìn)行拼接，使運(yùn)算效率得到顯著提高。

在探究路徑規(guī)劃算法的過程中，應(yīng)用場(chǎng)景由于物理?xiàng)l件的限制會(huì)存在額外硬約束條件，而上述算法在處理此類問題時(shí)，往往需要簡化前置條件，忽略硬約束，導(dǎo)致實(shí)際解算過程中會(huì)存在求解難度高、求解速度慢、求解結(jié)果不可靠甚至不可行等的不足，需要做出相應(yīng)改進(jìn)。本文以第十五屆全國大學(xué)生智能車競賽室外光電組總決賽實(shí)車比賽[17]為例，將比賽賽道抽象建模為無向帶權(quán)圖表示，提出一種基于深度優(yōu)先搜索的隨機(jī)搜索算法，以解決具有額外硬約束條件下過必經(jīng)點(diǎn)集的最短路徑問題。該算法的創(chuàng)新點(diǎn)在于，搜索過程中對(duì)路徑的可行性加入額外硬約束條件進(jìn)行實(shí)時(shí)判定，在給定的真實(shí)環(huán)境中最終尋找到過必經(jīng)點(diǎn)集的最優(yōu)或次優(yōu)的最短路徑。

1 問題描述

1.1 背景

第十五屆全國大學(xué)生智能車競賽室外光電組總決賽采用G型等比縮小的無人車模，場(chǎng)景化地復(fù)現(xiàn)人工智能在實(shí)際領(lǐng)域中的應(yīng)用。無人車在長寬17 m×10.5 m大小的場(chǎng)地內(nèi)進(jìn)行比賽，賽道由若干區(qū)域連通而成，分布如圖1（a）和圖1（b）中所示。比賽要求無人車從起點(diǎn)區(qū)域處出發(fā)并開始計(jì)時(shí)，規(guī)劃合理的路徑，經(jīng)過賽道上若干所有指定的區(qū)域后到達(dá)指定終點(diǎn)區(qū)域，停止計(jì)時(shí)并判定完賽，最終的比賽成績按完成時(shí)間進(jìn)行排名；無人車在未經(jīng)過所有指定區(qū)域之前到達(dá)終點(diǎn)，不會(huì)停止計(jì)時(shí)。起點(diǎn)區(qū)域、終點(diǎn)區(qū)域，以及中途要經(jīng)過的若干區(qū)域和無人車的發(fā)車方向，在比賽開始前隨機(jī)指定給出。無人車在運(yùn)行途中可以多次通過賽場(chǎng)中的某個(gè)賽道區(qū)域，且經(jīng)過隨機(jī)指定區(qū)域的先后順序不限，但需要至少穿過一次指定區(qū)域。

本文即在此背景下展開工作，解算無人車在給定起點(diǎn)和終點(diǎn)之間的最短路徑。舉例如下：如圖1（b）中所示，設(shè)比賽要求從起點(diǎn)（start）vs=1出發(fā)，經(jīng)過指定區(qū)域（pass）vp={2，7，10}后到達(dá)終點(diǎn)（destination）vd=6。通過直接觀察可以得出最優(yōu)解，即路徑1→2→10→7→6為最短路徑，如圖1（c）中所示；該賽道可以建模抽象為無向帶權(quán)圖如圖1（d）中所示。然而，在面臨比賽現(xiàn)場(chǎng)更加復(fù)雜的環(huán)境要素時(shí)，需要將該最短路徑問題建立合適的數(shù)學(xué)模型，引入硬約束條件后，設(shè)計(jì)合適的算法，才能進(jìn)行快速且完備的求解。

圖1 應(yīng)用場(chǎng)景示意圖Fig.1 Schematic diagram of match field

1.2 建模

圖1 所示的賽道區(qū)域位置圖可以抽象成一個(gè)無向帶權(quán)圖，權(quán)值即為賽道圖中點(diǎn)與點(diǎn)之間的路程距離。假設(shè)無人車在各段賽道上的行駛速度一致，則可以將時(shí)間最優(yōu)化目標(biāo)轉(zhuǎn)換為總路程最優(yōu)化目標(biāo)，將該問題抽象為過必經(jīng)點(diǎn)集的最短路徑問題。與此同時(shí)，本次最優(yōu)化問題還存在有額外的硬約束：無人車ART-RC底盤機(jī)械尺寸為560 mm（長）×350 mm（寬）×230 mm（高），由于賽道寬度的限制，使得無人車無法調(diào)頭行駛，即路徑中不能存在包含相鄰節(jié)點(diǎn)的子路徑A→B→A（設(shè)A、B 為相鄰節(jié)點(diǎn)）；由于無人車車模轉(zhuǎn)彎半徑的物理?xiàng)l件限制，無人車在實(shí)際賽道上無法轉(zhuǎn)過轉(zhuǎn)角小于90°的彎道（銳角彎，即急彎，下文稱為“銳角彎”），如對(duì)于圖1（b）中的路徑8→7→10，無人車無法通過，但路徑8→7和7→10，在無向帶權(quán)圖（d）中存在，且不能通過預(yù)處理的方法將該路徑從圖中剔除。

依據(jù)上文所述優(yōu)化目標(biāo)和約束條件，可以轉(zhuǎn)化為如下給定的一個(gè)無向帶權(quán)圖G(P,E) 數(shù)學(xué)模型，其中P={p1,p2,…,pn}為節(jié)點(diǎn)集，E={e1,e2,…,en}為無向邊集，設(shè)ωij為連接pi節(jié)點(diǎn)和pj節(jié)點(diǎn)的無向邊的權(quán)值。必經(jīng)點(diǎn)集P′?P-{s,d}，其中s和d分別為路徑規(guī)劃的起點(diǎn)和終點(diǎn)。硬約束條件邊集H，其內(nèi)部的邊元素由前中后三個(gè)節(jié)點(diǎn)構(gòu)成，如上文所舉例的{8,7,10}。最短路徑可以有兩種等價(jià)的表示形式：以節(jié)點(diǎn)集描述的最短路徑Wp={pa,pb,…,px,py}和以無向邊集描述的最短路徑We={eab,ebc,…,exy}。求解滿足以下約束條件的優(yōu)化目標(biāo)函數(shù)獲得最短路徑。

其中，式（1）表明以路徑最短為優(yōu)化目標(biāo)；式（2）為約束條件之一，要求路徑Wp經(jīng)過必經(jīng)點(diǎn)集P′中的每一個(gè)節(jié)點(diǎn)；式（3）為約束條件之二，要求路徑滿足額外硬約束條件。

因此，在求解過必經(jīng)點(diǎn)集的最短路徑問題的過程中，受到如上文所述額外硬約束的限制。為了便于程序處理并計(jì)算數(shù)據(jù)，將抽象出來的無向帶權(quán)圖轉(zhuǎn)化為二維鄰接矩陣，矩陣中存有圖中任意相鄰兩點(diǎn)之間的距離。當(dāng)兩點(diǎn)不是相鄰時(shí)，距離值設(shè)為-1；點(diǎn)與其自身的距離值設(shè)為0。

1.3 變量定義

定義算法中的相關(guān)變量，如表1中所示。設(shè)定算法中路徑規(guī)劃的起點(diǎn)節(jié)點(diǎn)start、面朝點(diǎn)節(jié)點(diǎn)next（小車運(yùn)行方向前方選擇的后一個(gè)節(jié)點(diǎn)，從起點(diǎn)出發(fā)時(shí)即為所選擇經(jīng)過的第一個(gè)節(jié)點(diǎn)）、必經(jīng)點(diǎn)集point_list[]和終點(diǎn)所在節(jié)點(diǎn)區(qū)域destination等，根據(jù)這些參數(shù)計(jì)算出一條可行的最優(yōu)路徑；在計(jì)算的過程中，分別定義當(dāng)前搜索到的路徑way[]、已知路徑當(dāng)中的最短路徑temp_way[]和最終的最優(yōu)最短路徑shortest_way[]；無向帶正權(quán)圖的所有信息保存到一個(gè)二維鄰接矩陣dis[][]。

表1 變量定義1Table 1 Variable definition in algorithm，part 1

額外硬約束（“point_constraint”）：將指定的額外硬約束條件存放在一個(gè)列表當(dāng)中，作為參數(shù)進(jìn)行設(shè)定，在進(jìn)行路徑搜索時(shí)，對(duì)搜索得出的解進(jìn)行是否滿足額外硬約束的判定，即判斷解路徑中是否含有額外硬約束當(dāng)中的子路徑。硬約束使用連續(xù)三個(gè)點(diǎn)作為約束，中點(diǎn)作為索引，如在圖1中，路徑2→3→11為不可通行的銳角彎，故point_constraint[3]中含有[2，3，11]；路徑3→11→5 也是不可通行的銳角彎，故point_constraint[11]中含有[3，11，5]，以此類推。將完整的硬約束提前設(shè)定好，供搜索時(shí)使用。

2 算法實(shí)現(xiàn)

算法主要分為預(yù)處理和核心算法兩個(gè)部分實(shí)現(xiàn)。預(yù)處理階段通過一定的步驟，將使用者輸入的信息轉(zhuǎn)化為后續(xù)階段核心算法所需要的信息，完成對(duì)問題的無向帶權(quán)圖的處理和建模。核心算法部分則使用基于深度優(yōu)先的隨機(jī)搜索算法，在滿足額外硬約束的要求下，求解過必經(jīng)點(diǎn)集的最短路徑問題。

2.1 預(yù)處理

2.1.1 輸入?yún)?shù)

通過程序輸入起點(diǎn)start、起點(diǎn)時(shí)的面朝點(diǎn)next、終點(diǎn)destination和存放在point_list[]當(dāng)中的必經(jīng)點(diǎn)序號(hào)列表，額外硬約束條件由point_constraint[]變量載入，圖的信息以鄰接矩陣的形式存放在文件當(dāng)中讀入。

2.1.2 相鄰點(diǎn)查找函數(shù)

輸入的鄰接矩陣僅僅描述了各點(diǎn)之間的距離，預(yù)處理時(shí)使用查找函數(shù)尋找遍歷各節(jié)點(diǎn)位置上的所有相鄰點(diǎn)，算法流程如圖2所示，具體步驟列舉如下：

圖2 相鄰點(diǎn)查找算法流程圖Fig.2 Flow chart of adjacent point set search algorithm

（1）得到圖的大小，創(chuàng)建合適的數(shù)據(jù)結(jié)構(gòu)變量存儲(chǔ)各點(diǎn)的相鄰點(diǎn)信息，首先求得圖中節(jié)點(diǎn)的個(gè)數(shù)length，然后以維度為length的一個(gè)列表對(duì)象用以存儲(chǔ)變量。

（2）對(duì)圖中任意未遍歷的點(diǎn)進(jìn)行探索，判斷其與其余點(diǎn)的距離，如果距離大于0，則代表兩點(diǎn)相鄰，將后點(diǎn)加入前點(diǎn)的相鄰點(diǎn)列表。

（3）重復(fù)步驟（2），直到圖中所有的點(diǎn)均被遍歷。

（4）最后得到完整的相鄰點(diǎn)列表choices 并存儲(chǔ)。

對(duì)于本次賽題，預(yù)處理后得到賽道無向帶權(quán)圖中①～?各個(gè)節(jié)點(diǎn)的相鄰點(diǎn)列表，具體為[[2，9]，[1，3，4，10]，[2，4，11]，[2，3，5]，[4，6，11]，[5，7]，[6，8，10]，[7，9，10]，[1，8]，[2，7，8，11]，[3，5，10]]。

2.1.3 預(yù)處理階段的輸出

預(yù)處理工作結(jié)束后，得到如前所述的各項(xiàng)初始參數(shù)：start，next，destination，point_list[]，dis[][]，choices[]。

2.2 核心算法描述

2.2.1 參數(shù)定義

有效路徑次數(shù)限制（t_limit）：使用隨機(jī)搜索時(shí)，需要設(shè)置一個(gè)上限值來結(jié)束路徑的查找，每當(dāng)找到一條符合條件的路徑時(shí)，有效路徑次數(shù)（t）加1。次數(shù)上限值越高，計(jì)算的結(jié)果最優(yōu)性也就越高，但相對(duì)的，時(shí)間與空間的消耗也就越大。

路徑長度限制（L_limit）：使用深度優(yōu)先的隨機(jī)算法尋找一條路徑時(shí)，限制路徑的長度（L）有助于結(jié)束對(duì)過長路徑做無意義的搜索，可以節(jié)省每次路徑搜索所耗費(fèi)的時(shí)間和空間，但是相對(duì)的，如果受到限制后無法求得解，則需把該限制放寬。這個(gè)值不應(yīng)該大于任意一條能遍歷圖上所有節(jié)點(diǎn)的路徑長度的兩倍，否則就失去效用。如圖1 中的路徑1→2→10→7→6→5→4→3→11→10→8→9→1 可以循環(huán)遍歷所有節(jié)點(diǎn)，當(dāng)起點(diǎn)要求為vs=10，終點(diǎn)要求為vd=1，要經(jīng)過vp={2，7，6}時(shí)，按上文所述的這條路徑則需要經(jīng)過10→7→6→5→4→3→11→10→8→9→1→2→10→7→6→5→4→3→11→10→8→9→1。由此可以得到結(jié)論，最多循環(huán)走過該條路徑兩次可以保證該問題有解。

狀態(tài)定義：在搜索時(shí)，每一個(gè)狀態(tài)含有參數(shù)的定義：當(dāng)前點(diǎn)（now），即當(dāng)前點(diǎn)的序號(hào)；當(dāng)前路徑（way[]），即由多次循環(huán)當(dāng)中的多個(gè)當(dāng)前點(diǎn)形成；前點(diǎn)（pre），即當(dāng)前路徑中前一點(diǎn)的序號(hào)；當(dāng)前距離（d），即當(dāng)前路徑總的距離長度。

變量定義總結(jié)成表格如表2所示。

表2 變量定義2Table 2 Variable definition in algorithm，part 2

2.2.2 偽代碼描述

（1）最短路徑求解函數(shù)

算法1 最短路徑求解

（2）必經(jīng)點(diǎn)路由判斷函數(shù)

算法2 必經(jīng)點(diǎn)路由判斷

（3）硬約束條件狀態(tài)判斷函數(shù)

算法3 硬約束條件判斷

其中變量point_constraint即為本問題中的額外硬約束條件參數(shù)，以節(jié)點(diǎn)7 為例，point_constraint[7]=[[8，7，10]，[10，7，8]]，經(jīng)過判斷即可得出該路徑的可行性。

2.2.3 算法流程圖描述

算法流程圖如圖3中所示，各步驟簡述如下：

圖3 核心算法流程圖Fig.3 Flow chart of core algorithm

（1）初始化搜索狀態(tài)，將變量L_limit歸零，所有臨時(shí)路徑和節(jié)點(diǎn)清空。

（2）隨機(jī)探索下一個(gè)非前點(diǎn)（pre），并更換搜索的狀態(tài)。探索的方式是從當(dāng)前點(diǎn)的相鄰點(diǎn)列表中，排除前點(diǎn)后隨機(jī)選擇一個(gè)。

（3）判斷是否到達(dá)終點(diǎn)。若否，重復(fù)步驟（2）。

（4）判斷是否過所有必經(jīng)點(diǎn)。若否，重復(fù)步驟（2）。對(duì)必經(jīng)點(diǎn)集的各點(diǎn)進(jìn)行逐個(gè)判斷。

（5）判斷是否滿足額外硬約束。任意截取長度為3的子路徑，判斷是否為point_constraint列表中的元素：若是，則不滿足額外硬約束；若否，重復(fù)步驟（2）。

（6）比較路徑長度與已知最短長度，如果當(dāng)前路徑較短則替換為最短路徑。

（7）判斷是否超過次數(shù)限定，若否，重復(fù)步驟1。

（8）輸出最短路徑。

3 實(shí)驗(yàn)測(cè)試與結(jié)果分析

實(shí)驗(yàn)測(cè)試環(huán)境為：Windows 10操作系統(tǒng)，Intel 2.3 GHz i5-8300H CPU，8 GB 內(nèi)存，編程語言為Python3.7，編程環(huán)境為PyCharm Community Edition 2020.2.3。使用第十五屆全國大學(xué)生智能車競賽室外光電組總決賽賽題[17]的賽道建模數(shù)據(jù)進(jìn)行仿真測(cè)試，所獲得的最短路徑用于實(shí)車測(cè)試。

3.1 時(shí)間效率和最優(yōu)率的影響因素——必經(jīng)點(diǎn)集中節(jié)點(diǎn)個(gè)數(shù)

在程序當(dāng)中設(shè)置計(jì)時(shí)器記錄程序運(yùn)行時(shí)間來粗略計(jì)算算法的時(shí)間效率。在其他點(diǎn)不變的情況下，增加必經(jīng)點(diǎn)集中節(jié)點(diǎn)的個(gè)數(shù)，每次實(shí)驗(yàn)取100次最優(yōu)輸出進(jìn)行結(jié)果平均。此次實(shí)驗(yàn)條件為：start=1，next=2，destination=6，t_limit=20，L_limit=20，同時(shí)實(shí)驗(yàn)結(jié)果還必須滿足額外的硬約束，即不能轉(zhuǎn)過小于90°的銳角彎賽道且不能倒車。取實(shí)驗(yàn)結(jié)果的平均值記錄在表3。

由實(shí)驗(yàn)結(jié)果可見，在序號(hào)為1、2、3 和序號(hào)為4、5 的實(shí)驗(yàn)中得到的解算時(shí)間結(jié)果相差較大，數(shù)值不在一個(gè)數(shù)量級(jí)，但最優(yōu)率都為100%，最優(yōu)率的問題將留在后續(xù)的實(shí)驗(yàn)2進(jìn)行討論。針對(duì)時(shí)間結(jié)果，經(jīng)過分析可知求解花費(fèi)時(shí)間較大差異的原因：經(jīng)過點(diǎn)v={3}的最短路徑同時(shí)也經(jīng)過vm={5，7}，所以計(jì)算時(shí)通過隨機(jī)搜索容易搜索到最優(yōu)解，而因?yàn)関n={9，11}沒有出現(xiàn)在此路徑中，當(dāng)需要經(jīng)過它們的時(shí)候，需要更多的時(shí)間去搜索。其余實(shí)驗(yàn)條件不變的情況下，必經(jīng)點(diǎn)集選為{3，9}，重做實(shí)驗(yàn)6驗(yàn)證上述分析，表3中給出實(shí)驗(yàn)相關(guān)結(jié)果。比較實(shí)驗(yàn)1、2、3、6的結(jié)果，可發(fā)現(xiàn)該算法的效率更多地取決于中間節(jié)點(diǎn)集的選取，而不是由中間節(jié)點(diǎn)的數(shù)量決定。由于解算過程中使用隨機(jī)搜索的算法，同一種實(shí)驗(yàn)條件下，不同次實(shí)驗(yàn)之間的時(shí)間可能會(huì)存在比較大的差異，但多次重復(fù)實(shí)驗(yàn)后得到的時(shí)間結(jié)果會(huì)穩(wěn)定在一定均值附近范圍內(nèi)。

表3 必經(jīng)節(jié)點(diǎn)集的影響Table 3 Impact of choosing necessary node set

3.2 時(shí)間效率和最優(yōu)率的影響因素——t_limit參數(shù)

基于實(shí)驗(yàn)1，在僅僅選取3、9 兩點(diǎn)時(shí)平均需要消耗6.710 s的時(shí)間，此時(shí)的實(shí)驗(yàn)條件中t_limit設(shè)為20。將該數(shù)值從小到大變化，進(jìn)行100次實(shí)驗(yàn)取實(shí)驗(yàn)結(jié)果的平均值，將其變化對(duì)時(shí)間效率和最優(yōu)率的影響記錄在表4，其中最優(yōu)率為所求路徑結(jié)果中，最優(yōu)路徑（可能有多種）數(shù)量占所有路徑結(jié)果數(shù)量的比率。由表4 中的實(shí)驗(yàn)結(jié)果可以看出，當(dāng)t_limit設(shè)為較小的數(shù)時(shí)，計(jì)算時(shí)間較短，最優(yōu)率低；當(dāng)t_limit參數(shù)值增大時(shí)，運(yùn)行時(shí)間變長，最優(yōu)率增加；當(dāng)設(shè)為10及以上數(shù)值時(shí)，最優(yōu)率可增長到97%以上直至100%。

表4 參數(shù)t_limit 的影響Table 4 Impact of t_limit parameter

3.3 不同算法對(duì)TSP問題求解的效果

本文提出的過必經(jīng)點(diǎn)集且具有額外硬約束的最短路徑搜索算法也可以用以解決旅行商問題（traveling salesman problem，TSP），按如下參數(shù)進(jìn)行初始設(shè)置：起點(diǎn)start=1，面朝點(diǎn)next=2，終點(diǎn)destination=1，必經(jīng)點(diǎn)集point_list=[3，4，5，6，7，8，9，10，11]。和爬山法（hill climbing，HC）、模擬退火法（simulated annealing，SA）、遺傳算法（genetic algorithm，GA）等算法[18]做對(duì)比實(shí)驗(yàn)，實(shí)驗(yàn)分別測(cè)試100次，取實(shí)驗(yàn)結(jié)果的平均值，列舉如表5中所示。

表5 不同算法效果之間的比較Table 5 Comparison results of different algorithms

從實(shí)驗(yàn)結(jié)果可以看到，在多種算法之間，爬山法的計(jì)算速度最快，遺傳算法的計(jì)算速度最慢。從理論上分析，這三種傳統(tǒng)算法，會(huì)犧牲解的質(zhì)量來提高計(jì)算的速度，具體表現(xiàn)為爬山法較其余算法更容易陷入局部最優(yōu)解。但在本次實(shí)驗(yàn)中由于計(jì)算規(guī)模較小，解的質(zhì)量差異不明顯，在此僅討論求解時(shí)間和最優(yōu)結(jié)果?？梢钥吹角叭N傳統(tǒng)算法給出的最優(yōu)結(jié)果均是：[1，2，10，11，3，4，5，6，7，8，9]，如圖4 中虛線所示，很明顯，所包含的中間路徑[…，2，10，11，…]是不滿足額外硬約束的，無人車無法轉(zhuǎn)過此處的賽道轉(zhuǎn)角。而本文提出的算法給出的最優(yōu)結(jié)果是：[1，2，10，7，6，5，4，3，11，10，8，9]，如圖4中實(shí)線所示，其中沒有包含違反額外硬約束條件的中間路徑，無人車可以順利完成任務(wù)。盡管本文算法在計(jì)算時(shí)間上不具有絕對(duì)的優(yōu)勢(shì)，但是可以有針對(duì)性地解決具有額外硬約束的過必經(jīng)點(diǎn)集的最短路徑問題。

圖4 不同算法求解得到的最短路徑示意圖Fig.4 Schematic diagram of obtained shortest path

4 結(jié)束語

本文對(duì)“過必經(jīng)點(diǎn)集且具有額外硬約束的最短路徑問題”進(jìn)行抽象處理，并提出基于深度優(yōu)先搜索的隨機(jī)搜索算法。實(shí)驗(yàn)測(cè)試表明，該算法具有可以添加額外的硬約束、解的最優(yōu)性好的優(yōu)勢(shì)。由于該算法是采用隨機(jī)搜索的算法，時(shí)間效率上受必經(jīng)節(jié)點(diǎn)數(shù)目的影響較小，但受必經(jīng)節(jié)點(diǎn)元素集的選取影響較大，難以得出統(tǒng)一的評(píng)判標(biāo)準(zhǔn)。通過TSP問題的求解對(duì)比實(shí)驗(yàn)，該算法相比于傳統(tǒng)算法，盡管在計(jì)算時(shí)間上不具有絕對(duì)的優(yōu)勢(shì)，但是針對(duì)性地解決具有額外硬約束的過必經(jīng)點(diǎn)集最短路徑問題。該算法的優(yōu)勢(shì)在于代碼量少、最優(yōu)性好，可以解決額外硬約束問題，同時(shí)容易調(diào)整參數(shù)。