### Python 实现8数码问题的宽度优先搜索与深度优先搜索 #### 状态空间表示方法 在解决8数码问题时，可以将棋盘上的每一个布局视为一种状态。通常使用一维列表来存储这些状态，其中`0`代表空白位置。例如，初始状态 `[1, 2, 3, 4, 5, 6, 7, 8, 0]` 表示如下布局： ``` 1 2 3 4 5 6 7 8 * ``` 目标状态一般定义为 `[1, 2, 3, 4, 5, 6, 7, 8, 0]` 或其他指定形式。 为了便于操作，可以通过索引来定位空白块的位置，并基于此设计移动规则[^1]。 --- #### 宽度优先搜索 (BFS) 宽度优先搜索是一种逐层扩展节点的方法，在每一步都会探索当前层次的所有可能状态后再进入下一层级。以下是具体实现代码： ```python from collections import deque def bfs(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 ((zero_index // 3 == new_index // 3) or abs(offset) != 1): new_state = list(current_state) new_state[zero_index], new_state[new_index] = new_state[new_index], new_state[zero_index] queue.append((new_state, path + [(move_name, new_state)])) # 将新状态加入队列 return None ``` 上述代码通过维护一个队列 `queue` 来保存待处理的状态及其路径历史。每次从队列头部取出一个状态并尝试所有合法动作，如果未被访问过，则将其子状态加入队列中继续扩展。 --- #### 深度优先搜索 (DFS) 深度优先搜索则采用递归方式深入某一方向直至无法再前进或者找到解决方案为止。由于其可能会陷入无限循环（特别是对于无界图），因此需要设置最大深度限制或其他约束条件。 下面是 DFS 的实现版本： ```python def dfs_helper(state, goal_state, max_depth, depth=0, path=None, visited=None): if path is None: path = [] if visited is None: visited = set() if state == goal_state: # 如果到达目标状态返回路径 return path if depth >= max_depth: # 达到最大深度停止进一步探索 return None visited.add(tuple(state)) zero_index = state.index(0) possible_moves = [("UP", -3), ("DOWN", +3), ("LEFT", -1), ("RIGHT", +1)] for name, offset in possible_moves: next_index = zero_index + offset if 0 <= next_index < 9 and ((zero_index // 3 == next_index // 3) or abs(offset) != 1): new_state = list(state) new_state[zero_index], new_state[next_index] = new_state[next_index], new_state[zero_index] if tuple(new_state) not in visited: result = dfs_helper( new_state, goal_state, max_depth, depth + 1, path + [(name, new_state)], visited.copy(), ) if result is not None: return result return None def dfs(initial_state, goal_state, max_depth): return dfs_helper(initial_state, goal_state, max_depth=max_depth) ``` 这里引入了一个辅助函数 `dfs_helper` 进行实际递归调用，并设置了参数控制递归的最大深度以防止栈溢出等问题发生。 --- #### 测试运行结果 假设我们有以下输入情况： - **初始状态**: `[1, 2, 3, 4, 5, 6, 7, 8, 0]` - **目标状态**: `[1, 2, 3, 4, 5, 6, 7, 8, 0]` 执行 BFS 和 DFS 后均应得到相同的结果——即零步变换即可完成任务。然而当改变起始配置时，两者会表现出不同的行为模式：前者按广度展开而后者沿单一路径深挖下去[^2]。 ---