基于C#实现的多种路径搜索算法模拟程序

Haggard

发布日期: 2020-11-18 10:26:46 浏览量: 128
评分:
star star star star star star star star star star_border
*转载请注明来自write-bug.com

1 题目背景

小王是一位职业电竞选手,且胜率保持在 100%。在一次比赛的过程中,小王饥寒交迫。但是为 了保持体力,他需要寻找他最爱的热狗。但是中间会有重重阻碍,比如写有“我爱 wxz”的灯牌、“新 浪微博”、“暖宝宝”、“老王”以及无法逾越的墙壁。小王开始了他对热狗的寻求之旅。

2 UI 设计及操作方法

UI 整体面板如下。采用单面板设计,简洁且美观。UI 部分分为地图区、按钮区、设置区。由于 时间关系,没有进行美工,但是能够体现出本次大作业的核心,即对于不同搜索算法的理解和比较。

单终点搜索程序界面

多终点搜索程序界面

2.1 UI 设计

2.1.1 地图区域

地图区域主要应用的控件为 button,即地图上的每一个点是一个 button。在点击新游戏之后,根据设置的方形地图大小动态生成 button,且每个 button 有自己的众多属性。点击按钮,则会按照对应的地图设置方式进行起点、终点或者障碍物的设置。

2.1.2 按钮区

按钮区主要包括“建立新游戏”、“开始搜索/模拟退火”、“隐藏/显示障碍物”、“刷新地图”、“载入地图”、“保存地图”。其中,“建立新游戏时”,要先输入地图的大小,默认地图大小为 8×8。

2.1.3 地图设置区

可以选择地图的设置方式,即设置“障碍物”、“起点”、“终点”。而对于障碍物,可以设置不同等级,代价分别从 2 到 5(路面代价为 1,墙的代价为 ∞)。且可以对是否设置多终点进行选择,如果进行多终点设置,则显示终点的总个数。

2.1.4 搜索方法选择区

对于单终点搜索,搜索方法有“BFS”,“双向 BFS”,“A* 算法”,“迭代加深搜索”,“贪婪最佳优先搜索”,“Dijkstra”;对于多终点搜索,搜索方法为模拟退火 1 。对于搜索邻域,可以选择“四方向搜索”与“八方向搜索”。而对于距离类型,可以选择“欧氏距离”、“曼哈顿距离”、“对角距离”。

2.2 开发与程序运行环境

2.2.1 开发环境

本程序基于 VS2017 开发,使用 C# 语言编写。

2.2.2 程序运行环境

运行时,请将分辨率设置为 1366×768,Win10 系统。

2.3 程序操作

2.3.1 创建新游戏

设置地图大小,点击新游戏后,即开始新游戏,且在游戏过程中点击新游戏,会直接重置为新游戏。

2.3.2 设置起点、终点及障碍物

设置起点、终点以及障碍物操作基本相同,即首先选择设置方式,点击地图上的点即可设置,再点击一个可以取消设置。

2.4 地图的载入与保存

地图保存成 txt 文件,将地图 mapData 存成矩阵的形式 (mapData 存储障碍物的信息)。地图的载入即将所保存的 txt 文件读取进来。

2.5 搜索方式选择

选择好对应的搜索方法、搜索邻域、距离类型后,点击开始搜索即可进行搜索,且在地图上会显示访问记录及目标路径。其中,“宽度优先搜索”、“双向 BFS”、“迭代加深搜索”、“贪婪最佳优先搜索”将所有代价一视同仁,即除了墙之外的路的代价均为 1。而“A* 算法”、“Dijkstra”、“模拟退火”均考虑了不同代价带来的影响。

2.6 便于观察的其他操作

由于没有对界面做太多的美工,故在搜索结果的可视性上需要相应的措施进行提高。 “隐藏与/显示障碍物”主要为了避免由于 Button 的图片设置而挡住了其背景颜色;“刷新地图”是用于在比较不同的搜索算法时,将访问记录和目的路径删除,即只保留起点、终点以及障碍物,便于下一个方法的搜索。除此之外,由于起点、终点只在最初时的 button 上进行设置,即在搜索路径和访问记录上,无法进行起点、终点的设置,故可以考虑刷新地图之后再进行起点、终点的设置。

3 数学建模

3.1 单终点搜索

对于单终点搜索,将该实际问题抽象为迷宫寻径问题,即构成以地图上的点 (Button) 为节点,以两节点连线为边的无向图。边的权重为所经过的下一个顶点的代价值。搜索的过程即从起点开始进行图搜索,直到搜索到目标节点为止。

3.2 多终点搜索

对于多终点搜索,将该实际问题抽象为 TSP 问题 (Traveling Salesman Problem,旅行商问题) 。将起点作为出发城市,多个热狗 (终点) 作为其他所需要经过的城市,经过所有的城市之后,回到最初的起点。

4 项目架构

项目主要分为逻辑层和界面层,逻辑层为搜索算法,界面层为对地图的更新。逻辑层与界面层的交互是通过地图信息的读取和地图界面的更新进行。整体框图如下:

除此之外,定义节点类,相关代码如下:

5 搜索算法的实现

