启发式搜索 八数码问题.docx

启发式搜索
介绍
八数码问题也称为九宫问题。在3X3的棋盘，摆有八个棋子，每个棋子上标有1至8 的某一数字，不同棋子上标的数字不相同。棋盘上还有一个空格(以数字0来表示)， 与空格相邻的棋子可以移到空格中。
要求解决的问题是：给出一个;
}
〃计算启发值的函数
int calvalue(int a[]) 〃不在位棋子数
{
int c = 0;
for (int i = 0;i <= 8;i++)
if (a[i] != goal[i])
if (goal[i] != 0)
c++;
return c;
}
〃生成一个新节点的函数
NodeLink *newnode(NodeLink *TEM, int depth, int flag)
{
NodeLink *temp = new NodeLink;
for (int i = 0;i <= 8;i++)
temp->[i] = TEM->[i];
switch (flag)
{
case 1:
{
temp->[0]--;
temp->[sgoal[temp->[0]]]++; 〃向左移
break;
}
case 2:
{
temp->[0]++;
temp->[sgoal[temp->[0]]]--; //向右移
break;
}
case 3:
{
temp->[0] -= 3;
temp->[sgoal[temp->[0]]] += 3; 〃向上移
break;
}
case 4:
{
temp->[0] += 3;
temp->[sgoal[temp->[0]]] -= 3; //向下移
break;
}
}
temp-> = depth + 1;
setboard(sgoal, temp->, 1);
temp-> = temp-> + calvalue(sgoal);
temp-> = flag;
temp->parent = TEM;
return temp;
}
//把新节点加入OPEN队列
NodeLink *addnode(NodeLink *head, NodeLink *node) 〃把 node 插入到 head 链中
{
NodeLink *TEM;
TEM = head;
head = node;
head->next = TEM;
head->previous = NULL;
if (TEM)
TEM->previous = head; //TEM 已为空，无需操作
return head;
}
90.
〃求启发值最小的结点
NodeLink *minf(NodeLink *head)
{
NodeLink *min, *forward;
min = head;
forward = head;
while (forward)
{
if (min->>forward->)
min = forward;
forward = forward->next;
}
return min;
}
105.
int main()
{
int depth = 0;
int source[9];
int i, j;
111.
NodeLink *OPEN = new NodeLink;
NodeLink *TEMP, *TEM;
114.
printf("请输入初始状态：\n");
for (i = 0;i<9;i++)
scanf_s("%d”, &source[i]);
118.
setboard(source, OPEN->, 0);
OPEN-> = depth;
OPEN-> = 0;
OPEN-> = depth + calvalue(source);
OPEN->next = NULL;
OPEN->previous = NULL;
OPEN->parent = NULL;
126