Astar

#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)); //请实现该函数 int i,j; for(i=0;i<3;i++) { for(j=0;j<3;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]) { //相同则返回true,否则返回false int i,j,count=0; for(i=0;i<3;i++) { for(j=0;j<3;j++) { if(a[i][j]==b[i][j]) { count++; } } } if(count==9) { return true; } else { return false; }

}

// 打印拼图状态 void printPuzzle(int puzzle[N][N]) { //双重for循环实现拼图的打印 int i,j; for(i=0;i<3;i++) { for(j=0;j<3;j++) { printf("%d ",puzzle[i][j]); if((j==2)&&(i!=2)) { printf("\n"); } } }

printf("\n");

}

// 启发函数，计算当前状态到目标状态的估计代价 int heuristic(Node* current, Node* goal) { int h = 0; // 计算不匹配的拼图块数量 int i,j; for(i=0;i<3;i++) { for(j=0;j<3;j++) { if(current->puzzle[i][j]!=goal->puzzle[i][j]) { h++; } } } return h; }

// 移动操作，生成新的拼图状态 Node* move(Node* current, int dir) { int key_x, key_y,new_x,new_y;//记录空白块的位置 // 找到空白块的位置 int i,j; for(i=0;i<3;i++) { for(j=0;j<3;j++) { if(current->puzzle[i][j]==0) { key_x=i; key_y=j; } } } //给new_x、new_y赋值 new_x=key_x; new_y=key_x; // 根据移动方向更新新块的位置，上下左右移动 switch(dir) { case 0:new_y=new_y-1;break; case 1:new_y=new_y+1;break; case 2:new_x=new_x-1;break; case 3:new_x=new_x+1;break; } // 检查新位置是否在边界内 if((new_x<0)||(new_x>2)||(new_y<0)||(new_y>2)) { 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;  // 开放列表的大小设置为1
CLOSED_SIZE = 0;  // 关闭列表的大小设置为0

while (OPEN_SIZE > 0) {//对open列表进行操作
    int min_f = OPEN[0]->f;//初始化最小的f
    int min_index = 0;
    // 查找开放列表中具有最小f值的节点
	int i,j;
	for(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];  // 获取具有最小f值的节点

    // 如果当前节点与目标状态匹配，表示找到解
	if (isSamePuzzle(current->puzzle, goal->puzzle)) return current;

    //开放列表的大小减1，表示从开放列表中移除了一个节点
    OPEN_SIZE--;

    //将最小 f 值的节点移到开放列表的末尾，以便稍后将其添加到关闭列表中。
    //这是为了优化开放列表的结构。
    Node* temp = OPEN[min_index];
    OPEN[min_index] = OPEN[OPEN_SIZE];
    OPEN[OPEN_SIZE] = temp;

    //将当前节点添加到关闭列表，关闭列表大小加1
	CLOSED[CLOSED_SIZE++] = current;

    int key = 0;
    // 查找当前节点中空白块的位置
    for (i = 0; i < N; i++) {
        for ( j = 0; j < N; j++) {
            if (current->puzzle[i][j] == 0) {
                key = i * N + j;
                break;
            }
        }
    }
		int dir;
    // 尝试四个方向的移动操作
    for (dir = 0; dir < 4; dir++) {
        Node* new_node = move(current, dir);

        if (new_node != NULL && !isSamePuzzle(new_node->puzzle, current->puzzle)) {
            //得到对应的g、f、h值
            int gNew = current->g + 1;
            int hNew = heuristic(new_node, goal);
            int fNew = gNew + hNew;

            bool in_OPEN = false;
            int open_index = -1;
            // 检查新节点是否在开放列表中
            for (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 ( i = 0; i < CLOSED_SIZE; i++) {
                if (isSamePuzzle(new_node->puzzle, CLOSED[i]->puzzle)) {
                    in_CLOSED = true;
                    break;
                }
            }

            //若该节点机不在开放列表中也不在关闭列表中
            if (!in_OPEN && !in_CLOSED) {
                //把gNew、hNew、fNew赋给new_nod对应的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;
            } 
            //如果新节点已经在开放列表中，但新的 f 值更小，将更新开放列表中已存在节点的信息。
            else if (in_OPEN && fNew < OPEN[open_index]->f) {
				OPEN[open_index] = new_node;
            }
        }
    }
}

return NULL;  // 无解

}

// 打印解路径 void printPath(Node* final) { if (final == NULL) { return; } int i,j; printPath(final->parent); // 递归打印路径 for ( i = 0; i < N; i++) { if (i%3==0){ printf("-------\n"); } for ( 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！\n");
}

return 0;

}