文档介绍：A*算法实验报告
实验目的
熟悉和掌握启发式搜索的定义、估价函数和算法过程
学会利用A*算法求解N数码难题
理解求解流程和搜索顺序
实验原理
A*算法是一种有序搜索算法，其特点在于对估价函数的定义上。对于一般的 有序搜索，总是选[index].index;
while (index != 0)
{
(node_v[index]);
index = node_v[index].index;
}
for (int i = () - 1; i >= 0; i--)/输出每一步的 探索过程
cout << "Step " << () - i
<< endl << rstep_v[i] << endl;
}
void Swap(int& a, int& b)
{
int t;
t — a;
a — b;
b — t;
}
void Assign(Node& node, int index)
{
for (int i = 0; i < ROW; i++)
for (int j = 0; j < COL; j++)
[i][j] = node_v[index].digit[i][j];
} —
int GetMinNode() //找到最小的节点的位置 即最优节点
{
int dist = MAXNUM;
int loc; // the location of minimize node
for (int i = 0; i < (); i++)
{
if (node_v[i].dist == MAXNUM) continue;
else if ((node_v[i].dist + node_v[i].dep) < dist) { loc = i;
dist = node_v[i].dist + node_v[i].dep;
}
}
return loc;
}
bool isExpandable(Node& node)
{
for (int i = 0; i < (); i++) {
if (isEqual(i, )) return false;
}
return true;
}
int Distance(Node& node, int digit[][COL])
{
int distance = 0;
bool flag = false;
for(int i = 0; i < ROW; i++)
for (int j = 0; j < COL； j++)
for (int k = 0; k < ROW; k++) {
for (int l = 0; l < COL; l++) { if ([i][j] == digit[k][l]) { distance += abs(i - k) + abs(j - l); flag = true;
break;
}
else
flag = false;
}
if (flag) break;
}
return distance;
}
int MinDistance(int a, int b)
{ return (a < b ? a : b);
}
void ProcessNode(int index)
{
int x, y;
bool flag;
for (int i = 0; i < ROW; i++) {
for (int j = 0; j < COL; j++) {
if (node_v[index].digit[i][j] == 0)
{
x =i; y = j;
flag = true;
break;
}
else flag = false;
}
if(flag)
break；
}
Node node_up;
Assign(node_up, index)；// 向上扩展的节点
int dist_up = MAXDISTANCE；
if (x > 0)
{
Swap([x][y], [x - 1][y]);
if (isExpandable(node_up))
{
dist_up = Distance(node_up, );
= index;
= dist_up;
= node