[發明專利]一種應用于GPS的快速K最短路徑規劃方法

有效

• 申請號: 201310400749.0
• 申請日: 2013-09-06
• 公開（公告）號: CN103439726A
• 公開（公告）日: 2013-12-11
• 發明（設計）人: 劉貴松;邱釗;謝娟;張浩;屈鴻;陳文宇
• 申請（專利權）人: 電子科技大學
• 主分類號: G01S19/39
• 分類號: G01S19/39
• 代理公司: 成都華典專利事務所(普通合伙) 51223
• 代理人: 徐豐;楊保剛

1.一種應用于GPS的快速K最短路徑規劃方法，其特征在于，包括以下步驟：

（1）導入地圖，并由用戶根據GPS確定起始點s和終點t以及相應的K值，其中K是用戶期望查找的最短路徑數目；

（2）對結點t調用A*算法得到最短s-t路徑，定義變量k，令k=1;

（3）遞歸計算k條最短s-t路徑：依次遍歷第k條最短路徑上各結點的所有為sidetrack?edge的入邊得到候選路徑，并加入集合C，sidetrack?edge表示不在最短路徑樹上的邊；

（4）從集合C中取出一條最短路徑作為第k+1條最短路徑；

（5）判斷K，如果路徑條數未達到K值，則進入步驟6，否則跳轉到步驟7；

（6）判斷集合C，如果該集合非空，則返回步驟3，否則進入步驟8;

（7）算法成功結束，返回搜索結果；

（8）算法結束，未找到足夠的K條路徑，返回搜索結果。

2.根據權利要求1所述的一種應用于GPS的快速K最短路徑規劃方法，其特征在于，所述步驟2中利用A*得到第一條最短路徑后A*暫停，且后續步驟中再次調用A*進行結點擴展，在A*的運行過程中，對當前節點的所有出邊進行迭代，將位于最短路徑樹上的邊標記為tree?edge，不在最短路徑樹上的邊標記為sidetrack?edge，對于所有被擴展過的頂點標記其狀態為close。

3.根據權利要求2所述的一種應用于GPS的快速K最短路徑規劃方法，其特征在于，所述步驟3中遍歷各結點是按照從第k條路徑中的最后一個sidetrack?edge邊的尾結點前向搜索到起始結點，候選路徑用sidetrack?edge的集合來表示，最后用sidetrack?edge表示的路徑一一對應地表示為一條常規路徑。

4.根據權利要求2所述的一種應用于GPS的快速K最短路徑規劃方法，其特征在于，所述步驟3中依次遍歷第k條最短路徑上各結點，其方法包括以下步驟：

（4-1）依次遍歷當前第k條路徑上從最后一條sidetrack?edge到起始結點中的所有結點，記為v；

（4-2）依次遍歷結點v的所有的sidetrack?edge出邊，記為e；

（4-3）判斷邊e的頭結點，如果其狀態不是close，則重啟A*直到e的頭結點的狀態被標記為close；

（4-4）將e加入到當前第k條路徑的末尾，形成一條新的候選路徑并計算其長度，其中候選路徑長度為d(t)-d(v)+w(e)+d(tail(e)，將該候選路徑加入到集合C中。

5.根據權利要求1所述的一種應用于GPS的快速K最短路徑規劃方法，其特征在于，所述步驟4取出當前集合C中路徑長度最短的候選路徑作為下一條待處理的路徑。

6.根據權利要求1所述的一種應用于GPS的快速K最短路徑規劃方法，其特征在于，所述步驟5對K的判斷，如果已經達到K值，返回K條最短路徑。

7.根據權利要求1所述的一種應用于GPS的快速K最短路徑規劃方法，其特征在于，所述步驟6對C進行判斷，集合C如果為空，表示沒有候選路徑可供選擇，算法結束返回不能成功找到K條路徑。

8.根據權利要求6所述的一種應用于GPS的快速K最短路徑規劃方法，其特征在于，k為循環變量，每次循環后k++，表示當前已經得到的路徑條數。