### 使用Python实现基于A*算法的八数码问题 以下是使用Python编写的基于A*算法解决八数码问题的代码示例。该程序通过定义状态空间、启发函数以及路径搜索来找到最优解。 #### 启发式搜索的核心概念 A*算法是一种启发式搜索算法，其核心在于利用估价函数 \( f(n) = g(n) + h(n) \)，其中： - \( g(n) \) 表示从初始节点到当前节点的实际代价。 - \( h(n) \) 是一个估计值，表示从当前节点到达目标节点的最佳路径的代价[^1]。 对于八数码问题，通常采用曼哈顿距离作为\( h(n) \) 的计算方式。 --- ```python import heapq class PuzzleState: def __init__(self, board, parent=None, move=""): self.board = tuple(board) # Board as immutable tuple for hashing self.parent = parent # Parent state reference self.move = move # Move description from parent to this state self.g_cost = 0 # Cost from start node to current node if parent: self.g_cost = parent.g_cost + 1 def get_f_cost(self): """Calculate total cost f(n) = g(n) + h(n).""" return self.g_cost + self.heuristic() def heuristic(self): """Manhattan distance heuristic.""" goal_positions = {1: (0, 0), 2: (0, 1), 3: (0, 2), 4: (1, 0), 5: (1, 1), 6: (1, 2), 7: (2, 0), 8: (2, 1)} manhattan_distance = 0 for i, value in enumerate(self.board): if value != 0: # Ignore empty space target_x, target_y = goal_positions[value] current_x, current_y = divmod(i, 3) manhattan_distance += abs(target_x - current_x) + abs(target_y - current_y) return manhattan_distance def find_zero_index(self): """Find index of zero (empty space).""" return self.board.index(0) def generate_neighbors(self): """Generate all valid neighboring states.""" neighbors = [] zero_idx = self.find_zero_index() possible_moves = { 0: [1, 3], 1: [0, 2, 4], 2: [1, 5], 3: [0, 4, 6], 4: [1, 3, 5, 7], 5: [2, 4, 8], 6: [3, 7], 7: [4, 6, 8], 8: [5, 7] } for swap_idx in possible_moves[zero_idx]: new_board = list(self.board) new_board[zero_idx], new_board[swap_idx] = new_board[swap_idx], new_board[zero_idx] direction = "" if swap_idx == zero_idx + 1: direction = "Right" elif swap_idx == zero_idx - 1: direction = "Left" elif swap_idx == zero_idx + 3: direction = "Down" elif swap_idx == zero_idx - 3: direction = "Up" neighbor_state = PuzzleState(new_board, parent=self, move=direction) neighbors.append(neighbor_state) return neighbors def a_star_search(initial_state, goal_state=(1, 2, 3, 4, 5, 6, 7, 8, 0)): open_set = [] # Priority queue for frontier nodes closed_set = set() # Set of visited nodes initial_node = PuzzleState(list(initial_state)) heapq.heappush(open_set, (initial_node.get_f_cost(), id(initial_node), initial_node)) # Use unique ID to avoid comparison issues while open_set: _, _, current_node = heapq.heappop(open_set) if current_node.board == goal_state: path = [] while current_node.parent: path.insert(0, current_node.move) current_node = current_node.parent return path closed_set.add(current_node.board) for neighbor in current_node.generate_neighbors(): if neighbor.board not in closed_set: heapq.heappush(open_set, (neighbor.get_f_cost(), id(neighbor), neighbor)) # Example usage if __name__ == "__main__": initial_configuration = [1, 2, 3, 4, 5, 6, 7, 0, 8] # Replace with your starting configuration solution_path = a_star_search(tuple(initial_configuration)) print(f"Solution Path ({len(solution_path)} steps): {' -> '.join(solution_path)}") ``` --- #### 关键点解析 1. **PuzzleState 类**: 定义了每个状态的关键属性及其操作方法，包括获取启发值、生成邻居状态等。 2. **曼哈顿距离**: 计算当前状态与目标状态之间的总移动步数，忽略障碍物的影响[^1]。 3. **优先队列**: 利用 `heapq` 实现最小堆结构，确保每次扩展的是具有最低 \( f(n) \) 值的状态。 4. **终止条件**: 当前状态等于目标状态时返回路径；如果无法达到，则可能无解[^3]。 ---