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

《奥鹏大工20春《人工智能》大作业题目及要求 - A算法参考答案.docx》由会员分享，可在线阅读，更多相关《奥鹏大工20春《人工智能》大作业题目及要求 - A算法参考答案.docx（20页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、奥鹏大工20春人工智能大作业题目 及要求- A算法参考答案大连理工大学远程与继续教育学院人工智能课程设计大工20春人工智能大作业题目及要求 参考答案题目：A*算法1 .谈谈你对本课程学习过程中的心得体会与建议？人工智能是研究如何利用计算机来模拟人脑所从事的感知、 推理、学习、思考、规划等人类智能活动，来解决需要用人类 智能才能解决的问题，以延伸人们智能的科学。掌握人工智能 的基本概念、基本原理、知识的表示、推理机制和求解技术， 以及机器学习的技术方法.掌握人工智能的一个问题和三大技 术，即通用问题求解和知识表示技术、搜索技术、推理技术。人工智能的定义可以分为两局部，即“人工”和“智能”。“人工

2、”比拟好理解，争议性也不大。有时我们会要考虑什么是 人力所能及制造的，或者人自身的智能程度有没有高到可以创int main() int fromCOLCOL;int toCOLCOL;int k=O,c;memset(ha,0,sizeof(ha);memset(parl ,sizeof(pa);printf(请按行输入原始九宫格，空白的输入0W)input(from);printf(原始九宫格为：n);output(from);printf(请按行输入目标九宫格，空白的输入0n);input(to);大连理工大学远程与继续教育学院人工智能课程设计printf(目标九宫格为：nn);outpu

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

4、j,pak);output_tow(from,to);coutendl;)return 0;)void output(int aCOL)大连理工大学远程与继续教育学院人工智能课程设计int i,j;for(i=0;iCOL;i+)for(j=0;jCOL;j+)printf(%d n,aij);putchar(n);)void output_tow(int from COL ,int toCOL)(int i,j;for(i=0;iCOL;i+)for(j=0;jCOL;j+)printf(%d n,fromij);cout,tt;for(j=0;jCOL;j+)printf(%d ,toij

5、);putchar(n);void input(int aCOL) int i,j,c;s:intg9;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;goto s;)gc+；)int Astar(int fromCOL,int toCOLJnt deepjnt path) if(eq(from,to)memcpy(pa,path,sizeof(pa);return deep;)int i,

6、j ;/*记录当前状态，白板位置*/int *a=from0;int b9;int m=0;for(i=0;i9;i+)bi=ai;for(i=0;i9;i+)for(j=0;jaj)bi-；m+=hi*bi;)ham=l;for(i=0;i3;i+)for(j=0;j3;j+)if(fromij=0)大连理工大学远程与继续教育学院人工智能课程设计goto ok;ok: for(int step=0;step4;step+) if(change(from J j 9step) int v=value(from,to)+deep+l;Node n;n=make(from,deep+1 path,

7、step);q.push(n);change(from J j ,step);)Node p=q.top();int flag=0;while(!flag)a=p.x0;m=0;for(i=0;i9;i+)bi=ai;for(i=0;i9;i+)for(j=0;jaj)bi-；m+=hi*bi;)if(!ham)q.popO;break;)q.popO;p=q.top();大连理工大学远程与继续教育学院人工智能课程设计)return Astar(p.x,to,p.deep,p.path);)booleq(intfromCOL,inttoCOL)/* 判断起始与终止是否 相同*/for(intj

8、=0;j3;j+)if(fromij!=toij)return 0;)return 1;)bool change(int fromCOL,const int i,const int j,const intstep)/*判断当前状态是否可以进行相应移动*/(if(i=0&step=0)|(i=2&step=l)|(j=0&step=2)|(j =2&step=3)return 0;int a=from i皿；switch(step)case 0:fromi j=fromi-1 j;fromi-lj=a;break;fromi j =from i+lj;fromi+lj=a;break;大连理工大

9、学远程与继续教育学院人工智能课程设计case 1: fromi j=fromi j-1 ;fromij-l=a;break;case 2: from ij=fromij+l;fromij+l=a;break;default:coutWRONG! nendl;break;)return 1;)int value(const int from COL,const int to口 COL)/*估价函数*/intint v=0;for(i=0;i3;i+)for(j=0;j3;j+)for(m=0;m3 ;m+)for(n=0;n3;n+)if (from i j =to m n)goto p;P-i

