频道栏目
首页 > 程序开发 > 软件开发 > C语言 > 正文
经典算法研究系列:一之续、A*,Dijkstra,双向BFS算法性能比较及A*算法的应用
2011-04-10 14:00:38           
收藏   我要投稿

 本文,即以演示图的形式,比较它们各自的寻路过程,让各位对它们有一个清晰而直观的印象。
    我们比较,以下五种算法:
        1. A* (使用曼哈顿距离)
        2. A* (采用欧氏距离)
        3. A* (利用切比雪夫距离)
        4. Dijkstra
        5. Bi-Directional Breadth-First-Search(双向广度优先搜索)

    咱们以下图为例,图上绿色方块代表起始点,色方块代表目标点,色的方块代表障碍物,白色的方块代表可以通行的路径。
    下面,咱们随意摆放起始点绿块,目标点红块的位置,然后,在它们中间随便画一些障碍物,
    最后,运行程序,比较使用上述五种算法,得到各自不同的路径,各自找寻过程中所覆盖的范围,各自的工作流程,并从中可以窥见它们的效率高低。


A*、Dijkstra、BFS算法性能比较演示:
    ok,任意摆放绿块与红块的三种状态:
一、起始点绿块,与目标点红块在同一条水平线上:\


各自的搜寻路径为:
        1. A* (使用曼哈顿距离)\

        2. A* (采用欧氏距离)\

        3. A* (利用切比雪夫距离)\

        4. Dijkstra 算法.//很明显,Dijkstra 搜寻效率明显差于上述A* 算法。(看它最后找到目标点红块所走过的路径,和覆盖的范围,即能轻易看出来,下面的比较,也是基于同一个道理。看路径,看覆盖的范围,评价一个算法的效率)。

\ 

       5. Bi-Directional Breadth-First-Search(双向广度优先搜索) \

 

二、起始点绿块,目标点红块在一斜线上:

\

各自的搜寻路径为:
        1. A* (使用曼哈顿距离)\

        2. A* (采用欧氏距离)\

        3. A* (利用切比雪夫距离)\

        4. Dijkstra 算法。 //与上述A* 算法比较,覆盖范围大,搜寻效率较低。

 \

        5. Bi-Directional Breadth-First-Search(双向广度优先搜索)\ \

 

三、起始点绿块,目标点红块被多重障碍物阻挡:

\

各自的搜寻路径为(同样,还是从绿块到红块):
        1. A* (使用曼哈顿距离)\

        2. A* (采用欧氏距离)..\

        3. A* (利用切比雪夫距离)\

        4. Dijkstra....\

        5. Bi-Directional Breadth-First-Search(双向广度优先搜索)  //覆盖范围同上述Dijkstra 算法一样很大,效率低下。\\


A*搜寻算法的高效之处
      如上,是不是对A*、Dijkstra、双向BFS算法各自的性能有了个总体大概的印象列?由上述演示,我们可以看出,在最短路径搜寻效率上,一般有A*>Dijkstra、双向BFS,其中Dijkstra、双向BFS到底哪个算法更优,还得看具体情况。
      由上,我们也可以看出,A*搜寻算法的确是一种比较高效的寻路算法。

      A*算法最为核心的过程,就在每次选择下一个当前搜索点时,是从所有已探知的但未搜索过点中(可能是不同层,亦可不在同一条支路上),选取f值最小的结点进行展

点击复制链接 与好友分享!回本站首页
上一篇:经典算法研究系列:二之三续、Dijkstra 算法+Heap堆的完整c实现源码
下一篇:经典算法研究系列:三、动态规划算法解微软一道面试题[第56题]
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站