基于python的九宫重排问题的启发式搜索（A*算法）求解程序

一、实验内容

在3х3组成的九宫棋盘上，放置数码为1~8的8个棋子，棋盘中留有一个空格，空格周围的棋子可以移动到空格中，从而改变棋盘的布局。根据给定初始布局和目标布局，编程给出一个最优的走法序列。输出每个状态的棋盘

二、启发式搜索算法的描述

（1）把初始节点S0 放入Open表中，f(S0)=g(S0)+h(S0);

（2）如果Open表为空，则问题无解，失败退出；

（3）把Open表的第一个节点取出放入Closed表，并记该节点为n;

（4）考察节点n是否为目标节点。若是，则找到了问题的解，成功退出；

（5）若节点n不可扩展，则转到第（2)步；

（6）扩展节点n，生成子节点ni(i=1,2,……)，计算每一个子节点的估价值f(ni) (i=1,2,……)，并为每一个子节点设置指向父节点的指针，然后将这些子节点放入Open表中；

（7）根据各节点的估价函数值，对Open表中的全部节点按从小到大的顺序重新进行排序；

（8）转到第（2）步。

三、具体算法实现

1、根据逆序数判断该九宫重排问题是否有解

由数学知识可知，可计算这两个有序数列的逆序值，如果两者都是偶数或奇数，则可通过变换到达，否则，这两个状态不可达。这样，就可以在具体解决问题之前判断出问题是否可解，从而可以避免不必要的搜索。

# 计算是奇数列还是偶数列def getStatus(array2d):a=[]for x in range(0, 3): # 把数组转化成队列for y in range(0, 3):a.append(array2d[x][y])ans = 0for i in range(len(a)):for j in range(i):if a[j] > a[i]:ans += 1return ans

2、描述A*算法中的结点数据

# 描述A*算法中的结点数据class Node:def __init__(self, array2d, g=0, h=0):self.array2d = array2d # 二维数组self.father = None # 父节点self.g = g # g值self.h = h # h值"""估价公式"""def setH(self, endNode):for x in range(0, 3):for y in range(0, 3):for m in range(0, 3):for n in range(0, 3):if self.array2d[x][y] == endNode.array2d[m][n]:self.h += abs(x * y - m * n)def setG(self, g):self.g = gdef setFather(self, node):self.father = nodedef getG(self):return self.g

3、将A*算法的主要代码用类封装

