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

《大工21春《人工智能》大作业答案.pdf》由会员分享，可在线阅读，更多相关《大工21春《人工智能》大作业答案.pdf（12页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

2、计算机科学理论基础研究的重要组成部分，是计算机科学技术专业的专业拓展课，适合计算机专业人员使用。这门课程需要学生掌握人工智能的基本概念、基本方法，会用知识表示方法、推理方法和机器学习等方法求解简单问题。2.人工智能课程设计,从以下 5 个题目中任选其一作答。人工智能课程设计 题目五：广度优先搜索算法 要 求：（1）撰写一份word 文档，里面包括（算法思路、算法程序框图、主要函数代码）章节。（2）算法思路：简单介绍该算法的基本思想，至少 100 字。（3）算法程序框图：绘制流程图或原理图，从算法的开始大连理工大学远程与继续教育学院人工智能课程设计 到结束的程序框图。（4）主要函数代码：列出算法

3、的具体代码。（5）简单描述在人工智能的哪些领域需要使用广度优先搜索算法。答：人工智能(Artificial Intelligence，简记为 AI)是当前科学技术迅速发展及新思想、新理 广度优先搜索,即 BFS(Breadth First Search)，是一种相当常用的图算法，其特点是：每次搜索指定点，并将其所有未访问过的邻近节点加入搜索队列，循环搜索过程直到队列为空。算法描述如下：（1）将起始节点放入队列尾部（2）While(队列不为空）取得并删除队列首节点 Node 处理该节点 Node 把 Node 的未处理相邻节点加入队列尾部#include stdafx.h#include/构造有

4、向图 p162,无向图 p168#include#include#include/包含 exit 函数/广度优先#define Null 0/广度优先#define INFINITY 10000/最大值,无穷#define MAX_VERTEX_NUM 20/最大顶点个数,即可以计算的最大规模 typedef struct ArcCell float adj;/无权图为 1 或 0,有权图为权重 大连理工大学远程与继续教育学院人工智能课程设计 char info30;/该弧相关信息 ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef st

5、ruct char vexsMAX_VERTEX_NUM20;/顶点向量,如 v1,v2,.等 AdjMatrix arcs;int vexnum,arcnum;MGraph;/广度优先 typedef struct QNode int data;struct QNode*next;QNode,*QueuePtr;typedef struct QueuePtr front;/队头指针 QueuePtr rear;/队尾指针 LinkQueue;/广度优先 int LocateVex(MGraph G,char*v)int i,num=-1;for(i=0;iG.vexnum;i+)if(str

6、cmp(v,G.vexsi)=0)/相等时为 0,大于为正,小于为负 大连理工大学远程与继续教育学院人工智能课程设计 num=i;break;if(num0)cout没有匹配的顶点,输入错误!endl;return-1;else return num;void CreateNet(MGraph&G)int i,j,k,s=0;int IncInfo=-1;/IncInfo 为 0 则各弧不含其它信息,有信息则为其他数字 char v220;/存放一条边的两个顶点 char*p;float w;/输入的权重 int direct=-1;/有向图为 1,无向图为其他数字 /char temp100

7、20;/这个temp不能放到本函数内,or,G.vexsi引用他时,赋了值,跳出这个函数就没有值.这样不好 /scanf(&G.vexnum,&G.arcnum,&IncInfo);cout构建有向图请输入数字 1,构建无向图请输入其他数字(无向图请输入上三角的边).direct;大连理工大学远程与继续教育学院人工智能课程设计 cout各顶点无信息则输入数字 0,有信息输入其他数字.IncInfo;cout请输入顶点和弧数目:G.vexnumG.arcnum;cout请输入G.vexnum个顶点的符号,如 v1,v2.endl;for(i=0;ip;/注 意vexsMAX_VERTEX_NUM

8、 中 的MAX_VERTEX_NUM大 于G.vexnum for(i=0;iG.vexnum;i+)coutG.vexsi;for(i=0;iG.vexnum;+i)for(j=0;jG.vexnum;+j)G.arcsij.adj=INFINITY;p=G.arcsij.info;p=0;/问题 for(k=0;kG.arcnum;+k)/循环弧的次数 cout第k+1次输入:endl;coutp;i=LocateVex(G,p);coutp;j=LocateVex(G,p);coutw;/输入格式:v1 v2 18 couti=i j=jendl;G.arcsij.adj=w;if(In

9、cInfo)coutp;if(direct!=1)G.arcsji=G.arcsij;cout顶点数是:G.vexnumendl;cout弧数是:G.arcnumendl;cout各顶点分别是:;for(i=0;iG.vexnum;i+)coutG.vexsi;coutendl;for(i=0;iG.vexnum;i+)for(j=0;jG.vexnum;j+)大连理工大学远程与继续教育学院人工智能课程设计 coutsetw(8)G.arcsij.adj;if(IncInfo)if(G.arcsij.adj!=INFINITY)coutsetw(6)G.arcsij.info;else cou

10、tsetw(6);coutnext=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队头等于队尾!next;e=p-data;Q.front-next=p-next;if(Q.rear=p)Q.

11、rear=Q.front;free(p);int QueueEmpty(LinkQueue&Q)if(Q.front=Q.rear)return 1;else return 0;void visit(MGraph G,int v)cout访问了第v个顶点endl;cout即G.vexsv顶点endl;大连理工大学远程与继续教育学院人工智能课程设计 int FirstAdjVex(MGraph G,int v)int i,num=-1;for(i=0;iG.vexnum;i+)if(G.arcsvi.adj!=INFINITY)num=i;break;return num;int NextAdj

12、Vex(MGraph G,int v,int w)int i,num=-1;for(i=w+1;iG.vexnum;i+)if(G.arcsvi.adj!=INFINITY)num=i;break;return num;void BFSTraverse(MGraph G)int v;大连理工大学远程与继续教育学院人工智能课程设计 int u;/出队元素 int w;LinkQueue Q;for(v=0;vG.vexnum;v+)visitedv=0;InitQueue(Q);for(v=0;v=0;w=NextAdjVex(G,u,w)if(!visitedw)visitedw=1;visi

13、t(G,w);EnQueue(Q,w);大连理工大学远程与继续教育学院人工智能课程设计 /广度优先 void main()MGraph G;CreateNet(G);/这时上面已经求出 G.vexnum 即顶点个数 BFSTraverse(G);使用该算法注意的问题：（1）使用该算法关键的数据结构为：队列，队列保证了广度渡优先，并且每个节点都被处理到；（2）新加入的节点一般要是未处理过的，所以某些情况下最初要对所有节点进行标记；（3）广度优先在实际使用时，很对情况已超出图大连理工大学远程与继续教育学院人工智能课程设计 论的范围，将新节点加入队列的条件不再局限于相邻节点这个概念。例如，使用广度优先的网络爬虫在抓取网页时，会把一个链接指向的网页中的所 URL 加入队列供后续处理。