![[python 那些事儿] 八数码问题(深度搜索 宽度搜索 输出最优解 提前判断无解状态！A算法！)](https://2000zi.500zi.com/uploadfile/img/15/579/56db0d301494c180f4a791cb5c09af9b.jpg)
导引
理论宽度优先搜索算法 (python代码)宽度优先——未输出最优解方法宽度优先——输出最优解方法深度优先算法(python代码)深度优先——未输出最优解方法深度优先——输出最优解方法判断无解状态（以宽度搜索为例）A算法理论
视频教程
CSDN
B战
问题描述：八数码问题是在一个3×3的方格盘上，放有1~8八个数码，余下一格为空格。空格可以与其四周的数码交换位置，从而改变八个数码在方格盘上的摆法。问题中可以使用的操作算子有四种：空格上移（up）、空格下移（down）、空格左移（left）、空格右移（right）
实验要求： 给定如下初始状态S0和目标状态Sg，要求编程实现：当输入初始状态S0后，通过搜索得到目标状态Sg，并记录下从S0到Sg的所有中间状态以及每一次状态改变所使用的操作算子。
（1）宽度优先搜索算法（伪代码）：
Procedure_breadth_first_search:Beginopen:=[Initial state]; closed:=[Initial state]; //初始化while open ≠ [ ] dobegin从open表中删除第一个状态，记作n；将n放入closed表中；if n = 目标状态, then return(success); //成功，返回求解路径 生产n的所有子状态； 从n的子状态中删除已在open或closed表中出现的状态；//避免重复搜索将n的其余子状态，按生成的次序加入open表中已有结点的后面；endend
（2）深度优先算法（伪代码）：
Procedure_breadth_first_search:Beginopen:=[Initial state]; closed:=[Initial state]; d:=深度限制值； //初始化while open ≠ [ ] dobegin从open表中删除第一个状态，记作n；将n放入closed表中；if n = 目标状态, then return(success); //成功，返回求解路径 if n的深度<d, then continue;//继续向深度方向搜索生产n的所有子状态； 从n的子状态中删除已在open或closed表中出现的状态；//避免重复搜索将n的其余子状态，按生成的次序加入open表中已有结点的前面；endend
宽度优先搜索算法 (python代码)
宽度优先——未输出最优解方法
import numpy as npimport copyclass test:def __init__(self,initial,goals):self.length = int(math.sqrt(len(initial)))self.initial=np.reshape(initial,(self.length,self.length))self.goals=np.reshape(goals,(self.length,self.length))##初始化程序self.open_=[self.initial]self.close_=[]#展示数据函数def __show_data(self,a):for i in a:print(i)#移动函数def __move(self,n,postion,row,col):if postion =="left":n[row,col] , n[row,col-1] = n[row,col-1], n[row,col]elif postion == "right":n[row,col] , n[row,col+1] = n[row,col+1], n[row,col]elif postion == "up":n[row,col] , n[row-1,col] = n[row-1,col], n[row,col]elif postion == "down":n[row,col] , n[row+1,col] = n[row+1,col], n[row,col]return ndef __ifexists(self,three_result,close,open_):for i in range(len(close)):if (three_result == close[i]).all():#print("在close表中有重复")return Truefor i in range(len(open_)):if (three_result == open_[i]).all():#print("在open表中有重复")return Truereturn Falsedef find_do(self):flag = 0#print(self.open_)while self.open_:flag = flag+1#初始化算子direction=['up', 'down', 'right', 'left']#从open表中删除第一个状态并放入close表中n = self.open_.pop(0)self.close_.append(n)#print(n)#print(self.initial)#print(n==b)#如果n为目标状态则返回求解路径'''np.all所有都是true才能是truenp.any一个是true就是true '''#print(n)#print(self.goals)if (n == self.goals).all():print("展示搜索到的目标值")self.__show_data(n)print("----------------------------------找到目标值啦-----------------------------------")break #生产n的所有子状态,并加入到open表后方postion = np.where(n == 0)#print(postion)#print("aa")i = postion[0]j = postion[1]length_down=n.shape[0]length_right=n.shape[1]#清除左操作if i==0:direction.remove("up")#清除上操作if j==0:direction.remove("left")#清除下操作if i == length_down-1:direction.remove("down")#清除右操作if j == length_right-1:direction.remove("right")#print(direction)#找到子状态for p in range(len(direction)):copy_n = copy.deepcopy(n)three_result = self.__move(copy_n,direction[p],i,j)#print(three_result)#判断是否存在于close表if (self.__ifexists(three_result,self.close_,self.open_)):#直接跳出此次循环 不加入open表continueself.open_.append(three_result)print("完成第"+str(flag)+"次查找，此轮中间项为：\n",n)##初始化状态a=[0,1,3,4,2,5,7,8,6]b=[4,1,3,7,0,5,8,2,6]#初始化类test1 = test(a,b)test1.find_do()
宽度优先——输出最优解方法
import numpy as npimport copyclass Node:def __init__(self,data,level,parent):self.data=dataself.level=levelself.parent = parentclass test1:def __init__(self,initial,goals):self.initial=Node(np.reshape(initial,(3,3)),0,"None")self.goals=Node(np.reshape(goals,(3,3)),0,"None")##初始化程序self.open_=[self.initial]self.close_=[]self.b=15#展示数据函数def __show_data(self,a):for i in a.data:print(i)#移动函数def __move(self,n,postion,row,col):if postion =="left":n[row,col] , n[row,col-1] = n[row,col-1], n[row,col]elif postion == "right":n[row,col] , n[row,col+1] = n[row,col+1], n[row,col]elif postion == "up":n[row,col] , n[row-1,col] = n[row-1,col], n[row,col]elif postion == "down":n[row,col] , n[row+1,col] = n[row+1,col], n[row,col]return ndef __ifexists(self,three_result,close,open_):for i in range(len(close)):if (three_result == close[i].data).all():#print("在close表中有重复")return Truefor i in range(len(open_)):if (three_result == open_[i].data).all():#print("在open表中有重复")return Truereturn Falsedef find_do(self):#遍历个数flag = 0#levellevel=1while self.open_:flag = flag+1#初始化算子direction=['up', 'down', 'right', 'left']#从open表中删除第一个状态并放入close表中n = self.open_.pop(0)self.close_.append(n)#print(n)#print(self.initial)#print(n==b)#如果n为目标状态则返回求解路径'''np.all所有都是true才能是truenp.any一个是true就是true '''#print(n.data)#print(self.goals)if (n.data == self.goals.data).all():resultAll=[]resultAll.append(n)print("展示搜索到的目标值最优路径！")# print("---->") while n.parent!="None":resultAll.append(n.parent)n = n.parentfor j in range(len(resultAll)):print(str(j)+"->")result = resultAll.pop(-1)self.__show_data(result)print("----------------------------------结束搜索-----------------------------------")break #生产n的所有子状态,并加入到open表后方postion = np.where(n.data == 0)i = postion[0]j = postion[1]length_down=n.data.shape[0]length_right=n.data.shape[1]#清除左操作if i==0:direction.remove("up")#清除上操作if j==0:direction.remove("left")#清除下操作if i == length_down-1:direction.remove("down")#清除右操作if j == length_right-1:direction.remove("right")#找到子状态for p in range(len(direction)):copy_n = copy.deepcopy(n)three_result = self.__move(copy_n.data,direction[p],i,j)#print(three_result)#判断是否存在于close表if (self.__ifexists(three_result,self.close_,self.open_)):#直接跳出此次循环 不加入open表continueself.open_.append(Node(three_result,n.level+1,n))print("完成第"+str(flag)+"次查找，此轮中间项为：\n",n.data)print("层数",n.level)# if n.parent=="None":# print("父节点","None")# else:# print("父节点",n.parent.data)#print("open表第一个数的内容",self.open_[0].data)# print("open表第一个数的内容",self.open_[0].data)# print("open表第一个数的level",self.open_[0].level)# print("open表第二个数的内容",self.open_[1].data)# print("open表第一个数的level",self.open_[0].level)# if flag==3:# break##初始化状态a=[0,1,3,4,2,5,7,8,6]b=[4,1,3,7,0,5,8,2,6]#初始化类test1 = test1(a,b)test1.find_do()
深度优先算法(python代码)
深度优先——未输出最优解方法
import numpy as npimport copyclass Node:def __init__(self,data,level):self.data=dataself.level=levelclass test1:def __init__(self,initial,goals):self.initial=Node(np.reshape(initial,(3,3)),0)self.goals=Node(np.reshape(goals,(3,3)),0)##初始化程序self.open_=[self.initial]self.close_=[]self.b=15#展示数据函数def __show_data(self,a):for i in a.data:print(i)#移动函数def __move(self,n,postion,row,col):if postion =="left":n[row,col] , n[row,col-1] = n[row,col-1], n[row,col]elif postion == "right":n[row,col] , n[row,col+1] = n[row,col+1], n[row,col]elif postion == "up":n[row,col] , n[row-1,col] = n[row-1,col], n[row,col]elif postion == "down":n[row,col] , n[row+1,col] = n[row+1,col], n[row,col]return ndef __ifexists(self,three_result,close,open_):for i in range(len(close)):if (three_result == close[i].data).all():#print("在close表中有重复")return Truefor i in range(len(open_)):if (three_result == open_[i].data).all():#print("在open表中有重复")return Truereturn Falsedef find_do(self):#遍历个数flag = 0#levellevel=1while self.open_:flag = flag+1#初始化算子direction=['up', 'down', 'right', 'left']#从open表中删除第一个状态并放入close表中n = self.open_.pop(0)self.close_.append(n)#print(n)#print(self.initial)#print(n==b)#如果n为目标状态则返回求解路径'''np.all所有都是true才能是truenp.any一个是true就是true '''#print(n.data)#print(self.goals)if (n.data == self.goals.data).all():print("展示搜索到的目标值")self.__show_data(n)print("----------------------------------找到目标值啦-----------------------------------")break #生产n的所有子状态,并加入到open表后方postion = np.where(n.data == 0)i = postion[0]j = postion[1]length_down=n.data.shape[0]length_right=n.data.shape[1]#清除左操作if i==0:direction.remove("up")#清除上操作if j==0:direction.remove("left")#清除下操作if i == length_down-1:direction.remove("down")#清除右操作if j == length_right-1:direction.remove("right")if n.level>=self.b:continue#print(direction)# level = level+1#找到子状态for p in range(len(direction)):copy_n = copy.deepcopy(n)three_result = self.__move(copy_n.data,direction[p],i,j)#print(three_result)#判断是否存在于close表if (self.__ifexists(three_result,self.close_,self.open_)):#直接跳出此次循环 不加入open表continueself.open_.insert(0,Node(three_result,n.level+1))print("完成第"+str(flag)+"次查找，此轮中间项为：\n",n.data)print("层数",n.level)#print("open表第一个数的内容",self.open_[0].data)# print("open表第一个数的内容",self.open_[0].data)# print("open表第一个数的level",self.open_[0].level)# print("open表第二个数的内容",self.open_[1].data)# print("open表第一个数的level",self.open_[0].level)# if flag==3:# break##初始化状态a=[0,1,3,4,2,5,7,8,6]b=[4,1,3,7,0,5,8,2,6]#初始化类test1 = test1(a,b)test1.find_do()
深度优先——输出最优解方法
import numpy as npimport copyclass Node:def __init__(self,data,level,parent):self.data=dataself.level=levelself.parent = parentclass test1:def __init__(self,initial,goals):self.initial=Node(np.reshape(initial,(3,3)),0,"None")self.goals=Node(np.reshape(goals,(3,3)),0,"None")##初始化程序self.open_=[self.initial]self.close_=[]self.b=15#展示数据函数def __show_data(self,a):for i in a.data:print(i)#移动函数def __move(self,n,postion,row,col):if postion =="left":n[row,col] , n[row,col-1] = n[row,col-1], n[row,col]elif postion == "right":n[row,col] , n[row,col+1] = n[row,col+1], n[row,col]elif postion == "up":n[row,col] , n[row-1,col] = n[row-1,col], n[row,col]elif postion == "down":n[row,col] , n[row+1,col] = n[row+1,col], n[row,col]return ndef __ifexists(self,three_result,close,open_):for i in range(len(close)):if (three_result == close[i].data).all():#print("在close表中有重复")return Truefor i in range(len(open_)):if (three_result == open_[i].data).all():#print("在open表中有重复")return Truereturn Falsedef find_do(self):#遍历个数flag = 0#levellevel=1while self.open_:flag = flag+1#初始化算子direction=['up', 'down', 'right', 'left']#从open表中删除第一个状态并放入close表中n = self.open_.pop(0)self.close_.append(n)#print(n)#print(self.initial)#print(n==b)#如果n为目标状态则返回求解路径'''np.all所有都是true才能是truenp.any一个是true就是true '''#print(n.data)#print(self.goals)if (n.data == self.goals.data).all():resultAll=[]resultAll.append(n)print("展示搜索到的目标值最优路径！")# print("---->") while n.parent!="None":resultAll.append(n.parent)n = n.parentfor j in range(len(resultAll)):print(str(j)+"->")result = resultAll.pop(-1)self.__show_data(result)print("----------------------------------结束搜索-----------------------------------")break #生产n的所有子状态,并加入到open表后方postion = np.where(n.data == 0)i = postion[0]j = postion[1]length_down=n.data.shape[0]length_right=n.data.shape[1]#清除左操作if i==0:direction.remove("up")#清除上操作if j==0:direction.remove("left")#清除下操作if i == length_down-1:direction.remove("down")#清除右操作if j == length_right-1:direction.remove("right")if n.level>=self.b:continue#print(direction)# level = level+1#找到子状态for p in range(len(direction)):copy_n = copy.deepcopy(n)three_result = self.__move(copy_n.data,direction[p],i,j)#print(three_result)#判断是否存在于close表if (self.__ifexists(three_result,self.close_,self.open_)):#直接跳出此次循环 不加入open表continueself.open_.insert(0,Node(three_result,n.level+1,n))print("完成第"+str(flag)+"次查找，此轮中间项为：\n",n.data)print("层数",n.level)# if n.parent=="None":# print("父节点","None")# else:# print("父节点",n.parent.data)#print("open表第一个数的内容",self.open_[0].data)# print("open表第一个数的内容",self.open_[0].data)# print("open表第一个数的level",self.open_[0].level)# print("open表第二个数的内容",self.open_[1].data)# print("open表第一个数的level",self.open_[0].level)# if flag==3:# break##初始化状态a=[0,1,3,4,2,5,7,8,6]b=[4,1,3,7,0,5,8,2,6]#初始化类test1 = test1(a,b)test1.find_do()
判断无解状态（以宽度搜索为例）
import mathimport numpy as npimport copyclass test:def __init__(self,initial,goals):self.initial = initialself.goals = goalsself.length = int(math.sqrt(len(initial)))#print(self.length)self.initial=np.reshape(initial,(self.length,self.length))self.goals=np.reshape(goals,(self.length,self.length))##初始化程序self.open_=[self.initial]self.close_=[]#展示数据函数def __show_data(self,a):for i in a:print(i)#移动函数def __move(self,n,postion,row,col):if postion =="left":n[row,col] , n[row,col-1] = n[row,col-1], n[row,col]elif postion == "right":n[row,col] , n[row,col+1] = n[row,col+1], n[row,col]elif postion == "up":n[row,col] , n[row-1,col] = n[row-1,col], n[row,col]elif postion == "down":n[row,col] , n[row+1,col] = n[row+1,col], n[row,col]return ndef __ifexists(self,three_result,close,open_):for i in range(len(close)):if (three_result == close[i]).all():#print("在close表中有重复")return Truefor i in range(len(open_)):if (three_result == open_[i]).all():#print("在open表中有重复")return Truereturn Falsedef __inverse_number(self,string):ans = 0for i in range(len(string)):for j in range(i):if string[j] > string[i]:ans += 1return ansdef find_do(self):##判断八数码是否有解str1=','.join('%s' % id for id in self.initial)str2=','.join('%s' % id for id in self.goals)if self.__inverse_number(str1)%2 != self.__inverse_number(str2)%2:print("无解！ 停止搜索！")return Falseflag = 0#print(self.open_)while self.open_:flag = flag+1#初始化算子direction=['up', 'down', 'right', 'left']#从open表中删除第一个状态并放入close表中n = self.open_.pop(0)self.close_.append(n)#print(n)#print(self.initial)#print(n==b)#如果n为目标状态则返回求解路径'''np.all所有都是true才能是truenp.any一个是true就是true '''#print(n)#print(self.goals)if (n == self.goals).all():print("展示搜索到的目标值")self.__show_data(n)print("----------------------------------找到目标值啦-----------------------------------")break #生产n的所有子状态,并加入到open表后方postion = np.where(n == 0)#print(postion)#print("aa")i = postion[0]j = postion[1]length_down=n.shape[0]length_right=n.shape[1]#清除左操作if i==0:direction.remove("up")#清除上操作if j==0:direction.remove("left")#清除下操作if i == length_down-1:direction.remove("down")#清除右操作if j == length_right-1:direction.remove("right")#print(direction)#找到子状态for p in range(len(direction)):copy_n = copy.deepcopy(n)three_result = self.__move(copy_n,direction[p],i,j)#print(three_result)#判断是否存在于close表if (self.__ifexists(three_result,self.close_,self.open_)):#直接跳出此次循环 不加入open表continueself.open_.append(three_result)print("完成第"+str(flag)+"次查找，此轮中间项为：\n",n)##初始化状态# ###三数码# a=[0,1,3,4]# b=[4,0,1,3]###八数码# a=[0,1,3,4,2,5,7,8,6]# b=[4,1,3,7,0,5,8,2,6]a=[0,1,3,4,2,5,7,8,6]b=[0,1,4,3,2,5,7,8,6]# ###十五数码# a=[0,1,3,4,2,5,7,8,6,10,11,12,13,14,15,16]# b=[1,0,3,4,2,5,7,8,6,10,11,12,13,14,15,16]#初始化类test1 = test(a,b)test1.find_do()
A算法
import numpy as npimport copyimport mathclass Node:def __init__(self,data,level,parent,score):self.data=dataself.level=levelself.parent = parentself.score = scoreclass test1:def __init__(self,initial,goals):#查看传入长度self.length = int(math.sqrt(len(initial)))#初始化初始节点与目标节点self.initial=Node(np.reshape(initial,(self.length,self.length)),0,"None",0)self.goals=Node(np.reshape(goals,(self.length,self.length)),0,"None",0)##初始化初始节点估价数值self.__score_N(self.initial,self.goals,self.length)##初始化程序self.open_=[self.initial]self.close_=[]self.b=15#估价函数def __score_N(self,node,goals,length):#d(n)a = node.level#w(n)b = np.count_nonzero(node.data-goals.data)node.score = a+b# print(a)# print(b)# print("数据长度",math.pow(length,2))# print("统计对应位置不相同的数",np.count_nonzero(node.data-goals.data))return node#展示数据函数def __show_data(self,a):for i in a.data:print(i)#移动函数def __move(self,n,postion,row,col):if postion =="left":n[row,col] , n[row,col-1] = n[row,col-1], n[row,col]elif postion == "right":n[row,col] , n[row,col+1] = n[row,col+1], n[row,col]elif postion == "up":n[row,col] , n[row-1,col] = n[row-1,col], n[row,col]elif postion == "down":n[row,col] , n[row+1,col] = n[row+1,col], n[row,col]return ndef __ifexists(self,three_result,close,open_):#print(open_)for i in range(len(close)):if (three_result == close[i].data).all():#print("在close表中有重复")return Truefor i in range(len(open_)):if (three_result == open_[i].data).all():#print("在open表中有重复")return Truereturn Falsedef __sort_threelist(self,arr):n = len(arr)for i in range(n):for j in range(0,n-i-1):if arr[j].score>arr[j+1].score:arr[j],arr[j+1] = arr[j+1] ,arr[j]return arrdef find_do(self):#遍历个数flag = 0#levellevel=1while self.open_:flag = flag+1#初始化算子direction=['up', 'down', 'right', 'left']#从open表中删除第一个状态并放入close表中n = self.open_.pop(0)self.close_.append(n)#print(self.close_[0].data)#print(n)#print(self.initial)#print(n==b)#如果n为目标状态则返回求解路径'''np.all所有都是true才能是truenp.any一个是true就是true '''#print(n.data)#print(self.goals)if (n.data == self.goals.data).all():resultAll=[]resultAll.append(n)print("展示搜索到的目标值最优路径！")# print("---->") while n.parent!="None":resultAll.append(n.parent)n = n.parentfor j in range(len(resultAll)):print(str(j)+"->")result = resultAll.pop(-1)self.__show_data(result)print("----------------------------------结束搜索-----------------------------------")break #生产n的所有子状态,并加入到open表后方postion = np.where(n.data == 0)i = postion[0]j = postion[1]length_down=n.data.shape[0]length_right=n.data.shape[1]#清除左操作if i==0:direction.remove("up")#清除上操作if j==0:direction.remove("left")#清除下操作if i == length_down-1:direction.remove("down")#清除右操作if j == length_right-1:direction.remove("right")#初始化对比表three_result_list = []#找到子状态for p in range(len(direction)):copy_n = copy.deepcopy(n)three_result = self.__move(copy_n.data,direction[p],i,j)#print(three_result)#判断是否存在于close表if (self.__ifexists(three_result,self.close_,self.open_)):#直接跳出此次循环 不加入open表continue#评估节点score_t = self.__score_N(Node(three_result,n.level+1,n,0),self.goals,self.length)self.open_.append(score_t)#对比表排序self.open_ =self.__sort_threelist(self.open_)print("完成第"+str(flag)+"次查找，此轮中间项为：\n",n.data)print("层数",n.level)print("评估函数值",n.score)##初始化状态a=[0,1,3,4,2,5,7,8,6]b=[4,1,3,7,0,5,8,2,6]#初始化类test1 = test1(a,b)test1.find_do()
