[發(fā)明專利]一種基于貪婪算法的路徑規(guī)劃算法

在審

• 申請(qǐng)?zhí)枺?/td>: 202210883285.2
• 申請(qǐng)日: 2022-07-26
• 公開（公告）號(hào): CN115392539A
• 公開（公告）日: 2022-11-25
• 發(fā)明（設(shè)計(jì)）人: 王志剛;阮亞良;周旭;虞儒新;王戰(zhàn);張英馳;韓昊一;魯鼎
• 申請(qǐng)（專利權(quán)）人: 浙江浙能嘉華發(fā)電有限公司;浙江浙能數(shù)字科技有限公司
• 主分類號(hào): G06Q10/04
• 分類號(hào): G06Q10/04
• 代理公司: 杭州九洲專利事務(wù)所有限公司 33101
• 代理人: 張羽振

本發(fā)明涉及一種基于貪婪算法的路徑規(guī)劃算法，包括：在遍歷遇到分支時(shí)，把分支提取出來，兩條分支都遍歷完之后，對(duì)比先遍歷哪條分支總體結(jié)果更優(yōu)來確定優(yōu)先走哪一條分支而不是固定走最近點(diǎn)分支。本發(fā)明的有益效果是：本發(fā)明保證貪婪算法不會(huì)由于陷入局部最優(yōu)，導(dǎo)致很難得到全局最優(yōu)解，從而達(dá)到了路徑規(guī)劃效率高的效果。

技術(shù)領(lǐng)域

本發(fā)明涉及路徑規(guī)劃算法技術(shù)領(lǐng)域，更確切地說，它涉及一種基于貪婪算法的路徑規(guī)劃算法。

背景技術(shù)

機(jī)器人路徑規(guī)劃的應(yīng)用場景簡單描述就是給定n個(gè)點(diǎn)，尋找遍歷這n個(gè)點(diǎn)的最短路徑。很明顯這是一個(gè)圖論中的經(jīng)典問題，旅行商問題的變種，區(qū)別只有最終是否需要回到出發(fā)點(diǎn)。

旅行商問題(Traveling Salesman Problem，TSP)是一個(gè)經(jīng)典的組合優(yōu)化問題，TSP可以描述為：一個(gè)商品推銷員要去若干個(gè)城市推銷商品，該推銷員從一個(gè)城市出發(fā)，需要經(jīng)過所有城市后，回到出發(fā)地。應(yīng)如何選擇行進(jìn)路線，以使總的行程最短。旅行商問題是個(gè)多項(xiàng)式復(fù)雜程度的非確定性(Non-deterministic Polynomial，NP)完全問題，窮舉算法的效率太差，時(shí)間復(fù)雜度為O(n！)，所以目前比較主流的方法是采用一些隨機(jī)的、啟發(fā)式的搜索算法，比如遺傳算法、蟻群算法、模擬退火算法、神經(jīng)網(wǎng)絡(luò)等等。

但這些算法都有一個(gè)缺點(diǎn)，就是不一定能求出最優(yōu)解，只能收斂于(近似逼近)最優(yōu)解，得到一個(gè)近似最優(yōu)解，因?yàn)樗麄儽举|(zhì)都是隨機(jī)算法，大多都會(huì)以類似“一定概率接受或舍去”的思路去篩選解；各算法的實(shí)現(xiàn)思路都有不同，但也或多或少有互相借鑒的地方，有的與隨機(jī)因子有關(guān)、有的與初始狀態(tài)有關(guān)、有的與隨機(jī)函數(shù)有關(guān)、有的與選擇策略有關(guān)。綜合上述分析，TSP問題的求解大概是由以下兩步構(gòu)成：1.計(jì)算兩兩城市間的最短路徑：利用類似Dijkstra、Flord、A星的算法求出最短路線；2.計(jì)算最短巡回路徑：利用類似遺傳算法、蟻群算法的搜索算法求巡回拜訪的次序。

現(xiàn)有技術(shù)中，第一步使用的是迪克斯特拉(Dijkstra)算法求出的每兩個(gè)點(diǎn)之間的最短路徑。然后第二步做路徑規(guī)劃的時(shí)候使用的是求解TSP問題的經(jīng)典算法：林-克尼根-赫爾斯岡(Lin-Kernighan-Helsgaun，LKH)算法。但是該算法的思想是基于最終需要回到出發(fā)點(diǎn)的TSP問題，求解的是最優(yōu)環(huán)路，不是機(jī)器人路徑規(guī)劃應(yīng)用場景需要最優(yōu)路徑。所以需要找到適合現(xiàn)在機(jī)器人路徑規(guī)劃應(yīng)用場景的新算法。

已知的算法中，貪婪算法的效率是最高的，但是由于會(huì)陷入局部最優(yōu)，導(dǎo)致很難得到全局最優(yōu)解。貪婪算法陷入局部最優(yōu)的一個(gè)具有代表性的例子是當(dāng)遇到分支路徑時(shí)，會(huì)遍歷完最近點(diǎn)所在分支后再返回另一分支；但是很多情況下，優(yōu)先遍歷另一分支才是全局最優(yōu)解，進(jìn)而降低路徑規(guī)劃效率。

發(fā)明內(nèi)容

本發(fā)明的目的是克服現(xiàn)有技術(shù)中的不足，提供了一種基于貪婪算法的路徑規(guī)劃算法。

第一方面，提供了一種基于貪婪算法的路徑規(guī)劃算法，包括：

S1、獲取待遍歷節(jié)點(diǎn)集合，并將所述待遍歷節(jié)點(diǎn)集合中的任一節(jié)點(diǎn)確定為起始節(jié)點(diǎn)；

S2、計(jì)算所述起始節(jié)點(diǎn)和所述待遍歷節(jié)點(diǎn)集合中的其余節(jié)點(diǎn)之間的距離，獲取第一距離集合，并確定所述起始節(jié)點(diǎn)的最近節(jié)點(diǎn)；若所述起始節(jié)點(diǎn)到所述最近節(jié)點(diǎn)的最短路徑中存在路徑序列集合中的節(jié)點(diǎn)，則將所述最近節(jié)點(diǎn)從待遍歷節(jié)點(diǎn)集合中移出并存入等待節(jié)點(diǎn)集合，重新執(zhí)行S2；將所述起始節(jié)點(diǎn)從所述待遍歷節(jié)點(diǎn)集合移出，并存入當(dāng)前路徑序列；

S3、將所述起始節(jié)點(diǎn)賦值為上一節(jié)點(diǎn)，并將所述最近節(jié)點(diǎn)賦值為起始節(jié)點(diǎn)，將第一距離集合賦值為第二距離集合，重復(fù)S2；

S4、將所述第一距離集合和所述第二距離集合進(jìn)行對(duì)比，若所述待遍歷節(jié)點(diǎn)集合中存在和起始節(jié)點(diǎn)距離大于和上一節(jié)點(diǎn)距離的節(jié)點(diǎn)，將這些節(jié)點(diǎn)從所述待遍歷節(jié)點(diǎn)集合中移出，并存入等待節(jié)點(diǎn)集合，將上一節(jié)點(diǎn)存入分支點(diǎn)序列，重復(fù)S3；