奥鹏大工20春《人工智能》大作业题目及要求 - A算法参考答案

1、大工20春人工智能大作业题目及要求参考答案题目：A*算法谈谈你对本课程学习过程中的心得体会与建议？人工智能是研究如何利用计算机来模拟人脑所从事的感知、推理、学习、思考、规划等人类智能活动，来解决需要用人类智能才能解决的问题，以延伸人们智能的科学。掌握人工智能的基本概念、基本原理、知识的表示、推理机制和求解技术，以及机器学习的技术方法.掌握人工智能的一个问题和三大技术，即通用问题求解和知识表示技术、搜索技术、推理技术。人工智能的定义可以分为两部分，即“人工”和“智能”“人工”比较好理解，争议性也不大。有时我们会要考虑什么是人力所能及制造的，或者人自身的智能程度有没有高到可以创造人工智能的地步，等

2、等。但总的来说，“人工系统”就是通常意义下的人工系统。关于什么是“智能”，就问题多多了。这涉及到其它诸如意识、自我、思维等等问题。人唯一了解的智能是人本身的智能，这是普遍认同的观点。但是我们对我们自身智能的理解都非常有限，对构成人的智能的必要元素也了解有限，所以就很难定义什么是“人工”制造的“智能”了。人工智能课程设计,从以下5个题目中任选其一作答。人工智能课程设计题目一：A*算法要求：（1）撰写一份word文档，里面包括（算法思路、算法程序框图、重排九宫问题）章节。（2）算法思路：简单介绍该算法的基本思想，100字左右即可。算法程序框图：绘制流程图或原理图，从算法的开始到结束的程序框图。对于

3、重排九宫问题的启发式函数：f(x)=p(x)+3s(x)p(x)是x结点和目标结点相比每个将牌“离家”的最短距离之和；s(x)是：每个将牌和目标相比，若该将牌的后继和目标中该将牌的后继不同，则该将牌得2分，相同则该将牌得0分，中间位置有将牌得1分，没将牌得0分。对于给定的初始格局和目标状态请按此启发式函数给出搜索的状态空间图。TI2436初始格局28463目标状态答:一、问题描述八数码问题作为一个经典的问题被大家所熟知，该问题是求解如何从开始的一个状态(布局)到达目标状态所需步数最少的问题。问题描述如下面第一个图的九宫格中，放着18的数字卡片，还有一个格子空着。与空格子相邻的格子中的卡片可以移

4、动到空格中。经过若干次移动，可以形成第二个图所示的局面。我们把第一个图的局面记为：12345678.把第二个图的局面记为：123.46758显然是按从上到下，从左到右的顺序记录数字，空格记为句点。本题目的任务是已知九宫的初态和终态，求最少经过多少步的移动可以到达。如果无论多少步都无法到达，则输出-1。输入格式输入第一行包含九宫的初态，第二行包含九宫的终态。输出格式输出最少的步数，如果不存在方案，则输出-1。样例输入12345678.123.46758样例输出3样例输入13524678.46758123.样例输出22二、流程图三、问题分析将每一个状态作为一个结点容易想到可以用广搜的方法解决，这种

5、方法简单，但是就算是加入哈希判重也会搜索很多的无用结点。我们打算用A*算法解决这个问题，既然确定了用A*算法，那么我们首先应该确定估价函数h(x)，估价函数的选取直接决定A*算法的效率，一般对于八数码问题有三种估价函数的选法：以不在位的数码的个数为估价函数以不在位的数码归位所需的最短距离和即曼哈顿距离为估价函数将逆序对数作为估价函数可以证明前两种都是乐观估计，最后一种不是，因此前两种都可以作为八数码问题的估价函数，但是你的估计值与真实值越近所需要搜索的状态越少，很明显第一种方法太乐观了(估价函数的选取直接决定算法的效率)，因此我们采用第二种方法作为八数码问题的估价函数解决了估价函数的问题以后，

6、第二个需要解决的问题就是判重，我们首先想到的是用集合set,这种方法最简单，但是很不幸这种方法耗时也是最多的，如果时间要求比较高的话，这种情况很容易超时。这里我们不用这种方法，判重问题自然而然想到的是哈希表，好了现在问题又来了，如何创建哈希表，也就是哈希函数怎么写，这个东西比较有技巧，还好对于这种问题有一种现成的方法解决，那就是康托展开，还有一个问题就是有些问题是无解的，这种情况我们不希望进行很大力气的搜索之后发现无解，最好是能提前预知，值得庆幸的是八数码无论怎么移动逆序的奇偶性不变，因此我们可以直接通过O(1)的时间判断开始和目标结点的逆序奇偶性是否相同就可以了。有了上面的分析之后，程序就可

7、以写出来了/*A*算法解决八数码问题(九宫重排)*程序看起来比较长，核心只有intAstar(intCOL,intCOL,int,int);函数*其它函数供Astar函数调用，起辅助作用，还有几个函数仅仅是为了使界面更友好所有函数均有注释说明其中可行性判断函数需要对八数码问题进行数学上的简单分析，hash函数的设计有些技巧，其他函数的原理都是显然的程序运行有问题可以和我联系*/#include#include#include#include#include#defineCOL3#defineMAXSTEP70usingnamespacestd;voidoutput(intCOL);/*输出函数

