### 使用Python实现BFS、DFS和A*算法解决8数码问题 #### 1. 问题描述 八数码问题是一个经典的搜索问题，目标是将一个3x3的棋盘从初始状态通过移动空格（用0表示）变换到目标状态。 #### 2. 代码实现 ```python import heapq from collections import deque # 目标状态 goal_state = '123456780' # 计算曼哈顿距离 def manhattan_distance(state): distance = 0 for i in range(9): if state[i] != '0': target_index = int(state[i]) - 1 current_row, current_col = i // 3, i % 3 target_row, target_col = target_index // 3, target_index % 3 distance += abs(current_row - target_row) + abs(current_col - target_col) return distance # 生成可能的后继状态 def get_successors(state): successors = [] index = state.index('0') row, col = index // 3, index % 3 # 向上移动 if row > 0: new_index = (row - 1) * 3 + col new_state = list(state) new_state[index], new_state[new_index] = new_state[new_index], new_state[index] successors.append(''.join(new_state)) # 向下移动 if row < 2: new_index = (row + 1) * 3 + col new_state = list(state) new_state[index], new_state[new_index] = new_state[new_index], new_state[index] successors.append(''.join(new_state)) # 向左移动 if col > 0: new_index = row * 3 + (col - 1) new_state = list(state) new_state[index], new_state[new_index] = new_state[new_index], new_state[index] successors.append(''.join(new_state)) # 向右移动 if col < 2: new_index = row * 3 + (col + 1) new_state = list(state) new_state[index], new_state[new_index] = new_state[new_index], new_state[index] successors.append(''.join(new_state)) return successors # BFS算法 def bfs(initial_state): queue = deque([(initial_state, [initial_state])]) visited = set([initial_state]) while queue: current_state, path = queue.popleft() if current_state == goal_state: return path for successor in get_successors(current_state): if successor not in visited: visited.add(successor) queue.append((successor, path + [successor])) return None # DFS算法 def dfs(initial_state): stack = [(initial_state, [initial_state])] visited = set([initial_state]) while stack: current_state, path = stack.pop() if current_state == goal_state: return path for successor in get_successors(current_state): if successor not in visited: visited.add(successor) stack.append((successor, path + [successor])) return None # A*算法 def astar(initial_state): open_list = [(manhattan_distance(initial_state), 0, initial_state, [initial_state])] closed_set = set() while open_list: _, cost, current_state, path = heapq.heappop(open_list) if current_state == goal_state: return path if current_state in closed_set: continue closed_set.add(current_state) for successor in get_successors(current_state): if successor not in closed_set: new_cost = cost + 1 priority = new_cost + manhattan_distance(successor) heapq.heappush(open_list, (priority, new_cost, successor, path + [successor])) return None # 测试 initial_state = '283164705' print("BFS solution:", bfs(initial_state)) print("DFS solution:", dfs(initial_state)) print("A* solution:", astar(initial_state)) ``` ### 单独使用DFS解决八数码问题 上述代码中已经包含了单独使用DFS解决八数码问题的部分，即`dfs`函数。 ```python # DFS算法 def dfs(initial_state): stack = [(initial_state, [initial_state])] visited = set([initial_state]) while stack: current_state, path = stack.pop() if current_state == goal_state: return path for successor in get_successors(current_state): if successor not in visited: visited.add(successor) stack.append((successor, path + [successor])) return None # 测试 initial_state = '283164705' print("DFS solution:", dfs(initial_state)) ```