我听说8拼图问题可以通过BFS解决,但我不明白如何解决。我想知道我需要从这样的板上获得的中间步骤:
3 1 2
6 4 5
0 7 8
到
1 2 3
4 5 6
7 8 0
BFS 搜索的中间步骤是“级别”吗?
顺便说一下,这是基本作业,我不关心最优性。
这几乎是任何 BFS 搜索的模板
function next_boards(board)
yields a set of reachable in one move from the current board
queue = [start_board]
while true:
current = queue.pop()
if current = goal: break
queue.push for all next_boards(current)
请注意,我们没有做任何花哨的事情,例如检查周期或任何事情。如果是的话,将队列更改为堆栈,然后您将获得 DFS。