《人工智能》实验一题目
实验一 启发式搜索算法
1. 实验内容：
使用启发式搜索算法求解8数码问题。
⑴ 编制程序实现求解8数码问题
算法，采用估价函数
，
其中：
是搜索树中结点
的深度；
为结点的数据库中错放的棋子个数；
为结点的数据库中每个棋子与其目标位置之间的距离总和。
⑵ 分析上述⑴中两种估价函数求解8数码问题的效率差别，给出一个是的上界的
的定义，并测试使用该估价函数是否使算法失去可采纳性。
2. 实验目的
熟练掌握启发式搜索算法及其可采纳性。
3.数据结构与算法设计
该搜索为一个搜索树。为了简化问题，搜索树节点设计如下：
typedef struct Node//棋盘
{//节点结构体
int data[9];
double f,g;
struct Node * parent; //父节点
}Node,*Lnode;
int data[9]; 数码数组：记录棋局数码摆放状态。
struct Chess * Parent; 父节点：指向父亲节点。
下一步可以通过启发搜索算法构造搜索树。
1、局部搜索树样例：
2、搜索过程
搜索采用广度搜索方式，利用待处理队列辅助，逐层搜索（跳过劣质节点）。搜索过程如下：
（1）、把原棋盘压入队列；
（2）、从棋盘取出一个节点；
（3）、判断棋盘估价值，为零则表示搜索完成，退出搜索；
（4）、扩展子节点，即从上下左右四个方向移动棋盘，生成相应子棋盘；
（5）、对子节点作评估，是否为优越节点（子节点估价值小于或等于父节点则为优越节点），是则把子棋盘压入队列，否则抛弃；
（5）、跳到步骤（2）；
3、算法的评价
完全能解决简单的八数码问题，但对于复杂的八数码问题还是无能为力。现存在的一些优缺点。
1、可以改变数码规模（N），来扩展成N*N的棋盘，即扩展为N数码问题的求解过程。
<!--[if !supportLists]-->2、 <!--[endif]-->内存泄漏。由于采用倒链表的搜索树结构，简化了数据结构，但有部分被抛弃节点的内存没有很好的处理，所以会造成内存泄漏；
<!--[if !supportLists]-->3、 <!--[endif]-->采用了屏蔽方向，有效防止往回搜索（节点的回推），但没能有效防止循环搜索，所以不能应用于复杂度较大的八数码问题；
源码：
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
typedef struct Node
{//节点结构体
int data[9];
double f,g;
struct Node * parent;
}Node,*Lnode;
typedef struct Stack
{//OPEN CLOSED 表结构体
Node * npoint;
struct Stack * next;
}Stack,* Lstack;
Node * Minf(Lstack * Open)
{//选取OPEN表上f值最小的节点，返回该节点地址
Lstack temp = (*Open)->next,min = (*Open)->next,minp = (*Open);
Node * minx;
while(temp->next != NULL)
{
if((temp->next ->npoint->f) < (min->npoint->f))
{
min = temp->next;
minp = temp;
}
temp = temp->next;
}
minx = min->npoint;
temp = minp->next;
minp->next = minp->next->next;
free(temp);
return minx;
}
int Canslove(Node * suc, Node * goal)
{//判断是否可解
int a = 0,b = 0,i,j;
for(i = 1; i< 9;i++)
for(j = 0;j < i;j++)
{
if((suc->data[i] > suc->data[j]) && suc->data[j] != 0)a++;
if((goal->data[i] > goal->data[j]) && goal->data[j] != 0)b++;
}
if(a%2 == b%2)return 1;
else return 0;
}
int Equal(Node * suc,Node * goal)
{//判断节点是否相等，相等，不相等
for(int i = 0; i < 9; i ++ )
if(suc->data[i] != goal->data[i])return 0;
return 1;
}
Node * Belong(Node * suc,Lstack * list)
{//判断节点是否属于OPEN表或CLOSED表，是则返回节点地址，否则返回空地址
Lstack temp = (*list) -> next ;
if(temp == NULL)return NULL;
while(temp != NULL)
{
if(Equal(suc,temp->npoint))return temp -> npoint;
temp = temp->next;
}
return NULL;
}
void Putinto(Node * suc,Lstack * list)
{//把节点放入OPEN 或CLOSED 表中
Stack * temp;
temp =(Stack *) malloc(sizeof(Stack));
temp->npoint = suc;
temp->next = (*list)->next;
(*list)->next = temp;
}
///////////////计算f值部分-开始//////////////////////////////
double Fvalue(Node suc, Node goal, int m)
{//计算f值
switch(m)
{
case 1:{
int error(Node,Node);
int w=0;
w=error(suc,goal);
return w+suc.g;
}
case 2:{
double Distance(Node,Node,int);
double p = 0;
for(int i = 1; i <= 8; i++)
p = p + Distance(suc, goal, i);
return p + suc.g; //f = h + g;
}
default:
break;
}
}
int error(Node suc,Node goal)
{//计算错位个数
int w,i;
w=0;
for(i=0;i<9;i++){
if(suc.data[i]!=goal.data[i])
w++;
}
return w;
}
double Distance(Node suc, Node goal, int i)
{//计算方格的错位距离
int k,h1,h2;
for(k = 0; k < 9; k++)
{
if(suc.data[k] == i)h1 = k;
if(goal.data[k] == i)h2 = k;
}
return double(fabs(h1/3 - h2/3) + fabs(h1%3 - h2%3));
}
///////////////计算f值部分-结束//////////////////////////////
///////////////////////扩展后继节点部分的函数-开始/////////////////
int BelongProgram(Lnode * suc ,Lstack * Open ,Lstack * Closed ,Node goal ,int m)
{//判断子节点是否属于OPEN或CLOSED表并作出相应的处理
Node * temp = NULL;
int flag = 0;
if((Belong(*suc,Open) != NULL) || (Belong(*suc,Closed) != NULL))
{
if(Belong(*suc,Open) != NULL) temp = Belong(*suc,Open);
else temp = Belong(*suc,Closed);
if(((*suc)->g) < (temp->g))
{
temp->parent = (*suc)->parent;
temp->g = (*suc)->g;
temp->f = (*suc)->f;
flag = 1;
}
}
else
{
Putinto(* suc, Open);
(*suc)->f = Fvalue(**suc, goal, m);
}
return flag;
}
int Canspread(Node suc, int n)
{//判断空格可否向该方向移动，，，表示空格向上向下向左向右移
int i,flag = 0;
for(i = 0;i < 9;i++)
if(suc.data[i] == 0)break;
switch(n)
{
case 1:
if(i/3 != 0)flag = 1;break;
case 2:
if(i/3 != 2)flag = 1;break;
case 3:
if(i%3 != 0)flag = 1;break;
case 4:
if(i%3 != 2)flag = 1;break;
default:break;
}
return flag ;
}
void Spreadchild(Node * child,int n)
{//扩展child节点的字节点n表示方向，，，表示空格向上向下向左向右移
int i,loc,temp;
for(i = 0;i < 9;i++)
child->data[i] = child->parent->data[i];
for(i = 0;i < 9;i++)
if(child->data[i] == 0)break;
if(n==0)
loc = i%3+(i/3 - 1)*3;
else if(n==1)
loc = i%3+(i/3 + 1)*3;
else if(n==2)
loc = i%3-1+(i/3)*3;
else
loc = i%3+1+(i/3)*3;
temp = child->data[loc];
child->data[i] = temp;
child->data[loc] = 0;
}
void Spread(Lnode * suc, Lstack * Open, Lstack * Closed, Node goal, int m)
{//扩展后继节点总函数
int i;
Node * child;
for(i = 0; i < 4; i++)
{
if(Canspread(**suc, i+1)) //判断某个方向上的子节点可否扩展
{
child = (Node *) malloc(sizeof(Node)); //扩展子节点
child->g = (*suc)->g +1; //算子节点的g值
child->parent = (*suc); //子节点父指针指向父节点
Spreadchild(child, i); //向该方向移动空格生成子节点
if(BelongProgram(&child, Open, Closed, goal, m)) // 判断子节点是否属于OPEN或CLOSED表并作出相应的处理
free(child);
}
}
}
///////////////////////扩展后继节点部分的函数-结束//////////////////////////////////
Node * Process(Lnode * org, Lnode * goal, Lstack * Open, Lstack * Closed, int m)
{//总执行函数
while(1)
{
if((*Open)->next == NULL)return NULL; //判断OPEN表是否为空，为空则失败退出
Node * minf = Minf(Open); //从OPEN表中取出f值最小的节点
Putinto(minf, Closed); //将节点放入CLOSED表中
if(Equal(minf, *goal))return minf; //如果当前节点是目标节点，则成功退出
Spread(&minf, Open, Closed, **goal, m); //当前节点不是目标节点时扩展当前节点的后继节点
}
}
int Shownum(Node * result)
{//递归显示从初始状态到达目标状态的移动方法
if(result == NULL)return 0;
else
{
int n = Shownum(result->parent);
printf("第%d步：",n);
for(int i = 0; i < 3; i++)
{
printf("\n");
for(int j = 0; j < 3; j++)
{
if(result->data[i*3+j] != 0)
printf(" %d ",result->data[i*3+j]);
else printf(" 0 ");
}
}
printf("\n");
return n+1;
}
}
void Checkinput(Node *suc)
{//检查输入
int i = 0,j = 0,flag = 0;
char c;
while(i < 9)
{
while(((c = getchar()) != 10))
{
if(c == ' ')
{
if(flag >= 0)flag = 0;
}
else if(c >= '0' && c <= '8')
{
if(flag == 0)
{
suc->data[i] = (c-'0');
flag = 1;
for(j =0; j < i; j++)
if(suc->data[j] == suc->data[i])flag = -2;
i++;
}
else if(flag >= 0)flag = -1;
}
else
if(flag >= 0)flag = -1;
}
if(flag <0 || i < 9)
{
if(flag < 0)
{
if(flag == -1)printf("含有非法字符或数字!\n请重新输入:\n");
else if(flag == -2)printf("输入的数字有重复!\n请重新输入:\n");
}
else if(i < 9)printf("输入的有效数字不够!\n请重新输入:\n");
i = 0;
flag = 0;
}
}
}
int meassure(Lstack s)
{
int k=0;
while((s->next)!=NULL)
{
k++;
s=s->next;
}
return k;
}
void main()
{//主函数 //初始操作，建立open和closed表
Lstack Open = (Stack *) malloc(sizeof(Stack));
Open->next = NULL;
Lstack Closed = (Stack *) malloc(sizeof(Stack));
Closed->next = NULL;
Node * org = (Node *) malloc(sizeof(Node));
org->parent = NULL; //初始状态节点
org->f =1;
org->g =1;
Node * goal = (Node *) malloc(sizeof(Node)); //目标状态节点
Node * result;
int m;
char c;
int k;
printf("=================================\n");
printf("说明:状态矩阵由0-8 九个数字表示,\n请依次按照九宫格上的行列顺序输入,每个数字间用空格隔开。\n");
printf("=================================\n");
printf("请输入初始状态(0-8 9个数字以空格隔开回车表示输入结束):\n");
Checkinput(org);
printf("请输入目标状态(0-8 9个数字以空格隔开回车表示输入结束):\n");
Checkinput(goal);
if(Canslove(org, goal))
{//A*算法开始，先将初始状态放入OPEN表
printf("请选择：1.按w(n)搜索 2.按p(n)搜索 \n");
scanf("%d",&m);
while((c = getchar()) != 10);
printf("搜索中，请耐心等待(如果您觉得时间太久请重新执行程序并输入更快的速度,默认值为)......\n");
Putinto(org,&Open);
result = Process(&org, &goal, &Open, &Closed, m); //进行剩余的操作
printf("总步数:%d",Shownum(result)-1);
printf("\n");
k=meassure(Closed);
printf("扩展节点数：\n");
printf("%d\n",k);
printf("Press Enter key to exit!");
while((c = getchar()) != 10);
}
else
printf("程序认定该起始状态无法道达目标状态!\n");
}