实验2：A*算法求解迷宫寻路问题实验

一、实验目的

通过本节的学习，你将熟悉和掌握 A* 算法的原理、估价函数和算法过程，并利用A* 算法求解迷宫寻路问题，理解求解流程和搜索顺序。

二、实验设备与器件

PC机

三、实验内容

本节将学习启发式搜索中的A* 算法和迷宫寻路问题，最后使用 A* 搜索算法完成迷宫寻路问题初始状态到最终状态的最优求解实验。

A* 算法是一种启发式图搜索算法，其特点在于对估价函数的定义上。对于一般的启发式图搜索，总是选择估价函数f值最小的节点作为扩展节点。

 

任务描述

本关任务：编写一个使用 A* 搜索算法完成求解迷宫问题最优解的小程序。

相关知识

为了完成本关任务，你需要掌握：

1.A*算法的原理和步骤；

2.解决迷宫问题的思路。

A* 搜索算法简介

A* 搜索算法是一种启发式搜索算法。所谓启发式搜索算法，就是在盲目搜索算法中加入一个启发函数，在当前节点搜索完毕后，通过这个启发函数来进行计算，选择代价最少的节点作为下一步搜索的节点。通过这样的方式就能够找到最优解。DFS，BFS这两种搜索方式都属于盲目的搜索方式，它不会在选择下一个节点的时候进行代价计算，而是按照一个固定的方式选择，这样在运气不好的情况，会对所有节点进行遍历。

A* 搜索算法的核心就在于如何设计一个好的启发函数，启发函数的表达形式为：f(n)=g(n)+h(n)。其中f(n)是每个节点可能的估值或者代价值，它由两部分组成：

g(n)：它表示从起点到搜索点的代价；

h(n)：它表示从搜索点到目标点的代价，h(n)设计的好坏，直接影响到该 A* 算法的效率。

A* 算法步骤

OPEN 表：保留所有已生成而未扩展的状态；

CLOSED 表：记录已扩展过的状态。

A* 算法求解迷宫问题

迷宫问题指的是在一个n×m的迷宫里，入口坐标和出口坐标分别为(startx,starty)和(endx,eny)，每一个坐标点有两种可能：0或1，其中0表示该位置允许通过，1表示该位置不允许通过。求解目标是找到一个最短路径从入口到出口。

在采用A*算法对迷宫路径求解中，g(n)和h(n)函数都采用曼哈顿距离，曼哈顿距离代表两个点在标准坐标系上的绝对轴距总和。计算公式为：d(i,j)=∣x1−x2∣+∣y1−y2∣

即每次获取的当前通道块，都会对其到入口通道块和出口通道块的曼哈顿距离进行计算。因此，我们定义估价函数为：f(n)=g(n)+h(n)，式中，g(n)为起点到n状态的最短路径代价的估计值，我们使用起点到n状态的曼哈顿距离表示；而h(n)是n状态到目的状态的最短路径代价的估计值，由于在搜索过程中，每次只走一步，我们姑且设置h(n)为1。综上，可得到估价函数的代码定义为：

# 曼哈顿距离比较  f = g + h，h=1

def getFunctionValue(self, end):

  dist = abs(self.x - end.x) + abs(self.y - end.y)

  return dist + 1

迷宫寻路问题的目标是：如何在最短的路径基础上从起始点到目的地。

输入：

[[0, 0, 0, 0, 0],

[1, 0, 1, 0, 1],

[0, 0, 0, 0, 1],

[0, 1, 0, 0, 0],

[0, 0, 0, 1, 0]]

预期结果：最短路径为 8，具体如下，

*  *  0  0  0  

1  *  1  0  1  

0  *  *  0  1  

0  1  *  *  *  

0  0  0  1  *  

其中，*表示走过的路径。

编程要求

根据提示，在右侧 vscode 编辑器补充代码，参考寻路过程中向左、向右、向上三个方向的移动方式，完成向下的移动代码的编写，达到通过使用 A* 搜索算法完成求解迷宫寻路问题的最短路径。

编程路径：/data/workspace/myshixun/step1/test.py

测试说明

平台会对你编写的代码进行测试：

测试输入：无；

预期输出：

Best Way:

*  *  0  0  0  

1  *  1  0  1  

0  *  *  0  1  

0  1  *  *  *  

0  0  0  1  *  

Total steps is 8