10、f(fromij!=0)v+=(abs(i-m)+abs(j-n);)return v;大连理工大学远程与继续教育学院人工智能课程设计)Nodemake(intfrom COL JntdeepJntv,intpath Jntstep)/* 转 换函数*/(Node p;造人工智能的地步，等等。但总的来说，“人工系统”就是通常 意义下的人工系统。关于什么是“智能”，就问题多多了。这涉 及到其它诸如意识、自我、思维等等问题。人唯一了解的智能 是人本身的智能，这是普遍认同的观点。但是我们对我们自身 智能的理解都非常有限，对构成人的智能的必要元素也了解有 限，所以就很难定义什么是“人工”制造的“智能”

11、了。2.人工智能课程设计,从以下5个题目中任选其一 作答。人工智能课程设计题目一：A*算法 要求：(1)撰写一份word文档，里面包括(算法思 路、算法程序框图、重排九宫问题)章节。(2)算法思路：简单介绍该算法的基本思想，100字 左右大连理工大学远程与继续教育学院人工智能课程设计即可。for(intj=0;j3;j+)p.xij=fromij;)p.deep=deep;p.expend二v;memcpy(p.path,path,sizeof(int)*MAXSTEP);p .path deep=step;return p;)bool possible(int fromCOL,int toC

12、OL)/*可行性判断*/ (int m=0,n=0;intint aCOL*COL,bCOL*COL;for(i=0;iCOL;i+)for(j=0;jCOL;j+)ai *COL+j =fromi j ;bi*COL+j=toij;for(l=k+ l;lCOL*COL;l+)if(alak&al!=O)m+;if(blbk&bl!=O)大连理工大学远程与继续教育学院人工智能课程设计 n+;)return (n%2)=(m%2);)题目二:归算法要求：(1)撰写一份word文档，里面包括(常见的回归算法、基于实例的算法具体细节)章节。常见的回归算法包括：最小二乘法(Ord i naryLea

13、stSquare )(Logi sticRegress ion )(Ord i naryLeastSquare )(Logi sticRegress ion )逻辑 逐步式(Stepw i seRegress i on )(Stepw i seRegress i on )多元自适应回归样条(Multivar iate Adaptive Regression SpIines ) 以及本地散点平滑估计(LocaI ly EstimatedScatterplot Smoothing),请选择一个算法描述下算 法核心思想(3)随意选用一个实例实现你所选择的回归算法。题目三：深度优先搜索算法 要求：(1

14、)撰写一份word文档，里面包括(算法思路、算法程序框图、主要函数代码)章节。(2)算法思路:简单介绍该算法的基本思想,至少100字。(3)算法程序框图：绘制流程图或原理图, 从算法的开始到结束的程序框图。(4)主要函数代码：列出算法的具体代码。大连理工大学远程与继续教育学院人工智能课程设计(5)简单描述在人工智能的哪些领域需要使用深度优 先搜索算法。题目四：博弈树要求：(1)撰写一份word文档，里面包括(基本概计算倒推值、剪枝技术)章节。(2)基本概念：简单描述博弈树，至少200字。(3)简单描述-剪枝技术。(4)图示博弈树，其中末一行的数字为假设的估值,请对博弈树作如下工作：计算各节点的

15、倒推值。利用-剪枝技术剪去不必要的分支。(可在节点分支上 直接加注释)题目五：广度优先搜索算法 要求：(1)撰写一份word文档，里面包括(算法思 路、算法程序框图、主要函数代码)章节。(2)算法思路：简单介绍该算法的基本思想，至少 100字。(3)算法程序框图：绘制流程图或原理图,从算法的开始大连理工大学远程与继续教育学院人工智能课程设计到结束的程序框图。（4）主要函数代码：列出算法的具体代码。(3)算法程序框图：绘制流程图或原理图，从算法的 开始到结束的程序框图。(4)对于重排九宫问题的启发式函数：f (x) = p(x)+3s(x)p(x)是x结点和目标结点相比每个将牌“离家”的最短距离

