寻路算法实践1

时间:2022-04-23 15:17:47

本文乃Siliphen原创,转载请注明出处:http://blog.csdn.net/stevenkylelee


寻路算法实践一共2篇文章

下一篇《寻路算法实践2》:http://blog.csdn.net/stevenkylelee/article/details/7605836




最近一段时间学了 Qt , Boost , 图论基础算法 后,就做了这个练习作品。

本程序是为了测试,从点S到点D是否有通路。如果有通路,那么路径都是什么

最短的路径又是什么。

 

 先上运行时的效果图吧。

(可执行程序和源代码下载在本帖末尾)

 

寻路算法实践1

 

 

点击左下角的“开始搜索”按键后,就会按照按钮右边的组合框中选择的算法来搜索从S到D的路径。

目前实现的算法有:DFS,BFS,自己的一个启发式,Bellman-Ford , Dijkstra

如下图:

 

寻路算法实践1

  

下图是用 Dfs 搜索的结果

 

寻路算法实践1

 

在地图上右键,选择“显示搜索树”,会看到搜索过程生成的一棵“访问过的路径”的树映射到地图上的形态。

树节点的数值有2种。一种是顶点被的访问顺序号。另一种是顶点距离源点S的路径长度。

对于BFS,DFS来说,路径长度是顶点距离源点S的边数。

对于求最短路径算法来说,路径长度是距离源点S的边权值总和(定义直边是20,斜边28)

效果如下图:(嘿嘿,这可以方便直观地看到算法的执行效果)

 

寻路算法实践1

 

DFS(随机) 是盲目搜索。

随机的意思是,在搜索过程中,随机选择当前访问的顶点的邻居顶点来入栈或入队。

所以,每次执行DFS、BFS(随机)生成的路径和路径树都可能不一样、

 

BFS(随机)有比较大的几率找到S到D的最短路径,但通常它只是找到一条接近最短路径的路径。

原因就是BFS只考虑边,而不考虑边的权值。(斜边的长度和直边是不同的)

 

我的启发式搜索,启发函数是优先挑选距离目的地D最近的那个顶点来扩展。

其实,我写的DFS,BFS,启发式 结构上都非常类似。OPEN表用STL的deque容器。

顶点的邻居顶点push_back到容器,然后容器从末端pop顶点出来扩展的话,就是DFS

从前端pop的话,就是BFS。

如果,根据某种信息从容器中挑选一个认为最有希望找到D的顶点出来扩展的话,就是启发式了。

当然,我的启发式很简单。能比较快地找到去D的路径,但不保证那条路径是最短的。- -

 

启发式效果图:

 

寻路算法实践1

 

 

关于最短路径:

找最短路径有比较多的做法。本人水平有限,目前就只做了Bellman-Ford和Dijkstra。呵呵。

Bellman-Ford不复杂。一句话可以总结,那就是:对所有的边都进行N-1次松弛。

 

Bellman-Ford执行效果图:

 

寻路算法实践1

 

Bellman-Ford 能计算负权回路,但执行效率比较低。

本程序中当然不存在负权值的边(一点到另一点的距离是负的,这不可能吧)

做上Bellman-Ford纯属练习咯。呵呵。

 

计算最短路径比Bellman-Ford快的,有Dijkstra。但Dijkstra只能计算没有负权回路的网。

Dijkstra也能用一句话总结:迭代N次,每次选择一个距离源点S最近的顶点出来,并松弛该顶点的所有邻边。

每次迭代选出一个顶点,就得到了源点S到该顶点的最短路径。

Dijkstra很类似BFS,它也是一圈圈地向外”扩张“找目的地。

 

Dijkstra执行效果如下:

 

寻路算法实践1

 

最后,关于地图:

在地图上右键,弹出的菜单,可以编辑地图:重设起点、终点的位置。增加、删除障碍物。

地图也可以保存到文件,或从文件中载入。

本来,我打算用Boost的multi_array类,模拟动态二位数组,做地图的。

但该类与我用的Qt版本冲突,无法通过编译。

百度只出了一篇英文文章,说什么Qt语法扩展与该类实现代码不兼容。- -

没辙,只好自己封装个类,写operator=

内部维护一个 vector< vector< int > > 类型的对象做地图了。

 

 

我的程序的可执行文件下载地址:

http://download.csdn.net/detail/stevenkylelee/4054168

源代码下载地址:

http://download.csdn.net/detail/stevenkylelee/4054346

 

编写这个程序的环境是:

Qt Creator 2.8.1

Qt 4.7.4

Boost 1.48.0

 

除了C++语言外。做这程序的所有技术,俺都是最近学到的。

SO,肯定有巨多不足。这还望高手指点!寻路算法实践1