python算法问题_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]