631306050115陆奇+启发式搜索+单层感知器实现and分类

《631306050115陆奇+启发式搜索+单层感知器实现and分类》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、重庆交通大学计算机与信息学院验证性实验报告班级：软件专业2013级1班学号：631306050115__________姓名：陆奇________________实验项目名称：启发式搜索A*算法实验项目性质：验证性实验_______实验所属课程：人工智能__________实验室(中心)：软件中心实验室（语音楼8楼）指导教师：朱振国____________实验完成时间：2016年6月11日评阅意见：实验成绩：签名：年月日一、实验目的理解和掌握A*算法。二、实验内容及要求在8数码问题中，利用策略函数判断搜索，并使用A*算法减少搜索目标。三、实验设备及软件Windows操作系统，vs20

2、13四、设计方案㈠题目启发式搜索A*算法㈡设计的主要思路该搜索为一个搜索树。为了简化问题，搜索树节点设计如下：typedefstructNode//棋盘{//节点结构体intdata[9];doublef,g;structNode*parent;//父节点}Node,*Lnode;intdata[9];   数码数组：记录棋局数码摆放状态。structChess*Parent; 父节点：指向父亲节点。下一步可以通过启发搜索算法构造搜索树。1、局部搜索树样例：2、搜索过程 搜索采用广度搜索方式，利用待处理队列辅助，逐层搜索（跳过劣质节点）。搜索过程如下： （1）、把原棋盘压入队列； （

3、2）、从棋盘取出一个节点； （3）、判断棋盘估价值，为零则表示搜索完成，退出搜索； （4）、扩展子节点，即从上下左右四个方向移动棋盘，生成相应子棋盘；（5）、对子节点作评估，是否为优越节点（子节点估价值小于或等于父节点则为优越节点），是则把子棋盘压入队列，否则抛弃； （5）、跳到步骤（2）；㈢主要功能解决简单的八数码问题五、主要代码#include#include#includetypedefstructNode{//节点结构体intdata[9];doublef,g;structNode*parent;}Node,*Lnode;

4、typedefstructStack{//OPENCLOSED表结构体Node*npoint;structStack*next;}Stack,*Lstack;Node*Minf(Lstack*Open){//选取OPEN表上f值最小的节点，返回该节点地址Lstacktemp=(*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=te

5、mp->next;}minx=min->npoint;temp=minp->next;minp->next=minp->next->next;free(temp);returnminx;}intCanslove(Node*suc,Node*goal){//判断是否可解inta=0,b=0,i,j;for(i=1;i<9;i++)for(j=0;jdata[i]>suc->data[j])&&suc->data[j]!=0)a++;if((goal->data[i]>goal->data[j])&&goal->data[j]!=0)b++;}if(a%

6、2==b%2)return1;elsereturn0;}intEqual(Node*suc,Node*goal){//判断节点是否相等，相等，不相等for(inti=0;i<9;i++)if(suc->data[i]!=goal->data[i])return0;return1;}Node*Belong(Node*suc,Lstack*list){//判断节点是否属于OPEN表或CLOSED表，是则返回节点地址，否则返回空地址Lstacktemp=(*list)->next;if(temp==NULL)returnNULL;while(temp!=NULL){if(Equal(suc

7、,temp->npoint))returntemp->npoint;temp=temp->next;}returnNULL;}voidPutinto(Node*suc,Lstack*list){//把节点放入OPEN或CLOSED表中Stack*temp;temp=(Stack*)malloc(sizeof(Stack));temp->npoint=suc;temp->next=(*list)->next;(*list)->next=temp;}/////