人工智能实验报告-八数码(1)

《人工智能》实验一题目

实验一 启发式搜索算法

1. 实验内容：

使用启发式搜索算法求解8数码问题。

⑴ 编制程序实现求解8数码问题A?算法，采用估价函数

??w?n?， f?n??d?n???pn????其中：d?n?是搜索树中结点n的深度；w?n?为结点n的数据库中错放的棋子个数；p?n?为结点n的数据库中每个棋子与其目标位置之间的距离总和。

⑵ 分析上述⑴中两种估价函数求解8数码问题的效率差别，给出一个是p?n?的上界的h?n?的定义，并测试使用该估价函数是否使算法失去可采纳性。

2. 实验目的

熟练掌握启发式搜索A算法及其可采纳性。 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数码问题的求解过程。 2、 内存泄漏。由于采用倒链表的搜索树结构，简化

了数据结构，但有部分被抛弃节点的内存没有很好的处理，所以会造成内存泄漏； 3、 采用了屏蔽方向，有效防止往回搜索（节点的回

推），但没能有效防止循环搜索，所以不能应用于复杂度较大的八数码问题；

源码：

#include #include #include

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步：\ for(int i = 0; i < 3; i++) { printf(\ for(int j = 0; j < 3; j++) { if(result->data[i*3+j] != 0) printf(\ else printf(\ } } printf(\

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(\ printf(\说明:状态矩阵由0-8 九个数字表示,\\n请依次按照九宫格上的行列顺序输入,每个数字间用空格隔开。\\n\

printf(\ 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(\ while((c = getchar()) != 10); printf(\搜索中，请耐心等待(如果您觉得时间太久请重新执行程序并输入更快的速度,默认值为)......\\n\

Putinto(org,&Open);

result = Process(&org, &goal, &Open, &Closed, m); //进行剩余的操作 printf(\总步数:%d\ printf(\ k=meassure(Closed); printf(\扩展节点数：\\n\ printf(\ printf(\ while((c = getchar()) != 10); } else printf(\程序认定该起始状态无法道达目标状态!\\n\}

本文来源：https://www.bwwdw.com/article/j0wa.html