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; }