人工智能-實(shí)驗(yàn)四-城市交通圖的代價(jià)樹深度優(yōu)先搜索

實(shí) 驗(yàn) 報(bào) 告 4一、實(shí)驗(yàn)?zāi)康模赫莆丈疃葍?yōu)先搜索求解算法的基本思想。二、實(shí)驗(yàn)要求：用C語(yǔ)言實(shí)現(xiàn)城市交通圖的代價(jià)樹深度優(yōu)先搜索求解三、實(shí)驗(yàn)語(yǔ)言環(huán)境：C語(yǔ)言四、設(shè)計(jì)思路：解法：采用 代價(jià)樹的深度優(yōu)先搜索理論： 1. 首先根據(jù)交通圖，畫出代價(jià)圖代價(jià)圖 2. 開始搜索 open表存放剛剛生成的節(jié)點(diǎn)。 closed表存放將要擴(kuò)展的節(jié)點(diǎn)或已經(jīng)擴(kuò)展過(guò)的節(jié)點(diǎn)。背景：如圖是5城市之間交通路線圖，A城市是出發(fā)地，E城市是目的地，兩城市間的交通費(fèi)用(代價(jià))如圖中數(shù)字所示，求從A到E的最小費(fèi)用路線。 解法：采用 代價(jià)樹的廣度優(yōu)先搜索 理論： 1. 首先根據(jù)交通圖，畫出代價(jià)圖 代價(jià)圖 如圖 2. 開始搜索 oepn表存放剛剛生成的節(jié)點(diǎn)。 closed表存放將要擴(kuò)展的節(jié)點(diǎn)或已經(jīng)擴(kuò)展過(guò)的節(jié)點(diǎn)。 open表結(jié)構(gòu)： 代價(jià)|節(jié)點(diǎn)|父節(jié)點(diǎn) closed表結(jié)構(gòu)： 序號(hào)|節(jié)點(diǎn)|父節(jié)點(diǎn) 1) 把A放入 open表 open表： 0| A | 0 Closed表： 空 2) 把A從open表放入closed表 open表： 空 closed表： 1 | A | 0 3) 擴(kuò)展A，得C1，B1，放入open表 C1的代價(jià)：3 B1的代價(jià)：4 Open表： 3 | C1 | A 4 | B1 | A closed表： 1 | A | 0 4 | B1 | A closed表： 1 | A | 0 2 | C1 | A C1不是目標(biāo)節(jié)點(diǎn)，于是繼續(xù)擴(kuò)展 5) 把C1擴(kuò)展得到 D1，放入open表 D1的代價(jià)：3+2=5 B1的代價(jià)：4 open表： 4 | B1 | A 5 | D1 | C1 closed表： 1 | A | 0 2 | C1 | A 6) 把B1從open放入closed表 open表： 5 | D1 | C1 closed表： 1 | A | 0 2 | C1 | A 3 | B1 | A B1不是目標(biāo)節(jié)點(diǎn)，于是繼續(xù)擴(kuò)展 7) 擴(kuò)展B1得D2，E1，放入Open表 D2的代價(jià)：4+4=8 E1的代價(jià)：4+5=9 open表： 5 | D1 | C1 8 | D2 | B1 9 | E1 | B1 closed表： 1 | A | 0 2 | C1 | A 3 | B1 | A 8) 把D1從open表放入closed表 open表： 8 | D2 | B1 9 | E1 | B1 closed表： 1 | A | 0 2 | C1 | A 3 | B1 | A 4 | D1 | C1 D1不是目標(biāo)節(jié)點(diǎn)，于是繼續(xù)擴(kuò)展 9) 把D1擴(kuò)展得到E2，B2，放入open表 E2的代價(jià)：3+2+3=8 B2的代價(jià)：3+2+4=9 D2的代價(jià)：8 E1的代價(jià)：9 open表： 8 | E2 | D1 8 | D2 | B1 9 | B2 | D1 9 | E1 | B1 closed表： 1 | A | 0 2 | C1 | A 3 | B1 | A 4 | D1 | C1 10) 把E2從open表放入closed表 open表： 8 | D2 | B1 9 | B2 | D1 9 | E1 | B1 closed表： 1 | A | 0 2 | C1 | A 3 | B1 | A 4 | D1 | C1 5 | E2 | D1 E2 是目標(biāo)節(jié)點(diǎn)，搜索結(jié)束。 則搜索路徑 A - C1 - D1 -E2 即：A - C - D - E 五、實(shí)驗(yàn)代碼：#include #include #define INF 32767 /*INF表示*/typedef int InfoType;typedef char Vertex;#defineMAXV 6 /*最大頂點(diǎn)個(gè)數(shù)*/*以下定義鄰接矩陣類型*/typedef struct /*圖的定義*/ InfoType edgesMAXVMAXV; /*鄰接矩陣*/ int n,e; /*頂點(diǎn)數(shù)，弧數(shù)*/Vertex vexsMAXV; /*存放頂點(diǎn)信息*/ MGraph;/*圖的鄰接矩陣類型*/*以下定義鄰接表類型*/typedef struct ANode /*弧的結(jié)點(diǎn)結(jié)構(gòu)類型*/int adjvex; /*該弧的終點(diǎn)位置*/ struct ANode *nextarc; /*指向下一條弧的指針*/ InfoType info; /*該弧的相關(guān)信息,這里用于存放權(quán)值*/ ArcNode;typedef struct Vnode /*鄰接表頭結(jié)點(diǎn)的類型*/Vertex data; /*頂點(diǎn)信息*/ ArcNode *firstarc; /*指向第一條弧*/ VNode;typedef VNode AdjListMAXV;/*AdjList是鄰接表類型*/typedef struct AdjList adjlist; /*鄰接表*/ int n,e; /*圖中頂點(diǎn)數(shù)n和邊數(shù)e*/ ALGraph; /*圖的鄰接表類型*/typedef struct char vi,vj; int info;etype;typedef struct CLOSEDListint id; /記住矢量int datan;int cost;int dad;/記住父節(jié)點(diǎn) 回溯用closed; /open表和close表都用這個(gè)類型void MatToList(MGraph g,ALGraph *&G)/*將鄰接矩陣g轉(zhuǎn)換成鄰接表G*/int i,j,n=g.n;ArcNode *p;G=(ALGraph *)malloc(sizeof(ALGraph);for (i=0;iadjlisti.firstarc=NULL;G-adjlisti.data=g.vexsi;for (i=0;i=0;j-)if (g.edgesij!=INF) p=(ArcNode *)malloc(sizeof(ArcNode);p-adjvex=j;p-info=g.edgesij;p-nextarc=G-adjlisti.firstarc;G-adjlisti.firstarc=p;G-n=n;G-e=g.e;void ListToMat(ALGraph *G,MGraph &g)/*將鄰接表G轉(zhuǎn)換成鄰接矩陣g*/int i,j,n=G-n;ArcNode *p;for(i=0;in;i+)for(j=0;jn;j+)g.edgesij=INF;for (i=0;iadjlisti.data;p=G-adjlisti.firstarc; while (p!=NULL) g.edgesip-adjvex=p-info; p=p-nextarc;g.n=n;g.e=G-e;void DispMat(MGraph g)/*輸出鄰接矩陣g*/int i,j;for (i=0;ig.n;i+)for (j=0;jg.n;j+)if (g.edgesij=INF)printf(%3s,);elseprintf(%3d,g.edgesij);printf(n);void DispAdj(ALGraph *G)/*輸出鄰接表G*/int i;ArcNode *p;for (i=0;in;i+)p=G-adjlisti.firstarc; printf(n%3d %c : ,i,G-adjlisti.data );while (p!=NULL)printf(-%d(%d),p-adjvex,p-info);p=p-nextarc;printf(n);void creatmat(MGraph &g,char vex,int n,etype edge,int e)/建立鄰接矩陣g.n=n;g.e=e; int k,i,j;for(k=0;kn;k+) g.vexsk=vexk; for(i=0;in;i+)for(j=0;jn;j+)g.edgesij=INF;for(k=0;kn=n;G-e=e;int k,i,j;for (i=0;iadjlisti.firstarc=NULL;G-adjlisti.data=vexi;for(k=0;kadjlisti.data !=edgek.vi) i+; j=0; while(G-adjlistj.data !=edgek.vj) j+; p=(ArcNode *)malloc(sizeof(ArcNode); p-adjvex=j; p-info=; p-nextarc=G-adjlisti.firstarc; G-adjlisti.firstarc=p; p=(ArcNode *)malloc(sizeof(ArcNode); p-adjvex=i; p-info=; p-nextarc=G-adjlistj.firstarc; G-adjlistj.firstarc=p;/char dfsv10;char bfsv10;int k;int visited10;/*void DFS(ALGraph *G,int v)/深度優(yōu)先遍歷 ArcNode *p; int w; dfsvk=G-adjlistv.data;k+; visitedv=1; p=G-adjlistv.firstarc; while(p!=NULL) w=p-adjvex; if(visitedw=0) DFS(G,w); p=p-nextarc; */*void BFS(ALGraph *G,int v,int dest) /廣度優(yōu)先搜索,v是出發(fā)結(jié)點(diǎn)序號(hào)，dest是目標(biāo)節(jié)點(diǎn)序號(hào)closed op20;/定義open表大小closed cl20; /定義closed表大小 int front,rear; /定義指針 int crear=-1; int cost=0; /定義費(fèi)用變量 ArcNode *p; front=rear=-1; k=0; rear+; oprear.id=0; oprear.datan=0; oprear.cost=0; oprear.dad=-1; while(frontadjlistii.data;ii=clii.dad;to+;for(int j=to-1;j=0;j-)printf(%c-,toprtj);printf(%cn,G-adjlistclcrear.datan.data);/printf(Least cost: %dnn,clcrear.cost);return;p=(ArcNode *)malloc(sizeof(ArcNode); p=G-adjlistclcrear.datan.firstarc; /first tobe 擴(kuò)展結(jié)點(diǎn) while(p!=NULL) /若不是目標(biāo)節(jié)點(diǎn)，則對(duì)其擴(kuò)展，并將擴(kuò)展結(jié)果放入open表表尾部 rear+;oprear.id=rear; /open新節(jié)點(diǎn)位置oprear.dad=crear; /記錄父節(jié)點(diǎn)在close表中的位置，方便后來(lái)回溯oprear.datan=p-adjvex; /是哪個(gè)字符，即位置oprear.cost=clcrear.cost+p-info;/計(jì)算費(fèi)用p=p-nextarc; int i=rear,j;bool exchange=true; /將open表在所有待擴(kuò)展范圍內(nèi)全排序，代價(jià)小的在上面。排序方法：冒泡closed temp;while(exchange) exchange=false; for(j=front+1;ji;j+) if( opj.costopj.cost) temp=opj+1;opj+1=opj;opj=temp;exchange=true; i-; /*/以下為主函數(shù)；void main()MGraph g;char vex=abcde; etype edge=a,b,4, a,c,