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

学习中心：奥鹏远程教育青岛学习中心（直属）25专业：计算机科学与技术年级：19年秋季学号：191032407940学生：王希龙题目：题目五：广度优先搜索算法1谈谈你对本课程学习过程中的心得体会与建议？人工智能是计算机专业的专业课之一。本课程主要介绍如何用计算机来模拟人类智能，如何用计算机实现诸如问题求解、规划推理、模式识别、知识工程、自然语言处理、机器学习等只有人类才具备的智能，使得计算机更好的为人类服务。该课程是计算机科学理论基础研究的重要组成部分，是计算机科学技术专业的专业拓展课，适合计算机专业人员使用。该课程是计算机科学理论基础研究的重要组成部分，是计算机科学技术专业的专业拓展课，适合计算机专业人员使用。这门课程需要学生掌握人工智能的基本概念、基本方法，会用知识表示方法、推理方法和机器学习等方法求解简单问题。2.人工智能课程设计，从以下5个题目中任选其一作答。人工智能课程设计题目五：广度优先搜索算法要求：（1）撰写一份WOrd文档，里面包括（算法思路、算法程序框图、主要函数代码）章节。（2）算法思路：简单介绍该算法的基本思想，至少I（X）字。（3）算法程序框图：绘制流程图或原理图，从算法的开始到结束的程序框图。(4)主要函数代码：列出算法的具体代码。(5)简单描述在人工智能的哪些领域需要使用广度优先搜索算法。答：人工智能(ArtifiCiaIInte11igence,简记为A1)是当前科学技术迅速发展及新思想、新理广度优先搜索，即BFS(BreadthFirstSearch),是一种相当常用的图算法，其特点是：每次搜索指定点，并将其所有未访问过的邻近节点加入搜索队列，循环搜索过程直到队列为空。算法描述如下：(1)将起始节点放入队列尾部(2) Whi1e(队列不为空)取得并删除队列首节点Node处理该节点Node把Node的未处理相邻节点加入队列尾部inc1ude"stdafx.h#inc1ude<iostream.h>构造有向图p162,无向图p168inc1ude<string.h>#inc1ude<iOmanip.h>#inc1udestd1ib.h>包含exit函数广度优先defineNu11(V/广度优先defineINF1NITY1ooo0最大值，无穷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;QNode,*QueuePtr;typedefstructQueuePtrfront;队头指针QueuePtrrear;队尾指针1inkQueue;广度优先int1ocateVex(MGraphG,char*v)inti,num=-1;for(i=0;i<G.vexnum;i÷+)if(strcmp(v,G.vexsi)=O)相等时为O,大于为正，小于为负num-;break;)if(num<O)cout。没有匹配的顶点，输入错误!zz<<end1;return-1;e1sereturnnum;)voidCreateNet(MGraph&G)inti,j,k,s=0;intIncInfo=-I;/IncInfo为O则各弧不含其它信息,有信息则为其他数字charv220;存放一条边的两个顶点char*p;f1oatw;输入的权重intdirect=9;有向图为1,无向图为其他数字/chartemp10020;这个temp不能放到本函数内，or,G.vexsi引用他时,赋了值,跳出这个函数就没有值.这样不好/scanf(&G.vexnum,&G.arcnum,&1nc1nfo);COUt<<构建有向图请输入数字1,构建无向图请输入其他数字(无向图请输入上三角的边).zz<<end1;cin>>direct;COUt。各顶点无信息则输入数字0,有信息输入其他数字.”<<end1;cin>>1nc1nfo;CoUt<<请输入顶点和弧数目：<<end1;cin>>G.vexnum>>G.arcnum;CoUt<X请输入<XG.VeXnUm个顶点的符号，如v1,v2.zz<<end1;for(i-0;i<G.vexnum;+i)p-G.vexsi;cin>>p;注意vexsMAX_VERTEX_NUM中的MAX_VERTEX_NUM大于G.vexnumfor(i=0;i<G.vexnum;i+)cout<<G.vexsi<<z,;for(i=0;i<G.vexnum;+i)for(j-0;j<G,vexnum;+j)G.arcsiEj1adj=INFINITY;p-G.arcsij.info;P='0'/问题)for(k=O;k<G.arcnum;+k)循环弧的次数COUt<<第<<k+1<<"次输入:zz<<end1;COUt出发点：“；P=v0;cin>>p;i=1ocateVex(G,p);CoUt<<"接受点:"P=v1;cin>>p;J=1ocateVex(G,p);COUt<<“权重:"Cin>>w;输入格式：v1v218cout<<,zi=zz<<i<<zzj=zz<<j<<end1;G.arcsij.adj=w;if(1nc1nfo)COUt输入信息：；p-G.arcsij1info;cin>>p;if(direct!=1)G.arcsji=G.arcsij;COUt<<”顶点数是:"<<G.vexnum<<end1;CoUt弧数是:'z<<G.arcnum<<end1;cout<<各顶点分别是:；for(i-0;i<G.vexnum;i+)cout<<G.vexsi<<z,；cout<<end1;for(i=0;i<G,vexnum;i+)for(j-0;j<G,vexnum;j+)cout<<setw(8)<<G.arcsij.adj;if(1nc1nfo)if(G.arcsij.adj!=INFINITY)cout<<setw(6)<<G,arcsij.info;e1secout<<setw(6)<<,zz,;)cout<<end1;)Iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii/广度优先boo1ViSited100;随便设置一百个布尔值voidInitQueue(1inkQueue&Q)Q.front=Q.rear=(QueuePtr)ma1Ioc(sizeof(QNode);if(!Q.front)exit(-1);Q.front->next=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队头等于队尾！"<<end1;p=Q.front->next;e-p->data;Q.front->next=p->next;if(Q.rear=p)Q.rear=Q.front;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;i<G.vexnum;i+)if(G.arcsvi.adj!=INFINITY)num=i;break;returnnum;)intNextAdjVex(MGraphG,intv,intw)inti,num=-1;for(i-w+1;i<G,vexnum;i+)if(G.arcsvi.adj!=INFINITY)num=i;break;)returnnum;)voidBFSTraverse(MGraphG)intv;intu;出队元素intw;1inkQueueQ;for(v=0;v<G*vexnum;v+)visitedv=O;InitQueue(Q);for(v=0;v<G.vexnum;v+)if(!visitedv)visitedv=1;visit(G,v);EnQueue(Q,v);whi1e(!QueueEmpty(Q)DeQueue(Q,u);for(W=FirstAdjVex(G,u);w>=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