人工智能实验报告-八数码(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; el …… 此处隐藏：4414字，全部文档内容请下载后查看。喜欢就下载吧 ……