A*算法解决8数码问题python实现

1.A*的通俗理解

很多游戏特别是rts，rpg类游戏，都需要用到寻路。寻路算法有深度优先搜索（DFS），广度优先搜索(BFS)，A星算法等，而A星算法是一种具备启发性策略的算法，效率是几种算法中最高的，因此也成为游戏中最常用的寻路算法。
对于A星算法的具体理解可以参考下面这篇文章，本文着重讲解A星算法，在解决8数码问题的思路以及代码
A*算法的通俗理解

2.8数码问题

首先：估价函数对求解八数码问题有不同的影响。
这里我们介绍4种不同启发函数，我们主要使用第一种:

• 最简单的估价函数:取一格局与目的格局相比，其位置不符的将牌数目。
• 较 好的估价函数:各将牌移到目的位置所需移动的距离的总和
• 第三种估价函数:对每一对逆转将牌乘以一个倍数。
• 第四种估价函数:克服了仅计算将牌逆转数目策略的局限，将位置不符将牌数目的总和与3倍将牌逆转数目相加。

下面我们开始移动，并计算各个状态的估价函数值，然后选估价函数值最小的节点继续移动，直到出现目标状态为止如下图所示**（注意：图种有两处错误A（4）应为A（7），C（4）应为C（7）)**：

3.代码

import numpy as np
import operator
O=int(input(("请输入方阵的行/列数：")))
A=list(input("请输入初始状态："))
B=list(input("请输入目标状态："))
z=0
M=np.zeros((O,O))
N=np.zeros((O,O))
for i in range(O):for j in range(O):M[i][j]=A[z]N[i][j]=B[z]z=z+1
openlist=[]#open表class State:def __init__(self,m):self.node=m#节点代表的状态self.f=0#f(n)=g(n)+h(n)self.g=0#g(n)self.h=0#h(n)self.father=None#节点的父亲节点init = State(M)#初始状态
goal=State(N)#目标状态
#启发函数
def h(s):a=0for i in range(len(s.node)):for j in range(len(s.node[i])):if s.node[i][j]!=goal.node[i][j] and s.node[i][j]!=0:a=a+1return a
#对节点列表按照估价函数的值的规则排序
def list_sort(l):cmp=operator.attrgetter('f')l.sort(key=cmp)
#A*算法    
def A_star(s):global openlist#全局变量可以让open表进行时时更新openlist=[s]fatherlist=[s.node]while(openlist):get=openlist[0] #取出open表的首节点  if (get.node==goal.node).all():#判断是否与目标节点一致return getopenlist.remove(get)#将get移出open表#判断此时状态的空格位置for a in range(len(get.node)):for b in range(len(get.node[a])):if get.node[a][b]==0:breakif get.node[a][b]==0:break#开始移动for i in range(len(get.node)):for j in range(len(get.node[i])):c=get.node.copy()if (i-a)**2+(j-b)**2==1:c[a][b]=c[i][j]c[i][j]=0new=State(c)K=0for k in range(len(fatherlist)):if (new.node==fatherlist[k]).all():breakelse:K=K+1if K==len(fatherlist):     new.father=get#此时取出的get节点成为新节点的父亲节点new.g=get.g+1#新节点与父亲节点的距离new.h=h(new)#新节点的启发函数值new.f=new.g+new.h#新节点的估价函数值openlist.append(new)fatherlist.append(new.node)# 递归打印路径
def printpath(f):if f is None:return#注意print()语句放在递归调用前和递归调用后的区别。放在后实现了倒叙输出printpath(f.father)print(f.node)final=A_star(init)
if final:print("有解，解为：")printpath(final)
else:print("无解")