基于A*搜索和深度优先搜索解迷宫问题

FullHouse

发布日期: 2020-06-24 10:59:03 浏览量: 241
评分:
star star star star star star star star star star_border
*转载请注明来自write-bug.com

摘 要

迷宫问题是指能够从起始点寻找一条通往目标点的路径,迷宫的传统搜索是采用深度优先和宽度优先搜索,虽然也能够解决迷宫的求解问题,但是这些方法效率比较低。我们已经知道深度优先和广度优先搜索归于为盲目搜索,搜索中缺乏启发信息,时间和空间浪费较大。本文利用A*算法求解迷宫,按照A*算法的思想,针对迷宫问题提出了求解方案、制定了启发函数、在搜索中使用启发信息,缩小搜索的空间,尽快的求得问题的解,并编程验证了该算法的有效性。

关键词:迷宫问题 ;A*算法;启发函数

引 言

人工智能(Artificial Intelligence ,简称AI) 是近几年来游戏业最炙手可热的研究领域。现代生活中,我们需要在不确定的空间里面寻找一些特定的东西将会需要的越来越多。比如说游戏里面的寻找一条最优解的路径、机器人在一个未知的空间里面救援,这些都是生活中可以应用上的方面, 其中涉及一个寻找路径的问题,即AI 中的图搜索技术。所谓搜索问题,就是在地图上的起点A 和目标点B 之间寻找一条可通行的路径。显然, A 和B 之间可以有很多条路径,我们的目的是用最短的时间找到最佳路径。 在起点A 和目标点B 之间寻找一条最佳路径,其本质就是搜索,是一个从初始节点出发,沿着与之相连的边试探前进,寻找目标节点的过程。 由于搜索具有探索性,所以要找到最佳路径就必须注意搜索策略。 常用的搜索策略分为盲目搜索和启发式搜索两大类[1] ,其中启发式搜索是利用“启发性信息”引导的搜索,搜索效率比较高,而且能找到问题的最优解. 在启发式搜索中,通常用启发函数表示启发性信息,但如何定义启发函数并无固定的模式,需要具体问题具体分析[2]。采用A*算法求解迷宫问题能够比较快速高效的求得问题的解,其中对于A*算法的评估函数的确定又是至关重要的。对于A*算法中启发式函数的选取已有多种选择,有对A*算法估价函数所出现的问题,将距离和角度进行归一化处理[3]; 也有在对当前节点进行评估的思想上,增加了最短路径中当前节点的父节点,并对当前节点与终点节点的距离进行评估,这使得A*算法的搜索方向更加趋向终点,从而提高了搜索速度[4]; 还有一般情况下对启发式函数的设定选择为两点间的欧几里德距离[5]。

本文的启发函数采用对当前节点进行估计的思想,并对当前节点与终结点的距离进行评估,即所谓的曼哈顿距离,使得搜索能够尽快的趋近目标点。

1 实验研究

1.1 实验问题的描述

