### 将深度优先搜索改为广度优先搜索 为了将一个解决八数码问题的深度优先搜索 (DFS) 改为广度优先搜索 (BFS)，主要需要调整以下几个方面： 1. **数据结构的选择**： DFS 使用栈（Stack）来管理待处理节点，而 BFS 则使用队列（Queue）。因此，在实现中需要用 `collections.deque` 替代递归调用或者显式的栈操作。 2. **状态扩展顺序**： 在 BFS 中，总是先处理最早加入队列的状态。这意味着我们需要按层逐步探索所有可能的状态，而不是像 DFS 那样沿着一条路径深入到底再返回。 3. **终止条件和路径记录**： 和 DFS 类似，BFS 同样需要检查当前状态是否为目标状态，并且通过保存父节点的方式回溯最终解法路径[^2]。 以下是基于 Python 的广度优先搜索代码示例，用于解决八数码问题： ```python from collections import deque def bfs_eight_puzzle(initial_state, goal_state): visited = set() # 记录已访问过的状态 queue = deque([(initial_state, [])]) # 初始化队列，元组形式为 (当前状态, 路径) while queue: current_state, path = queue.popleft() if tuple(current_state) == tuple(goal_state): # 如果达到目标状态 return path if tuple(current_state) not in visited: # 检查当前状态是否已经访问过 visited.add(tuple(current_state)) zero_index = current_state.index(0) # 获取空白格的位置索引 moves = [ ("UP", -3), # 上移 ("DOWN", +3), # 下移 ("LEFT", -1), # 左移 ("RIGHT", +1) # 右移 ] for move_name, offset in moves: new_index = zero_index + offset if 0 <= new_index < 9 and abs(zero_index % 3 - new_index % 3) != 2: new_state = list(current_state) new_state[zero_index], new_state[new_index] = new_state[new_index], new_state[zero_index] if tuple(new_state) not in visited: queue.append((new_state, path + [(move_name, new_index)])) return None # 若无解则返回 None # 测试代码 if __name__ == "__main__": initial_state = [1, 2, 3, 4, 5, 6, 7, 8, 0] # 初始状态 goal_state = [1, 2, 3, 4, 5, 6, 7, 8, 0] # 目标状态 solution_path = bfs_eight_puzzle(initial_state, goal_state) if solution_path is not None: print("Solution found:") for step in solution_path: print(f"Move {step[0]} to index {step[1]}") else: print("No solution exists.") ``` #### 关键点解释 - **队列初始化**：初始状态及其对应的空路径被放入队列中。 - **状态转换逻辑**：通过定义四个方向的操作 (`UP`, `DOWN`, `LEFT`, `RIGHT`) 来生成新的合法状态。 - **合法性判断**：确保移动不会超出边界或违反棋盘规则。 - **路径记录**：每一步都更新到达该状态所需的路径列表[^2]。 此代码实现了标准的广度优先搜索过程，能够有效求解八数码问题并找到最优解。 --- ###