实验四：A星算法求解迷宫问题实验

1、实验4:解决迷宫问题实验的算法一、实验目的熟悉和掌握启发式搜索的定义、评估函数和算法过程，利用A*算法解决迷宫问题，了解解决方案过程和搜索顺序。二、实验内容迷宫问题可以表示为二维网格，0不能点走，1不能点走，点为(x，y)，从给定起始单元格开始，通过相邻行或列(可通过)找到相邻单元格，最终到达目标单元格，经过的单元格顺序等。在任何单元格中，只能看到其旁边的4个单元格(如果在底部边缘，则有3个)，如果在4个边缘，是否只能通过2个。A*算法是人工智能的搜索算法，它使用包含问题发现信息的评估函数对节点进行排序，从而定位搜索方向最可能的目标，并向生成最佳解决方案的方向移动，而无需遍历所有节点。在确定最

2、短路径上每个可能的节点时，引入了全局信息，以估计端点处的当前节点距离，并用作评估节点在最短路径上的可能性的度量。A*算法引入了f(n)=g(n) h(n)评估函数其中：n是搜索中发生的任意状态。G(n)是从开始状态到n的成本。H(n)是从n到目标状态的成本的启发式估计。也就是说，评估函数f (n)是初始节点到节点n的成本和节点n到目标节点的估计值的总和。其中，从n点到目标点的最小实际距离为h(n)*，A*算法为h(n)=h(n)*迷宫只能一步一步上下左右。此处，从当前节点到目标节点的曼哈顿距离，即：h(n)=| end . xn . x | | end . yn . y |其中end表示迷宫的

3、目标点，n表示当前点。其中h(n)=h(n)*。G(n)很容易表示。也就是说，每个阶段的成本都是1，因此使用像f(n)=g(n) h(n)这样的策略，可以不断接近目标点，找出问题的解决方法。时间复杂度：m行n列的迷宫矩阵实现算法的时间复杂度为O(m*n)。实验结果：实验源：#include#include#includeUsing namespace STDIntdiec 4 2=0，1，-1，0，0，-1，1，0 ；Enum FlagSEAL、OPEN、UNVISITEDTypedef struct nodeInt _x，_ y；/节点坐标(x，y)int _ G；/实际开销gint _ H

4、；/探测开销hint _ F；/优先级_F=_G _HStruct node * pre/上一个顶点 Queue _ NodeTypedef structFlag flagQueue _ Node * point SealA类_StarPublic:/建构函式A_Star()input()；A_Star()for(int I=1)；I=_ lenI)for(int j=1)；J=_ widj)If(_sealij)。point！=NULL)Delete _sealij。pointfor(I=0)；I=_ lenI)delete_ sealI；delete_ mazeI；delete_ seal

5、；delete_ maze；Void input() Cout 输入：迷宫左侧长度，顶部宽度！范例：30 20 _ len _ wid_ Seal=new Seal *_ len 1；_ maze=new unsigned char *_ len 1；for(int I=0)；I=_ lenI)_ SealI=new Seal_ wid 1；_ mazeI=new unsigned char_ wid 1；从 Cout 下一行开始输入迷宫信息： _ mazeIj；_sealij。flag=UNVISITED_sealij。point=NULL Cout 起始坐标，目标点坐标，例如：1 1 30

6、 20 _ sx _ sy _ ex _ eyif(_ maze_ sx_ sy=1 | | _ maze_ ex_ ey=1 | | bound(_)Cout 不能有这样的情况！Pre=NULLP_node-_H=get_H(_sx，_ sy)；p _ node-_ G=0；p _ node-_ x=_ sx；p _ node-_ y=_ sy；p _ node-_ F=p _ node-_ H p _ node-_ G；_ open . push(p _ node)；_seal_sx_sy。flag=OPEN_seal_sx_sy。point=p _ nodeWhile(！_open.em

7、pty()p _ node=_ open . top()；_ open . pop()；int x=p _ node-_ x；int y=p _ node-_ y；_sealxy。flag=SEALfor(int I=0)；i4；I)inttx=x diracI0；int ty=y diracI1；If (bound (tx，ty)=false | | _ mazetxty=1 | | _ sealtxty)。flag=seal)ContinueIf (_ seal tx ty)。flag=unvisited)If(tx=_exty=_ey)print(p _ node)；Cout(_F 步骤

8、 pre=p _ nodetemp-_ G=p _ node-_ G 1；temp-_ x=tx；temp-_ y=ty；Temp-_H=get_H(tx，ty)；temp-_ F=temp-_ G temp-_ H；_ open . push(temp)；ElseQueue _ node * temp=_ seal tx ty。pointIf(p_node-_G 1_G)temp-_ G=p _ node-_ G 1；temp-pre=p _ node；temp-_ F=temp-_ G temp-_ H；“Cout”没有来自(“_ sx”，“_ sy”)-“”(“_ ex”，“ey”)的路

9、径“pre”。Cout(_x ， _y )，；Bool bound(int x，int y)return(x=_ len)(x=1)(y=_ wid)(y=1)；Int get_H(int x，int y)return ab(x-_ ex)ab(y-_ ey)；Int ab(int I)Return i0？-I : I；Private:Struct CMPBoolstor () (queue _ node * n1，queue _ node * N2)return n1-_ Fn2-_ F；Priority_queue，cmp _ open/最小堆(打开的列表)Int _len，_ wid/迷宫左侧长度，顶部宽度Int _sx、_sy、_ex、_ eySeal * *