導引
- 理論
- 代碼
- 寬度優先搜索演算法 (python代碼)
- 深度優先演算法(python代碼)
理論
問題描述：八數碼問題是在一個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()
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/182553.html
標籤：python
下一篇：Python極速上手教程