我正在嘗試實作各種演算法來解決 8 個難題。對于不熟悉這個問題的人，有 3 行 3 列，和一個空的 tile，這里用零表示。它看起來像這樣：
這是我的代碼：
initial_state = [1,2,3,4,5,6,7,0,8]
goal_state = [1,2,3,4,5,6,7,8,0]
moves = [
[ (0,1), (0,3) ],
[ (1,1), (1,0), (1,4) ],
[ (2,1), (2,5) ],
[ (3,0), (3,6), (3,4) ],
[ (4,1), (4,7), (4,5), (4,3) ],
[ (5,2), (5,8), (5,4) ],
[ (6,3), (6,7) ],
[ (7,4), (7,8), (7,6) ],
[ (8,5), (8,7) ],
]
def find_new_nodes(state):
return [ swap_positions(state[:],a,b) for a,b in moves[find_zero(state)] ]
def find_zero(state):
return state.index(0)
def swap_positions(lis, pos1, pos2):
lis[pos1],lis[pos2] = lis[pos2],lis[pos1]
return lis
def BFS(start,goal):
visited = [] #visited list
node_queue= [start] #main queue
visited.append(start)
while node_queue:
current = node_queue.pop(0)
print(current)
if current == goal:
return True
for newnode in find_new_nodes(current):
if newnode not in visited:
node_queue.append(newnode)
visited.append(newnode)
return False
def DFS(start,goal):
visited = [] #visited list
node_queue= [start] #main queue
visited.append(start)
while node_queue:
current = node_queue.pop()
print(current)
if current == goal:
return True
for newnode in find_new_nodes(current):
if newnode not in visited:
node_queue.append(newnode)
visited.append(newnode)
return False
我將 pop(0) 更改為 pop() 以便它是 lifo，而不是 fifo。我的 DFS 輸出似乎是一個永無止境的回圈，但距離這個起始串列只有幾步之遙，它在 3 次移動中通過 bfs 函式達到了目標。為什么不起作用？
uj5u.com熱心網友回復：
沒有任何問題。由于幾個原因，它很慢。
它運行緩慢的第一個原因是，由于它是一個 DFS，它最終不得不在找到答案之前查看所有 181440 個可解狀態。
第二個原因是線if newnode not in visited最終不得不掃描整個陣列。因此，我們需要掃描超過 100,000 個長度的串列數十萬次，并且比較陣列并不便宜。這需要數百億次操作，需要一段時間。
您可以通過切換到這樣的集合來消除第二個問題：
def DFS(start,goal):
visited = set() #visited list
node_queue= [start] #main queue
visited.add(tuple(start))
while node_queue:
current = node_queue.pop()
print((len(visited), current))
if current == goal:
return True
for newnode in find_new_nodes(current):
if tuple(newnode) not in visited:
node_queue.append(newnode)
visited.add(tuple(newnode))
return False
您可以通過檢查來驗證演算法沒有發生根本性的變化，但其性能應該有所提高。事實上，在我的筆記本電腦上，它現在可以在大約一秒鐘內完成。
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/365904.html
下一篇：帶記憶的遞回河內塔的空間復雜度？