|
|
#include <stdio.h>
|
|
|
#include <stdlib.h>
|
|
|
#include <stdbool.h>
|
|
|
#include <string.h>
|
|
|
|
|
|
#define N 3 // 定义拼图的维度，这是一个3x3的拼图
|
|
|
|
|
|
typedef struct Node {
|
|
|
int puzzle[N][N]; // 存储拼图状态的数组
|
|
|
struct Node* parent; // 指向父节点的指针，用于追踪路径
|
|
|
int f, g, h; // A*算法中的 f, g, h 值
|
|
|
} Node;
|
|
|
|
|
|
// 创建新的拼图节点
|
|
|
Node* createNode(int puzzle[N][N]) {
|
|
|
Node* newnode = (Node*)malloc(sizeof(Node));
|
|
|
//请实现该函数
|
|
|
// 用 malloc 函数在内存中分配空间
|
|
|
|
|
|
|
|
|
// 将 puzzle 数组的值复制到新节点的 puzzle 数组中
|
|
|
for (int i = 0; i < N; i++) {
|
|
|
for (int j = 0; j < N; j++) {
|
|
|
newnode->puzzle[i][j] = puzzle[i][j];
|
|
|
}
|
|
|
}
|
|
|
|
|
|
// 初始化新节点的 parent 节点为 NULL
|
|
|
newnode->parent = NULL;
|
|
|
|
|
|
// 初始化新节点的 f, g, h 的值为 0
|
|
|
newnode->f = 0;
|
|
|
newnode->g = 0;
|
|
|
newnode->h = 0;
|
|
|
|
|
|
// 返回指向新节点的指针
|
|
|
return newnode;
|
|
|
|
|
|
|
|
|
}
|
|
|
|
|
|
// 检查两个拼图状态是否相同
|
|
|
bool isSamePuzzle(int a[N][N], int b[N][N]) {
|
|
|
//相同则返回true,否则返回false
|
|
|
for (int i = 0; i < N; i++) {
|
|
|
for (int j = 0; j < N; j++) {
|
|
|
// 如果有任何一个元素不相同，则返回 false
|
|
|
if (a[i][j] != b[i][j]) {
|
|
|
return false;
|
|
|
|
|
|
}
|
|
|
|
|
|
}
|
|
|
}
|
|
|
return true;
|
|
|
// 如果所有元素都相同，则返回 true
|
|
|
|
|
|
|
|
|
|
|
|
}
|
|
|
|
|
|
// 打印拼图状态
|
|
|
void printPuzzle(int puzzle[N][N]) {
|
|
|
//双重for循环实现拼图的打印
|
|
|
|
|
|
for (int i = 0; i < N; i++) {
|
|
|
for (int j = 0; j < N; j++) {
|
|
|
// 打印每个元素，并在元素间空一格
|
|
|
printf("%d ", puzzle[i][j]);
|
|
|
}
|
|
|
// 换行
|
|
|
printf("\n");
|
|
|
}
|
|
|
// 打印额外的换行，提高输出的可读性
|
|
|
printf("\n");
|
|
|
}
|
|
|
|
|
|
|
|
|
// 启发函数，计算当前状态到目标状态的估计代价
|
|
|
int heuristic(Node* current, Node* goal) {
|
|
|
int h = 0;
|
|
|
// 计算不匹配的拼图块数量
|
|
|
|
|
|
// 利用双重 for 循环计算遍历两节点的 puzzle 数组，若不匹配则 h 加 1
|
|
|
for (int i = 0; i < N; i++) {
|
|
|
for (int j = 0; j < N; j++) {
|
|
|
if (current->puzzle[i][j] != goal->puzzle[i][j]) {
|
|
|
h++;
|
|
|
}
|
|
|
}
|
|
|
}
|
|
|
|
|
|
// 返回 h 的值
|
|
|
return h;
|
|
|
|
|
|
}
|
|
|
|
|
|
// 移动操作，生成新的拼图状态
|
|
|
Node* move(Node* current, int dir) {
|
|
|
int key_x, key_y; // 记录空白块的位置
|
|
|
|
|
|
// 找到空白块的位置
|
|
|
for (int i = 0; i < N; i++) {
|
|
|
for (int j = 0; j < N; j++) {
|
|
|
if (current->puzzle[i][j] == 0) {
|
|
|
key_x = i;
|
|
|
key_y = j;
|
|
|
break;
|
|
|
}
|
|
|
}
|
|
|
}
|
|
|
|
|
|
// 给 new_x、new_y 赋值
|
|
|
int new_x = key_x;
|
|
|
int new_y = key_y;
|
|
|
|
|
|
// 根据移动方向更新新块的位置，上下左右移动
|
|
|
if (dir == 0) { // 上移
|
|
|
new_x--;
|
|
|
}
|
|
|
else if (dir == 1) { // 下移
|
|
|
new_x++;
|
|
|
}
|
|
|
else if (dir == 2) { // 左移
|
|
|
new_y--;
|
|
|
}
|
|
|
else if (dir == 3) { // 右移
|
|
|
new_y++;
|
|
|
}
|
|
|
|
|
|
// 检查新位置是否在边界内
|
|
|
if (new_x < 0 || new_x >= N || new_y < 0 || new_y >= N) {
|
|
|
return NULL; // 无效移动
|
|
|
}
|
|
|
|
|
|
// 创建新节点，复制当前拼图状态，并交换块的位置
|
|
|
Node* new_node = createNode(current->puzzle);
|
|
|
new_node->puzzle[key_x][key_y] = current->puzzle[new_x][new_y];
|
|
|
new_node->puzzle[new_x][new_y] = 0;
|
|
|
|
|
|
return new_node;
|
|
|
|
|
|
}
|
|
|
|
|
|
// A*算法，寻找最短路径
|
|
|
Node* AStar(Node* start, Node* goal) {
|
|
|
Node* OPEN[1000];
|
|
|
Node* CLOSED[1000];
|
|
|
int OPEN_SIZE = 0;
|
|
|
int CLOSED_SIZE = 0;
|
|
|
|
|
|
OPEN[0] = start;
|
|
|
OPEN_SIZE = 1;
|
|
|
CLOSED_SIZE = 0;
|
|
|
|
|
|
while (OPEN_SIZE > 0) {//对open列表进行操作
|
|
|
int min_f = OPEN[0]->f;//初始化最小的f
|
|
|
int min_index = 0;
|
|
|
|
|
|
// 查找开放列表中具有最小 f 值的节点
|
|
|
for (int i = 1; i < OPEN_SIZE; i++) {
|
|
|
if (OPEN[i]->f < min_f) {
|
|
|
min_f = OPEN[i]->f;
|
|
|
min_index = i;
|
|
|
}
|
|
|
}
|
|
|
|
|
|
Node* current = OPEN[min_index]; // 获取具有最小f值的节点
|
|
|
|
|
|
// 从开放列表中移除当前节点
|
|
|
OPEN[min_index] = OPEN[OPEN_SIZE - 1];
|
|
|
OPEN_SIZE--;
|
|
|
|
|
|
// 将当前节点添加到关闭列表，关闭列表大小加1
|
|
|
CLOSED[CLOSED_SIZE] = current;
|
|
|
CLOSED_SIZE++;
|
|
|
|
|
|
// 检查是否找到解
|
|
|
if (isSamePuzzle(current->puzzle, goal->puzzle)) {
|
|
|
// 找到解，返回当前节点
|
|
|
return current;
|
|
|
}
|
|
|
|
|
|
int key = 0;
|
|
|
|
|
|
for (int i = 0; i < N; i++) {
|
|
|
for (int j = 0; j < N; j++) {
|
|
|
if (current->puzzle[i][j] == 0) {
|
|
|
key = i * N + j;
|
|
|
break;
|
|
|
}
|
|
|
}
|
|
|
}
|
|
|
|
|
|
for (int dir = 0; dir < 4; dir++) {
|
|
|
Node* new_node = move(current, dir);
|
|
|
|
|
|
if (new_node != NULL && !isSamePuzzle(new_node->puzzle, current->puzzle)) {
|
|
|
int gNew = current->g + 1;
|
|
|
int hNew = heuristic(new_node, goal);
|
|
|
int fNew = gNew + hNew;
|
|
|
|
|
|
bool in_OPEN = false;
|
|
|
int open_index = -1;
|
|
|
|
|
|
// 检查新节点是否在开放列表中
|
|
|
for (int i = 0; i < OPEN_SIZE; i++) {
|
|
|
if (isSamePuzzle(new_node->puzzle, OPEN[i]->puzzle)) {
|
|
|
in_OPEN = true;
|
|
|
open_index = i;
|
|
|
break;
|
|
|
}
|
|
|
}
|
|
|
|
|
|
bool in_CLOSED = false;
|
|
|
|
|
|
// 检查新节点是否在关闭列表中
|
|
|
|
|
|
if (!in_OPEN && !in_CLOSED) {
|
|
|
// 新节点既不在开放列表中也不在关闭列表中
|
|
|
// 把gNew、hNew、fNew赋给new_node对应的g、h、f值，并将其父节点设置为当前节点。
|
|
|
|
|
|
new_node->g = gNew;
|
|
|
new_node->h = hNew;
|
|
|
new_node->f = fNew;
|
|
|
new_node->parent = current;
|
|
|
|
|
|
// 添加新节点new_node到开放列表，开放列表大小加1
|
|
|
OPEN[OPEN_SIZE] = new_node;
|
|
|
OPEN_SIZE++;
|
|
|
}
|
|
|
else if (in_OPEN && fNew < OPEN[open_index]->f) {
|
|
|
// 新节点已经在开放列表中，但新的 f 值更小
|
|
|
// 更新开放列表中已存在节点的信息
|
|
|
OPEN[open_index]->g = gNew;
|
|
|
OPEN[open_index]->h = hNew;
|
|
|
OPEN[open_index]->f = fNew;
|
|
|
OPEN[open_index]->parent = current;
|
|
|
}
|
|
|
}
|
|
|
}
|
|
|
}
|
|
|
|
|
|
return NULL; // 无解
|
|
|
}
|
|
|
|
|
|
// 打印解路径
|
|
|
void printPath(Node* final) {
|
|
|
if (final == NULL) {
|
|
|
return;
|
|
|
}
|
|
|
printPath(final->parent); // 递归打印路径
|
|
|
for (int i = 0; i < N; i++) {
|
|
|
if (i % 3 == 0) {
|
|
|
printf("-------\n");
|
|
|
}
|
|
|
for (int j = 0; j < N; j++) {
|
|
|
printf("%d ", final->puzzle[i][j]);
|
|
|
}
|
|
|
|
|
|
printf("\n");
|
|
|
|
|
|
}
|
|
|
}
|
|
|
|
|
|
int main() {
|
|
|
//int start[N][N] = {{1, 0, 3}, {0, 8, 4}, {7, 6, 5}};
|
|
|
// int target[N][N] = {{1, 2, 3}, {7, 0, 4}, {8, 6, 5}};
|
|
|
|
|
|
int start[N][N] = { {2, 0, 3}, {1, 5, 6}, {4, 7, 8} };
|
|
|
int target[N][N] = { {1, 2, 3}, {4, 5, 6}, {7, 8, 0} };
|
|
|
|
|
|
// int start[N][N] = { {2, , 3}, {1, 0, 4}, {7, 6, 5} };
|
|
|
// int target[N][N] = { {1, 2, 3}, {8, 0, 4}, {7, 6, 5} };
|
|
|
Node* init = createNode(start);
|
|
|
Node* goal = createNode(target);
|
|
|
|
|
|
Node* final = AStar(init, goal);
|
|
|
if (final) {
|
|
|
printf("This problem has a solution:\n");
|
|
|
printPath(final); // 打印解路径
|
|
|
}
|
|
|
else {
|
|
|
printf("This problem has no solution！\n");
|
|
|
}
|
|
|
|
|
|
return 0;
|
|
|
}
|
|
|
|
