首页 > 程序开发 > 软件开发 > C语言 >

经典算法研究系列:一之续、A*,Dijkstra,双向BFS算法性能比较及A*算法的应用

2011-04-10

 本文,即以演示图的形式,比较它们各自的寻路过程,让各位对它们有一个清晰而直观的印象。    我们比较,以下五种算法:        1. A* (使用曼哈顿距离)   &nbs

本文,即以演示图的形式,比较它们各自的寻路过程,让各位对它们有一个清晰而直观的印象。
我们比较,以下五种算法:
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值最小的结点进行展

相关文章
最新文章
热点推荐