大工21春《人工智能》大作业答案.docx
大连理工大学远程与继续教育学院人工智能课程设计学习中心： 奥鹏远程教育青岛学习中心（直属）心5专 业：计算机科学与技术年 级： 19年秋季学 生：题 目：题目五：广度优先搜索算法L谈谈你对本课程学习过程中的心得体会与建议?人工智能是计算机专业的专业课之一。本课程主要介绍如何用计算机来 模拟人类智能，如何用计算机实现诸如问题求解、规划推理、模式识别、知识工 程、自然语言处理、机器学习等只有人类才具备的智能，使得计算机更好的为人 类服务。该课程是计算机科学理论基础研究的重要组成局部，是计算机科学技术专MBSMBS业的专业拓展课，适合计算机专业人员使用。该课程是计算机科学理论基础研究的 重要组成局部，是计算机科学技术专业的专业拓展课，适合计算机专业人员使用。这门课程需要学生掌握人工智能的基本概念、基本方法，会用知识表示方法、推理方法和机器学习等方法求解简单问题。 2.人工智能课程设计，从以下5个题目中任选其一作答。人工智能课程设计题目五：广度优先搜索算法要求：（1）撰写一份word文档，里面包括（算法思路、算法程序框图、主要函数代码）章节。0 算法思路：简单介绍该算法的基本思想，至少100字。0 算法程序框图：绘制流程图或原理图，从算法的开始大连理工大学远程与继续教育学院人工智能课程设计int u;出队元素int w;LinkQueue Q;for(v=0;v<G. vexnum;v+)visitedv=O;InitQueue (Q);for(v=0;v<G. vexnum;v+)(if(!visitedv)visitedv=l;visit (G, v);EnQueue (Q, v);while(!QueueEmpty (Q)DeQueue (Q, u);for(w=FirstAdjVex(G, u);w>=0;w=NextAdjVex (G, u,w) if(!visitedw)visitedw=l;visit (G, w);EnQueue (Q, w);大连理工大学远程与继续教育学院人工智能课程设计/广度优先void main()MGraph G;CreateNet(G);这时上面已经求出G. vexnum即顶点个数BFSTraverse(G);)如如输入3个顶点的符号.班有问图请输入数字工，构各顶点无信息那么输入数字。，有信息输入其他数字.；1 21231 v2 V3笫1次输入：S点：”点：。2：2i=0 j=l2次输入：发点:u2遂点心2 EK - r7 J-数是点 1点数顶 二贝队于2 355 的了顶了顶了顶百 问U1问U2问 T 3 访即访即访即pru2lift)函410000y e kycuntinucA上三把的边工,11 x|使用该算法注意的问题：（1）使用该算法关键的数据结构为：队列，队列保证了广度渡优先，并且每个节点都被处理到；（2）新加入的节点一般要是未处理过的，所以某些情况下最初要对所有节点进行标记；（3）广度优先在实际使用时，很对情况已超出图大连理工大学远程与继续教育学院人工智能课程设计论的范围，将新节点加入队列的条件不再局限于相邻节点这个概念。例如，使用 广度优先的网络爬虫在抓取网页时，会把一个链接指向的网页中的所URL加入队 列供后续处理。大连理工大学远程与继续教育学院人工智能课程设计到结束的程序框图。 主要函数代码：列出算法的具体代码。6 简单描述在人工智能的哪些领域需要使用广度优先搜索算法。答：人工智能(Artificial Intelligence,简记为AI)是当前科学技术迅速开展及新思想、新理 广 度优先搜索，即BFS(Breadth First Search),是一种相当常用的图算法，其特 点是：每次搜索指定点，并将其所有未访问过的邻近节点加入搜索队列，循环搜 索过程直到队列为空。算法描述如下：(1)将起始节点放入队列尾部While(队列不为空)取得并删除队列首节点Node处理该节点Node把Node的未处理相邻节点加入队列尾部ttinclude “stdafx. h# includeiostream. h>构造有向图 pl62,无向图 pl68 #include<string. h>#include<iomanip. h># includestdlib.h包含 exit 函数广 度优先# define Null 0广度优先ttdefine INFINITY 10000最大值，无穷define MAX_VERTEX_NUM 20最大顶点个数，即可以计算的最大规模 typedef struct ArcCellfloat adj;无权图为1或0,有权图为权重大连理工大学远程与继续教育学院人工智能课程设计char info30;该弧相关信息ArcCel1, AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef structchar vexsMAX_VERTEX_NUM 20;顶点向量,如 vl, v2,.等 AdjMatrix arcs;int vexnum, arcnum;MGraph;广度优先typedef struct QNodeint data;struct QNode *next;QNode, *QueuePtr;typedef structQueuePtr front;队头指针QueuePtr rear;队尾指针LinkQueue;广度优先int LocateVex(MGraph G, char *v)(int i,num=-l;for (i=0;i<G. vexnum;i+)if (strcmp (v, G. vexsi)=0)相等时为0,大于为正，小于为负大连理工大学远程与继续教育学院人工智能课程设计num=i;break;if(num<0)(cout*没有匹配的顶点，输入错误! 0endl;return -1;elsereturn num;)void CreateNet(MGraph &G)int i, j, k, s=0;int Inclnfo=-l;lnclnfo为0那么各弧不含其它信息，有信息那么为其他数 字char v2 20;存放一条边的两个顶点char *p;float w;输入的权重int directs1;有向图为1,无向图为其他数字/char temp100 20;这个temp 不能放到本函数内，or, G. vexsi引用 他时,赋了值,跳出这个函数就没有值.这样不好/scanf(&G. vexnum, &G, arcnum, &lnclnfo);cout。构建有向图请输入数字1,构建无向图请输入其他数字(无向图请 输入上三角的边).endl;cin>>direct;大连理工大学远程与继续教育学院人工智能课程设计cout«各顶点无信息那么输入数字0,有信息输入其他数字. cin>>lnclnfo;cout<<请输入顶点和弧数目:，«endl;cin>>G. vexnum>>G. arcnum;cout<请输入G. vexnu水个顶点的符号，如vl, v2. zz«endl;for(i=0;i<G. vexnum;+i) (p=G. vexs i;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. arcsij. adj=INFINITY;p=G arcsij. info;p=' 0' ;/问题 for (k=0;k<G. arcnum; +k)循环弧的次数(cout第<k+l<次输入：endl;cout<<"出发点:"P=v0;大连理工大学远程与继续教育学院人工智能课程设计cin>>p;i=LocateVex (G,p);cout«接受点:；P=vl;cin>>p;j=LocateVex (G,p);cout权重：；cin>>w;输入格式：vl v2 18couti=j=zz<< j<<endl;G. arcsij. adj=w; if(Inclnfo)|cout<<输入信息:"p=G. arcsij. info;cin>>p;if(direct!=1)G. arcsj i=G. arcsi j;)cout<顶点数是:，Z«G. vexnum<<endl;cout<弧数是：G. arcnum<<endl;cout« 各顶点分别是:；for(i=0;i<G. vexnum;i+)cout<<G. vexsi<<z/ ；cout<<endl;for (i=0;i<G. vexnum;i+)for (j=0;j<G. vexnum;j+)大连理工大学远程与继续教育学院人工智能课程设计cout<<setw(8)<<G. arcsi j. adj ;if(Inclnfo)if (G. arcsij. adj!=INFINITY)cout<<setw(6)<<G. arcsij. info;elsecout<<setw(6) <<z/ ；cout<<endl;)/广度优先bool visited100;随便设置一百个布尔值void InitQueue(LinkQueue &Q)Q. front=Q. rear= (QueuePtr)malloc(sizeof(QNode);if (!Q. front)exit (-1);Q.front-next=Null;)void EnQueue(LinkQueue &Q, int e)(QueuePtr p;p=(QueuePtr)malloc(sizeof(QNode);if(!p)exit (-1);p->data=e;大连理工大学远程与继续教育学院人工智能课程设计p->next=Null;Q.rear->next=p;Q.rear=p;void DeQueue (LinkQueue &Q, int &e)(QueuePtr p;if (Q. front=Q. rear)cout<队头等于队尾！<<endl;p=Q. front->next;e=p->data;Q.front->next=p->next;if (Q. rear=p)Q rear=Q. front;free(p);int QueueEmpty(LinkQueue &Q)if (Q. front=Q. rear)return 1;elsereturn 0;)void visit (MGraph G, int v)cout<<"访问 了 第"<<v<<"个顶点”"endl;cout即G. vexs v顶点endl;大连理工大学远程与继续教育学院人工智能课程设计int FirstAdjVex(MGraph G, int v)int i,num=-l;for (i=0;i<G. vexnum;i+)(if(G. arcsvi.adj!=INFINITY)(num=i;break;return num;)int NextAdjVex(MGraph G, int v, int w) int i, num=-l;for(i=w+l;i<G. vexnum;i+)(if(G. arcsvi. adj!=INFINITY)(num=i;break;return num;void BFSTraverse (MGraph G)