class A:def __init__(self, startNode, endNode):"""startNode: 寻路起点endNode: 寻路终点"""# 开放列表self.openList = []# 封闭列表self.closeList = []# 起点self.startNode = startNode# 终点self.endNode = endNode# 当前处理的节点self.currentNode = startNode# 最后生成的路径self.pathlist = []# step步self.step = 0returndef getMinFNode(self):"""获得openlist中F值最小的节点"""nodeTemp = self.openList[0]for node in self.openList:if node.g + node.h < nodeTemp.g + nodeTemp.h:nodeTemp = nodereturn nodeTempdef nodeInOpenlist(self, node):for nodeTmp in self.openList:if nodeTmp.array2d == node.array2d:return Truereturn Falsedef nodeInCloselist(self, node):for nodeTmp in self.closeList:if nodeTmp.array2d == node.array2d:return Truereturn Falsedef endNodeInOpenList(self):for nodeTmp in self.openList:if nodeTmp.array2d == self.endNode.array2d:return Truereturn Falsedef getNodeFromOpenList(self, node):for nodeTmp in self.openList:if nodeTmp.array2d == node.array2d:return nodeTmpreturn Nonedef searchOneNode(self, node):"""搜索一个节点"""# 忽略封闭列表if self.nodeInCloselist(node):return# G值计算gTemp = self.step# 如果不再openList中，就加入openlistif self.nodeInOpenlist(node) == False:node.setG(gTemp)# H值计算node.setH(self.endNode);self.openList.append(node)node.father = self.currentNode# 如果在openList中，判断currentNode到当前点的G是否更小# 如果更小，就重新计算g值，并且改变fatherelse:nodeTmp = self.getNodeFromOpenList(node)if self.currentNode.g + gTemp < nodeTmp.g:nodeTmp.g = self.currentNode.g + gTempnodeTmp.father = self.currentNodereturndef searchNear(self):"""搜索下一个可以动作的数码找到0所在的位置并以此进行交换"""x=0y=0flag = Falsefor x in range(0, 3):for y in range(0, 3):if self.currentNode.array2d[x][y] == 0:flag = Truebreakif flag == True:breakself.step += 1if x - 1 >= 0:arrayTemp = move(copy.deepcopy(self.currentNode.array2d), x, y, x - 1, y)self.searchOneNode(Node(arrayTemp))if x + 1 < 3:arrayTemp = move(copy.deepcopy(self.currentNode.array2d), x, y, x + 1, y)self.searchOneNode(Node(arrayTemp))if y - 1 >= 0:arrayTemp = move(copy.deepcopy(self.currentNode.array2d), x, y, x, y - 1)self.searchOneNode(Node(arrayTemp))if y + 1 < 3:arrayTemp = move(copy.deepcopy(self.currentNode.array2d), x, y, x, y + 1)self.searchOneNode(Node(arrayTemp))returndef start(self):'''''开始寻路'''# 根据奇数列和偶数列判断是否有解startY = getStatus(self.startNode.array2d)endY = getStatus(self.endNode.array2d)if startY % 2 != endY % 2:return False# 将初始节点加入开放列表self.startNode.setH(self.endNode)self.startNode.setG(self.step)self.openList.append(self.startNode)while True:# 获取当前开放列表里F值最小的节点# 并把它添加到封闭列表，从开发列表删除它self.currentNode = self.getMinFNode()self.closeList.append(self.currentNode)self.openList.remove(self.currentNode)self.step = self.currentNode.getG()self.searchNear()# 检验是否结束if self.endNodeInOpenList():nodeTmp = self.getNodeFromOpenList(self.endNode)while True:self.pathlist.append(nodeTmp)if nodeTmp.father != None:nodeTmp = nodeTmp.fatherelse:return Trueelif len(self.openList) == 0:return Falseelif self.step > 30:return Falsereturn Truedef showPath(self):for node in self.pathlist[::-1]: # 是返回倒序的原列表showMap(node.array2d)

四、程序运行结果的部分截图

初始状态: [[2,8,3],[1,0,5],[4,7,6]]

目标状态: [[1,2,3],[4,0,5],[6,7,8]]

源码

文件A.py

