最新消息: 电脑我帮您提供丰富的电脑知识,编程学习,软件下载,win7系统下载。

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

IT培训 admin 3浏览 0评论

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("无解")

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("无解")

与本文相关的文章

发布评论

评论列表 (0)

  1. 暂无评论