八数码问题a*算法c语言

八数码问题是一种经典的搜索问题，可以使用A*算法进行求解。A*算法是一种启发式搜索算法，能够在搜索过程中有针对性地搜索最优解，减小搜索空间，提高搜索效率。

以下是使用C语言实现八数码问题A*算法的示例代码：

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

#define N 3

// 定义状态结构体
typedef struct state {
    int board[N][N];  // 棋盘状态
    int f;  // f = g + h，g为从起始状态到当前状态的代价，h为从当前状态到目标状态的估价函数值
    int g;  // g为从起始状态到当前状态的代价
    int h;  // h为从当前状态到目标状态的估价函数值
    int x;  // 空格所在行
    int y;  // 空格所在列
    struct state *parent;  // 父状态指针
} state_t;

// 定义状态队列节点结构体
typedef struct node {
    state_t *data;  // 队列节点数据为状态指针
    int priority;  // 节点优先级，即状态f值
    struct node *next;  // 指向下一个节点的指针
} node_t;

// 定义状态队列结构体
typedef struct queue {
    node_t *front;  // 队列头指针
    node_t *rear;  // 队列尾指针
} queue_t;

// 初始化状态队列
void init_queue(queue_t *q) {
    q->front = q->rear = NULL;
}

// 判断状态队列是否为空
int is_empty(queue_t *q) {
    return q->front == NULL;
}

// 向状态队列添加状态
void enqueue(queue_t *q, state_t *s) {
    node_t *new_node = (node_t *)malloc(sizeof(node_t));
    new_node->data = s;
    new_node->priority = s->f;
    new_node->next = NULL;
    if (q->rear == NULL) {
        q->front = q->rear = new_node;
    } else {
        node_t *p = q->front;
        node_t *prev = NULL;
        while (p != NULL && p->priority <= new_node->priority) {
            prev = p;
            p = p->next;
        }
        if (prev == NULL) {
            new_node->next = q->front;
            q->front = new_node;
        } else if (p == NULL) {
            q->rear->next = new_node;
            q->rear = new_node;
        } else {
            new_node->next = prev->next;
            prev->next = new_node;
        }
    }
}

// 从状态队列中取出状态
state_t *dequeue(queue_t *q) {
    if (q->front == NULL) {
        return NULL;
    } else {
        node_t *p = q->front;
        state_t *s = p->data;
        q->front = q->front->next;
        if (q->front == NULL) {
            q->rear = NULL;
        }
        free(p);
        return s;
    }
}

// 判断状态是否为目标状态
int is_goal(state_t *s) {
    int i, j, num = 1;
    for (i = 0; i < N; i++) {
        for (j = 0; j < N; j++) {
            if (s->board[i][j] != num && !(i == N - 1 && j == N - 1 && s->board[i][j] == 0)) {
                return 0;
            }
            num++;
        }
    }
    return 1;
}

// 计算状态的估价函数值
int heuristic(state_t *s) {
    int i, j, k, l, num, dist = 0;
    for (i = 0; i < N; i++) {
        for (j = 0; j < N; j++) {
            num = s->board[i][j];
            if (num == 0) {
                continue;
            }
            k = (num - 1) / N;
            l = (num - 1) % N;
            dist += abs(i - k) + abs(j - l);
        }
    }
    return dist;
}

// 复制状态
state_t *copy_state(state_t *s) {
    state_t *new_state = (state_t *)malloc(sizeof(state_t));
    memcpy(new_state->board, s->board, sizeof(s->board));
    new_state->f = s->f;
    new_state->g = s->g;
    new_state->h = s->h;
    new_state->x = s->x;
    new_state->y = s->y;
    new_state->parent = s->parent;
    return new_state;
}

// 生成子状态
void generate_successors(state_t *s, queue_t *q) {
    int i, j, tx, ty;
    state_t *new_state;
    for (i = -1; i <= 1; i++) {
        for (j = -1; j <= 1; j++) {
            if (i == 0 && j == 0) {
                continue;
            }
            tx = s->x + i;
            ty = s->y + j;
            if (tx < 0 || tx >= N || ty < 0 || ty >= N) {
                continue;
            }
            new_state = copy_state(s);
            new_state->board[s->x][s->y] = s->board[tx][ty];
            new_state->board[tx][ty] = 0;
            new_state->x = tx;
            new_state->y = ty;
            new_state->g++;
            new_state->h = heuristic(new_state);
            new_state->f = new_state->g + new_state->h;
            new_state->parent = s;
            enqueue(q, new_state);
        }
    }
}

// 输出状态
void print_state(state_t *s) {
    int i, j;
    printf("f=%d, g=%d, h=%d\n", s->f, s->g, s->h);
    for (i = 0; i < N; i++) {
        for (j = 0; j < N; j++) {
            printf("%d ", s->board[i][j]);
        }
        printf("\n");
    }
}

// 输出解路径
void print_solution(state_t *s) {
    if (s->parent != NULL) {
        print_solution(s->parent);
    }
    print_state(s);
}

// 释放状态队列节点内存
void free_queue_node(node_t *p) {
    if (p != NULL) {
        free_queue_node(p->next);
        free(p->data);
        free(p);
    }
}

// 释放状态队列内存
void free_queue(queue_t *q) {
    free_queue_node(q->front);
}

// A*算法求解八数码问题
void solve(state_t *start) {
    queue_t open;
    state_t *s, *goal = NULL;
    init_queue(&open);
    start->g = 0;
    start->h = heuristic(start);
    start->f = start->g + start->h;
    start->parent = NULL;
    enqueue(&open, start);
    while (!is_empty(&open)) {
        s = dequeue(&open);
        if (is_goal(s)) {
            goal = s;
            break;
        }
        generate_successors(s, &open);
    }
    if (goal != NULL) {
        printf("Solution found:\n");
        print_solution(goal);
    } else {
        printf("No solution.\n");
    }
    free_queue(&open);
}

int main() {
    state_t start = {
        {{1, 2, 3}, {4, 0, 5}, {6, 7, 8}},
        0, 0, 0, 1, 1, NULL
    };
    solve(&start);
    return 0;
}

以上代码实现了八数码问题A*算法的求解，代码中使用了状态队列优化搜索效率。在代码中，我们需要定义状态结构体，其中包含了当前棋盘状态、从起始状态到当前状态的代价g、从当前状态到目标状态的估价函数值h、状态f值、空格所在位置以及父状态指针。我们还需要定义状态队列节点结构体和状态队列结构体，以实现状态队列的操作。代码中使用了启发式函数h(n) = 曼哈顿距离来计算状态的估价函数值。

在main函数中，我们定义了起始状态，并调用solve函数求解八数码问题。在solve函数中，我们首先初始化状态队列，并将起始状态加入队列。然后循环取出队列头部的状态，如果该状态为目标状态，则搜索结束；否则，生成该状态的所有子状态，并将其加入状态队列中。最后，输出解路径或提示无解，并释放状态队列内存。

注意，上述代码仅为示例代码，可能存在不足之处，请以实际应用为准。