迷宫问题可以表述为:一个二维的网格,0表示点可走,1表示点不可以走,点用(x,y)表示,寻找从某一个给定的起始单元格出发, 经由行相邻或列相邻的单元格(可以通过的),最终可以到达目标单元格的、所走过的单元格序列。在任一个单元格中,都只能看到与它邻近的4个单元格(如果位于底边,则只有3个;位于4个角上,则只有2个是否能通过。迷宫问题用传统的广度优先搜索或带回溯的深度优先搜索等算法都能很好地解决。当然采用A*算法更能体现对人工智能这门的理解,比起盲目的搜索,A*算法更具有针对性。

1.2 深度优先搜索算法实现

所谓“深度优先”,即:状态树的生长或展开,首先沿状态树的深度方向进行。深度优先搜索算法需要记录下状态树的生长过程[6]。深度优先搜索算法是一种盲目的搜索算法,搜索中可能很多次的搜索到目标点,深度搜索算法通过不断剪枝,寻找出一条从起始点到目标点最近且最省时的路径,即深度优先搜索算法也是一种全局的搜索算法,这样的深度优先搜索算法运用到未知迷宫搜救中是没有意义的。而本次实验中,深度优先搜索算法是以找到目标物为目的,没有剪枝的步骤,只要搜索到目标物,迷宫的搜索过程就成功退出。

深度优先搜索的一些特点:

  • 一般不能保证找到最优解

  • 当深度限制不合理时,可能找不到解,可以将算法改为可变深度限制

  • 最坏情况时,搜索空间等同于穷举

  • 是一个通用的与问题无关的方法[7]

深度优先伪码:

  1. 1Push(S,Open) 将初始节点放入Open表中
  2. 2Judge(S) 判断S节点是不是目标节点,ifS为目标节点),那么找到目标节点
  3. 3While(判断Open表是否为空)
  4. 如果为空,那么搜索失败 end
  5. 否则把第一个节点NOpen表中移至Close表中
  6. 4)将N的后继节点放入Open表中
  7. 5)判断后继节点中是否有目标节点:
  8. If(存在目标节点)
  9. 成功
  10. Else
  11. 返回(3

1.3 A*算法实现

A*算法是人工智能中的一种搜索算法,是一种启发式搜索算法,它不需遍历所有节点,只是利用包含问题启发式信息的评价函数对节点进行排序(Node Ordering),使搜索方向朝着最有可能找到目标并产生最优解的方向[9]。它的独特之处是检查最短路径中每个可能的节点时引入了全局信息,对当前节点距终点的距离做出估计,并作为评价节点处于最短路线上的可能性的度量。

1.3.1 启发函数的确定

A*算法中引入了评估函数,评估函数如下:

  1. f(n) = g(n) + h(n)

其中:n是搜索中遇到的任意状态。g(n)是从起始状态到n的代价。h(n)是对n到目标状态代价的启发式估计。即评估函数f ( n) 是从初始节点到达节点n 处已经付出的代价与节点n 到达目标节点的接近程度估价值的总和[10]。

这里我们定义n点到目标点的最小实际距离为h(n)*,A*算法要满足的条件为:

  1. h(n) <= h(n)*

由前面的迷宫问题的描述我们可以知道,迷宫走的时候只能往上下左右走,每走一步,代价为1,这里我们采用的估价函数为当前节点到目标节点的曼哈顿距离,即:

  1. h(n)= |end.x n.x| + |end.y n.y|

这里end表示迷宫的目标点,n表示当前点,很明显这里h(n) <= h(n)*。

g(n)容易表示,即每走一步的代价是1,所以利用f(n) = g(n) + h(n) 这种策略,我们可以不断地逼近目标点,从而找到问题的解。

1.3.2 A*的主要实现步骤的伪码表示

  1. 1 OPEN:=(s), f(s):=g(s)+h(s);
  2. 2LOOP: IF OPEN=( ) THEN EXIT(FAIL);
  3. 3 n:=FIRST(OPEN);
  4. 4IF GOAL(n) THEN EXIT(SUCCESS);
  5. 5REMOVE(n, OPEN), ADD(n, CLOSED);
  6. 6EXPAND(n) →{mi},
  7. 计算f(n, mi):=g(n, mi)+h(mi);
  8. ADD(mj, OPEN), 标记mjn的指针;
  9. IF f(n, mk)<f(mk) THEN f(mk):=f(n, mk),
  10. 标记mkn的指针;
  11. IF f(n, ml)<f(ml,) THEN f(ml):=f(n, ml),
  12. 标记mln的指针,
  13. ADD(ml, OPEN);
  14. 7OPEN中的节点按f值从小到大排序;
  15. 8GO LOOP

这里OPEN表和CLOSED表分别用来存储要搜索的状态结点和存储已经访问过的状态。

2 编程实现

该测试程序在 VS2013 环境下编译实现,编程语言用的是 C 语言。

2.1 代码中数据结构设计

  1. struct mark //定义迷宫内点的坐标类型
  2. {
  3. int x;
  4. int y;
  5. };
  6. struct mark start,end; //start,end入口和出口的坐标
  7. struct Element //栈元素,
  8. {
  9. int f;//估价函数
  10. int g;//代价
  11. int h;//启发函数
  12. int x,y; //x行,y列
  13. };
  14. Element elem,e;
  15. typedef struct LStack //链栈
  16. {
  17. Element elem;
  18. struct LStack *next;
  19. }*PLStack;
  20. PLStack Open,Close;//OPEN表和CLOSE表用来储存链节点

2.2 函数框架实现

  1. InitStack(Open); //用于初始化open 表
  2. InitStack(Close); //用于初始化close表
  3. Push(Open,elem); //表示初始节点elem进入open表
  4. while(!StackEmpty(Open)&&Flag==0) //栈不为空 有路径可走
  5. {
  6. Pop(Open,elem); //将open表中的当前元素提出来
  7. Push(Close,elem);//将从open表取出来的元素放入close表
  8. if(判断elem节点的子节点是否可以走)判断上下左右{
  9. ifelem_child不为目标节点){
  10. Push(Open,elem_child) 子节点进Open表,这里的push()函数进入栈中,为有序进入,也就是说进栈是按顺序插入的。
  11. }//if
  12. else(该节点为目标节点){
  13. Push(Close,elem_child)//目标节点进close表
  14. Flag=1//将标志置为一表示已经找到了目标节点
  15. End//找到了目标节点结束
  16. }//else
  17. }//if
  18. }//while
  19. ifStackEmpty(Open)||Flag==0
  20. printf(”迷宫没有解\n”) //表示走到这里还没有找到解则迷宫走不出去

