### A*算法实现8数码问题 Python 示例代码 以下是使用A*算法解决8数码问题的Python实现代码。代码基于启发式搜索，结合了曼哈顿距离作为启发函数来计算每个状态的估计代价。 ```python import heapq class PuzzleState: def __init__(self, puzzle, parent=None, move=""): self.puzzle = puzzle # 当前状态 self.parent = parent # 父状态 self.move = move # 到达此状态的操作 self.g = 0 if parent is None else parent.g + 1 # 到达此状态的实际代价 self.h = self.calculate_h() # 启发函数值（曼哈顿距离） self.f = self.g + self.h # 总代价 def __lt__(self, other): return self.f < other.f # 用于优先队列排序 def calculate_h(self): """计算曼哈顿距离""" distance = 0 for i in range(9): if self.puzzle[i] != 0: # 忽略空格 target_x, target_y = divmod(self.puzzle[i] - 1, 3) current_x, current_y = divmod(i, 3) distance += abs(target_x - current_x) + abs(target_y - current_y) return distance def get_blank_position(self): """获取空格位置""" return self.puzzle.index(0) def generate_children(self): """生成子节点""" blank_pos = self.get_blank_position() children = [] moves = [ (-1, "U"), (1, "D"), # 上下移动 (-3, "L"), (3, "R") # 左右移动 ] for move, direction in moves: new_pos = blank_pos + move if 0 <= new_pos < 9 and not ( (blank_pos % 3 == 0 and direction == "L") or (blank_pos % 3 == 2 and direction == "R") ): new_puzzle = list(self.puzzle) new_puzzle[blank_pos], new_puzzle[new_pos] = new_puzzle[new_pos], new_puzzle[blank_pos] child = PuzzleState(tuple(new_puzzle), self, direction) children.append(child) return children def __str__(self): return "\n".join([str(self.puzzle[i:i+3]) for i in range(0, 9, 3)]) + "\n" def a_star_search(initial_state, goal_state): """A*算法主函数""" open_list = [] closed_set = set() heapq.heappush(open_list, initial_state) while open_list: current_state = heapq.heappop(open_list) if current_state.puzzle == goal_state: moves = [] while current_state.parent: moves.append(current_state.move) current_state = current_state.parent return moves[::-1] # 返回反向操作序列 closed_set.add(current_state.puzzle) for child in current_state.generate_children(): if child.puzzle not in closed_set: heapq.heappush(open_list, child) return None # 测试代码 initial = (1, 2, 3, 4, 5, 6, 7, 8, 0) # 初始状态 goal = (1, 2, 3, 4, 5, 6, 7, 8, 0) # 目标状态 solution = a_star_search(PuzzleState(initial), goal) if solution: print("解决方案：", " -> ".join(solution)) else: print("无解") ``` 上述代码实现了A*算法解决8数码问题的核心逻辑[^4]。它通过定义`PuzzleState`类表示每个状态，并使用曼哈顿距离作为启发函数来评估状态的代价。最终通过优先队列实现最优路径搜索。 ### 注意事项 - 曼哈顿距离是常用的启发函数，能够显著提高搜索效率。 - 如果初始状态和目标状态不可达（逆序数奇偶性不同），则问题无解[^2]。