• <tr id="yyy80"></tr>
  • <sup id="yyy80"></sup>
  • <tfoot id="yyy80"><noscript id="yyy80"></noscript></tfoot>
  • 99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

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

    2022-09-21 05:38:28郭展羽張志明賀蘭山鄭家齊趙師兵
    關(guā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ù)。

    猜你喜歡
    約束條件賽道無人
    自制冰墩墩不能滑出“法律賽道”
    公民與法治(2022年4期)2022-08-03 08:20:24
    基于一種改進(jìn)AZSVPWM的滿調(diào)制度死區(qū)約束條件分析
    科創(chuàng)引領(lǐng),搶跑新賽道
    走向世界(2022年3期)2022-04-19 12:38:58
    征服蒙特卡洛賽道
    無人戰(zhàn)士無人車
    反擊無人機(jī)
    A literature review of research exploring the experiences of overseas nurses in the United Kingdom (2002–2017)
    無人駕駛,先上賽道如何?
    空中之家(2017年11期)2017-11-28 05:28:21
    詩到無人愛處工
    岷峨詩稿(2017年4期)2017-04-20 06:26:43
    無人超市會(huì)流行起來嗎?
    国产精品久久久久久久电影 | 国产不卡一卡二| 日韩三级视频一区二区三区| 午夜精品久久久久久毛片777| 日本三级黄在线观看| 亚洲午夜理论影院| 国产av在哪里看| 亚洲18禁久久av| 两个人视频免费观看高清| 夜夜夜夜夜久久久久| 国产激情偷乱视频一区二区| 午夜福利在线观看免费完整高清在 | 真实男女啪啪啪动态图| 亚洲中文字幕日韩| 国产成年人精品一区二区| 亚洲国产精品成人综合色| 又爽又黄无遮挡网站| 在线国产一区二区在线| 国产三级中文精品| 淫秽高清视频在线观看| 亚洲成a人片在线一区二区| 免费一级毛片在线播放高清视频| www.自偷自拍.com| 亚洲av电影在线进入| 99精品久久久久人妻精品| 两个人看的免费小视频| 一级黄色大片毛片| 亚洲,欧美精品.| 欧美成人一区二区免费高清观看 | 国产成年人精品一区二区| 日韩高清综合在线| 99热这里只有是精品50| 99久久久亚洲精品蜜臀av| 亚洲av美国av| 别揉我奶头~嗯~啊~动态视频| 国产精品一区二区免费欧美| av在线蜜桃| 97超视频在线观看视频| 一本一本综合久久| 99热这里只有是精品50| 国内少妇人妻偷人精品xxx网站 | 日韩精品中文字幕看吧| 黄色女人牲交| 亚洲成av人片免费观看| 99久久精品一区二区三区| 国产aⅴ精品一区二区三区波| 又黄又爽又免费观看的视频| 国产伦精品一区二区三区视频9 | 久久这里只有精品19| 美女被艹到高潮喷水动态| 国产一级毛片七仙女欲春2| 国产91精品成人一区二区三区| 免费搜索国产男女视频| 中文字幕最新亚洲高清| 两个人的视频大全免费| 亚洲狠狠婷婷综合久久图片| 美女高潮的动态| 久久精品国产综合久久久| 国产三级中文精品| 日日干狠狠操夜夜爽| 成年女人毛片免费观看观看9| 精品99又大又爽又粗少妇毛片 | 国产精品久久视频播放| 高潮久久久久久久久久久不卡| 欧美三级亚洲精品| 亚洲精品美女久久久久99蜜臀| 午夜福利视频1000在线观看| 成人欧美大片| 国产三级中文精品| 欧美在线一区亚洲| 国产人伦9x9x在线观看| 在线观看免费视频日本深夜| 欧美又色又爽又黄视频| 国产欧美日韩一区二区三| 亚洲av电影在线进入| 18禁裸乳无遮挡免费网站照片| 欧美国产日韩亚洲一区| 身体一侧抽搐| 国产精品自产拍在线观看55亚洲| 日本撒尿小便嘘嘘汇集6| 国产熟女xx| 久久久久亚洲av毛片大全| 久久中文看片网| 宅男免费午夜| 亚洲av片天天在线观看| 怎么达到女性高潮| 看免费av毛片| 成人一区二区视频在线观看| 欧美高清成人免费视频www| 午夜福利高清视频| 欧美性猛交╳xxx乱大交人| av片东京热男人的天堂| 欧美日韩精品网址| 男女床上黄色一级片免费看| bbb黄色大片| 日韩欧美在线乱码| 五月伊人婷婷丁香| 日本一二三区视频观看| 99久久精品一区二区三区| 人人妻,人人澡人人爽秒播| 亚洲性夜色夜夜综合| 日本黄色片子视频| 熟女电影av网| 久久久久久大精品| 美女扒开内裤让男人捅视频| 免费av不卡在线播放| 久久天堂一区二区三区四区| 欧美成狂野欧美在线观看| 国产探花在线观看一区二区| 国产三级在线视频| 麻豆av在线久日| 亚洲人成网站高清观看| 日本五十路高清| 亚洲欧美一区二区三区黑人| 观看免费一级毛片| 2021天堂中文幕一二区在线观| 一个人免费在线观看电影 | 在线视频色国产色| 99riav亚洲国产免费| 高清在线国产一区| 欧美日韩黄片免| 国产精品九九99| 桃色一区二区三区在线观看| 精品不卡国产一区二区三区| 亚洲精品粉嫩美女一区| 亚洲欧美精品综合久久99| 白带黄色成豆腐渣| 九色成人免费人妻av| 亚洲人成伊人成综合网2020| 又黄又爽又免费观看的视频| 床上黄色一级片| 午夜激情福利司机影院| 不卡av一区二区三区| 久久99热这里只有精品18| 给我免费播放毛片高清在线观看| 国产亚洲精品一区二区www| 欧美在线黄色| 久久久色成人| 91九色精品人成在线观看| 亚洲成人中文字幕在线播放| 亚洲色图 男人天堂 中文字幕| 真人做人爱边吃奶动态| 日本 av在线| 免费观看的影片在线观看| 成人欧美大片| 亚洲美女视频黄频| 一本久久中文字幕| 国产免费男女视频| 亚洲熟妇中文字幕五十中出| 久久草成人影院| av福利片在线观看| 国产精品爽爽va在线观看网站| 久久精品国产99精品国产亚洲性色| 国产精品1区2区在线观看.| 88av欧美| 久久久久国产一级毛片高清牌| 网址你懂的国产日韩在线| 99热只有精品国产| 欧美中文日本在线观看视频| 身体一侧抽搐| 色播亚洲综合网| 亚洲欧美日韩高清在线视频| 巨乳人妻的诱惑在线观看| 在线观看午夜福利视频| 人人妻人人看人人澡| 国产成人系列免费观看| 1024手机看黄色片| 国产毛片a区久久久久| 美女高潮喷水抽搐中文字幕| 夜夜夜夜夜久久久久| 亚洲精品一卡2卡三卡4卡5卡| 国产欧美日韩精品亚洲av| 成年免费大片在线观看| 成人特级黄色片久久久久久久| 亚洲精品粉嫩美女一区| 久久久久精品国产欧美久久久| 欧美一区二区精品小视频在线| 国产伦人伦偷精品视频| 夜夜躁狠狠躁天天躁| 午夜免费成人在线视频| 毛片女人毛片| 好看av亚洲va欧美ⅴa在| 免费av毛片视频| 一级作爱视频免费观看| 两性午夜刺激爽爽歪歪视频在线观看| 长腿黑丝高跟| 色尼玛亚洲综合影院| 草草在线视频免费看| 午夜精品在线福利| 激情在线观看视频在线高清| 欧美性猛交黑人性爽| 人妻久久中文字幕网| 国产一区二区三区视频了| 制服丝袜大香蕉在线| 久久人妻av系列| 亚洲真实伦在线观看| 国产精品 国内视频| 99热精品在线国产| 九九久久精品国产亚洲av麻豆 | 熟女电影av网| 91在线精品国自产拍蜜月 | 亚洲熟妇中文字幕五十中出| 熟女少妇亚洲综合色aaa.| 免费无遮挡裸体视频| 国产av不卡久久| 久久久久国产一级毛片高清牌| 国产极品精品免费视频能看的| 国产精品精品国产色婷婷| 亚洲第一电影网av| 美女免费视频网站| 久久这里只有精品19| 三级男女做爰猛烈吃奶摸视频| 亚洲精品美女久久久久99蜜臀| 成人鲁丝片一二三区免费| 动漫黄色视频在线观看| 69av精品久久久久久| 一级毛片女人18水好多| 亚洲成人中文字幕在线播放| 午夜激情福利司机影院| 人妻夜夜爽99麻豆av| 亚洲av第一区精品v没综合| 99热这里只有是精品50| 美女免费视频网站| 日本撒尿小便嘘嘘汇集6| 亚洲成人免费电影在线观看| 免费搜索国产男女视频| 特级一级黄色大片| 露出奶头的视频| 亚洲国产精品久久男人天堂| 久久久国产欧美日韩av| 亚洲欧美日韩高清专用| 国产精品99久久99久久久不卡| 色综合站精品国产| 久久久久久久久免费视频了| 亚洲成人中文字幕在线播放| 国产成人一区二区三区免费视频网站| 夜夜看夜夜爽夜夜摸| 偷拍熟女少妇极品色| 一本精品99久久精品77| 色噜噜av男人的天堂激情| 日韩有码中文字幕| 国内精品美女久久久久久| 欧美zozozo另类| 国产欧美日韩精品一区二区| 丰满人妻一区二区三区视频av | 色av中文字幕| 最好的美女福利视频网| 精品一区二区三区视频在线 | 日本 av在线| 精品一区二区三区四区五区乱码| 一区二区三区高清视频在线| 桃红色精品国产亚洲av| 免费无遮挡裸体视频| 亚洲av电影在线进入| 最近最新中文字幕大全电影3| 国产精品久久久久久亚洲av鲁大| 国产真实乱freesex| 国产黄片美女视频| 日本a在线网址| 99久久精品一区二区三区| 一进一出好大好爽视频| 国产精品久久电影中文字幕| 成人三级黄色视频| 久久久久性生活片| 18禁观看日本| 午夜精品在线福利| 夜夜看夜夜爽夜夜摸| 国产成人精品无人区| 欧美高清成人免费视频www| 深夜精品福利| 日韩欧美国产在线观看| 男女做爰动态图高潮gif福利片| 精品无人区乱码1区二区| 999久久久精品免费观看国产| 51午夜福利影视在线观看| 看免费av毛片| 国产高清视频在线观看网站| 亚洲天堂国产精品一区在线| 国产精品久久久人人做人人爽| 色视频www国产| 麻豆久久精品国产亚洲av| 一个人观看的视频www高清免费观看 | 亚洲精品在线观看二区| 狂野欧美白嫩少妇大欣赏| 国产亚洲av高清不卡| 精品免费久久久久久久清纯| 特级一级黄色大片| 国产欧美日韩精品亚洲av| 亚洲人成伊人成综合网2020| 中文字幕av在线有码专区| 身体一侧抽搐| 91麻豆精品激情在线观看国产| 久久九九热精品免费| 制服人妻中文乱码| 国产午夜福利久久久久久| 性色av乱码一区二区三区2| 脱女人内裤的视频| 久久精品影院6| 制服人妻中文乱码| 一进一出好大好爽视频| 99久久成人亚洲精品观看| 亚洲成人中文字幕在线播放| 欧美3d第一页| 国产三级在线视频| av片东京热男人的天堂| 大型黄色视频在线免费观看| 1024手机看黄色片| 1000部很黄的大片| 后天国语完整版免费观看| 免费av不卡在线播放| 成人午夜高清在线视频| 在线十欧美十亚洲十日本专区| 欧美一区二区国产精品久久精品| 一级毛片女人18水好多| 国产精品一区二区三区四区久久| 国产在线精品亚洲第一网站| 色综合亚洲欧美另类图片| 色av中文字幕| 一区福利在线观看| 日本三级黄在线观看| 美女午夜性视频免费| av片东京热男人的天堂| 午夜福利18| 午夜激情福利司机影院| 人人妻,人人澡人人爽秒播| 日韩有码中文字幕| 18禁观看日本| 午夜激情福利司机影院| 亚洲精品在线观看二区| av片东京热男人的天堂| 久久国产乱子伦精品免费另类| 中文字幕精品亚洲无线码一区| av在线蜜桃| 免费观看的影片在线观看| 亚洲专区国产一区二区| 亚洲五月天丁香| 又黄又粗又硬又大视频| 少妇裸体淫交视频免费看高清| 午夜日韩欧美国产| 亚洲狠狠婷婷综合久久图片| 久久久久免费精品人妻一区二区| 亚洲狠狠婷婷综合久久图片| 人人妻人人看人人澡| 国产精品九九99| 免费观看精品视频网站| 九色成人免费人妻av| 亚洲在线观看片| 亚洲av美国av| 99热精品在线国产| 99在线人妻在线中文字幕| 亚洲在线自拍视频| 亚洲,欧美精品.| 天堂影院成人在线观看| 岛国视频午夜一区免费看| 观看免费一级毛片| 亚洲国产欧洲综合997久久,| 99热精品在线国产| 欧美性猛交黑人性爽| 国产欧美日韩精品一区二区| 床上黄色一级片| 99热精品在线国产| 久久精品综合一区二区三区| 99国产精品99久久久久| 淫秽高清视频在线观看| 国产精品亚洲美女久久久| 国产精品av久久久久免费| 亚洲av片天天在线观看| 欧美日韩乱码在线| 欧美日韩瑟瑟在线播放| 色精品久久人妻99蜜桃| 国产亚洲精品久久久久久毛片| 久久精品91无色码中文字幕| 亚洲电影在线观看av| 日本一二三区视频观看| 12—13女人毛片做爰片一| 国产真实乱freesex| 久久久久久九九精品二区国产| 中文字幕人成人乱码亚洲影| 欧美另类亚洲清纯唯美| 国产伦精品一区二区三区视频9 | 最近最新中文字幕大全电影3| 丰满人妻一区二区三区视频av | 黑人操中国人逼视频| 亚洲无线在线观看| 亚洲国产日韩欧美精品在线观看 | 国产亚洲欧美98| 男女午夜视频在线观看| 亚洲欧美精品综合久久99| 亚洲国产精品sss在线观看| 亚洲精品456在线播放app | 天堂影院成人在线观看| 天堂动漫精品| 一级毛片精品| 俄罗斯特黄特色一大片| 国内精品一区二区在线观看| 男女视频在线观看网站免费| 黑人巨大精品欧美一区二区mp4| 嫁个100分男人电影在线观看| 九九在线视频观看精品| 男人和女人高潮做爰伦理| 亚洲一区二区三区色噜噜| 久久久色成人| 97碰自拍视频| 久久草成人影院| 国产又色又爽无遮挡免费看| 成人18禁在线播放| 亚洲熟妇中文字幕五十中出| 国产欧美日韩精品一区二区| 极品教师在线免费播放| 久久久久国产精品人妻aⅴ院| 夜夜爽天天搞| 精品国产亚洲在线| 无人区码免费观看不卡| 亚洲成人精品中文字幕电影| 法律面前人人平等表现在哪些方面| 男女做爰动态图高潮gif福利片| 亚洲欧洲精品一区二区精品久久久| 午夜免费观看网址| 脱女人内裤的视频| av在线天堂中文字幕| 不卡av一区二区三区| 啪啪无遮挡十八禁网站| 日本成人三级电影网站| 午夜精品久久久久久毛片777| www.自偷自拍.com| 欧美一级毛片孕妇| 久久久成人免费电影| 亚洲人成网站高清观看| 亚洲无线在线观看| 亚洲va日本ⅴa欧美va伊人久久| 国产精品久久久久久人妻精品电影| 国产精品99久久99久久久不卡| 99riav亚洲国产免费| 我的老师免费观看完整版| 操出白浆在线播放| 天天躁狠狠躁夜夜躁狠狠躁| 黄色丝袜av网址大全| 亚洲熟妇中文字幕五十中出| 91在线观看av| 男女视频在线观看网站免费| 身体一侧抽搐| 夜夜夜夜夜久久久久| 99re在线观看精品视频| xxx96com| 欧美日韩中文字幕国产精品一区二区三区| 久久久久免费精品人妻一区二区| 母亲3免费完整高清在线观看| 亚洲国产高清在线一区二区三| 亚洲人成电影免费在线| 色在线成人网| 99久久成人亚洲精品观看| 十八禁网站免费在线| 一区二区三区国产精品乱码| 亚洲欧美一区二区三区黑人| 中文亚洲av片在线观看爽| 国产欧美日韩一区二区精品| 长腿黑丝高跟| 窝窝影院91人妻| 偷拍熟女少妇极品色| 小蜜桃在线观看免费完整版高清| 亚洲熟妇熟女久久| 9191精品国产免费久久| av视频在线观看入口| 国产亚洲精品久久久久久毛片| 在线观看日韩欧美| 成人三级黄色视频| 久久国产精品人妻蜜桃| 综合色av麻豆| 曰老女人黄片| 麻豆国产av国片精品| 午夜免费成人在线视频| 久久伊人香网站| 国产私拍福利视频在线观看| 看黄色毛片网站| 国产伦人伦偷精品视频| 夜夜看夜夜爽夜夜摸| 黄色片一级片一级黄色片| 午夜福利18| www.熟女人妻精品国产| 九九久久精品国产亚洲av麻豆 | 亚洲午夜精品一区,二区,三区| 国产午夜精品久久久久久| 蜜桃久久精品国产亚洲av| 日韩免费av在线播放| 亚洲国产欧美一区二区综合| 欧美乱色亚洲激情| 久久精品综合一区二区三区| 日本熟妇午夜| 国产亚洲av嫩草精品影院| 日本黄色视频三级网站网址| a在线观看视频网站| 国产乱人伦免费视频| 露出奶头的视频| 日本一本二区三区精品| 国产精品一及| 日韩大尺度精品在线看网址| 亚洲av电影在线进入| 免费无遮挡裸体视频| 精品欧美国产一区二区三| 午夜免费成人在线视频| 99久久成人亚洲精品观看| 久久精品综合一区二区三区| 欧美不卡视频在线免费观看| 别揉我奶头~嗯~啊~动态视频| 成人三级黄色视频| 国产成人av激情在线播放| 国产精品女同一区二区软件 | 在线观看日韩欧美| 少妇丰满av| 夜夜躁狠狠躁天天躁| 久久中文字幕一级| 国产精品久久久久久久电影 | 国产精品亚洲美女久久久| 日韩高清综合在线| 免费看a级黄色片| 99久久成人亚洲精品观看| 欧美一区二区国产精品久久精品| 欧美日韩精品网址| 亚洲人成电影免费在线| 少妇丰满av| 国产激情欧美一区二区| 亚洲aⅴ乱码一区二区在线播放| 999精品在线视频| 老司机午夜福利在线观看视频| 88av欧美| 一个人看视频在线观看www免费 | 99精品在免费线老司机午夜| 欧美成人性av电影在线观看| 老汉色∧v一级毛片| 99久久综合精品五月天人人| АⅤ资源中文在线天堂| 欧美日韩瑟瑟在线播放| 成人性生交大片免费视频hd| 99re在线观看精品视频| 国产av麻豆久久久久久久| 91久久精品国产一区二区成人 | 美女大奶头视频| 久久久久久久久免费视频了| 18禁美女被吸乳视频| 国产99白浆流出| 精品久久蜜臀av无| 亚洲精品美女久久久久99蜜臀| 亚洲最大成人中文| 别揉我奶头~嗯~啊~动态视频| 色噜噜av男人的天堂激情| 国产欧美日韩精品一区二区| 男女视频在线观看网站免费| 男人舔奶头视频| 国产精品永久免费网站| 久久久水蜜桃国产精品网| 日韩欧美在线乱码| 国产精品女同一区二区软件 | 久久久久免费精品人妻一区二区| 九九热线精品视视频播放| 国产av麻豆久久久久久久| 久久久久久大精品| 欧美日韩综合久久久久久 | 亚洲天堂国产精品一区在线| 一区福利在线观看| 色av中文字幕| 国产精品香港三级国产av潘金莲| 蜜桃久久精品国产亚洲av| 美女午夜性视频免费| 精品午夜福利视频在线观看一区| 国产主播在线观看一区二区| 在线国产一区二区在线| 国产不卡一卡二| 国产在线精品亚洲第一网站| 欧美日韩中文字幕国产精品一区二区三区| 久久精品国产综合久久久| 最近最新中文字幕大全免费视频| 久久国产精品影院| 久久久国产成人免费| 女人高潮潮喷娇喘18禁视频| 成熟少妇高潮喷水视频| 美女高潮喷水抽搐中文字幕| 久久久久久久久中文| 亚洲精品中文字幕一二三四区| 在线观看66精品国产| 香蕉国产在线看| 国产高清视频在线播放一区| 18禁黄网站禁片午夜丰满| 国产三级在线视频| 最新美女视频免费是黄的| 一夜夜www| 日韩免费av在线播放| 久久久久精品国产欧美久久久| 久久中文字幕一级| 99久久久亚洲精品蜜臀av| 国产精品 欧美亚洲| 国产精品爽爽va在线观看网站| 日韩中文字幕欧美一区二区| 特大巨黑吊av在线直播| 国产一区二区在线av高清观看| av福利片在线观看| 国产精品亚洲av一区麻豆| 国产黄a三级三级三级人| 麻豆成人av在线观看| 国产97色在线日韩免费| 亚洲熟妇中文字幕五十中出| 网址你懂的国产日韩在线| 国产亚洲欧美98| 99在线人妻在线中文字幕| 日本成人三级电影网站| 免费看日本二区| 久久香蕉国产精品| 亚洲成人免费电影在线观看| 精品日产1卡2卡| 国产一区二区三区在线臀色熟女| 国产极品精品免费视频能看的| 亚洲男人的天堂狠狠| 亚洲狠狠婷婷综合久久图片| 三级国产精品欧美在线观看 | 99在线人妻在线中文字幕| 欧美日韩综合久久久久久 |