### 不同启发函数求解15数码问题的Python实现 15数码问题是经典的路径规划问题之一，通常可以通过A*算法或其他启发式搜索方法来解决。以下是基于不同启发函数（Heuristic Functions）的15数码问题的Python实现。 #### 启发函数的选择 常用的启发函数包括曼哈顿距离（Manhattan Distance）、欧几里得距离（Euclidean Distance），以及线性冲突修正后的曼哈顿距离等[^1]。这些启发函数可以帮助评估当前状态到目标状态的距离。 #### A*算法框架 A*算法是一种结合了最佳优先搜索和Dijkstra算法特点的启发式搜索算法。它通过估计代价 \(f(n) = g(n) + h(n)\)，其中\(g(n)\)是从起始节点到达当前节点的实际代价，\(h(n)\)是启发函数估算的从当前节点到目标节点的代价。 #### Python 实现 下面是一个使用多种启发函数的15数码问题的A*算法实现： ```python import heapq from copy import deepcopy class PuzzleNode: def __init__(self, board, parent=None, move=""): self.board = board self.parent = parent self.move = move if parent: self.g = parent.g + 1 else: self.g = 0 def get_f(self, heuristic_func): return self.g + heuristic_func(self.board) def manhattan_distance(board): size = int(len(board) ** 0.5) distance = 0 for i in range(size * size): value = board[i] if value != 0: target_row = (value - 1) // size target_col = (value - 1) % size current_row = i // size current_col = i % size distance += abs(target_row - current_row) + abs(target_col - current_col) return distance def euclidean_distance(board): size = int(len(board) ** 0.5) distance = 0 for i in range(size * size): value = board[i] if value != 0: target_row = (value - 1) // size target_col = (value - 1) % size current_row = i // size current_col = i % size distance += ((target_row - current_row)**2 + (target_col - current_col)**2)**0.5 return distance def linear_conflict(board): size = int(len(board) ** 0.5) conflicts = 0 for row in range(size): start_index = row * size end_index = start_index + size row_tiles = board[start_index:end_index] for tile_a in row_tiles: if tile_a == 0: continue target_row_a = (tile_a - 1) // size if target_row_a != row: continue for tile_b in row_tiles: if tile_b == 0 or tile_b == tile_a: continue target_row_b = (tile_b - 1) // size if target_row_b != row: continue col_a = (tile_a - 1) % size col_b = (tile_b - 1) % size pos_a = row_tiles.index(tile_a) pos_b = row_tiles.index(tile_b) if pos_a < pos_b and col_a > col_b: conflicts += 1 return manhattan_distance(board) + 2 * conflicts def find_zero_position(board): return board.index(0) def generate_moves(node): moves = [] zero_pos = find_zero_position(node.board) size = int(len(node.board) ** 0.5) # Up if zero_pos >= size: new_board = node.board[:] new_board[zero_pos], new_board[zero_pos - size] = new_board[zero_pos - size], new_board[zero_pos] moves.append(PuzzleNode(new_board, node, "Up")) # Down if zero_pos < len(node.board) - size: new_board = node.board[:] new_board[zero_pos], new_board[zero_pos + size] = new_board[zero_pos + size], new_board[zero_pos] moves.append(PuzzleNode(new_board, node, "Down")) # Left if zero_pos % size != 0: new_board = node.board[:] new_board[zero_pos], new_board[zero_pos - 1] = new_board[zero_pos - 1], new_board[zero_pos] moves.append(PuzzleNode(new_board, node, "Left")) # Right if zero_pos % size != size - 1: new_board = node.board[:] new_board[zero_pos], new_board[zero_pos + 1] = new_board[zero_pos + 1], new_board[zero_pos] moves.append(PuzzleNode(new_board, node, "Right")) return moves def solve_puzzle(initial_board, goal_board, heuristic_func=manhattan_distance): open_list = [] closed_set = set() initial_node = PuzzleNode(initial_board) heapq.heappush(open_list, (initial_node.get_f(heuristic_func), initial_node)) while open_list: _, current_node = heapq.heappop(open_list) if tuple(current_node.board) in closed_set: continue if current_node.board == goal_board: path = [] while current_node.parent: path.insert(0, current_node.move) current_node = current_node.parent return path closed_set.add(tuple(current_node.board)) neighbors = generate_moves(current_node) for neighbor in neighbors: if tuple(neighbor.board) not in closed_set: heapq.heappush(open_list, (neighbor.get_f(heuristic_func), neighbor)) return None # Example Usage initial_board = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0] goal_board = list(range(1, 16)) + [0] solution_manhattan = solve_puzzle(initial_board, goal_board, manhattan_distance) print(f"Solution using Manhattan Distance: {solution_manhattan}") solution_euclidean = solve_puzzle(initial_board, goal_board, euclidean_distance) print(f"Solution using Euclidean Distance: {solution_euclidean}") solution_linear_conflict = solve_puzzle(initial_board, goal_board, linear_conflict) print(f"Solution using Linear Conflict Heuristic: {solution_linear_conflict}") ``` #### 解释 - `PuzzleNode` 类表示每一个拼图的状态。 - 提供了三种启发函数：曼哈顿距离、欧几里得距离和带线性冲突修正的曼哈顿距离。 - `solve_puzzle` 函数实现了A*算法的核心逻辑。 ---