c语言 启发式搜索 解决八数码问题

启发式搜索是一种常用于解决八数码问题的算法。八数码问题是指在一个3x3的棋盘上，摆放了1-8的数字和一个空格，要求通过交换数字和空格的位置，最终将棋盘恢复为如下状态：

1 2 3
4 5 6
7 8

以下是使用C语言实现八数码问题的启发式搜索的基本步骤：

1. 定义状态结构体，包含当前状态的数组、空格位置、当前状态的代价和深度等信息。

2. 定义启发式函数，用于评估当前状态的优劣程度。启发式函数可以使用曼哈顿距离或者不在位数等方式进行计算。

3. 定义状态扩展函数，用于生成当前状态的所有可能的下一步状态。

4. 定义搜索函数，使用优先队列来存储待扩展的状态，每次取出代价最小的状态进行扩展，直到找到目标状态。

5. 在搜索过程中，需要记录每个状态的深度和父状态，以便在找到目标状态后回溯路径。

下面是一个简单的C语言实现八数码问题的启发式搜索的代码示例：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N 3

typedef struct {
    int board[N][N]; // 当前状态的数组
    int x, y; // 空格位置
    int cost; // 当前状态的代价
    int depth; // 当前状态的深度
    int parent; // 父状态的下标
} State;

int goal[N][N] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 0}}; // 目标状态
int dx[4] = {0, 1, 0, -1}; // 上下左右四个方向
int dy[4] = {-1, 0, 1, 0};

int manhattan(State s) { // 曼哈顿距离启发式函数
    int sum = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (s.board[i][j] != 0) {
                int x = (s.board[i][j] - 1) / N;
                int y = (s.board[i][j] - 1) % N;
                sum += abs(x - i) + abs(y - j);
            }
        }
    }
    return sum;
}

int misplaced(State s) { // 不在位数启发式函数
    int sum = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (s.board[i][j] != goal[i][j]) {
                sum++;
            }
        }
    }
    return sum;
}

int is_goal(State s) { // 判断是否为目标状态
    return memcmp(s.board, goal, sizeof(goal)) == 0;
}

void print_board(State s) { // 打印当前状态的数组
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            printf("%d ", s.board[i][j]);
        }
        printf("\n");
    }
}

void print_path(State *states, int n) { // 打印路径
    if (n == -1) {
        return;
    }
    print_path(states, states[n].parent);
    printf("Step %d:\n", states[n].depth);
    print_board(states[n]);
    printf("\n");
}

void search(State initial_state, int (*heuristic)(State)) { // 启发式搜索函数
    State states[362880]; // 最多有9!个状态
    int visited[362880] = {0}; // 标记是否访问过
    int front = 0, rear = 0; // 队列的头和尾
    initial_state.cost = heuristic(initial_state);
    initial_state.depth = 0;
    initial_state.parent = -1;
    states[rear++] = initial_state;
    visited[initial_state.cost] = 1;
    while (front < rear) {
        State s = states[front++];
        if (is_goal(s)) { // 找到目标状态
            printf("Found goal state!\n");
            print_path(states, front - 1);
            return;
        }
        for (int i = 0; i < 4; i++) { // 扩展当前状态
            int nx = s.x + dx[i];
            int ny = s.y + dy[i];
            if (nx < 0 || nx >= N || ny < 0 || ny >= N) {
                continue;
            }
            State t = s;
            t.board[s.x][s.y] = t.board[nx][ny];
            t.board[nx][ny] = 0;
            t.x = nx;
            t.y = ny;
            t.cost = heuristic(t);
            t.depth = s.depth + 1;
            t.parent = front - 1;
            if (!visited[t.cost]) { // 新状态
                states[rear++] = t;
                visited[t.cost] = 1;
            }
        }
    }
    printf("Failed to find goal state!\n");
}

int main() {
    State initial_state = {
        {{2, 8, 3}, {1, 6, 4}, {7, 0, 5}}, // 初始状态
        1, 2, 0, 0, -1 // 空格位置为(1, 2)，代价为0，深度为0，父状态为-1
    };
    search(initial_state, manhattan); // 使用曼哈顿距离启发式函数进行搜索
    return 0;
}