人工智能实验（A，BP）
人工智能实验（A*，BP）实验一A*算法一、实验目的：
熟悉和掌握启发式搜索的定义、估价函数和算法过程，并利用A*算法求解N数码难题，理解求解流程和搜索顺序。
二、实验原理：
A算法是一种启发式图搜索算法，其特点在于对估价函数的定义上。对于一般的启发式图搜索，总是选择估价函数f值最小的节点作为扩展节点。因此，f是根据需要找到一条最小代价路径的观点来估算节点的，所以，可考虑每个节点n的估价函数值为两个分量：从起始节点到节点n的实际代价以及从节点n*到达目标节点的估价代价。
三、实验内容：
1参考A算法核心代码，以8数码问题为例实现A算法的求解程序（编程语言不限），要求设计两种不同的估价函数。
估价函数1:代价函数为扩展的层数,启发函数为数码中不在位的数字的个数。
估价函数2：代价函数位扩展的层数，启发函数为由当前状态当目标状态所有节点需要移动的次数，即曼哈顿距离。
2在求解8数码问题的A*算法程序中，设置相同的初始状态和目标状态，针对不同的估价函数，求得问题的解，并比较它们对搜索算法性能的影响，包括扩展节点数、生成节点数等。
算法流程图:
算法思路定义一个h(n)=f(n)+g(n),即定义一个代价函数和启发函数,代价函数这里取其探索的层数,启发函数为不在位的数码数码。
f(n):探索的层数
g(n):不在位的数码个数。
从初始结点开始，扩展可能的节点，并从可能节点中选取代价最小的节点进行下一步的扩展。
#获取给定数码的坐标defget_loc(num,_arr):#返回给定节点的坐标点_arr=np.array(_arr).reshape(3,3)foriinrange(len(_arr)):forjinrange(len(_arr[i])):ifnum==_arr[i][j]:#找到值所在的位置并返回returni,j#定义启发函数(1.以不在位的数量值为启发函数进行度量,2.初始状态和最终状态的节点曼哈顿距离,3.宽度优先启发为0)defval(arr,arr_final,method=0):ifmethod==1:#曼哈顿距离_arr=np.array(arr).reshape(3,3)_arr_final=np.array(arr_final).reshape(3,3)total=0foriinrange(len(_arr)):forjinrange(len(_arr[i])):m,n=get_loc(_arr[i][j],arr_final)#找到给定值的横坐标和纵坐标total+=np.abs(i-m)+np.abs(j-n)#计算所有节点的曼哈顿距离之和returntotalifmethod==2:#宽度优先return0#不在位数量total=[]foriinrange(len(arr)):#计算list中对不上的数量,0除外ifarr[i]!=0:total.append(arr[i]-arr_final[i])returnlen(total)-total.count(0)#定义一个函数用来执行,矩阵的变换工作,即移动"0"，这里以0来代替空格的移动defarr_swap(arr,destnation,flag=False):ifflag:#如果flag为true那么直接修改矩阵z_pos=arr.argmin()#获得0的位置tmp=arr[destnation]#和要修改的位置进行交换arr[destnation]=arr[z_pos]arr[z_pos]=tmpreturnlist(arr)#返回结果#如果flag为false,不修改传入的矩阵,而返回一个修改后的副本_arr=np.array(arr.copy())#创建副本z_pos=_arr.argmin()#获得0的位置tmp=_arr[destnation]#交换位置_arr[destnation]=_arr[z_pos]_arr[z_pos]=tmpreturnlist(_arr)#返回副本#定义节点类，用来记录节点之间的信息和方便后续的路径查找classnode:par=Nonevalue=-1arr=Nonestep=0def__init__(self,p,val,a,s):#根据传入的值初始化节点self.par=pself.step=sself.value=valself.arr=np.array(a)#定义向上移动的函数defup(self,ss):#定义节点中"0"向上为一个函数,ifnp.array(self.arr).argmin()-3>=0:#当能够向上移动时，返回向上移动后的节点#返回后的节点，计算启发值，更新数组，并将新节点的值父节点设置为调用函数的节点tmp=np.array(self.arr).argmin()-3ar=arr_swap(self.arr,tmp)v=val(ar,arr_final,ss)v+=self.step+1new_node=node(p=self,val=v,a=ar,s=self.step+1)returnnew_node#返回生成的子节点else:returnNone#同理定义向下，向左和向右的函数不赘述，若要完整代码去翻到最后的GitHub上下载即可。检查是否要扩展的节点已经生成，或者还没生成
#定义函数用来判断，一个节点是否在生成的表中defin_open(t,openl):foriinopenl:ifall(i.arr==t.arr):#如果找到了arr相同的节点ift.value