A搜索算法（python）之八数码问题
什么是启发式搜索算法
启发式搜索(Heuristically Search)又称为有信息搜索(Informed Search)，它是利用问题拥有的启发信息来引导搜索，达到减少搜索范围、降低问题复杂度的目的，这种利用启发信息的搜索过程称为启发式搜索。
启发式搜索包括A算法和A*算法。 启发式算法的核心思想：
f(x)=g(x)+h(x)
评估函数f(x)定义为：从初始节点S0出发，约束地经过节点X到达目标节点Sg的所有路径中最小路径代价的估计值。 其一般形式为f(x)=g(x)+h(x)，g(x)表示从初始节点S0到节点X的实际代价；h(x)表示从X到目标节点Sg的最优路径的估计代价。
A算法
1，将初始节点装入OPEN表 2，如果OPEN表为空，则失败，退出；否则，取出OPEN表中第一个节点，加入到CLOSE表中。 3，如果节点是目标节点，则成功，退出。 4，如果节点可扩展，将节点的扩展节点加入到OPEN表中，将OPEN表按照估价函数由小到大排列；否则跳转第2步。
A算法和A*算法的差异
A算法是由f(x)=g(x)+h(x)决定，g(x)是这一步的代价函数,h(x)是这一步的预估函数； A算法是f(x)=g(x)+h(x)这个算是决定，在A算法的基础上添加了约束条件，g(x)，h(x)<=任意h(x)； 以上只不过是定义，对于一个实例来说，h(x)由很多种，h(x)只是估值函数的一个集合，有各种方法h1(x)h2(x)h3(x)…，取其中任意一个方法带入上述公式，组成评判函数，都是A算法的实现，现在取从集合中一个函数h∗(x)，使得它比集合中任意的函数都优秀，这样的算法叫A算法。 也就是A*算法是最优的A算法，（因为估值函数最优）！
八数码问题
八数码问题也称为九宫问题。在3×3的棋盘上摆有八个棋子，每个棋子上标有1至8的某一数字，不同棋子上标的数字不相同。棋盘上还有一个空格，与空格相邻的棋子可以移到空格中。给出一个初始状态和一个目标状态，求出从初始状态转变成目标状态的移动棋子步数的最少值。
初始数码 | 目标数码 | |
|---|---|---|
283 | 123 | |
105 | 456 | |
476 | 780 | k |
值得注意的是编码过程中因为涉及到python列表的复制，所以采用了深度复制，对于python的语法还在学习当中，有兴趣的同学可以自己了解一下。
另外如何判断数码是否有解？
八数码问题的一个状态实际上是0~9的一个排列，对于任意给定的初始状态和目标，不一定有解，也就是说从初始状态不一定能到达目标状态。因为排列有奇排列和偶排列两类，从奇排列不能转化成偶排列或相反。 如果一个数字0~8的随机排列871526340，用F(X)表示数字X前面比它小的数的个数，全部数字的F(X)之和为Y=∑(F(X))，如果Y为奇数则称原数字的排列是奇排列，如果Y为偶数则称原数字的排列是偶排列。 例如871526340这个排列的 Y=0+0+0+1+1+3+2+3+0=10 10是偶数，所以他偶排列。871625340 Y=0+0+0+1+1+2+2+3+0=9 9是奇数，所以他奇排列。 因此，可以在运行程序前检查初始状态和目标状态的窘是否相同，相同则问题可解，应当能搜索到路径。否则无解。
废话不多说，接下来看代码： 文件A.py
# coding=utf-8
from __future__ import print_function
import copy
def showMap(array2d):
for x in xrange(0, 3):
for y in xrange(0, 3):
print(array2d[x][y], end='')
print(" ")
print("--------")
return;
def move(array2d, srcX, srcY, drcX, drcY):
temp = array2d[srcX][srcY]
array2d[srcX][srcY] = array2d[drcX][drcY]
array2d[drcX][drcY] = temp
return array2d;
#计算是奇数列还是偶数列
def getStatus(array2d):
y = 0;
for i in xrange(0, 3):
for j in xrange(0, 3):
for m in xrange(0, i+1):
for n in xrange(0, j):
if array2d[i][j] > array2d[m][n]:
y += 1;
return y;
#描述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 xrange(0, 3):
for y in xrange(0, 3):
for m in xrange(0, 3):
for n in xrange(0, 3):
if self.array2d[x][y] == endNode.array2d[m][n]:
self.h += abs(x*y - m*n)
def setG(self, g):
self.g = g
def setFather(self, node):
self.father = node
def getG(self):
return self.g
class A:
"""
A 算法
python 2.7
"""
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 = 0
return;
def getMinFNode(self):
"""
获得openlist中F值最小的节点
"""
nodeTemp = self.openList[0]
for node in self.openList:
if node.g + node.h < nodeTemp.g + nodeTemp.h:
nodeTemp = node
return nodeTemp
def nodeInOpenlist(self,node):
for nodeTmp in self.openList:
if nodeTmp.array2d == node.array2d:
return True
return False
def nodeInCloselist(self,node):
for nodeTmp in self.closeList:
if nodeTmp.array2d == node.array2d:
return True
return False
def endNodeInOpenList(self):
for nodeTmp in self.openList:
if nodeTmp.array2d == self.endNode.array2d:
return True
return False
def getNodeFromOpenList(self,node):
for nodeTmp in self.openList:
if nodeTmp.array2d == node.array2d:
return nodeTmp
return None
def searchOneNode(self,node):
"""
搜索一个节点
"""
#忽略封闭列表
if self.nodeInCloselist(node):
return
#G值计算
gTemp = self.step
#如果不再openList中，就加入openlist
if self.nodeInOpenlist(node) == False:
node.setG(gTemp)
#H值计算
node.setH(self.endNode);
self.openList.append(node)
node.father = self.currentNode
#如果在openList中，判断currentNode到当前点的G是否更小
#如果更小，就重新计算g值，并且改变father
else:
nodeTmp = self.getNodeFromOpenList(node)
if self.currentNode.g + gTemp < nodeTmp.g:
nodeTmp.g = self.currentNode.g + gTemp
nodeTmp.father = self.currentNode
return;
def searchNear(self):
"""
搜索下一个可以动作的数码
找到0所在的位置并以此进行交换
"""
flag = False
for x in xrange(0, 3):
for y in xrange(0,3):
if self.currentNode.array2d[x][y] == 0:
flag = True
break;
if flag == True:
break;
self.step += 1
if 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));
return;
def 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.father
else:
return True;
elif len(self.openList) == 0:
return False;
elif self.step > 30:
return False;
return True;
def showPath(self):
for node in self.pathlist[::-1]:
showMap(node.array2d)文件ATest.py
# coding=utf-8
import A
if __name__ == '__main__':
##构建A
a = A.A(A.Node([[2,8,3],[1,0,5],[4,7,6]]), A.Node([[1,2,3],[4,5,6],[7,8,0]]));
print "A start:";
##开始寻路
if a.start():
a.showPath();
else:
print "no way";运行结果
A start:
283
105
476
--------
203
185
476
--------
023
185
476
--------
123
085
476
--------
123
485
076
--------
123
485
706
--------
123
405
786
--------
123
450
786
--------
123
456
780
--------
[Finished in 0.8s]