5.0 KiB
A算法实现
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#define N 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));
for(int i=0;i<N;i++)
{
for(int j=0;j<N;j++)
{
newnode->puzzle[i][j]=puzzle[i][j];
}
}
newnode->parent=NULL;
newnode->f=0,newnode->g=0,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("%d ",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;
int new_x,new_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=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;
}
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) {
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=0;i<OPEN_SIZE;i++)
{
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]=OPEN[OPEN_SIZE];
CLOSED_SIZE++;
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;
int closed_index=-1;
for (int i = 0; i < CLOSED_SIZE; i++) {
if (isSamePuzzle(new_node->puzzle, CLOSED[i]->puzzle)) {
in_CLOSED = true;
closed_index = i;
break;
}
}
if (!in_OPEN && !in_CLOSED) {
new_node->f=fNew;
new_node->g=gNew;
new_node->h=hNew;
new_node->parent=current;
OPEN[OPEN_SIZE]=new_node;
OPEN_SIZE++;
}
else if (in_OPEN && fNew < OPEN[open_index]->f) {
OPEN[open_index]->f=fNew;
OPEN[open_index]->g=gNew;
OPEN[open_index]->h=hNew;
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] = {{2, 0, 3}, {1, 8, 4}, {7, 6, 5}};
//int target[N][N] = {{1, 2, 3}, {8, 0, 4}, {7, 6, 5}};
int start[N][N] = {{2, 8, 3}, {1, 6, 4}, {7, 0, 5}};
int target[N][N] = {{1, 2, 3}, {8, 0, 4}, {7, 6, 5}};
//int start[N][N] = {{2, 8, 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<6F><6E>\n");
}
return 0;
}