|
|
#include <stdio.h>
|
|
|
#include <stdlib.h>
|
|
|
#include <stdbool.h>
|
|
|
#include <string.h>
|
|
|
|
|
|
#define N 3 // 拼图的维度为3
|
|
|
|
|
|
typedef struct Node {
|
|
|
int puzzle[N][N];
|
|
|
struct Node* parent;
|
|
|
int f, g, h;
|
|
|
} Node;
|
|
|
|
|
|
Node* createNode(int puzzle[N][N]) // 创建新的节点
|
|
|
{
|
|
|
Node* newnode = (Node*)malloc(sizeof(Node));
|
|
|
memcpy(newnode->puzzle, puzzle, sizeof(int) * N * N);
|
|
|
newnode->parent = NULL;
|
|
|
newnode->f = newnode->g = newnode->h = 0;
|
|
|
return newnode;
|
|
|
}
|
|
|
|
|
|
bool isSamePuzzle(int a[N][N], int b[N][N]) // 检查两个拼图状态是否相同
|
|
|
{
|
|
|
for (int i = 0; i < N; i++)
|
|
|
{
|
|
|
for (int j = 0; j < N; j++)
|
|
|
{
|
|
|
if (a[i][j] != b[i][j])
|
|
|
return false;
|
|
|
}
|
|
|
}
|
|
|
return true;
|
|
|
}
|
|
|
|
|
|
void printPuzzle(int puzzle[N][N]) // 输出拼图状态
|
|
|
{
|
|
|
for (int i = 0; i < N; i++)
|
|
|
{
|
|
|
for (int j = 0; j < N; j++)
|
|
|
{
|
|
|
printf("%-2d", puzzle[i][j]);
|
|
|
}
|
|
|
printf("\n");
|
|
|
}
|
|
|
printf("\n");
|
|
|
}
|
|
|
|
|
|
int heuristic(Node* current, Node* goal) // 估计当前状态到目标状态的代价
|
|
|
{
|
|
|
int h = 0;
|
|
|
for (int i = 0; i < N; i++)
|
|
|
{
|
|
|
for (int j = 0; j < N; j++)
|
|
|
{
|
|
|
if (current->puzzle[i][j] != goal->puzzle[i][j])
|
|
|
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;
|
|
|
}
|
|
|
}
|
|
|
}
|
|
|
int new_x = key_x, new_y = key_y;
|
|
|
switch (dir) // 根据移动方向移动新块的位置
|
|
|
{
|
|
|
case 0:
|
|
|
new_x--;
|
|
|
break;
|
|
|
case 1:
|
|
|
new_x++;
|
|
|
break;
|
|
|
case 2:
|
|
|
new_y--;
|
|
|
break;
|
|
|
case 3:
|
|
|
new_y++;
|
|
|
break;
|
|
|
default:
|
|
|
break;
|
|
|
}
|
|
|
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;
|
|
|
}
|
|
|
|
|
|
Node* AStar(Node* start, Node* goal) // A*算法
|
|
|
{
|
|
|
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)
|
|
|
{
|
|
|
int min_f = OPEN[0]->f;
|
|
|
int min_index = 0;
|
|
|
for (int i = 1; i < OPEN_SIZE; i++) // 查找开放列表中具有最小f值的节点
|
|
|
{
|
|
|
if (OPEN[i]->f < min_f)
|
|
|
{
|
|
|
min_f = OPEN[i]->f;
|
|
|
min_index = i;
|
|
|
}
|
|
|
}
|
|
|
Node* current = OPEN[min_index];
|
|
|
if (isSamePuzzle(current->puzzle, goal->puzzle))
|
|
|
{
|
|
|
return current;
|
|
|
}
|
|
|
OPEN_SIZE--;
|
|
|
Node* temp = OPEN[min_index];
|
|
|
OPEN[min_index] = OPEN[OPEN_SIZE];
|
|
|
OPEN[OPEN_SIZE] = temp;
|
|
|
CLOSED[CLOSED_SIZE++] = 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;
|
|
|
for (int i = 0; i < CLOSED_SIZE; i++) // 检查新节点是否在关闭列表中
|
|
|
{
|
|
|
if (isSamePuzzle(new_node->puzzle, CLOSED[i]->puzzle))
|
|
|
{
|
|
|
in_CLOSED = true;
|
|
|
break;
|
|
|
}
|
|
|
}
|
|
|
if (!in_OPEN && !in_CLOSED) // 如果新节点均不满足，则将其添加到开放列表
|
|
|
{
|
|
|
new_node->g = gNew;
|
|
|
new_node->h = hNew;
|
|
|
new_node->f = fNew;
|
|
|
new_node->parent = current;
|
|
|
|
|
|
OPEN[OPEN_SIZE++] = new_node;
|
|
|
}
|
|
|
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++)
|
|
|
{
|
|
|
for (int j = 0; j < N; j++)
|
|
|
{
|
|
|
printf("%-2d", final->puzzle[i][j]);
|
|
|
}
|
|
|
printf("\n");
|
|
|
}printf("------");
|
|
|
printf("\n");
|
|
|
}
|
|
|
|
|
|
int main()
|
|
|
{
|
|
|
int start_puzzle[N][N] = { {2, 8, 3}, {1, 6, 4}, {7, 0, 5} };
|
|
|
int goal_puzzle[N][N] = { {1, 2, 3}, {8, 0, 4}, {7, 6, 5} };
|
|
|
Node* start = createNode(start_puzzle);
|
|
|
Node* goal = createNode(goal_puzzle);
|
|
|
Node* final = AStar(start, goal);
|
|
|
if (final != NULL)
|
|
|
{
|
|
|
printf("Solution path:\n");
|
|
|
printPath(final);
|
|
|
}
|
|
|
else
|
|
|
{
|
|
|
printf("No solution found.\n");
|
|
|
}
|
|
|
return 0;
|
|
|
} |
