本项目通过编程实现A*搜索算法来高效求解经典的8数码难题。采用启发式评估函数优化路径选择，展示A*算法在状态空间搜索中的强大能力。
```cpp
#include
using namespace std;
struct node {
int nodesun[4][4];
int pre; // 上一步在队列中的位置
int flag ; // 步数标识，表示当前的步数为有效的
int value; // 与目标的差距
int x,y; // 空格坐标
};
node queue[1000];
int zx[4] = {-1, 0, 1, 0};
int zy[4] = {0,-1, 0, 1};
// 当前步数
int top;
int desti[4][4];
// 检查是否找到目标
int detect(struct node *p) {
for(int i=1; i<4; ++i)
for(int j=1; j<4; ++j)
if(p->nodesun[i][j] != desti[i][j])
return 0;
return 1;
}
// 打印路径
void printlj() {
int tempt = top, i, j;
while(tempt != 0) {
for(i=1; i<4; ++i)
for(j=1; j<4; ++j)
cout << queue[tempt].nodesun[i][j];
if (j == 3)
cout<< <nodesun[i][j] != desti[i][j])
count++;
return count;
}
int main() {
// 初始化
int temp, find = 0;
top = 1;
cout << 请输入初始状态的值（一行4个数字，共3行） << endl;
for(int i=1; i<4; ++i)
for(int j=1; j<4; ++j) {
cin >> temp;
queue[1].nodesun[i][j] = temp;
}
cout << 请输入初始状态的空格的位置（行和列） << endl;
cin>>temp;
queue[1].x=temp;
cin>>temp;
queue[1].y=temp;
queue[1].value=VALUE(&queue[1]);
// 目标状态
cout<< 请输入目标状态的值（一行4个数字，共3行） << endl;
for(int i = 1 ;i < 4;i++)
for(int j = 1;j<4;j++) {
cin >> temp;
desti[i][j] = temp;
}
// 根据估价函数进行搜索
while(!find && top > 0) {
int min=999, minnumber;
for (int i = 1; i <= top; ++i)
if(queue[i].value < min && queue[i].flag == 0){
min = queue[i].value;
minnumber=i;
}
// 标记此节点有效
queue[minnumber].flag=1;
for(int f = 0 ;f<4; ++f) {
int m = queue[minnumber].x, n = queue[minnumber].y, i=m+zx[f], j=n+zy[f];
if(i>=1 && i<=3 && j>=1 && j<=3){
top++;
// 交换位置
node ¤tNode = queue[top];
currentNode.nodesun[m][n] = queue[minnumber].nodesun[i][j];
currentNode.nodesun[i][j]=0;
// 更新空格的位置和标志位
currentNode.x=i;
currentNode.y=j;
// 计算当前状态与目标的差距，并设置上一步位置
currentNode.value=VALUE(¤tNode);
currentNode.flag = 0;
if(detect(&queue[top])){
printlj();
find=1;
break;
}
}
}
}
return 0;
}
```
5星
