[python 那些事兒] 八數碼問題
2020-10-20 12:01:03
理論
問題描述：八數碼問題是在一個3×3的方格盤上，放有1~8八個數碼，餘下一格為空格。空格可以與其四周的數碼交換位置，從而改變八個數碼在方格盤上的擺法。問題中可以使用的操作運算元有四種：空格上移（up）、空格下移（down）、空格左移（left）、空格右移（right）
實驗要求： 給定如下初始狀態S0和目標狀態Sg，要求程式設計實現：當輸入初始狀態S0後，通過搜尋得到目標狀態Sg，並記錄下從S0到Sg的所有中間狀態以及每一次狀態改變所使用的操作運算元。
（1）寬度優先搜尋演演算法（虛擬碼）：
Procedure_breadth_first_search:
Begin
open:=[Initial state]; closed:=[Initial state]; //初始化
while open ≠ [ ] do
begin
從open表中刪除第一個狀態，記作n；
將n放入closed表中；
if n = 目標狀態, then return(success); //成功，返回求解路徑
生產n的所有子狀態；
從n的子狀態中刪除已在open或closed表中出現的狀態；//避免重複搜尋
將n的其餘子狀態，按生成的次序加入open表中已有結點的後面；
end
end
（2）深度優先演演算法（虛擬碼）：
Procedure_breadth_first_search:
Begin
open:=[Initial state]; closed:=[Initial state]; d:=深度限制值； //初始化
while open ≠ [ ] do
begin
從open表中刪除第一個狀態，記作n；
將n放入closed表中；
if n = 目標狀態, then return(success); //成功，返回求解路徑
if n的深度<d, then continue; //繼續向深度方向搜尋
生產n的所有子狀態；
從n的子狀態中刪除已在open或closed表中出現的狀態；//避免重複搜尋
將n的其餘子狀態，按生成的次序加入open表中已有結點的前面；
end
end
程式碼
寬度優先搜尋演演算法 (python程式碼)
import numpy as np
import copy
class test:
def __init__(self,initial,goals):
self.initial=np.reshape(initial,(3,3))
self.goals=np.reshape(goals,(3,3))
##初始化程式
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 n
def __ifexists(self,three_result,close,open_):
for i in range(len(close)):
if (three_result == close[i]).all():
#print("在close表中有重複")
return True
for i in range(len(open_)):
if (three_result == open_[i]).all():
#print("在open表中有重複")
return True
return False
def 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才能是true
np.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表
continue
self.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()
深度優先演演算法(python程式碼)
import numpy as np
import copy
class Node:
def __init__(self,data,level):
self.data=data
self.level=level
class 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 n
def __ifexists(self,three_result,close,open_):
for i in range(len(close)):
if (three_result == close[i].data).all():
#print("在close表中有重複")
return True
for i in range(len(open_)):
if (three_result == open_[i].data).all():
#print("在open表中有重複")
return True
return False
def find_do(self):
#遍歷個數
flag = 0
#level
level=1
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才能是true
np.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表
continue
self.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()