用C语言实现骑士寻游问题(用A*算法)

骑士寻游问题是一个经典的搜索问题，可以通过A*算法来解决。下面是用C语言实现骑士寻游问题的示例代码：

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

#define N 8

typedef struct {
    int x;
    int y;
} Point;

Point goal = {7, 7}; // 目标点

int h(Point p) {
    // 计算启发式函数值
    return abs(p.x - goal.x) + abs(p.y - goal.y);
}

bool valid(Point p) {
    // 判断当前点是否越界
    return p.x >= 0 && p.y >= 0 && p.x < N && p.y < N;
}

int a_star(Point start) {
    // 初始化起点
    start.g = 0;
    start.f = h(start);

    Point open_set[N * N];
    Point closed_set[N * N];
    int open_set_count = 1;
    int closed_set_count = 0;
    open_set[0] = start;

    while (open_set_count > 0) {
        // 从open集合中选取f值最小的点
        int min_index = 0;
        for (int i = 1; i < open_set_count; i++) {
            if (open_set[i].f < open_set[min_index].f) {
                min_index = i;
            }
        }

        Point current = open_set[min_index];

        if (current.x == goal.x && current.y == goal.y) {
            // 找到了目标点
            return current.g;
        }

        // 将当前点从open集合中移除
        for (int i = min_index; i < open_set_count - 1; i++) {
            open_set[i] = open_set[i + 1];
        }
        open_set_count--;

        // 将当前点添加到closed集合中
        closed_set[closed_set_count++] = current;

        // 遍历当前点的所有邻居
        int dx[] = {-2, -1, 1, 2, 2, 1, -1, -2};
        int dy[] = {1, 2, 2, 1, -1, -2, -2, -1};
        for (int i = 0; i < 8; i++) {
            Point neighbor = {current.x + dx[i], current.y + dy[i]};
            if (!valid(neighbor)) {
                continue;
            }

            // 计算邻居的g值和f值
            int g = current.g + 1;
            int f = g + h(neighbor);

            // 如果邻居已经在closed集合中，跳过
            bool is_closed = false;
            for (int j = 0; j < closed_set_count; j++) {
                if (closed_set[j].x == neighbor.x && closed_set[j].y == neighbor.y) {
                    is_closed = true;
                    break;
                }
            }
            if (is_closed) {
                continue;
            }

            // 如果邻居不在open集合中，添加到open集合中
            bool is_open = false;
            int open_index = -1;
            for (int j = 0; j < open_set_count; j++) {
                if (open_set[j].x == neighbor.x && open_set[j].y == neighbor.y) {
                    is_open = true;
                    open_index = j;
                    break;
                }
            }
            if (!is_open) {
                neighbor.g = g;
                neighbor.f = f;
                open_set[open_set_count++] = neighbor;
            } else if (g < open_set[open_index].g) {
                // 如果邻居已经在open集合中，更新其g值和f值
                open_set[open_index].g = g;
                open_set[open_index].f = f;
            }
        }
    }

    // 没有找到解
    return -1;
}

int main() {
    Point start = {0, 0};
    int steps = a_star(start);
    printf("步数：%d\n", steps);

    return 0;
}

在上述代码中，`Point`结构体表示一个点的坐标，其中`x`和`y`分别表示横坐标和纵坐标，`g`表示从起点到该点的实际代价，`f`表示启发式函数的值。

`valid`函数用于判断一个点是否越界，`h`函数用于计算启发式函数的值。`a_star`函数实现了A*算法，其中`open_set`和`closed_set`分别表示开放集合和关闭集合，`open_set_count`和`closed_set_count`分别表示开放集合和关闭集合中元素的个数。在算法中，需要遍历当前点的所有邻居，计算其g值和f值，并根据是否在开放集合或关闭集合中进行处理。

在`main`函数中，我们设定起点为$(0, 0)$，并调用`a_star`函数来求解最短路径的步数。