### 使用 Python 实现 A* 算法解决八数码问题 以下是基于 A* 启发式搜索算法的 Python 示例代码，用于解决八数码问题。该实现考虑了状态空间表示、启发函数的设计以及路径规划的核心逻辑。 #### 八数码问题的状态表示 八数码问题可以被建模为一个图搜索问题，其中每个节点代表棋盘的一个可能配置。空白格的位置决定了哪些移动是合法的。通过定义合适的启发函数（如曼哈顿距离），能够有效减少搜索的空间复杂度[^1]。 ```python from collections import deque import heapq class PuzzleNode: def __init__(self, state, parent=None, move=""): self.state = state # 当前状态 (列表形式) self.parent = parent # 上一状态 self.move = move # 到达此状态的操作 ("up", "down", "left", "right") def get_blank_index(self): return self.state.index(0) def generate_children(self): children = [] blank_idx = self.get_blank_index() moves = { 'up': -3, 'down': 3, 'left': -1, 'right': 1 } for direction, offset in moves.items(): new_pos = blank_idx + offset if 0 <= new_pos < 9 and abs(blank_idx % 3 - new_pos % 3) != 2: # 防止越界或非法交换 new_state = list(self.state) new_state[blank_idx], new_state[new_pos] = new_state[new_pos], new_state[blank_idx] child_node = PuzzleNode(new_state, self, direction) children.append(child_node) return children def heuristic(state, goal): # 曼哈顿距离作为启发函数 distance = 0 for i in range(len(goal)): if goal[i] != 0: # 不计算空白格的距离 current_row, current_col = divmod(i, 3) target_row, target_col = divmod(state.index(goal[i]), 3) distance += abs(current_row - target_row) + abs(current_col - target_col) return distance def a_star_search(start, goal): open_list = [] # 堆队列存储待扩展节点 closed_set = set() # 已访问过的状态集合 start_node = PuzzleNode(list(map(int, start.split(',')))) goal_node = list(map(int, goal.split(','))) initial_cost = heuristic(start_node.state, goal_node) heapq.heappush(open_list, (initial_cost, 0, start_node)) # 总代价f(n), g(n), 节点本身 while open_list: _, cost_so_far, current_node = heapq.heappop(open_list) if tuple(current_node.state) == tuple(goal_node): path = [] node = current_node while node is not None: path.insert(0, (node.state.copy(), node.move)) node = node.parent return path closed_set.add(tuple(current_node.state)) for child in current_node.generate_children(): if tuple(child.state) in closed_set: continue tentative_g_score = cost_so_far + 1 # 每次移动成本固定为1 estimated_total_cost = tentative_g_score + heuristic(child.state, goal_node) skip_child = False for (_, existing_g, _) in open_list: if child.state == _ and tentative_g_score >= existing_g: skip_child = True break if skip_child: continue heapq.heappush(open_list, (estimated_total_cost, tentative_g_score, child)) # 测试用例 start_config = "7,2,4,5,0,6,8,3,1" goal_config = "0,1,2,3,4,5,6,7,8" solution_path = a_star_search(start_config, goal_config) for step in solution_path: print(f"{step[1]} -> {step[0]}") # 输出每一步的动作及其对应状态 ``` 上述代码实现了完整的 A* 搜索过程，并利用曼哈顿距离作为启发函数来评估当前状态到目标状态的成本。它还支持动态生成子节点并记录路径信息以便最终回溯解决方案[^2]。 --- #### 关键概念解释 - **启发函数**：在此处采用的是曼哈顿距离，即对于每一个不在正确位置上的数字，其与目标位置之间的水平和垂直差之和。 - **优先级队列**：`heapq` 库提供了高效的最小堆数据结构，使得每次都能快速选取具有最低估计总费用的候选节点进行扩展。 - **剪枝策略**：为了避免重复探索相同的状态，在 `closed_set` 中保存已处理过的历史记录；同时对比开放表中的已有条目决定是否更新更优解。 ---