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

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

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

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

学习中心：

奥鹏远程教育青岛学习中心（直属）[25]

专业：

计算机科学与技术

年级：

19年秋季

学号：

************

学生：

王希龙

题目：

题目五：

广度优先搜索算法

1.谈谈你对本课程学习过程中的心得体会与建议？

《人工智能》是计算机专业的专业课之一。

本课程主要介绍如何用计算机来模拟人类智能，如何用计算机实现诸如问题求解、规划推理、模式识别、知识工程、自然语言处理、机器学习等只有人类才具备的智能，使得计算机更好的为人类服务。

该课程是计算机科学理论基础研究的重要组成部分，是计算机科学技术专业的专业拓展课，适合计算机专业人员使用。

该课程是计算机科学理论基础研究的重要组成部分，是计算机科学技术专业的专业拓展课，适合计算机专业人员使用。

这门课程需要学生掌握人工智能的基本概念、基本方法，会用知识表示方法、推理方法和机器学习等方法求解简单问题。

2.《人工智能》课程设计,从以下5个题目中任选其一作答。

《人工智能》课程设计

题目五：

广度优先搜索算法

要求：

（1）撰写一份word文档，里面包括（算法思路、算法程序框图、主要函数代码）章节。

（2）算法思路：

简单介绍该算法的基本思想，至少100字。

（3）算法程序框图：

绘制流程图或原理图，从算法的开始到结束的程序框图。

（4）主要函数代码：

列出算法的具体代码。

（5）简单描述在人工智能的哪些领域需要使用广度优先搜索算法。

答：

人工智能（ArtificialIntelligence，简记为AI）是当前科学技术迅速发展及新思想、新理广度优先搜索,即BFS（BreadthFirstSearch），是一种相当常用的图算法，其特点是：

每次搜索指定点，并将其所有未访问过的邻近节点加入搜索队列，循环搜索过程直到队列为空。

算法描述如下：

（1）将起始节点放入队列尾部

（2）While（队列不为空）

取得并删除队列首节点Node

处理该节点Node

把Node的未处理相邻节点加入队列尾部

#include"stdafx.h"

#include//构造有向图p162,无向图p168

#include

#include

#include//包含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

{

if（strcmp（v,G.vexs[i]）==0）//相等时为0,大于为正,小于为负

{

num=i;

break;

}

}

if（num<0）

{

cout<<"没有匹配的顶点,输入错误!

"<

return-1;

}

else

returnnum;

}

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,构建无向图请输入其他数字（无向图请输入上三角的边）."<

cin>>direct;

cout<<"各顶点无信息则输入数字0,有信息输入其他数字."<

cin>>IncInfo;

cout<<"请输入顶点和弧数目:

"<

cin>>G.vexnum>>G.arcnum;

cout<<"请输入"<

for（i=0;i

{

p=G.vexs[i];

cin>>p;//注意vexs[MAX_VERTEX_NUM]中的MAX_VERTEX_NUM大于G.vexnum

}

for（i=0;i

{

cout<

}

for（i=0;i

{

for（j=0;j

{

G.arcs[i][j].adj=INFINITY;

p=G.arcs[i][j].info;

p='\0';///////////////////////////////问题

}

}

for（k=0;k

{

cout<<"第"<

"<

cout<<"出发点:

";

p=v[0];

cin>>p;

i=LocateVex（G,p）;

cout<<"接受点:

";

p=v[1];

cin>>p;

j=LocateVex（G,p）;

cout<<"权重:

";

cin>>w;//输入格式:

v1v218

cout<<"i="<

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<<"顶点数是:

"<

cout<<"弧数是:

"<

cout<<"各顶点分别是:

";

for（i=0;i

cout<

cout<

for（i=0;i

{

for（j=0;j

{

cout<

if（IncInfo）

{

if（G.arcs[i][j].adj!

=INFINITY）

cout<

else

cout<

}

}

cout<

}

}

////////////////////////////////////////////////////////////////////广度优先

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<<"队头等于队尾!

"<

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;

else

return0;

}

voidvisit（MGraphG,intv）

{

cout<<"访问了第"<

cout<<"即"<

}

intFirstAdjVex（MGraphG,intv）

{

inti,num=-1;

for（i=0;i

{

if（G.arcs[v][i].adj!

=INFINITY）

{

num=i;

break;

}

}

returnnum;

}

intNextAdjVex（MGraphG,intv,intw）

{

inti,num=-1;

for（i=w+1;i

{

if（G.arcs[v][i].adj!

=INFINITY）

{

num=i;

break;

}

}

returnnum;

}

voidBFSTraverse（MGraphG）

{

intv;

intu;//出队元素

intw;

LinkQueueQ;

for（v=0;v

visited[v]=0;

InitQueue（Q）;

for（v=0;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（）

{

MGraphG;

CreateNet（G）;

//这时上面已经求出G.vexnum即顶点个数

BFSTraverse（G）;

}

使用该算法注意的问题：

（1）使用该算法关键的数据结构为：

队列，队列保证了广度渡优先，并且每个节点都被处理到；

（2）新加入的节点一般要是未处理过的，所以某些情况下最初要对所有节点进行标记；（3）广度优先在实际使用时，很对情况已超出图论的范围，将新节点加入队列的条件不再局限于相邻节点这个概念。

例如，使用广度优先的网络爬虫在抓取网页时，会把一个链接指向的网页中的所URL加入队列供后续处理。