A* 算法的数据结构

 

原始需求:求某电车到D公里范围内的地图显示

转换需求

  第一步:由某个点P到距离恰好大于等于D公里的所有的路的集合求出来

      第二步:所有的路外的点组成polygon 然后渲染

 

第一步的详细算法A*:

        1.我们有一个空的集合C用来放符合条件的R,和某个点P(简单起见,假设P在路上,用R表示路)

        1.1 R有属性id,权重weight(也就是路到A点的当前路径的距离)

        2. R根据graph模块找到和他直接相连的几条路Rx1…Rxn ,Rx1…Rxn权重weight小于D公里时放入集合C。在放入集合之前

           查看C中和Rx1…Rxn id是否有相同的Rx,如果有并且新的权重大的话就更新权重,否则放弃更新。 

        3. 在集合C中找到一个权重weight最小的Rmin

        4. 如果Rmin 的权重weight 小于D 重复2,3步。

           否则退出循环,表示目前的集合C已经满足情况。

 

 

本文重点-集合C需要的特性:

  1.根据id 快速查找id相同的Rx1…Rxn 

  2.插入新的Rx1…Rxn 

  3.根据权重weight找到Rmin

  4.删除Rmin

 

  也就是说集合C需要快速查找,插入,删除,有序。看到这个需求同事用了2版数据结构

  第一版:二叉堆版的优先级队列priority_queue, 性能7s,方案错误

      优点O(logN)的插入和删除Rmin,缺点O(N)的id查找,无法删除飞最小值

 

  第二版:有序链表版的优先级队列,性能5s

  优点O(1)的删除Rmin,缺点O(N)的id查找,O(N)的插入

 

  由LRU cache的list+map启发:

  第三版:list无序存放R,map1存放{id, node指针}, multimap存放{weight, node指针},性能1s

      优点:O(logN)的map1查找,更新,multimap的删除Rmin,插入

      缺点:这里的 weight是一个浮点型数,所以weight不能通过计算后查找比如(1.0+2.0)去find3.0。

           这里还得明白map的find函数是通过(key >= lower_bound)&&(lower_bound >= key)实现的。

 

 

 

 

 

 

原文地址:https://www.cnblogs.com/water-bear/p/15036071.html