大連理工大學(xué)遠(yuǎn)程與繼續(xù)教育學(xué)院《人工智能》大作業(yè)答案

1、大連理工大學(xué)遠(yuǎn)程與繼續(xù)教育學(xué)院人工智能課程設(shè)計(jì)學(xué)習(xí)中心： 奧鵬遠(yuǎn)程教育青島學(xué)習(xí)中心（直屬）25 專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)年級(jí)：19 年 秋季學(xué)號(hào)：191032407940學(xué)生：題目：題目五：廣度優(yōu)先搜索算法談?wù)勀銓?duì)本課程學(xué)習(xí)過程中的心得體會(huì)與建議？人工智能是計(jì)算機(jī)專業(yè)的專業(yè)課之一。本課程主要介紹如何用計(jì)算機(jī)來模擬人類智能，如何用計(jì)算機(jī)實(shí)現(xiàn)諸如問題求解、規(guī)劃推理、模式識(shí)別、知識(shí)工程、自然語言處理、機(jī)器學(xué)習(xí)等只有人類才具備的智能，使得計(jì)算機(jī)更好的為人類服務(wù)。該課程是計(jì)算機(jī)科學(xué)理論基礎(chǔ)研究的重要組成部分，是計(jì)算機(jī)科學(xué)技術(shù)專業(yè)的專業(yè)拓展課，適合計(jì)算機(jī)專業(yè)人員使用。該課程是計(jì)算機(jī)科學(xué)理論基礎(chǔ)研究的重要組成

2、部分，是計(jì)算機(jī)科學(xué)技術(shù)專業(yè)的專業(yè)拓展課，適合計(jì)算機(jī)專業(yè)人員使用。這門課程需要學(xué)生掌握人工智能的基本概念、基本方法，會(huì)用知識(shí)表示方法、推理方法和機(jī)器學(xué)習(xí)等方法求解簡(jiǎn)單問題。人工智能課程設(shè)計(jì), 從以下 5 個(gè)題目中任選其一作答。人工智能課程設(shè)計(jì)題目五：廣度優(yōu)先搜索算法要求：（1）撰寫一份 word 文檔，里面包括（算法思路、算法程序框圖、主要函數(shù)代碼）章節(jié)。算法思路：簡(jiǎn)單介紹該算法的基本思想，至少 100 字。算法程序框圖：繪制流程圖或原理圖，從算法的開始到結(jié)束的程序框圖。主要函數(shù)代碼：列出算法的具體代碼。簡(jiǎn)單描述在人工智能的哪些領(lǐng)域需要使用廣度優(yōu)先搜索算法。答：人工智能(Artificial I

3、ntelligence，簡(jiǎn)記為 AI)是當(dāng)前科學(xué)技術(shù)迅速發(fā)展及新思想、新理 廣度優(yōu)先搜索,即 BFS(Breadth First Search)，是一種相當(dāng)常用的圖算法，其特點(diǎn)是：每次搜索指定點(diǎn)，并將其所有未訪問過的鄰近節(jié)點(diǎn)加入搜索隊(duì)列，循環(huán)搜索過程直到隊(duì)列為空。算法描述如下：將起始節(jié)點(diǎn)放入隊(duì)列尾部While(隊(duì)列不為空）取得并刪除隊(duì)列首節(jié)點(diǎn) Node 處理該節(jié)點(diǎn) Node把 Node 的未處理相鄰節(jié)點(diǎn)加入隊(duì)列尾部#include stdafx.h#include/構(gòu)造有向圖 p162,無向圖 p168 #include#include#include/包含 exit 函數(shù)/廣度優(yōu)先#defi

4、ne Null 0/廣度優(yōu)先#define INFINITY 10000/最大值,無窮#define MAX_VERTEX_NUM 20/最大頂點(diǎn)個(gè)數(shù),即可以計(jì)算的最大規(guī)模typedef struct ArcCellfloat adj;/無權(quán)圖為 1 或 0,有權(quán)圖為權(quán)重char info30;/該弧相關(guān)信息ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM; typedef structchar vexsMAX_VERTEX_NUM20;/頂點(diǎn)向量,如 v1,v2,.等AdjMatrix arcs;int vexnum,arcnum;MGraph;/廣

5、度優(yōu)先typedef struct QNodeint data;struct QNode *next;QNode,*QueuePtr; typedef structQueuePtr front;/隊(duì)頭指針QueuePtr rear;/隊(duì)尾指針LinkQueue;/廣度優(yōu)先int LocateVex(MGraph G,char *v)int i,num=-1; for(i=0;iG.vexnum;i+)if(strcmp(v,G.vexsi)=0)/相等時(shí)為 0,大于為正,小于為負(fù)num=i; break;if(num0)cout沒有匹配的頂點(diǎn),輸入錯(cuò)誤!endl; return -1;else

6、return num;void CreateNet(MGraph &G)int i,j,k,s=0;int IncInfo=-1;/IncInfo 為 0 則各弧不含其它信息,有信息則為其他數(shù)字char v220;/存放一條邊的兩個(gè)頂點(diǎn)char *p;float w;/輸入的權(quán)重int direct=-1;/有向圖為 1,無向圖為其他數(shù)字/char temp10020;/這個(gè)temp 不能放到本函數(shù)內(nèi),or,G.vexsi引用他時(shí),賦了值,跳出這個(gè)函數(shù)就沒有值.這樣不好/scanf(&G.vexnum,&G.arcnum,&IncInfo);cout構(gòu)建有向圖請(qǐng)輸入數(shù)字 1,構(gòu)建無向圖請(qǐng)輸入其

7、他數(shù)字 (無向圖請(qǐng)輸入上三角的邊).direct;cout各頂點(diǎn)無信息則輸入數(shù)字 0,有信息輸入其他數(shù)字.IncInfo;cout請(qǐng)輸入頂點(diǎn)和弧數(shù)目:G.vexnumG.arcnum;cout請(qǐng)輸入G.vexnum個(gè)頂點(diǎn)的符號(hào),如 v1,v2.endl; for(i=0;ip;/ 注 意 vexsMAX_VERTEX_NUM 中 的 MAX_VERTEX_NUM 大 于G.vexnumfor(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.arc

8、; p=0;/問題for(k=0;kG.arcnum;+k)/循環(huán)弧的次數(shù)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(IncInfo)coutp;if(direct!=1) G.arcsji=G.arcsij;cout頂點(diǎn)數(shù)是:G.vexnumendl; cout弧數(shù)是:G.arcnumendl; cout各頂點(diǎn)分別是:; for(i=0;iG.vexnum;i+) cou

9、tG.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.; elsecoutsetw(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.r

10、ear-next=p;Q.rear=p;void DeQueue(LinkQueue &Q,int &e)QueuePtr p; if(Q.front=Q.rear)cout隊(duì)頭等于隊(duì)尾!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;else return 0;void visit(MGraph G,int v)cout訪問了第v個(gè)頂點(diǎn)endl; cout即G.vexsv頂點(diǎn)endl;i

11、nt 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 NextAdjVex(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;/出隊(duì)元素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; visit(G,w);EnQueue(Q,w);/廣度優(yōu)先void main()MGraph G;CreateNet(G);/這時(shí)上面已經(jīng)求出 G.vexnum 即頂點(diǎn)個(gè)數(shù)BFSTraverse(G);使用該算法注意的問題：