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

重庆交通大学计算机与信息学院验证性实验报告班 级： 软件 专业 2013 级 1 班 学 号： 631306050115_ 姓 名： 陆奇_ 实验项目名称： 启发式搜索 A*算法 实验项目性质： 验证性实验_ 实验所属课程： 人工智能_ 实验室(中心)：软件中心实验室（语音楼8楼）指 导 教 师 ： 朱振国_ 实验完成时间： 2016 年 6 月 11 日评阅意见：实验成绩： 签名： 年 月 日一、实验目的 理解和掌握A*算法。二、实验内容及要求在8数码问题中，利用策略函数判断搜索，并使用A*算法减少搜索目标。 三、实验设备及软件 Windows操作系统，vs2013 四、设计方案 题目 启发式搜索 A*算法 设计的主要思路该搜索为一个搜索树。为了简化问题，搜索树节点设计如下：typedef struct Node/棋盘/节点结构体 int data9;double f,g;struct Node * parent; /父节点Node,*Lnode;int data9; 数码数组：记录棋局数码摆放状态。struct Chess * Parent; 父节点：指向父亲节点。下一步可以通过启发搜索算法构造搜索树。1、局部搜索树样例：2、搜索过程 搜索采用广度搜索方式，利用待处理队列辅助，逐层搜索（跳过劣质节点）。搜索过程如下： （1）、把原棋盘压入队列； （2）、从棋盘取出一个节点； （3）、判断棋盘估价值，为零则表示搜索完成，退出搜索； （4）、扩展子节点，即从上下左右四个方向移动棋盘，生成相应子棋盘；（5）、对子节点作评估，是否为优越节点（子节点估价值小于或等于父节点则为优越节点），是则把子棋盘压入队列，否则抛弃； （5）、跳到步骤（2）； 主要功能解决简单的八数码问题五、主要代码 #include #include #include typedef struct Node/节点结构体 int data9;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) 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 datai suc-dataj) & suc-dataj != 0)a+;if(goal-datai goal-dataj) & goal-dataj != 0)b+;if(a%2 = b%2)return 1;else return 0;int Equal(Node * suc,Node * goal)/判断节点是否相等，相等，不相等for(int i = 0; i datai != goal-datai)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;i9;i+)if(suc.datai!=goal.datai)w+;return w;double Distance(Node suc, Node goal, int i)/计算方格的错位距离int k,h1,h2;for(k = 0; k g) g)temp-parent = (*suc)-parent;temp-g = (*suc)-g;temp-f = (*suc)-f; flag = 1;elsePutinto(* 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.datai = 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 datai = child-parent-datai;for(i = 0;i datai = 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;elseloc = i%3+1+(i/3)*3;temp = child-dataloc;child-datai = temp;child-dataloc = 0;void Spread(Lnode * suc, Lstack * Open, Lstack * Closed, Node goal, int m)/扩展后继节点总函数int i;Node * child;for(i = 0; i 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;elseint n = Shownum(result-parent);printf(第%d步：,n);for(int i = 0; i 3; i+)printf(n);for(int j = 0; j datai*3+j != 0)printf( %d ,result-datai*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 = 0)flag = 0;else if(c = 0 & c datai = (c-0);flag = 1;for(j =0; j dataj = suc-datai)flag = -2; i+;else if(flag = 0)flag = -1;elseif(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 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(%dn,k); printf(Press Enter key to exit!); while(c = getchar() != 10);else printf(程序认定该起始状态无法道达目标状态!n);六、测试结果及说明 七、实验体会实验有一定的难度，刚开始什么都不会，再慢慢的一点一点的学习与摸索，感觉这学科还是有它有趣之处。 验证性实验报告班 级： 软件 专业 2013 级 1 班 学 号： 631306050115_ _ 姓 名： 陆 奇 _ 实验项目名称：_ 用单层感知器实现AND分类 实验项目性质： 验证性实验 _ 实验所属课程： 人工智能 _ 实验室(中心)：软件中心实验室（语音楼8楼）指 导 教 师 ： 朱振国 _ 实验完成时间： 2016 年 6 月 11 日评阅意见：实验成绩： 签名： 年 月 日一、实验目的 理解和掌握单层感知器的工作方式。二、实验内容及要求 使用单层感知器利用有师学习方式，学习与分类。要求实现权值和阈值的改变。初始阈值给定为1，初始权值自己给定。三、实验设备及软件 VC2005,windows操作系统四、设计方案 题目 用单层感知器实现AND分类 设计的主要思路1、初始化联结权值和阈值就是给w(0)和(0)分别赋予一个较小的随机数，作为初始值。2、提供新的样本输入xi(t)(i=1,2.,n)和期望输出d(t)。3、计算网络的实际输出y(t)=f(wi(t)xi(t)-(t) i=1,2.n4、若y(t)=1，不需要调整联结权值。转步骤6。否则需要调整联结权值，执行下一步。5、调整联结权值wi(t+1)=wi(t)+d(t)-y(t)xi(t) i=1,2.n，其中0=1，是一个增益因子，用于控制修改速度，其值不能太大，也不能太小。如果太大，会影响wi的收敛性，否则会影响收敛速度。6、判断是否满足结束条件，若满足，算法结束，否则将t值加1，转2)重新执行。这里的结束条件一般是指wi(t)大意一切样本均稳定不变。 主要功能实现权值和阈值的改变五、主要代码 int time=11111; / 训练的循环数for(int i=0;itime;+i)/ 训练for(int j=0;jQ) return 1;else return 0;void train(bool x,bool std)if(not(x)!=std)double delta=double(std)-double(not(x);/ 误差Q=Q+n*delta*(-1.0);/ 调整阀值w=w+n*delta*x;/ 调整wneuralNetwork()/ 构造函数Q=1;/ 阀值初始化w=0.2;/ 关联权值初始化;六、测试结果及说明 1、对于!x： 输入因子为1，得出结果为!0=1，!1=0；关联权值为-1，阈值为1。 对于输入0，其结果为0*(-1)-(-0.6)0，所以为1，正确。对于输入1，其结果为1*(-1)-(-0.6)0，所以为0，正确