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

大连理工大学远程与继续教育学院《人工智能》课程设计学习中心：奥鹏远程教育青岛学习中心（直属）[25]专业：计算机科学与技术年级：19年秋季学号：191032407940学生：王希龙题目：题目五：广度优先搜索算法1.谈谈你对本课程学习过程中的心得体会与建议？《人工智能》是计算机专业的专业课之一。本课程主要介绍如何用计算机来模拟人类智能，如何用计算机实现诸如问题求解、规划推理、模式识别、知识工程、自然语言处理、机器学习等只有人类才具备的智能，使得计算机更好的为人类服务。该课程是计算机科学理论基础研究的重要组成部分，是计算机科学技术专业的专业拓展课，适合计算机专业人员使用。该课程是计算机科学理论基础研究的重要组成部分，是计算机科学技术专业的专业拓展课，适合计算机专业人员使用。这门课程需要学生掌握人工智能的基本概念、基本方法，会用知识表示方法、推理方法和机器学习等方法求解简单问题。2.《人工智能》课程设计,从以下5个题目中任选其一作答。《人工智能》课程设计题目五：广度优先搜索算法要求：（1）撰写一份word文档，里面包括（算法思路、算法程序框图、主要函数代码）章节。（2）算法思路：简单介绍该算法的基本思想，至少100字。（3）算法程序框图：绘制流程图或原理图，从算法的开始到结束的程序框图。（4）主要函数代码：列出算法的具体代码。（5）简单描述在人工智能的哪些领域需要使用广度优先搜索算法。答：人工智能(ArtificialIntelligence，简记为AI)是当前科学技术迅速发展及新思想、新理广度优先搜索,即BFS(BreadthFirstSearch)，是一种相当常用的图算法，其特点是：每次搜索指定点，并将其所有未访问过的邻近节点加入搜索队列，循环搜索过程直到队列为空。算法描述如下：（1）将起始节点放入队列尾部（2）While(队列不为空）取得并删除队列首节点Node处理该节点Node把Node的未处理相邻节点加入队列尾部#include"stdafx.h"#include<iostream.h>//构造有向图p162,无向图p168#include<string.h>#include<iomanip.h>#include<stdlib.h>//包含exit函数//////////////////////////////广度优先#defineNull0//////////////////////////////广度优先#defineINFINITY10000//最大值,无穷#defineMAX_VERTEX_NUM20//最大顶点个数,即可以计算的最大规模typedefstructArcCell{floatadj;//无权图为1或0,有权图为权重charinfo[30];//该弧相关信息}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefstruct{charvexs[MAX_VERTEX_NUM][20];//顶点向量,如v1,v2,...等AdjMatrixarcs;intvexnum,arcnum;}MGraph;//////////////////////////////广度优先typedefstructQNode{intdata;structQNode*next;}QNode,*QueuePtr;typedefstruct{QueuePtrfront;//队头指针QueuePtrrear;//队尾指针}LinkQueue;//////////////////////////////广度优先intLocateVex(MGraphG,char*v){inti,num=-1;for(i=0;i<G.vexnum;i++){if(strcmp(v,G.vexs[i])==0)//相等时为0,大于为正,小于为负{num=i;break;}}if(num<0){cout<<"没有匹配的顶点,输入错误!"<<endl;return-1;}elsereturnnum;}voidCreateNet(MGraph&G){inti,j,k,s=0;intIncInfo=-1;//IncInfo为0则各弧不含其它信息,有信息则为其他数字charv[2][20];//存放一条边的两个顶点char*p;floatw;//输入的权重intdirect=-1;//有向图为1,无向图为其他数字//chartemp[100][20];//这个temp不能放到本函数内,or,G.vexs[i]引用他时,赋了值,跳出这个函数就没有值.这样不好//scanf(&G.vexnum,&G.arcnum,&IncInfo);cout<<"构建有向图请输入数字1,构建无向图请输入其他数字(无向图请输入上三角的边)."<<endl;cin>>direct;cout<<"各顶点无信息则输入数字0,有信息输入其他数字."<<endl;cin>>IncInfo;cout<<"请输入顶点和弧数目:"<<endl;cin>>G.vexnum>>G.arcnum;cout<<"请输入"<<G.vexnum<<"个顶点的符号,如v1,v2..."<<endl;for(i=0;i<G.vexnum;++i){p=G.vexs[i];cin>>p;//注意vexs[MAX_VERTEX_NUM]中的MAX_VERTEX_NUM大于G.vexnum}for(i=0;i<G.vexnum;i++){cout<<G.vexs[i]<<"";}for(i=0;i<G.vexnum;++i){for(j=0;j<G.vexnum;++j){G.arcs[i][j].adj=INFINITY;p=G.arcs[i][j].info;p='\0';///////////////////////////////问题}}for(k=0;k<G.arcnum;++k)//循环弧的次数{cout<<"第"<<k+1<<"次输入:"<<endl;cout<<"出发点:";p=v[0];cin>>p;i=LocateVex(G,p);cout<<"接受点:";p=v[1];cin>>p;j=LocateVex(G,p);cout<<"权重:";cin>>w;//输入格式:v1v218cout<<"i="<<i<<"j="<<j<<endl;G.arcs[i][j].adj=w;if(IncInfo){cout<<"输入信息:";p=G.arcs[i][j].info;cin>>p;}if(direct!=1)G.arcs[j][i]=G.arcs[i][j];}cout<<"顶点数是:"<<G.vexnum<<endl;cout<<"弧数是:"<<G.arcnum<<endl;cout<<"各顶点分别是:";for(i=0;i<G.vexnum;i++)cout<<G.vexs[i]<<"";cout<<endl;for(i=0;i<G.vexnum;i++){for(j=0;j<G.vexnum;j++){cout<<setw(8)<<G.arcs[i][j].adj;if(IncInfo){if(G.arcs[i][j].adj!=INFINITY)cout<<setw(6)<<G.arcs[i][j].info;elsecout<<setw(6)<<"";}}cout<<endl;}}////////////////////////////////////////////////////////////////////广度优先boolvisited[100];//随便设置一百个布尔值voidInitQueue(LinkQueue&Q){Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));if(!Q.front)exit(-1);Q.front->next=Null;}voidEnQueue(LinkQueue&Q,inte){QueuePtrp;p=(QueuePtr)malloc(sizeof(QNode));if(!p)exit(-1);p->data=e;p->next=Null;Q.rear->next=p;Q.rear=p;}voidDeQueue(LinkQueue&Q,int&e){QueuePtrp;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);}intQueueEmpty(LinkQueue&Q){if(Q.front==Q.rear)return1;elsereturn0;}voidvisit(MGraphG,intv){cout<<"访问了第"<<v<<"个顶点"<<endl;cout<<"即"<<G.vexs[v]<<"顶点"<<endl;}intFirstAdjVex(MGraphG,intv){inti,num=-1;for(i=0;i<G.vexnum;i++){if(G.arcs[v][i].adj!=INFINITY){num=i;break;}}returnnum;}intNextAdjVex(MGraphG,intv,intw){inti,num=-1;for(i=w+1;i<G.vexnum;i++){if(G.arcs[v][i].adj!=INFINITY){num=i;break;}}returnnum;}voidBFSTraverse(MGraphG){intv;intu;//出队元素intw;LinkQueueQ;for(v=0;v<G.vexnum;v++)visited[v]=0;InitQueue(Q);for(v=0;v<G.vexnum;v++){if(!visited[v]){visited[v]=1;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(!visited[w]){visited[w]=1;visit(G,w);EnQueue(Q,w);}}}}}}///////////////////////////广度优先voidmain(){MG