A* 算法的數(shù)據(jù)結(jié)構(gòu)
原始需求:求某電車到D公里范圍內(nèi)的地圖顯示
轉(zhuǎn)換需求:
第一步:由某個點P到距離恰好大于等于D公里的所有的路的集合求出來
第二步:所有的路外的點組成polygon 然后渲染
第一步的詳細算法A*:
1.我們有一個空的集合C用來放符合條件的R,和某個點P(簡單起見,假設(shè)P在路上,用R表示路)
1.1 R有屬性id,權(quán)重weight(也就是路到A點的當前路徑的距離)
2. R根據(jù)graph模塊找到和他直接相連的幾條路Rx1…Rxn ,Rx1…Rxn權(quán)重weight小于D公里時放入集合C。在放入集合之前
查看C中和Rx1…Rxn id是否有相同的Rx,如果有并且新的權(quán)重大的話就更新權(quán)重,否則放棄更新。
3. 在集合C中找到一個權(quán)重weight最小的Rmin
4. 如果Rmin 的權(quán)重weight 小于D 重復(fù)2,3步。
否則退出循環(huán),表示目前的集合C已經(jīng)滿足情況。
本文重點-集合C需要的特性:
1.根據(jù)id 快速查找id相同的Rx1…Rxn
2.插入新的Rx1…Rxn
3.根據(jù)權(quán)重weight找到Rmin
4.刪除Rmin
也就是說集合C需要快速查找,插入,刪除,有序。看到這個需求同事用了2版數(shù)據(jù)結(jié)構(gòu)
第一版:二叉堆版的優(yōu)先級隊列priority_queue, 性能7s,方案錯誤
優(yōu)點O(logN)的插入和刪除Rmin,缺點O(N)的id查找,無法刪除飛最小值
第二版:有序鏈表版的優(yōu)先級隊列,性能5s
優(yōu)點O(1)的刪除Rmin,缺點O(N)的id查找,O(N)的插入
由LRU cache的list+map啟發(fā):
第三版:list無序存放R,map1存放{id, node指針}, multimap存放{weight, node指針},性能1s
優(yōu)點:O(logN)的map1查找,更新,multimap的刪除Rmin,插入
缺點:這里的 weight是一個浮點型數(shù),所以weight不能通過計算后查找比如(1.0+2.0)去find3.0。
這里還得明白map的find函數(shù)是通過(key >= lower_bound)&&(lower_bound >= key)實現(xiàn)的。

浙公網(wǎng)安備 33010602011771號