# coding=utf-8import copydef showMap(array2d):for x in range(0, 3):for y in range(0, 3):print(array2d[x][y], end=' ')print('\n')print("--------")returndef move(array2d, srcX, srcY, drcX, drcY):temp = array2d[srcX][srcY]array2d[srcX][srcY] = array2d[drcX][drcY]array2d[drcX][drcY] = tempreturn array2d# 计算是奇数列还是偶数列def getStatus(array2d):a=[]for x in range(0, 3): # 把数组转化成队列for y in range(0, 3):a.append(array2d[x][y])ans = 0for i in range(len(a)):for j in range(i):if a[j] > a[i]:ans += 1return ans# 描述A*算法中的结点数据class Node:def __init__(self, array2d, g=0, h=0):self.array2d = array2d # 二维数组self.father = None # 父节点self.g = g # g值self.h = h # h值"""估价公式"""def setH(self, endNode):for x in range(0, 3):for y in range(0, 3):for m in range(0, 3):for n in range(0, 3):if self.array2d[x][y] == endNode.array2d[m][n]:self.h += abs(x * y - m * n)def setG(self, g):self.g = gdef setFather(self, node):self.father = nodedef getG(self):return self.gclass A:def __init__(self, startNode, endNode):"""startNode: 寻路起点endNode: 寻路终点"""# 开放列表self.openList = []# 封闭列表self.closeList = []# 起点self.startNode = startNode# 终点self.endNode = endNode# 当前处理的节点self.currentNode = startNode# 最后生成的路径self.pathlist = []# step步self.step = 0returndef getMinFNode(self):"""获得openlist中F值最小的节点"""nodeTemp = self.openList[0]for node in self.openList:if node.g + node.h < nodeTemp.g + nodeTemp.h:nodeTemp = nodereturn nodeTempdef nodeInOpenlist(self, node):for nodeTmp in self.openList:if nodeTmp.array2d == node.array2d:return Truereturn Falsedef nodeInCloselist(self, node):for nodeTmp in self.closeList:if nodeTmp.array2d == node.array2d:return Truereturn Falsedef endNodeInOpenList(self):for nodeTmp in self.openList:if nodeTmp.array2d == self.endNode.array2d:return Truereturn Falsedef getNodeFromOpenList(self, node):for nodeTmp in self.openList:if nodeTmp.array2d == node.array2d:return nodeTmpreturn Nonedef searchOneNode(self, node):"""搜索一个节点"""# 忽略封闭列表if self.nodeInCloselist(node):return# G值计算gTemp = self.step# 如果不再openList中，就加入openlistif self.nodeInOpenlist(node) == False:node.setG(gTemp)# H值计算node.setH(self.endNode);self.openList.append(node)node.father = self.currentNode# 如果在openList中，判断currentNode到当前点的G是否更小# 如果更小，就重新计算g值，并且改变fatherelse:nodeTmp = self.getNodeFromOpenList(node)if self.currentNode.g + gTemp < nodeTmp.g:nodeTmp.g = self.currentNode.g + gTempnodeTmp.father = self.currentNodereturndef searchNear(self):"""搜索下一个可以动作的数码找到0所在的位置并以此进行交换"""x=0y=0flag = Falsefor x in range(0, 3):for y in range(0, 3):if self.currentNode.array2d[x][y] == 0:flag = Truebreakif flag == True:breakself.step += 1if x - 1 >= 0:arrayTemp = move(copy.deepcopy(self.currentNode.array2d), x, y, x - 1, y)self.searchOneNode(Node(arrayTemp))if x + 1 < 3:arrayTemp = move(copy.deepcopy(self.currentNode.array2d), x, y, x + 1, y)self.searchOneNode(Node(arrayTemp))if y - 1 >= 0:arrayTemp = move(copy.deepcopy(self.currentNode.array2d), x, y, x, y - 1)self.searchOneNode(Node(arrayTemp))if y + 1 < 3:arrayTemp = move(copy.deepcopy(self.currentNode.array2d), x, y, x, y + 1)self.searchOneNode(Node(arrayTemp))returndef start(self):'''''开始寻路'''# 根据奇数列和偶数列判断是否有解startY = getStatus(self.startNode.array2d)endY = getStatus(self.endNode.array2d)if startY % 2 != endY % 2:return False# 将初始节点加入开放列表self.startNode.setH(self.endNode)self.startNode.setG(self.step)self.openList.append(self.startNode)while True:# 获取当前开放列表里F值最小的节点# 并把它添加到封闭列表，从开发列表删除它self.currentNode = self.getMinFNode()self.closeList.append(self.currentNode)self.openList.remove(self.currentNode)self.step = self.currentNode.getG()self.searchNear()# 检验是否结束if self.endNodeInOpenList():nodeTmp = self.getNodeFromOpenList(self.endNode)while True:self.pathlist.append(nodeTmp)if nodeTmp.father != None:nodeTmp = nodeTmp.fatherelse:return Trueelif len(self.openList) == 0:return Falseelif self.step > 30:return Falsereturn Truedef showPath(self):for node in self.pathlist[::-1]: # 是返回倒序的原列表showMap(node.array2d)

文件main.py

# coding=utf-8import Aif __name__ == '__main__':##构建Aa = A.A(A.Node([[2,8,3],[1,0,5],[4,7,6]]), A.Node([[1,2,3],[4,0,5],[6,7,8]]));print ("A start:")##开始寻路if a.start():a.showPath()else:print("no way")