2.3 核心函数代码

  1. int InitStack(PLStack &S) //初始化链栈,Open表和Close表初始化
  2. {
  3. S=NULL;
  4. return 1;
  5. }
  6. int StackEmpty(PLStack S)//判断栈是否为空
  7. {
  8. if(S==NULL)
  9. return 1;
  10. else
  11. return 0;
  12. }
  13. int Push1(PLStack &S, Element e)//压入新数据元素
  14. {
  15. PLStack p;
  16. PLStack q,t;
  17. p=(PLStack)malloc(sizeof(LStack));
  18. p->elem.g=deep;//表示深度
  19. //估价函数即使用曼哈顿距离表示
  20. p->elem.h=abs(end.x-e.x)+abs(end.y-e.y);
  21. p->elem.f=p->elem.h+p->elem.g;
  22. p->elem.x=e.x;
  23. p->elem.y=e.y;
  24. p->next=NULL;
  25. if(NULL==S||p->elem.f<=S->elem.f)
  26. {
  27. p->next=S;
  28. S=p;
  29. //return 1;
  30. }
  31. else
  32. {
  33. q=S;
  34. t=q->next;
  35. while(t!=NULL)
  36. {
  37. if(p->elem.f>t->elem.f)
  38. {
  39. q=t;
  40. t=t->next;
  41. }
  42. else
  43. break;
  44. }
  45. p->next=t;
  46. q->next=p;
  47. }
  48. return 1;
  49. }
  50. int Pop(PLStack &S,Element &e) //栈顶元素出栈
  51. {
  52. PLStack p;
  53. if(!StackEmpty(S))
  54. {
  55. e=S->elem;
  56. p=S;
  57. S=S->next;
  58. free(p);
  59. return 1;
  60. }
  61. else
  62. return 0;
  63. }

2.4 界面设计

界面设计非常友好、清晰、表达明确、功能集中、操作简单。

迷宫大小设定为18*25的,入口和出口的位置分别设为(1.0)、(16,24),迷宫状态用一个二维表存储,0表示可以走,即界面中的可行域表示,1表示不能走,即界面中的黄金墙和铂金墙。可选的地图有三个,每次只能选择一个,选择完地图之后就可以画迷宫了,之后就可以搜索了。

我采用的Windows API程序设计,整个的界面是利用windows程序设计的窗口设计实现的,地图的样子是通过一个地图编辑器来实现的,总体给人的感觉是比较清楚、清晰,也比较新颖。然后把地图当作图片画出来,即每一小格代表的数字,决定了地图将会画出什么颜色的图片来,当二维表中的数据为1时,我们就可以画出墙的图片,当其中数据为0是我们就可以画出可行域的图片。通过这样的方法,我们可以比较简单的实现地图样式的变换,能够达到非常不错的效果,旁边的选择地图按钮能够帮助我们选择我们想要的地图,选择好了之后,运行完程序,然后通过地图重置可以实现地图的删除,然后可以再进行地图的选择,非常方便的实现了地图的更换。

调用函数:

  1. HWND hmap;
  2. HDC hm;
  3. hmap = GetDlgItem(hwnd,IDC_MAP);
  4. hm = GetDC(hmap);

将整个窗口的句柄控制,使用函数:

  1. BitBlt(hm,x,y,p_Lsize,p_Hsize,h,0,0,SRCCOPY);

其中hm为窗口句柄,x,y为对应位置的坐标,p_Lsize,p_Hsize为图片的大小,h为图片画的位置,这样就可以画出界面了。

2.5 运行结果分析

