大工21春《人工智能》大作业答案.docx

《大工21春《人工智能》大作业答案.docx》由会员分享，可在线阅读，更多相关《大工21春《人工智能》大作业答案.docx（14页珍藏版）》请在第一文库网上搜索。

1、学习中心：奥鹏远程教育青岛学习中心（直属）25专业：计算机科学与技术年级：19年秋季学号：191032407940学生：王希龙题目：题目五：广度优先搜索算法1谈谈你对本课程学习过程中的心得体会与建议？人工智能是计算机专业的专业课之一。本课程主要介绍如何用计算机来模拟人类智能，如何用计算机实现诸如问题求解、规划推理、模式识别、知识工程、自然语言处理、机器学习等只有人类才具备的智能，使得计算机更好的为人类服务。该课程是计算机科学理论基础研究的重要组成部分，是计算机科学技术专业的专业拓展课，适合计算机专业人员使用。该课程是计算机科学理论基础研究的重要组成部分，是计算机科学技术专业的专业拓展课，适合计

2、算机专业人员使用。这门课程需要学生掌握人工智能的基本概念、基本方法，会用知识表示方法、推理方法和机器学习等方法求解简单问题。2.人工智能课程设计，从以下5个题目中任选其一作答。人工智能课程设计题目五：广度优先搜索算法要求：（1）撰写一份WOrd文档，里面包括（算法思路、算法程序框图、主要函数代码）章节。（2）算法思路：简单介绍该算法的基本思想，至少I（X）字。（3）算法程序框图：绘制流程图或原理图，从算法的开始到结束的程序框图。(4)主要函数代码：列出算法的具体代码。(5)简单描述在人工智能的哪些领域需要使用广度优先搜索算法。答：人工智能(ArtifiCiaIInte11igence,简记为A

3、1)是当前科学技术迅速发展及新思想、新理广度优先搜索，即BFS(BreadthFirstSearch),是一种相当常用的图算法，其特点是：每次搜索指定点，并将其所有未访问过的邻近节点加入搜索队列，循环搜索过程直到队列为空。算法描述如下：(1)将起始节点放入队列尾部(2) Whi1e(队列不为空)取得并删除队列首节点Node处理该节点Node把Node的未处理相邻节点加入队列尾部inc1udestdafx.h#inc1ude构造有向图p162,无向图p168inc1ude#inc1ude#inc1udestd1ib.h包含exit函数广度优先defineNu11(V/广度优先defineINF1

4、NITY1ooo0最大值，无穷defineMAX_VERTEX_NUM20最大顶点个数，即可以计算的最大规模typedefstructArcCe11f1oatadj;无权图为1或0,有权图为权重charinfo30;该弧相关信息ArcCe11,AdjMatrixNfAX_VERTEX_NUMNfAX_VERTEX_NUM;typedefstructcharvexsMAX_VERTEX_NUM20;顶点向量，如v1,v2,.等AdjMatrixarcs;intvexnum,arcnum;MGraph;广度优先typedefstructQNodeintdata;structQNode*next;Q

5、Node,*QueuePtr;typedefstructQueuePtrfront;队头指针QueuePtrrear;队尾指针1inkQueue;广度优先int1ocateVex(MGraphG,char*v)inti,num=-1;for(i=0;iG.vexnum;i+)if(strcmp(v,G.vexsi)=O)相等时为O,大于为正，小于为负num-;break;)if(numO)cout。没有匹配的顶点，输入错误!zzend1;return-1;e1sereturnnum;)voidCreateNet(MGraph&G)inti,j,k,s=0;intIncInfo=-I;/IncI

6、nfo为O则各弧不含其它信息,有信息则为其他数字charv220;存放一条边的两个顶点char*p;f1oatw;输入的权重intdirect=9;有向图为1,无向图为其他数字/chartemp10020;这个temp不能放到本函数内，or,G.vexsi引用他时,赋了值,跳出这个函数就没有值.这样不好/scanf(&G.vexnum,&G.arcnum,&1nc1nfo);COUt构建有向图请输入数字1,构建无向图请输入其他数字(无向图请输入上三角的边).zzdirect;COUt。各顶点无信息则输入数字0,有信息输入其他数字.”1nc1nfo;CoUt请输入顶点和弧数目：G.vexnumG

7、.arcnum;CoUtX请输入XG.VeXnUm个顶点的符号，如v1,v2.zzend1;for(i-0;ip;注意vexsMAX_VERTEX_NUM中的MAX_VERTEX_NUM大于G.vexnumfor(i=0;iG.vexnum;i+)coutG.vexsiz,;for(i=0;iG.vexnum;+i)for(j-0;jG,vexnum;+j)G.arcsiEj1adj=INFINITY;p-G.arcsij.info;P=0;/问题)for(k=O;kG.arcnum;+k)循环弧的次数COUt第k+1次输入:zzp;i=1ocateVex(G,p);CoUtp;J=1ocat

8、eVex(G,p);COUtw;输入格式：v1v218cout,zi=zzizzj=zzjp;if(direct!=1)G.arcsji=G.arcsij;COUt”顶点数是:G.vexnumend1;CoUt弧数是:zG.arcnumend1;cout各顶点分别是:；for(i-0;iG.vexnum;i+)coutG.vexsiz,；coutend1;for(i=0;iG,vexnum;i+)for(j-0;jG,vexnum;j+)coutsetw(8)G.arcsij.adj;if(1nc1nfo)if(G.arcsij.adj!=INFINITY)coutsetw(6)G,arcsi

9、j.info;e1secoutsetw(6),zz,;)coutnext=Nu11;)voidEnQueue(1inkQueue&Q,inte)QueuePtrp;P=(QueuePtr)ma11oc(sizeof(QNode);if(!p)exit(-1);p-data=e;p-next=Nu11;Q.rear-next=p;Q.rear=p;voidDeQueue(1inkQueue&Q,int&e)QueuePtrp;if(Q.front=Q.rear)CoUt队头等于队尾！next;e-p-data;Q.front-next=p-next;if(Q.rear=p)Q.rear=Q.fr

10、ont;free(p);)intQueueEmpty(1inkQueue&Q)if(Q.front-Q.rear)return1;e1sereturnO;)voidvisit(MGraphG,intv)cout。”访问了第v个顶点end1;CoUt即“G.vexsv顶点end1;intFirstAdjVex(MGraphG,intv)inti,num=-1;for(i=0;iG.vexnum;i+)if(G.arcsvi.adj!=INFINITY)num=i;break;returnnum;)intNextAdjVex(MGraphG,intv,intw)inti,num=-1;for(i-

11、w+1;iG,vexnum;i+)if(G.arcsvi.adj!=INFINITY)num=i;break;)returnnum;)voidBFSTraverse(MGraphG)intv;intu;出队元素intw;1inkQueueQ;for(v=0;vG*vexnum;v+)visitedv=O;InitQueue(Q);for(v=0;v=0;W=NextAdjVex(G,u,w)if(!visitedw)visitedw=1;visit(G,w);EnQueue(Q,w);)/广度优先voidmain()MGraphG;CreateNet(G);这时上面已经求出G.vexnum即顶点个数BFSTraverse(G);Q1D:MicrosoftVisua1StudioMyProjectsGDDebugGD.exe-UX的建有向图请输入数字1,构建无向图请输入其他数字无向图请输入上三角的边各顶点无信息则输入数字。,有信息输入其他数字.请输入顶点和狐数目：32请输入3个顶点的符号,如u1,v2.u2m3u1u2v3第1次输入：出蓼点:U1接雪点:u2权逢：2i=0J-I第2次输入:由落点:u2董夏点:u3校重：4