16、之和；s(x)是：每个将牌和目标相比，假设该将牌的后继和目 标中该将牌的后继不同，那么该将牌得2分，相同那么该 将牌得分，中间位置有将牌得1分，没将牌得分。对于给定的初始格局和目标状态请按此启发式函数给 出搜索的状态空间图。8124376512384 765答：初始格局目标状态 一、问题描述八数码问题作为一个经典的问题被大家所熟知，该问题是 求解如何从开始的一个状态（布局）到达目标状态所需步数最 少的问题。问题描述如下面第一个图的九宫格中，放着18的数字卡片，还有 一个格子空着。与空格子相邻的格子中的卡片可以移动到空格 中。经过假设干次移动，可以形成第二个图所示的局面。大连理工大学远程与继续教

17、育学院人工智能课程设计 我们把第一个图的局面记为：12345678.把第二个图的局面记为：123.46758显然是按从上到下，从左到右的顺序记录数字，空格记为 句点。此题目的任务是九宫的初态和终态，求最少经过多少 步的移动可以到达。如果无论多少步都无法到达，那么输出-1。输入格式输入第一行包含九宫的初态，第二行包含九宫的终态。输出格式输出最少的步数，如果不存在方案，那么输出-1。样例输入12345678.123.46758样例输出3样例输入13524678.46758123.样例输出22二、流程图大连理工大学远程与继续教育学院人工智能课程设计 大连理工大学远程与继续教育学院人工智能课程设计三、

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

19、的效率），因此我们采用第二 种方法作为八数码问题的估价函数解决了估价函数的问题以后，第二个需要解决的问题就是 判重，我们首先想到的是用集合set,这种方法最简单，但是 很不幸这种方法耗时也是最多的，如果时间要求比拟高的话， 这种情况很容易超时。这里我们不用这种方法，判重问题自然 而然想到的是哈希表，好了现在问题又来了，如何创立哈希表, 也就是哈希函数怎么写，这个东西比拟有技巧，还好对于这种 问题有一种现成的方法解决，那就是康托展开，还有一个问题 就是有些问题是无解的，这种情况我们不希望进行很大力气的 搜索之后发现无解，最好是能提前预知，值得庆幸的是八数码无论怎么移动逆序的奇偶性不变，因此我们可

20、以直接通过0（1）的时间判断开始和目标结点的逆序奇偶性是否相同就可 以了。有了上面的分析之后，程序就可以写出来了/*A*算法解决八数码问题（九宫重排）* 程序看起来比拟长，核心只有intAstar（intCOL,int大连理工大学远程与继续教育学院人工智能课程设计COL,int,int）;函数* 其它函数供Astar函数调用，起辅助作用，还有几个函 数仅仅是为了使界面更友好所有函数均有注释说明* 其中可行性判断函数需要对八数码问题进行数学上的简 单分析，* hash函数的设计有些技巧，其他函数的原理都是显然 的程序运行有问题可以和我联系* /#include#include #include#

21、include#includedefine COL 3* define MAXSTEP 70using namespace std;void output(int口COL);/*输出函数*/void input(int COL);/*输出函数*/int Astar(int COL,int COL,int,int path);/*核心函数， 起始，终止，深度，方向*/bool eq(int fromCOL,int toCOL);/*判断起始与终止是 否相同*/bool change(int from COL,const int i,const int j,const intstep);/*判断当

22、前状态是否可以进行相应移动,并进行状态转 变*/int value(const int fromCOL,const int to口COL);/*估价 函数*/void output_tow(int fromCOL,int toCOL);/*输出函数, 和上面的outpput函数差不多*/bool possible(int fromCOL,int toCOL);/*可行性判断*/inth9=40320,5040,720,120,24,6,2,1,1;/*hash 函数用至U 的数据大连理工大学远程与继续教育学院人工智能课程设计8-0的阶乘*/bool ha400000;struct Nodeint pathMAXSTEP; /*路径信息*/int expend;/*权重*/int deep;/*深度*/int xCOLCOL;/*状态信息*/；struct cmp bool operator() (const Node A,const Node B)return A.expendB .expend;)；int paMAXSTEP;priority_queueNode,vector,cmp q;/*优先 队歹I */ Nodemake(intfrom口COL,intdeep,intv,intpath口,intstep);/*转换函数*/