### 关于8数码问题的A*算法实现 #### 使用C语言实现 以下是基于C语言的8数码问题A*算法实现，其中定义了两个启发式函数`h1(n)`和`h2(n)`： ```c #include <stdio.h> #include <stdlib.h> #define SIZE 3 #define MAX_NODES 100000 typedef struct { int grid[SIZE][SIZE]; int g; int h; } Node; int goalGrid[SIZE][SIZE] = { {1, 2, 3}, {4, 5, 6}, {7, 8, 0} }; // 计算h1(n): 不匹配的数字数量 int calculateH1(Node node) { int count = 0; for (int i = 0; i < SIZE; ++i) { for (int j = 0; j < SIZE; ++j) { if (node.grid[i][j] != goalGrid[i][j] && node.grid[i][j] != 0) { count++; } } } return count; } // 计算h2(n): 曼哈顿距离之和 int calculateH2(Node node) { int distanceSum = 0; for (int i = 0; i < SIZE; ++i) { for (int j = 0; j < SIZE; ++j) { if (node.grid[i][j] != 0) { int value = node.grid[i][j]; int targetX = (value - 1) / SIZE; int targetY = (value - 1) % SIZE; distanceSum += abs(i - targetX) + abs(j - targetY); } } } return distanceSum; } void solveEightPuzzle() { // 初始化并调用A*算法逻辑... } ``` --- #### 使用Java实现 下面是基于Java的8数码问题A*算法实现，同样支持两种估计函数。 ```java public class EightPuzzleSolver { static final int SIZE = 3; static final int[][] GOAL_GRID = {{1, 2, 3}, {4, 5, 6}, {7, 8, 0}}; public static void main(String[] args) { // 初始化并运行A*算法... } // 计算h1(n): 不匹配的数字数量 private static int calculateH1(int[][] currentGrid) { int mismatchCount = 0; for (int i = 0; i < SIZE; i++) { for (int j = 0; j < SIZE; j++) { if (currentGrid[i][j] != GOAL_GRID[i][j] && currentGrid[i][j] != 0) { mismatchCount++; } } } return mismatchCount; } // 计算h2(n): 曼哈顿距离之和 private static int calculateH2(int[][] currentGrid) { int manhattanDistance = 0; for (int i = 0; i < SIZE; i++) { for (int j = 0; j < SIZE; j++) { if (currentGrid[i][j] != 0) { int value = currentGrid[i][j]; int targetRow = (value - 1) / SIZE; int targetCol = (value - 1) % SIZE; manhattanDistance += Math.abs(i - targetRow) + Math.abs(j - targetCol); } } } return manhattanDistance; } } ``` --- #### 使用Python实现 这是基于Python的8数码问题A*算法实现，提供了两种不同的估计函数。 ```python from heapq import heappop, heappush GOAL_STATE = [[1, 2, 3], [4, 5, 6], [7, 8, 0]] def heuristic_h1(state): """计算h1(n): 数字与目标状态不对应的数量""" mismatches = 0 for i in range(3): for j in range(3): if state[i][j] != GOAL_STATE[i][j] and state[i][j] != 0: mismatches += 1 return mismatches def heuristic_h2(state): """计算h2(n): 所有数字到正确位置的曼哈顿距离之和""" total_distance = 0 for i in range(3): for j in range(3): if state[i][j] != 0: value = state[i][j] target_i = (value - 1) // 3 target_j = (value - 1) % 3 total_distance += abs(i - target_i) + abs(j - target_j) return total_distance def a_star(start_state, heuristic_func): open_list = [] closed_set = set() initial_g = 0 initial_f = initial_g + heuristic_func(start_state) heappush(open_list, (initial_f, start_state)) while open_list: _, current_state = heappop(open_list) if current_state == GOAL_STATE: return True closed_set.add(tuple(map(tuple, current_state))) successors = generate_successors(current_state) for successor in successors: if tuple(map(tuple, successor)) not in closed_set: g_score = initial_g + 1 f_score = g_score + heuristic_func(successor) heappush(open_list, (f_score, successor)) return False def generate_successors(state): zero_pos = find_zero_position(state) row, col = zero_pos moves = [(row-1,col),(row+1,col),(row,col-1),(row,col+1)] valid_moves = [ (r,c) for r,c in moves if 0<=r<3 and 0<=c<3 ] successors = [] for move_r, move_c in valid_moves: new_state = [list(row) for row in state] new_state[row][col], new_state[move_r][move_c] = new_state[move_r][move_c], new_state[row][col] successors.append(new_state) return successors def find_zero_position(state): for i in range(3): for j in range(3): if state[i][j] == 0: return (i,j) ``` --- #### 总结 以上展示了如何通过三种编程语言（C、Java 和 Python）实现8数码问题的A*算法，并分别实现了两种不同的估计函数 `h1(n)` 和 `h2(n)`。每种方法都遵循相同的思路：利用开放列表存储待探索的状态，并依据评估函数 `f(n)=g(n)+h(n)` 进行排序[^1]。