Asuanfashixian/README.md

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