八數(shù)碼問題也稱為九宮問題。在3×3的棋盤苗傅，擺有八個(gè)棋子，每個(gè)棋子上標(biāo)有1至8的某一數(shù)字班巩，不同棋子上標(biāo)的數(shù)字不相同渣慕。棋盤上還有一個(gè)空格，與空格相鄰的棋子可以移到空格中抱慌。要求解決的問題是：給出一個(gè)初始狀態(tài)和一個(gè)目標(biāo)狀態(tài)逊桦，找出一種從初始狀態(tài)轉(zhuǎn)變成目標(biāo)狀態(tài)的移動(dòng)棋子步數(shù)最少的移動(dòng)步驟。
一開始也是兩眼一抹黑抑进，連八數(shù)碼是什么都不知道强经，經(jīng)過度娘得到如上結(jié)果。那該如何實(shí)現(xiàn)呢寺渗？如果移動(dòng)數(shù)字的話匿情，8個(gè)數(shù)字兰迫，每次移動(dòng)有4種選擇，那就是32個(gè)種移動(dòng)方案炬称。那移動(dòng)空格就只有4種選擇汁果，一下子清楚了很多。至于存儲(chǔ)方案當(dāng)然是數(shù)組了玲躯，交換起來多方便据德，是吧？
實(shí)現(xiàn)方式呢跷车？最初實(shí)驗(yàn)要求使用回溯算法解決棘利，什么，回溯姓赤？赡译！那不是和深度優(yōu)先一樣嗎仲吏？無腦走找結(jié)果不铆？算了，先試試吧裹唆。
import numpy as np
#返回兩個(gè)數(shù)組對(duì)應(yīng)位置相同值的個(gè)數(shù)
def calc(state1):
b = np.array([[1, 2, 3], [8, 0, 4], [7, 6, 5]])
postion = np.where(state1 == b)
return len(state1[postion])
#打印八數(shù)碼
def showInfo(a):
for i in range(3):
for j in range(3):
print(a[i, j], end=' ')
print("\n")
print('->')
directions = ['up', 'down', 'left', 'right']
def SubStates(state):
subStates = []
row, col = np.where(state==0)
for direction in directions:
if 'left' == direction and col > 0:
s = state.copy()
s[row, col],s[row, col - 1] = s[row, col - 1],s[row, col]
subStates.append(s)
if 'up' == direction and row > 0:
s = state.copy()
s[row, col],s[row - 1, col] = s[row - 1, col],s[row, col]
subStates.append(s)
if 'down' == direction and row < 2:
s = state.copy()
s[row, col],s[row + 1, col] = s[row + 1, col],s[row, col]
subStates.append(s)
if 'right' == direction and col < 2:
s = state.copy()
s[row, col],s[row, col + 1] = s[row, col + 1],s[row, col]
subStates.append(s)
return subStates
def DFS(first):
stack = []
stack.append(first)
count = -1
while stack:
count += 1
node = stack.pop()
showInfo(node)
if calc(node) == 9:
return True,count
s = SubStates(node)
#res = sorted(s, key=calc)
for x in res:
stack.append(x)
#主函數(shù)
def main():
start = np.array([[0, 1, 3], [8, 2, 4], [7, 6, 5]])
#start = np.array([[2, 8, 3], [1, 0, 4], [7, 6, 5]])
res,count = DFS(start)
if res:
print('經(jīng)過%d次變換結(jié)束' %count)
if __name__ == '__main__':
main()
用迭代方式很容易的寫出了深度優(yōu)先算法誓斥，可是貌似跑不出結(jié)果。许帐。劳坑。what a fuck，什么鬼成畦？遂找了個(gè)只移動(dòng)兩次的距芬，運(yùn)行，還是不行循帐。隨機(jī)壓棧太瘋狂了框仔，加點(diǎn)約束吧。每次找和最終結(jié)果最相似的出棧應(yīng)該可以拄养。（這里說一下為了防止無限次循環(huán)离斩，用寬度優(yōu)先搜素比較合適，只需把pop()改成pop(0),如果用到排序的話那就要按相似度由高到低排列了）嗯瘪匿，加上這句res = sorted(s, key=calc),壓棧前按相似度由低到高做一次排序跛梗。移動(dòng)兩次的果然跑出來了，可是移動(dòng)多次的還是不行棋弥。
得核偿，再想辦法吧。做一個(gè)界限函數(shù)顽染，用八數(shù)碼迭代出來的層數(shù)加上相似度來搜索漾岳。這個(gè)值在一定限度才入棧聂薪，否則舍棄。
這里我將節(jié)點(diǎn)封裝成一個(gè)類來實(shí)現(xiàn)蝗羊。
import numpy as np
class eightPuzzle(object):
directions = ['up', 'down', 'left', 'right']
max = 7
def __init__(self,arr,cost=0,parent=None):
self.arr = arr
self.cost = cost
self.parent = parent
def getCost(self):
return self.cost
# 返回兩個(gè)數(shù)組對(duì)應(yīng)位置相同值的個(gè)數(shù)
def calc(self,state):
final = np.array([[1, 2, 3], [8, 0, 4], [7, 6, 5]])
postion = np.where(state.arr == final)
return len(state.arr[postion])
# 打印八數(shù)碼
def showInfo(self):
for i in range(3):
for j in range(3):
print(self.arr[i, j], end=' ')
print("\n")
print('->')
def calc2(self, state1, stop):
for x in stop:
postion = np.where(state1.arr == x.arr)
if len(state1.arr[postion]) == 9:
return True
return False
def SubStates(self):
subStates = []
row, col = np.where(self.arr==0)
for direction in self.directions:
if 'left' == direction and col > 0:
s = self.arr.copy()
s[row, col],s[row, col - 1] = s[row, col - 1],s[row, col]
new = eightPuzzle(s,self.cost+1,self)
subStates.append(new)
if 'up' == direction and row > 0:
s = self.arr.copy()
s[row, col],s[row - 1, col] = s[row - 1, col],s[row, col]
new = eightPuzzle(s, self.cost + 1,self)
subStates.append(new)
if 'down' == direction and row < 2:
s = self.arr.copy()
s[row, col],s[row + 1, col] = s[row + 1, col],s[row, col]
new = eightPuzzle(s, self.cost + 1,self)
subStates.append(new)
if 'right' == direction and col < 2:
s = self.arr.copy()
s[row, col],s[row, col + 1] = s[row, col + 1],s[row, col]
new = eightPuzzle(s, self.cost + 1,self)
subStates.append(new)
return subStates
def DFS(self):
stack = []
stop = []
stack.append(self)
count = -1
while True:
if not stack:
return False,count,node
count += 1
#stack = sorted(stack, key=self.calc)
node = stack.pop()
stop.append(node)
node.showInfo()
if self.calc(node) == 9:
return True,count,node
s = node.SubStates()
if s:
res = sorted(s, key=self.calc)
else:
continue
for x in res:
if (x.cost + 9 - self.calc(x))< eightPuzzle.max:
if self.calc2(x,stop):
continue
stack.append(x)
def showInfo(result):
for node in result:
for i in range(3):
for j in range(3):
print(node.arr[i, j], end=' ')
print('\n')
print('->')
#主函數(shù)
def main():
#start = np.array([[0, 1, 3], [8, 2, 4], [7, 6, 5]])
start = np.array([[2, 8, 3], [1, 0, 4], [7, 6, 5]])
p = eightPuzzle(start)
res,count,node = p.DFS()
result = []
if res:
print('經(jīng)過%d次變換結(jié)束' %count)
while node:
result.append(node)
node = node.parent
result.reverse()
showInfo(result)
else:
print('規(guī)定范圍內(nèi)未找到合適路徑藏澳，可增大界值')
if __name__ == '__main__':
main()
這次經(jīng)過七次搜索得到了最終答案。
這時(shí)候發(fā)現(xiàn)輸出很有意思耀找，會(huì)出現(xiàn)初始狀態(tài)翔悠。因此在深度搜索的過程中加了一個(gè)stop表，用來存儲(chǔ)已經(jīng)出棧的元素野芒，每次入棧的時(shí)候查看若已經(jīng)存在則扔掉蓄愁。此時(shí)運(yùn)行6次出現(xiàn)答案。
結(jié)束狞悲。
