一種利用二叉堆排序的尋路方法及裝置

基本信息

申請?zhí)?/td> CN201310728773.7 申請日 -
公開（公告）號 CN103716237A 公開（公告）日 2014-04-09
申請公布號 CN103716237A 申請公布日 2014-04-09
分類號 H04L12/701(2013.01)I 分類 電通信技術;
發(fā)明人 朱橋紅 申請（專利權）人 廣東星輝天拓互動娛樂有限公司
代理機構 北京集佳知識產權代理有限公司 代理人 廣東天拓資訊科技有限公司;廣東星輝天拓互動娛樂有限公司
地址 510663 廣東省廣州市天河區(qū)軟件園高唐新建區(qū)廣州互聯網產業(yè)園1號樓A401、B401房
法律狀態(tài) -

摘要

摘要 本發(fā)明公開了一種利用二叉堆排序的尋路方法及裝置，通過利用二叉堆排序方法對A*尋路算法中開放列表進行排序的方式，能夠快速尋找出最小開銷值，進而能夠快速的得到最小開銷路徑。本發(fā)明的方法包括：開放列表，用于存儲地圖格子節(jié)點，起始點與所述節(jié)點組成路徑；S1：將所述開放列表按二叉堆最小堆排列，得到二叉堆列表；S2：當向所述二叉堆列表添加新節(jié)點時，執(zhí)行步驟S3，當向所述二叉堆列表中取用最小值節(jié)點時，執(zhí)行步驟S4；S3：對所述二叉堆列表執(zhí)行堆插入操作；步驟S3包括：S31：將所述新節(jié)點放置在所述二叉堆列表末端，得到插入堆列表；S32：將所述插入堆列表進行二叉堆最小堆排列；S4：刪除所述最小值節(jié)點并對所述二叉堆列表執(zhí)行堆重排操作。