8、*/voidinput(intCOL);/*输出函数*/intAstar(intCOL,intCOL,int,intpath);/*核心函数，起始，终止，深度，方向*/booleq(intfromC0L,inttoCOL);/*判断起始与终止是否相同*/boolchange(intfromCOL,constinti,constintj,constintstep);/*判断当前状态是否可以进行相应移动，并进行状态转变*/intvalue(constintfromCOL,constinttoCOL);/*估价函数*/voidoutput_tow(intfromCOL,inttoCOL);/*输出函

9、数，和上面的outpput函数差不多*/boolpossible(intfromCOL,inttoCOL);/*可行性判断*/inth9=40320,5040,720,120,24,6,2,l,l;/*hash函数用到的数据8-0的阶乘*/boolha400000;structNodeintpathMAXSTEP;/*路径信息*/intexpend;/*权重*/intdeep;/*深度*/intxCOLCOL;/*状态信息*/;structcmpbooloperator()(constNodeA,constNodeB)returnA.expendB.expend;intpaMAXSTEP;pr

10、iority_queueNode,vector,cmpq;/*优先队列*/Nodemake(intfromCOL,intdeep,intv,intpath,intstep);/*转换函数*/intmain()intfromCOLCOL;inttoCOLCOL;intk=0,c;memset(ha,0,sizeof(ha);memset(pa,-1,sizeof(pa);printf(请按行输入原始九宫格，空白的输入0n);input(from);printf(原始九宫格为：n);output(from);printf(请按行输入目标九宫格，空白的输入0n);input(to);printf(目

11、标九宫格为：n);output(to);printf(按任意键显示执行步骤：n);fflush(stdin);getchar();if(!possible(from,to)cout目标状态不可达，请换一组数据测试！endl;return0;intd=Astar(from,to,0,pa);cout最优路径到目标位置需要d步endl;cout当前状态t目标状态endl;while(c=pa+k)!=-1)inti,j;/*记录当前状态，白板位置*/cout第k步endl;for(i=0;i3;i+)for(j=0;j3;j+)if(fromij=0)gotoo;o:change(from,i,j

12、,pak);output_tow(from,to);coutendl;return0;voidoutput(intaCOL)inti,j;for(i=0;iCOL;i+)for(j=0;jCOL;j+)printf(%d,aij);putchar(n);voidoutput_tow(intfromCOL,inttoCOL)inti,j;for(i=0;iCOL;i+)for(j=0;jCOL;j+)printf(%d,fromij);couttt;for(j=0;jCOL;j+)printf(%d,toij);putchar(n);voidinput(intaCOL)inti,j,c;s:in

13、tg9;memset(g,0,sizeof(g);for(i=0;iCOL;i+)for(j=0;jCOL;j+)scanf(%d,&aij);c=aij;if(gc|c8)cout输入有误，请重新输入endl;gotos;gc+;intAstar(intfromCOL,inttoCOL,intdeep,intpath)if(eq(from,to)memcpy(pa,path,sizeof(pa);returndeep;inti,j;/*记录当前状态，白板位置*/int*a=from0;intb9;intm=0;for(i=0;i9;i+)bi=ai;for(i=0;i9;i+)for(j=0

14、;jaj)bi-;m+=hi*bi;ham=1;for(i=0;i3;i+)for(j=0;j3;j+)if(fromij=0)gotook;ok:for(intstep=0;step4;step+)if(change(from,i,j,step)intv=value(from,to)+deep+1;Noden;n=make(from,deep+1,v,path,step);q.push(n);change(from,i,j,step);Nodep=q.top();intflag=0;while(!flag)a=p.x0;m=0;for(i=0;i9;i+)bi=ai;for(i=0;i9;i

15、+)for(j=0;jaj)bi-;m+=hi*bi;if(!ham)q.pop();break;q.pop();p=q.top();returnAstar(p.x,to,p.deep,p.path);booleq(intfromCOL,inttoCOL)/*判断起始与终止是否相同*/for(inti=0;i3;i+)for(intj=0;j3;j+)if(fromij!=toij)return0;return1;boolchange(intfromCOL,constinti,constintj,constintstep)/*判断当前状态是否可以进行相应移动*/if(i=0&step=0)|(

16、i=2&step=1)|(j=0&step=2)|(j=2&step=3)return0;inta=fromij;switch(step)case0:fromij=fromi-1j;fromi-1j=a;break;case1:fromij=fromi+1j;fromi+1j=a;break;case2:fromij=fromij-1;fromij-1=a;break;case3:fromij=fromij+1;fromij+1=a;break;default:coutWRONG!endl;break;return1;intvalue(constintfromCOL,constinttoCOL

17、)/*古价函数*/inti,j,m,n;intv=0;for(i=0;i3;i+)for(j=0;j3;j+)for(m=0;m3;m+)for(n=0;n3;n+)if(fromij=tomn)gotop;p:if(fromij!=0)v+=(abs(i-m)+abs(j-n);returnv;Nodemake(intfromCOL,intdeep,intv,intpath,intstep)/*转换函数*/Nodep;for(inti=0;i3;i+)for(intj=0;j3;j+)p.xij=fromij;p.deep=deep;p.expend=v;memcpy(p.path,path

18、,sizeof(int)*MAXSTEP);p.pathdeep=step;returnp;boolpossible(intfromC0L,inttoCOL)/*可行性判断*/intm=0,n=0;inti,j,k,l;intaCOL*COL,bCOL*COL;for(i=0;iCOL;i+)for(j=0;jCOL;j+)ai*COL+j=fromij;bi*COL+j=toij;for(k=0;kCOL*COL;k+)for(l=k+1;lCOL*COL;l+)if(alak&al!=0)m+;if(blbk&bl!=0)n+;return(n%2)=(m%2);题目二：回归算法要求：(1)撰写一份word文档，里面包括(常见的回归算法、基于实例的算法具体细节)章节。常见的回归算法包括：最小二乘法(OrdinaryLeastSquare)，逻辑回归(LogisticRegression)，逐步式回归(StepwiseRegression)，多元自适应回归样条(M