从程序运行的结果我们可以知道,深度优先搜索和A*搜索两种搜索策略都实现了。我们也已经知道,深度优先搜索是一种盲目的搜索,也就是说搜索过程中并没有带启发式信息,而A*搜索带了启发式信息,在程序运行过程中,我们可以明显的感知,这两种算法的区别。

我通过实验验证了深度优先搜索和A*搜索在本规模迷宫环境下的情况,可以利用遍历Open表和Close表中的节点,得出所扩展的节点和所走的步数。这里我们可以计算出三个地图走出迷宫需要走的步数。

下面的数据为两种搜索算法从初始节点走到目标节点所走的步数:

地图 所走步数
深度优先搜索 A*搜索
地图一 178 90
地图二 207 87
地图三 218 82

从上表我们可以明显看出来采用启发式的A*搜索比盲目的深度优先搜索所走的步数更少,也就是说,在迷宫问题中采用A*搜索算法较传统的深度优先搜索能更快的找到迷宫的目标节点,并且效率提高的非常快。从表中可以看出,效率提高了两倍多,这样在更大规模的迷宫问题中,能够节约更多的时间找到问题的解。

3 总结

刚开始本来想编程实现深度优先搜索求解迷宫问题,当上课后接触到了A*算法觉得,这个算法应该同样能够用来解决迷宫问题。于是就在以前的基础上添加了A*算法求解迷宫的过程。

在实验中,相对于刚开始采用盲目的深度优先搜索,能够明显的发现采用A*算法大大的提高了搜索的效率,主要归功于A*算法在搜索过程中通过引入启发式信息来实现向目标节点移动的判别,无须遍历地图,使得计算复杂度相对较小,实现了快速、高效。但是,这也导致搜索的过程中排除了大量节点,而由于经验及实际问题的复杂性,引入启发信息的代价函数无法做到完全正确,这些被排除的节点可能就是最优路径的节点之一。所以采用A*算法搜索迷宫,并不能总是找到最优路径,我们很有可能因为引入的启发式代价函数不合适,而丢弃了可能的最优路径节点。

总体来说,对于一个未知大小迷宫问题,在仅知道目标点的大概位置的情况下进行搜索时,A*算法要优于深度优先搜索算法。

参考文献

[1] 何国辉,陈家琪. 游戏开发中智能路径搜索算法的研究[J] . 计算机工程与设计,2006 ,27 (13) :233422337.

[2] 叶展,叶丁. 游戏的设计与开发[M] . 北京:人民交通出版社,2003 :3632369.

[3] 史辉,曹闻,朱述龙. A* 算法的改进及其在路径规划中的应用[J]. 测绘与空间地理信息,2009,32( 6) : 208-211.

[4] 张仁平,周庆忠,熊伟. A* 算法改进算法及其应用[J]. 计算机系统应用,2009,18( 9) : 98-100,107.

[5] NOBORIO H,FHJIMURA K,HORIUCHI Y. A comparative study ofsensor-based path-planning algorithms in an unknown maze[C]/ /Proc of IEEE/RSJ International Conference on Intelligent Robots and Systems. 2000: 909-916.

[6] 高济, 朱淼良, 何钦铭. 人工智能基础[M]. 北京: 高等教育出版社, 2002,22-24.

[7] Nilsson N J. Artificial Intelligence: A New Synthesis[M]. Morgan Kaufmann, 1998,88-90.

[8] 陈和平,张前哨. A~*算法在游戏地图寻径中的应用与实现[J]. 计算机应用与软件. 2005(12).

[9] 邱磊. 基于A~*算法的游戏地图寻路实现及性能比较[J]. 陕西科技大学学报(自然科学版). 2011(06).

[10] GOTO T,,KOSAKA T,NOBORIO H.On the heuristics of A*or an al-gorithm in ITS and robot path-planning. Proc of IEEE/RSJ In-ternational Conference on Intelligent Robots and Systems . 2003.

[11] 刘翔,龚道雄. 深度优先搜索算法和A*算法在迷宫搜索中的仿真研究[J]. 制造业自动化. 2011(11).

上传的附件 cloud_download 基于A-Star搜索和深度优先搜索解迷宫问题.7z ( 395.30kb, 2次下载 )
error_outline 下载需要12点积分

发送私信

人生百年,转眼成空。幸福靠的不是缘分,而是珍惜

7
文章数
8
评论数
最近文章
eject