5.1 宽度优先搜索

使用 Queue(队列) 进行操作,可以选择四方向和八方向搜索,无距离概念。

5.2 双向 BFS

从起点和终点同时进行 BFS,当相遇时即停止搜索。可以选择四方向和八方向搜索,无距离概念。

5.3 迭代加深搜索

使用 Stack(栈) 进行操作,可以选择四方向和八方向,无距离概念。

5.4 A* 算法

使用 SimplePriorityQueue(优先级队列) 进行实现,可以选择四方向和八方向,距离分为欧氏距离、曼哈顿距离、对角距离。

为了便于比较,将没有使用优先级队列的 A* 算法与其进行对比。

5.5 贪婪最佳优先搜索

使用 SimplePriorityQueue(优先级队列) 进行实现,可以选择四方向和八方向,距离分为欧氏距离、曼哈顿距离、对角距离,需要考虑到代价的不同。和只考虑 h(n) 的 A* 算法比较相似。

5.6 Dijkstra

使用 SimplePriorityQueue(优先级队列) 进行实现,可以选择四方向和八方向,距离分为欧氏距离、曼哈顿距离、对角距离,需要考虑到代价的不同。和只考虑 g(n) 的 A* 算法比较相似。

5.7 模拟退火

对于多终点问题,可以考虑使用模拟退火算法,具体算法和流程图 7 如下。

模拟退火解决 TSP 问题流程图

6 运行效果

6.1 无障碍物

6.1.1 无距离定义搜索算法

BFS 四方向邻域和八方向邻域搜索

BFS 四方向邻域和八方向邻域搜索

BFS 四方向邻域和八方向邻域搜索

BFS 四方向邻域和八方向邻域搜索

无信息搜索这几个算法搜索类似。在代价都相同的情况 (如为 1) 下,DijkStra 与 BFS 几乎完全相同,与理论符合。双向 BFS 与单向 BFS 相比,访问的节点数更小,与理论符合。

6.1.2 有距离定义搜索算法

A* 算法四方向邻域,三种不同的距离定义

A* 算法八方向邻域,三种不同的距离定义

A* 算法八方向邻域,三种不同的距离定义

A* 算法在四邻域搜索时,欧氏距离与对角距离几乎相同,且路径尽可能走对角线,而曼哈顿距离则走规则的矩形的两边,且访问的节点数相对少一些。

A* 算法在八邻域搜索时,欧氏距离、曼哈顿距离、对角距离几乎相同,且路径走对角线。曼哈顿距离访问的节点数要比欧式距离和对角距离稍微多一些。

A* 算法使用优先级队列后,曼哈顿距离四方向搜索路径会有所改变,其他几乎没有差异。

贪婪最佳优先搜索算法四方向邻域,三种不同的距离定义

贪婪最佳优先搜索算法八方向邻域,三种不同的距离定义

贪婪最佳优先搜索算法在四邻域搜索时,欧式距离与对角距离几乎完全相同,且路径尽可能走对角线,而对于曼哈顿距离,路径走矩形的两边,且三者访问的节点数均较少。

贪婪最佳优先搜索算法在八邻域搜索时,三者几乎完全相同,路径走对角线,访问节点数较少。

小结

有信息搜索的效率 (A* 算法、贪婪最佳优先搜索) 要高于无信息搜索 (BFS,双向 BFS,迭代加深搜索) 的效率,且贪婪最佳优先搜索访问节点数要远少于其他所有算法,效率最高,即直接向终点节点进行搜索。

6.2 障碍物只有墙

地图文件为 test2.txt。

6.2.1 无距离定义搜索算法

BFS 四方向邻域和八方向邻域搜索

双向 BFS 四方向邻域和八方向邻域搜索

Dijkstra 四方向邻域和八方向邻域

无信息搜索这几个算法搜索类似 9 。在代价都相同的情况 (如为 1) 下,DijkStra 与 BFS 几乎完全相同,与理论符合。双向 BFS 与单向 BFS 相比,访问的节点数更小,与理论符合。

6.2.2 有距离定义搜索算法

A* 算法四方向邻域,三种不同的距离定义

A* 算法八方向邻域,三种不同的距离定义

A* 算法 (优先级队列) 四方向邻域,三种不同的距离定义

A* 算法 (优先级队列) 八方向邻域,三种不同的距离定义

A* 算法在有障碍物的情况下与无障碍物的情况类似,故不再赘述。

贪婪最佳优先搜索算法四方向邻域,三种不同的距离定义

贪婪最佳优先搜索算法八方向邻域,三种不同的距离定义

贪婪最佳有限搜索算法在有障碍物的情况下与无障碍物的情况类似,故不再赘述。

小结

在障碍物比较少的时候,有信息搜索的效率要高于无信息搜索的效率,且贪婪最佳优先搜索访问的节点数最少,效率最高。

6.3 墙的地形崎岖

地图文件为 test3.txt。

6.3.1 无距离定义搜索算法

BFS 四方向邻域和八方向邻域搜索

双向 BFS 四方向邻域和八方向邻域搜索

Dijkstra 四方向邻域和八方向邻域

