[發明專利]一種基于窄帶模型的多目的地的最短路徑獲取方法

在審

• 申請號: 202010601792.3
• 申請日: 2020-06-29
• 公開（公告）號: CN111754043A
• 公開（公告）日: 2020-10-09
• 發明（設計）人: 李吉;田亞鈴;鄭金輝;李秀鑫;劉鋼;彭雨
• 申請（專利權）人: 成都航空職業技術學院;成都永峰科技有限公司
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06F30/20
• 代理公司: 成都正華專利代理事務所(普通合伙) 51229
• 代理人: 陳選中

本發明公開了一種基于窄帶模型的多目的地的最短路徑獲取方法，其包括以下步驟S1、獲取兩兩節點之間的距離；S2、獲取主動關聯節點和被動關聯節點；S3、判斷關聯節點是否能構成完整路徑，若是則進入步驟S7，否則進入步驟S4；S4、獲取局部小回路和大距離節點；S5、鎖定每個大距離節點的全局帶寬，將局部小回路中節點的全局帶寬加1；S6、判斷是否能構成完整路徑，若是則進入步驟S7，否則返回步驟S4；S7、驗證是否存在更短路徑，若是則進入步驟S8，否則輸出結果；S8、將更短的路徑作為新的備選最短路徑，返回步驟S7。本發明避免了所有節點同時運算造成的龐大計算量，有效節約了計算資源并提高了路徑獲取效率。

技術領域

本發明涉及路徑規劃領域，具體涉及一種基于窄帶模型的多目的地的最短路徑獲取方法。

背景技術

在數控設備(銑床、鉆床、切割機、鉆鉚設備等)、工業機器人等應用領域，針對刀路、刀軌、運動軌跡的優化，求算最短路徑可以優化工藝、提升效率。

在飛行器(戰斗機、無人機、運輸機等)的飛行軌跡(航跡)規劃應用領域，針對多目標、多任務條件下的飛行軌跡優化和最短路徑求算，對于戰局的控制也非常關鍵。

在交通運輸相關領域，尤其在物流、運輸領域，求算最短路線有利于節約運輸成本，提高運輸效率。

在計算機軟件、大數據、人工智能領域，在目標優化、數據精簡、數據提取領域，提取有限少的數據進行計算和建模是其中的重要環節，數據處理尤其是特征數據抽取是獲得高效率、高質量結果的關鍵所在。

但是，現有的最短路徑獲取方法通常直接將所有目的地采用全排列或動態優化方法來獲取，當目的地數量較大時，運算量將成指數級增加，該方式只適合獲取僅涉及少量目的地的最短路徑。

發明內容

針對現有技術中的上述不足，本發明提供的一種基于窄帶模型的多目的地的最短路徑獲取方法解決了現有最短路徑運算量大的問題。

為了達到上述發明目的，本發明采用的技術方案為：

提供一種基于窄帶模型的多目的地的最短路徑獲取方法，其包括以下步驟：

S1、將每個目的地作為一個節點，對于任一個節點，將其余節點均作為其關聯節點，獲取每個節點與其對應的所有關聯節點之間的距離；

S2、建立窄帶模型：將每一個節點分別作為目標節點，將距離其最近的前n個關聯節點作為該節點的主動關聯節點，并將該目標節點作為距離其最近的前n個關聯節點的被動關聯節點；其中n表示窄帶模型的全局帶寬，n為大于1的整數；

S3、將全局帶寬n取值為2，挑選出每個目標節點對應的所有主動關聯節點和被動關聯節點，按照目標節點僅與挑選出的關聯節點相連的方式，判斷是否能構成完整路徑，若是則進入步驟S7，否則進入步驟S4；

S4、對于節點數小于節點總數a％的局部路徑和節點數大于等于b且小于c的局部路徑，將其作為局部小回路；將局部帶寬為2時所有主動關聯節點和被動關聯節點與目標節點的距離大于距離閾值的節點作為大距離節點；

S5、鎖定每個大距離節點的全局帶寬，將局部小回路中節點的全局帶寬加1；

S6、挑選出每個目標節點對應的所有主動關聯節點和被動關聯節點，按照目標節點僅與挑選出的關聯節點相連的方式，判斷是否能構成完整路徑，若是則進入步驟S7，否則返回步驟S4；

S7、將當前完整路徑中最短的路徑作為備選最短路徑；將當前所有節點的全局帶寬加1并再次獲取路徑，判斷再次獲取的路徑中是否存在比備選最短路徑更短的路徑，若是則進入步驟S8，否則將備選最短路徑作為結果輸出；

S8、將更短的路徑作為新的備選最短路徑，返回步驟S7。

進一步地，步驟S2的具體方法為：