头歌——人工智能（启发式搜索算法）

第1关：评估函数和启发信息

1、

评估函数的作用就是估计待扩展结点在问题求解中的价值。

2、

启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标。

第2关：A*搜索算法

任务描述
本关任务：编写一个利用 A* 算法实现地图寻路的程序。

相关知识
为了完成本关任务，你需要掌握 A* 算法。

A算法
A 算法是由著名的人工智能学者 Nilsson 提出的，它是目前最具有影响的启发图搜索算法，也称为最佳图搜索算法。之前我们已经了解了一般的启发式搜索算法评估函数f(n)可定义为：
f(n)=g(n)+h(n)
而在 A 算法中定义 h(n) 为状态 n 到目的状态的最优路径的代价。* 下面是 A* 算法的描述。

1.把起点加入 open list ；
2.重复如下过程：
a. 遍历 open list ，查找 F 值最小的节点，把它作为当前要处理的节点。
b.把这个节点移到 close list 。
c.对当前方格的 8 个相邻方格的每一个方格？
◆如果它是不可抵达的或者它在 close list 中，忽略它。否则，做如下操作。
◆如果它不在 open list 中，把它加入 open list ，并且把当前方格设置为它的父亲，记录该方格的 F ， G 和 H 值。
◆如果它已经在 open list 中，检查这条路径 ( 即经由当前方格到达它那里 ) 是否更好，用 G 值作参考。更小的 G 值表示这是更好的路径。如果是这样，把它的父亲设置为当前方格，并重新计算它的 G 和 F 值。如果你的 open list 是按 F 值排序的话，改变后你可能需要重新排序。
d.停止，当你
◆把终点加入到了 open list 中，此时路径已经找到了，或者
◆查找终点失败，并且 open list 是空的，此时没有路径。
3.保存路径。从终点开始，每个方格沿着父节点移动直至起点，这就是你的路径。

编程要求
根据提示补全右侧编辑器 Begin-End 区间的程序，输出从入口到出口最短的路径。其中 0 标记可走区域；1 标记围墙；8 用来标记遍历路径。

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

测试输入：

0 0 0 0 1 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
预期输出：

0 8 8 8 1 8 8 8 8 8
0 0 0 8 1 8 0 0 0 0
0 0 0 8 1 8 0 0 0 0
0 0 0 8 1 8 0 0 0 0
0 0 0 8 1 8 0 0 0 0
0 0 0 8 1 8 0 0 0 0
0 0 0 8 1 8 0 0 0 0
0 0 0 8 8 8 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0

class Array2D:"""说明：1.构造方法需要两个参数，即二维数组的宽和高2.成员变量w和h是二维数组的宽和高3.使用：‘对象[x][y]’可以直接取到相应的值4.数组的默认值都是0"""def __init__(self, w, h):self.w = wself.h = hself.data = []self.data = [[0 for y in range(h)] for x in range(w)]def showArray2D(self):for y in range(self.h):for x in range(self.w):print(self.data[x][y], end=' ')print("")def __getitem__(self, item):return self.data[item]class Point:"""表示一个点"""def __init__(self, x, y):self.x = xself.y = ydef __eq__(self, other):if self.x == other.x and self.y == other.y:return Truereturn Falsedef __str__(self):return "x:" + str(self.x) + ",y:" + str(self.y)class AStar:"""AStar算法的Python3.x实现"""class Node:  # 描述AStar算法中的节点数据def __init__(self, point, endPoint, g=0):self.point = point  # 自己的坐标self.father = None  # 父节点self.endPoint = endPointself.g = g  # g值，g值在用到的时候会重新算self.h = (abs(endPoint.x - point.x) + abs(endPoint.y - point.y)) * 10  # 计算h值def __init__(self, map2d, startPoint, endPoint, passTag=0):"""构造AStar算法的启动条件:param map2d: Array2D类型的寻路数组:param startPoint: Point或二元组类型的寻路起点:param endPoint: Point或二元组类型的寻路终点:param passTag: int类型的可行走标记（若地图数据!=passTag即为障碍）"""# 开启表self.openList = []# 关闭表self.closeList = []# 寻路地图self.map2d = map2d# 起点终点# ********** Begin **********#self.startPoint = startPointself.endPoint = endPoint# ********** End **********## 可行走标记self.passTag = passTagdef getMinNode(self):"""获得openlist中F值最小的节点:return: Node"""# ********** Begin **********#nowf = self.openList[0]minf=self.openList[0].g +self.openList[0].hfor i in self.openList:if minf > i.g + i.h:minf = i.g + i.hnowf = ireturn nowf# ********** End **********#def pointInCloseList(self, point):for node in self.closeList:if node.point == point:return Truereturn Falsedef pointInOpenList(self, point):for node in self.openList:if node.point == point:return nodereturn Nonedef endPointInCloseList(self):for node in self.openList:if node.point == self.endPoint:return nodereturn Nonedef searchNear(self, minF, offsetX, offsetY):"""搜索节点周围的点:param minF:F值最小的节点:param offsetX:坐标偏移量:param offsetY::return:"""# 越界检测# ********** Begin **********#if minF.point.x + offsetX >= self.map2d.w or minF.point.y + offsetY >= self.map2d.h or minF.point.x + offsetX < 0 or minF.point.y + offsetY < 0:return# ********** End **********## 如果是障碍，就忽略if self.map2d[minF.point.x + offsetX][minF.point.y + offsetY] != self.passTag:return# 如果在关闭表中，就忽略currentPoint = Point(minF.point.x + offsetX, minF.point.y + offsetY)currentNode = AStar.Node(currentPoint,self.endPoint)if self.pointInCloseList(currentPoint):return# 设置单位花费if offsetX == 0 or offsetY == 0:step = 10else:step = 14# 如果不再openList中，就把它加入openlist# ********** Begin **********#if not self.pointInOpenList(currentPoint):# print(currentNode.g)currentNode.g = step + minF.g# print(currentNode)currentNode.father = minFself.openList.append(currentNode)# ********** End **********## 如果在openList中，判断minF到当前点的G是否更小if minF.g + step < currentNode.g:  # 如果更小，就重新计算g值，并且改变fathercurrentNode.g = minF.g + stepcurrentNode.father = minFdef start(self):"""开始寻路:return: None或Point列表（路径）"""# 判断寻路终点是否是障碍if self.map2d[self.endPoint.x][self.endPoint.y] != self.passTag:return None# 1.将起点放入开启列表startNode = AStar.Node(self.startPoint, self.endPoint)self.openList.append(startNode)# 2.主循环逻辑while True:# 找到F值最小的点minF = self.getMinNode()# 把这个点加入closeList中，并且在openList中删除它self.closeList.append(minF)self.openList.remove(minF)# 判断这个节点的上下左右节点# ********** Begin **********#self.searchNear(minF,0,-1)self.searchNear(minF,1,0)self.searchNear(minF,-1,0)self.searchNear(minF,0,1)# ********** End **********## 判断是否终止point = self.endPointInCloseList()if point:  # 如果终点在关闭表中，就返回结果# print("关闭表中")cPoint = pointpathList = []while True:if cPoint.father:pathList.append(cPoint.point)cPoint = cPoint.fatherelse:return list(reversed(pathList))if len(self.openList) == 0:return None