[發(fā)明專利]無序經過必經點的最短路徑獲取方法及裝置

在審

• 申請?zhí)枺?/td>: 201710099326.8
• 申請日: 2017-02-23
• 公開（公告）號: CN106845630A
• 公開（公告）日: 2017-06-13
• 發(fā)明（設計）人: 王志超
• 申請（專利權）人: 中國人民解放軍國防科學技術大學
• 主分類號: G06N3/00
• 分類號: G06N3/00;G06N3/12
• 代理公司: 長沙市護航專利代理事務所(特殊普通合伙)43220
• 代理人: 莫曉齊

技術領域

本發(fā)明主要涉及最短路獲取領域，特別地，涉及一種無序經過必經點的最短路徑獲取方法及獲取裝置。

背景技術

最短路徑問題是一類受普遍重視和研究的網絡優(yōu)化問題，廣泛應用于計算機科學，交通工程，通信工程，運籌學，信息論，控制理論，軍事等眾多領域。它為研究更復雜的網絡流問題提供了基礎，是解決其他許多復雜網絡優(yōu)化問題的子問題之一。

傳統(tǒng)的最短路徑問題是固定起點和終點的簡單模型。用于解決最短路徑問題的算法叫做最短路徑算法。最常用的最短路徑算法有：Dijkstra算法，A*算法，SPFA算法，Bellman-Ford算法和Floyd-Warshall算法。而在實際應用中，經常會對路徑加以限定條件，比如要求先經過超市，然后經過加油站，最后再到目的地。此外，軍事人員及物資的運輸中通常也要考慮必經點，該必經點可能是一些重要的城市、橋梁、加油站、彈藥庫、中轉站等；故必經點的考慮也必將是未來智能交通誘導系統(tǒng)的發(fā)展趨勢。

但是在實際應用需求中，會出現(xiàn)只是從起點開始，必須經過所有的必經點才到達終點的需求，但并未強調必經點的順序。這種經過必經點的無序性使得問題變得更加復雜，如何獲取無序經過必經點的最短路徑，成為了本領域技術人員亟待解決的技術問題。

發(fā)明內容

有鑒于此，本發(fā)明的目的在于提供一種無序經過必經點的最短路徑獲取方法，以解決現(xiàn)有技術中獲取最短路徑過程復雜的缺陷。

本發(fā)明無序經過必經點的最短路徑獲取方法，用于獲取經過K個必經點的N條最短路徑，其中K、N均是大于1的整數，包括以下步驟：

步驟S1：計算只經過非必經點的起點到任意必經點，任意必經點到終點以及兩兩必經點之間的最短路徑長度以及路徑；

步驟S2：初始化UN個種群個體，個體長度為K，填充為各個必經點的序號，其中UN是大于N的整數；

步驟S3：計算種群中每個個體的路徑以及路徑長度，依據路徑長度對種群進行排序并取N條最佳路徑；

步驟S4：從種群中取一定比例的個體，按照交叉變異規(guī)則進行生成，產生新一代可行解作為新的種群；

步驟S5：在迭代次數達到預設次數時，輸出N個最優(yōu)解。

進一步地，所述步驟S1之前還包括以下步驟：

初始化網絡以去掉沒有入度或出度的中間點；

縮減網絡矩陣，減少矩陣維度，降低時間復雜度。

進一步地，所述步驟S1具體包括：

步驟S11：將要求取的路徑抽象為從節(jié)點a到節(jié)點b，其中a是起點或者必經點，b是必經點或者終點；

步驟S12：將除了a和b之外所有必經點的出度清空；

步驟S13：使用最短路徑算法求取a到b的路徑及路徑長度。

進一步地，所述步驟S3中計算種群中每個個體的路徑及路徑長度具體包括：

步驟S31：設置經過的非必經點集合；

步驟S32：針對每個個體，生成隨機序列作為路徑搜索順序；

步驟S33：依據搜索順序，查詢當前點與下一必經點之間的最短路徑，如果經過的非必經點都不在非必經點集合內，則當前點即為此路徑中的非必經點；

步驟S34：否則，將網絡中涉及到的非必經點集合內的非必經點出度清空，獲得新的路徑中的非必經點；

步驟S35：將各段路徑長度加起來即可得到當前個體路徑。

進一步地，所述步驟S4中采用三交叉啟發(fā)交叉，進行啟發(fā)式生成，以生成更優(yōu)的一代種群。

本發(fā)明還提供一種無序經過必經點的最短路徑獲取裝置，用于獲取經過K個必經點的N條最短路徑，其中K、N均是大于1的整數，包括：

第一計算模塊，用于計算只經過非必經點的起點到任意必經點，任意必經點到終點以及兩兩必經點之間的最短路徑長度以及路徑；

第一初始化模塊，用于初始化UN個種群個體，個體長度為K，填充為各個必經點的序號，其中UN是大于N的整數；

第二計算模塊，用于計算種群中每個個體的路徑以及路徑長度，依據路徑長度對種群進行排序并取N條最佳路徑；

種群生成模塊，用于從種群中取一定比例的個體，按照交叉變異規(guī)則進行生成，產生新一代可行解作為新的種群；

輸出模塊，用于在迭代次數達到預設次數時，輸出N個最優(yōu)解。

進一步地，所述最短路徑獲取裝置還包括：

第二初始化模塊，用于初始化網絡以去掉沒有入度或出度的中間點，縮減網絡矩陣，減少矩陣維度，降低時間復雜度。

進一步地，所述第一計算模塊包括：