[發明專利]基于二叉堆節點排序的A星尋路方法及系統

在審

• 申請號: 201410531309.3
• 申請日: 2014-10-10
• 公開（公告）號: CN104268420A
• 公開（公告）日: 2015-01-07
• 發明（設計）人: 熊仕勇;林金朝;周敏;潘豪;田航;李沁翰;唐浩;張喜平;聶婧;譚世雨;李楊
• 申請（專利權）人: 重慶郵電大學
• 主分類號: G06F19/00
• 分類號: G06F19/00
• 代理公司: 北京眾合誠成知識產權代理有限公司 11246
• 代理人: 裴娜

1.基于二叉堆節點排序的A星尋路方法，其特征在于：包括以下步驟：

S1：初始化OPEN表、CLOSE表和目標點A，將起始結點S放入OPEN表，CLOSE表置空；

S2：判斷OPEN表是否為空，如果否，則從OPEN表的表頭取一個結點n；如果是，則結束算法過程；

S3：判斷結點n是否為目標解A，如果是，則結束算法，如果否，則轉入步驟S4；所述目標解是最終要尋找的目標點A；

S4：將結點n的所有后繼結點展開形成直接關聯子結點，判斷子結點是否在CLOSE表中，如果否，則將子結點放入OPEN表；

S5：把已經判斷的結點n放入CLOSE表，同時采用以下公式計算結點n的每一個后繼結點的估價值f′(n)；

f′(n)＝g′(n)+h′(n)；

其中，f′(n)是估價函數，g′(n)是起始結點到結點n的最短路徑值，h′(n)是結點n到目標的最短路經的啟發值；

S6：將OPEN表按估價值f′(x)進行堆排序，將估價值f′(x)最小的結點放在OPEN表的表頭，返回步驟S2重復循環。

2.根據權利要求1所述的基于二叉堆節點排序的A星尋路方法，其特征在于：所述OPEN表，用于存儲欲遍歷的下個節點；所述CLOSE表，用于存儲已經找到的路徑。

3.根據權利要求1所述的基于二叉堆節點排序的A星尋路方法，其特征在于：所述堆排序采用二叉堆進行排序；

所述二叉堆是通過以下方式進行的：

首先獲取OPEN表中節點的估價值f′(x)，將估價值f′(x)最小的節點放置在堆頂端；

然后從剩余的節點中選擇出估價值最小和次小的節點作為上一個節點的兩個子節點；

最后分別重復為兩個子節點選擇出估價值最小和次小的節點作為上一個節點的兩個子節點；直到將所有OPEN表中節點排列完成。

4.根據權利要求1所述的基于二叉堆節點排序的A星尋路方法，其特征在于：所述堆排序采用二叉堆進行排序；所述二叉堆是通過以下方式進行的：

首先獲取OPEN表中節點的估價值f′(x)，將估價值f′(x)最小的節點存儲在一維數組的第一個元素存儲地址中；然后將剩余的節點中的估價值f′(x)最小的節點存儲在一維數組的第二個元素存儲地址中，最后直到完成OPEN表中所有節點的排序。

5.基于二叉堆節點排序的A星尋路系統，其特征在于：包括初始化模塊、OPEN表判斷模塊、結點判斷模塊、關聯子結點模塊、結點估價值計算模塊、堆排序模塊；

所述初始化模塊，用于初始化OPEN表、CLOSE表和目標點A，將起始結點S放入OPEN表，CLOSE表置空；

所述OPEN表判斷模塊，用于判斷OPEN表是否為空，如果否，則從OPEN表的表頭取一個結點n；如果是，則結束算法過程；

所述結點判斷模塊，用于判斷結點n是否為目標解A，如果是，則輸出結點n，并返回步驟S2從OPEN表的表頭取另一個結點；如果否，則轉入步驟S4；所述目標解是最終要尋找的目標點A，即從起點找到一條路徑到達目標點；

所述關聯子結點模塊，用于將結點n的所有后繼結點展開形成直接關聯子結點，判斷子結點是否在CLOSE表中，如果否，則將子結點放入OPEN表；

所述結點估價值計算模塊，用于把已經判斷的結點n放入CLOSE表，同時采用以下公式計算結點n的每一個后繼結點的估價值f′(n)；

f′(n)＝g′(n)+h′(n)；

其中，f′(n)是估價函數，g′(n)是起始結點到結點n的最短路徑值，h′(n)是結點n到目標的最短路經的啟發值；

所述堆排序模塊，用于將OPEN表按估價值f′(x)進行堆排序，將估價值f′(x)最小的結點放在OPEN表的表頭。

6.根據權利要求1所述的基于二叉堆節點排序的A星尋路系統，其特征在于：所述OPEN表，用于存儲欲遍歷的下個節點；

所述CLOSE表，用于存儲已經找到的路徑。