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

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

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

4、ne Null 0/廣度優先#define INFINITY 10000/最大值,無窮#define MAX_VERTEX_NUM 20/最大頂點個數,即可以計算的最大規模typedef struct ArcCellfloat adj;/無權圖為 1 或 0,有權圖為權重char info30;/該弧相關信息ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM; typedef structchar vexsMAX_VERTEX_NUM20;/頂點向量,如 v1,v2,.等AdjMatrix arcs;int vexnum,arcnum;MGraph;/廣

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

6、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 temp10020;/這個temp 不能放到本函數內,or,G.vexsi引用他時,賦了值,跳出這個函數就沒有值.這樣不好/scanf(&G.vexnum,&G.arcnum,&IncInfo);cout構建有向圖請輸入數字 1,構建無向圖請輸入其

7、他數字 (無向圖請輸入上三角的邊).direct;cout各頂點無信息則輸入數字 0,有信息輸入其他數字.IncInfo;cout請輸入頂點和弧數目:G.vexnumG.arcnum;cout請輸入G.vexnum個頂點的符號,如 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)/循環弧的次數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頂點數是:G.vexnumendl; cout弧數是:G.arcnumendl; cout各頂點分別是:; 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隊頭等于隊尾!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個頂點endl; cout即G.vexsv頂點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;/出隊元素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);/廣度優先void main()MGraph G;CreateNet(G);/這時上面已經求出 G.vexnum 即頂點個數BFSTraverse(G);使用該算法注意的問題：