在障碍物 (墙) 比较多且绕路时,BFS 与双向 BFS 访问节点数均较多,双向 BFS 访问节点数相对较少。

6.3.2 有距离定义搜索算法

A* 算法四方向邻域,三种不同的距离定义

A* 算法八方向邻域,三种不同的距离定义

A* 算法在四邻域方向进行搜索,访问节点数均较多。其中,曼哈顿距离访问的节点较少,欧氏距离和对角距离访问节点数相当。

A* 算法在把淋浴方向进行搜索,访问节点数同样较多。其中,曼哈顿距离访问的节点较少,其次是欧式距离,对角距离访问的节点数最多。且三者的最终路径均不同,不同于前两种情况。

贪婪最佳优先搜索算法四方向邻域,三种不同的距离定义

贪婪最佳优先搜索算法八方向邻域,三种不同的距离定义

最佳优先搜索,欧氏距离和曼哈顿距离访问的节点数要少于对角线距离。

小结

在障碍物较多时 (道路崎岖),A* 算法和贪婪最佳优先搜索的优势大大下降。有信息搜索访问的节点数与无信息搜索访问的节点数相近,主要原因是启发函数对搜索的帮助不是很大,甚至会误导搜索的方向 (这对于贪婪最佳优先搜索最为明显,即先朝向终点行走,遇到墙转向,最后得到非最优解)。但贪婪最佳优先搜索的访问节点数还是相对较少。

6.4 有其他障碍物

地图文件为 test4.txt。对于含有不同代价的路径搜索,只考虑对比 A* 和 Dijkstra。

A* 算法四方向搜索,右图为隐藏障碍物后

A* 算法八方向搜索,右图为隐藏障碍物后

Dijkstra 算法四方向,右图为隐藏障碍物后

Dijkstra 算法八方向,右图为隐藏障碍物后

A* 算法访问节点数要少于 Dijkstra,且在八邻域方向搜索效果更佳明显,符合理论。

6.5 多终点

无障碍多终点模拟退火

少障碍多终点模拟退火

多障碍多终点模拟退火

访问数字从 0 一直到最后,颜色是几种颜色进行循环。

6.6 大地图

地图文件为 test5.txt。选取地图为 70×70,在起点附近和终点附近都有一定的障碍。统计算法运行时间如下:

无信息搜索算法运行时间

有信息搜索算法运行时间

7 不同搜索算法的效率比较

7.1 单终点

有上述表格可以看出 11 ,对于无信息搜索,双向 BFS 花费的时间要比 BFS 少,Dijkstra 时间远大于 BFS 算法和双向 BFS 算法。基本符合 BFS、双向 BFS 为 o(n+e) 时间复杂度、Dijkstra 为o((n + e)logn) 的复杂度。

而对于有信息搜索,贪婪最佳有限搜索最快。A* 算法在使用优先级队列后,时间有所减少,且优化较多。且使用优先级队列后的路径与未使用时不同,访问节点更少。四方向搜索中,曼哈顿距离效果最好;八方向搜索三者均较快。对于这种障碍物较少的地图,A* 算法的时间在贪婪最佳优先搜索和 Dijkstra 算法之间,符合理论。

有信息搜索与无信息搜索之间相比,贪婪最佳有限搜索效率最高,使用优先级队列且采用曼哈顿距离的 A* 算法与 BFS 时间接近。理论上 A* 应该快一点,但是考虑到内部实现的细节后,并没有大碍。此外,欧氏距离和对角线距离的效果较差。

7.2 多终点

对于多终点问题,即可以转化为 TSP 问题。由于时间关系只做了模拟退火方法。若将模拟退火和蛮力算法进行比较,则在终点个数比较少的情况下,蛮力算法更具有优势;而对于较多的终点时,则由于 TSP 问题是阶乘复杂度,故蛮力算法要得到最优解,则可能花费的时间会很长。而使用模拟退火,即以一定概率允许下山,这样得到的解可能不是最优解,但是会尽可能接近最优解,且时间较快。

8 总结与反思

8.1 问题与解决

8.1.1 迭代加深搜索

迭代加深搜索虽然过程比较简单,但是在写代码时,里面有很多小的细节。而且由于时间关系,我的迭代加深搜索还没有优化到极致,所以耗时非常长。但是考虑到迭代加深搜索的应用范围不是很广,故没有将其与其他算法进行比较。

8.1.2 UI 美工方面

计划是要做一个游戏风格的界面,但是由于时间关系以及本次大作业的核心是在于搜索算法的实现以及不同搜索算法效率之间的比较,所以没有将界面加大量美工,只是保持着最初的灰色风格。

8.2 总结与反思

本次人智大作业,让我对各个搜索算法都有了一定的了解,同时对于多终点问题,我实现了模拟退火算法。本来想实现其他的一些优化算法,但是由于时间关系,并没有去实现其他优化的算法。

上传的附件 cloud_download 基于C#实现的多种路径搜索算法模拟程序.7z ( 16.04mb, 1次下载 )
error_outline 下载需要12点积分

发送私信

所有的道别里,我还是最喜欢明天见

16
文章数
12
评论数
最近文章
eject