盲目搜索算法

實(shí)驗(yàn)一：盲目搜索算法—、實(shí)驗(yàn)?zāi)康模赫莆丈疃葍?yōu)先搜索求解算法的基本思想。二、 實(shí)驗(yàn)要求：用C語言實(shí)現(xiàn)城市交通圖的代價(jià)樹深度優(yōu)先搜索求解三、 實(shí)驗(yàn)語言環(huán)境：C語言、設(shè)計(jì)思路:解法：采用代價(jià)樹的深度優(yōu)先搜索理論：1.首先根據(jù)交通圖,畫出代價(jià)圖代價(jià)圖2.開始搜索open表存放剛剛生成的節(jié)點(diǎn)。closed表存放將要擴(kuò)展的節(jié)點(diǎn)或已經(jīng)擴(kuò)展過的節(jié)點(diǎn)。背景：如圖是5城市之間交通路線圖，A城市是出發(fā)地，E城市是目的地，兩城市間的交通費(fèi)用（代價(jià)）如圖中數(shù)字所示，求從A至UE的最小費(fèi)用路線。圖1 圖2解法：采用代價(jià)樹的廣度優(yōu)先搜索理論：首先根據(jù)交通圖1,畫出代價(jià)圖代價(jià)圖如圖2開始搜索oepn表存放剛剛生成的節(jié)點(diǎn)。closed表存放將要擴(kuò)展的節(jié)點(diǎn)或已經(jīng)擴(kuò)展過的節(jié)點(diǎn)。open表結(jié)構(gòu)：［代價(jià)］I［節(jié)點(diǎn)］I［父節(jié)點(diǎn)］closed表結(jié)構(gòu)：［序號(hào)］I［節(jié)點(diǎn)］I［父節(jié)點(diǎn)］1） 把A放入open表open表：0|A|0Closed表：空2） 把A從open表放入closed表open 表 :空closed表：IA|03） 擴(kuò)展A,得Cl,Bl,放入open表Open表：|Cl|A|Bl|Aclosed表：IA|04|Bl|Aclosed表：IA|0|Cl|ACl不是目標(biāo)節(jié)點(diǎn)，于是繼續(xù)擴(kuò)展5）把Cl擴(kuò)展得到D1,放入open表D1的代價(jià)：3+2=5B1的代價(jià)：4open表：|B1|A|D1|Clclosed表：|A|0ClACl的代價(jià)：3Bl的代價(jià)：4 6）把Bl從open放入closed表open表：5|DI|Clclosed表：|A|0|Cl|A|Bl|ABl不是目標(biāo)節(jié)點(diǎn)，于是繼續(xù)擴(kuò)展7） 擴(kuò)展Bl得D2,E1,放入Open表D2的代價(jià):4+4=8E1的代價(jià)：4+5=9open表：5|D1|C18|D2|B19|E1|B1closed表：IA|0|Cl|A|Bl|A8） 把DI從open表放入closed表open表：8D2Bl9|E1|B1closed表：TOC\o"1-5"\h\zI A| 0| Cl | A| Bl | A| DI | ClDI不是目標(biāo)節(jié)點(diǎn)，于是繼續(xù)擴(kuò)展9）把D1擴(kuò)展得到E2,B2,放入open表E2的代價(jià)：3+2+3=8B2的代價(jià)：3+2+4=9D2的代價(jià)：8E1的代價(jià)：9open表：8|E2|D18|D2|Bl9|B2|D19|E1|B1closed表：1A02|ClAclosed表：3|BlA1A04IDICl2ClA10)把E2從open表放入closed3BlA表4DICl5E2DIopen表：E2是目標(biāo)節(jié)點(diǎn)，搜索結(jié)束。8|D2Bl則搜索路徑A-Cl-DI-E29B2DI即：A-C-D-E9|E1Bl五、實(shí)驗(yàn)代碼:#iiiclude<stdio.h>#iiiclude<malloc.h>^defineINF32767/*INF表示8*/typedefintInfbType;typedefcharVertex;#defineMAXV6/*最大頂點(diǎn)個(gè)數(shù)*//*以下定義鄰接矩陣類型*/typedefstmct( IiifoT^eedges[MAXV][MAXV];/*鄰接矩陣*/intii,e;Vertexvexs[MAXV];}MGraph;/*圖的定義*//*頂點(diǎn)數(shù)，孤數(shù)*//*存放頂點(diǎn)信息*//*圖的鄰接矩陣類型*//*以卜定義鄰接表類型*/typedefstmctANode(intadjvex;/*弧的結(jié)點(diǎn)結(jié)構(gòu)類型*//*該孤的終點(diǎn)位置*//*指向下一條弧的指針*//*/*指向下一條弧的指針*//*該孤的相關(guān)信息，這里用于存放權(quán)值*//*鄰接表頭結(jié)點(diǎn)的類型*//*頂點(diǎn)信息*//*指向第一條弧*//*AdjList是鄰接表類型*//*鄰接表*//*圖中頂點(diǎn)數(shù)11和邊數(shù)e*//*圖的鄰接表類型*/InfoTypeiiifb;}ArcNode;typedefstructVnode(Vertexdata;AicNode*fkstaic;)VNode;typedefVNodeAdjListfMAXV];typedefstmct(AdjListadjlist;mtn,e;}ALGraph;typedefstmct{chatmtinfb;}etype;typedefstructCLOSEDList{mtid; 〃記住矢量intdatan;intcost;nitdad;〃記住父節(jié)點(diǎn)回溯用Jclosed;//open表和close表都用這個(gè)類型voidMatToList(MGraphg^ALGraph*&G)/*將鄰接矩陣g轉(zhuǎn)換成鄰接表G*/{nitij,n=g.n;AicNode*p;G=(ALGraph*)malloc(sizeof(ALGiaph));for(i=O;i<n;i++)G->adjlist[i].firstaic=NULL;G->adjlist[i].data=g.vexs[i];)for(i=O;i<n;i++)for(j=n-lj>=Oj-)if(g.edges[i][j]!=INF)p=(AicNode*)malloc(sizeof(AicNode));p->adjvex=j;p->infb=g.edges[i][j];p->nextarc=G->adjlist[i].firstaic;G->adjlist[i].firstarc=p;)G->n=n:G->e=g.e;}voidListToMat(ALGraph*QMGraph&g)/*將鄰接表G轉(zhuǎn)換成鄰接矩陣g*/{inti,j,n=G?>n;AicNode*p;fbi(i=O;i<n;i++)for(j=Oj<nj++)g.edges[i]|j]=INF;for(i=O;i<n;i++){ g.vexs[i]=G->adjlist[i].data;p=G->adjlist[i].firstaic;while(p!=NULL)(g.edges[i][p->adjvex]=p->infb;p=p->nextarc;)}g.n=n;g.e=G->e;}voidDispMat(MGraphg)/*輸出鄰接矩陣g*/{intij;for(i=0;i<g.n;i-H-)fIfor(j=0jvg.nj++)if(g.edges[i][j]=INF)pnntf(”％3s”,”8”)；elsepnntf(”％3d”,g.edges[i][j]);pnntR”\n");}}voidDispAdj(ALGiaph*G)/*輸出鄰接表G*/{inti;AicNode*p;for(i=0;i<G->n;i++)p=G->adjlist[i].firstare;priiitf(M\ii%3d%c:”,i,G4adjlist[i].data);while(p!=NULL)(prmtf(n—>%d(%d),\p->adjvex,p->iiifb);p=p->nextarc;)pnntR”\n");}}voidcreatmat(MGraph&g?charvex[]jntn.etypeedge[],mte)〃建立鄰接矩陣(g.n=n;g.e=e;intk,i,j;fbr(k=O;k<n;k++)g.vexs[k]=vex[k];fbi(i=O;i<n;i-H-)for(j=Oj<nj++)g.edges[i]|j]=INF;fbr(k=O;k<e;k++)(1=0；while(g.vexs[i]!=edge[k].vi)i++；J=0；while(g.vexs[j]?=edge[k].vj)j++;g.edges[i][j]=g.edges[j][i]=edge[k].infb;}}voidcreatluik(ALGiaph*&Qcharvex[].iiitn.etypeedge[].iiite)〃建立鄰接表(AicNode*p;G=(ALGraph*)malloc(sizeof(ALGraph));G->n=n:G->e=e;intk,ij;for(i=0;i<n;i++)fG->adjlist[i].firstaic=NULL;G->adjlist[i].data=vex[i];}fbr(k=O;k<e;k++)

1=0；while(G->adjlist[i].data!=edge[k].vi)i++；J=0；while(G->adjlist[j].data!=edge[k].vj)j++;p=(AicNode*)malloc(sizeof(AicNode));p->adjvex^j;p->infb=edge[k].iiifb;p->nextarc=G->adjlist[i].firstaic;G->adjlist[i].fiistarc=p;p=(AicNode*)malloc(sizeof(AicNode));p->adjvex=i;p->infb=edge[k].iiifb;p->nextarc=G->adj fiistaic;G->adjlist[j].fiistarc=p;}}//chardfsv[10];charbfsv[10];hitk;〃深度優(yōu)先遍歷hitvisited[10];〃深度優(yōu)先遍歷/*voidDFS(ALGraph*G,intv)AicNode*p;mtw;dfsv[k]=G->adjlist[v].data:k++;visited[v]=l;p=G->adjlist[v].fustarc;wliile(p!=NULL)(w=p?>adjvex;if(visited[w]==O)DFS(Gw);p=p->nextarc;)}*/〃**********************************************************************************************************************voidBFS(ALGiaph*G,intv,mtdest) //廣度優(yōu)先搜索，v是出發(fā)結(jié)點(diǎn)序號(hào)，dest是目標(biāo)節(jié)點(diǎn)序號(hào)closedop[20];//定義open表大小closedcl[20];〃定義closed表大小

intftontjear;〃定義指針hitcreai--l;mtcost=0; 〃定義費(fèi)用變量AicNode*p;ftont=reai--l;k=0;rear++;op[reai].id=0:op[rear].datan=0;op[reai].cost=0;op[reai].dad=-l;wliile(fiont<reai)(fiont++;creai-H-；〃取出open表表首節(jié)點(diǎn),crear為closed表的尾指針cl[crear]=op[front];〃放入close表if(cl[crear].dataii==dest)//判斷是目標(biāo)結(jié)點(diǎn),回溯輸出訪問路徑(chaitoprt[MAXV];pimtfC'\ii找到目標(biāo)，搜索路徑為：intii=creai;intto=0;(toprt[to]=G->adjlist[ii].data;ii=cl[ii].dad;to++;)fbr(intj=to-1；j>=0J~)pnntR”％c-?>”,toprt[j]);)prmtf(H%c\n,\G->adjlist[cl[creai].datan].data);//printf(nLeastcost:%d\n\n'',cl[creai].cost);return;}//fiisttobe擴(kuò)展結(jié)點(diǎn)//fiisttobe擴(kuò)展結(jié)點(diǎn)〃若不是目標(biāo)節(jié)點(diǎn)，則對(duì)其擴(kuò)展,p=G->adjlist[cl[crear].datan].fiistarc;wliile(p!=NULL)并將擴(kuò)展結(jié)果放入open表表尾部rear-H-；op[rear].id=rear;rear-H-；op[rear].id=rear;op[rear].dad=crear;后來回溯op[rear].datan=p->adjvex;//open新節(jié)點(diǎn)位置〃記錄父節(jié)點(diǎn)在close表中的位置，方便〃是哪個(gè)字符，即位置op[iear].cost=cl[creai].cost+p->infb;//計(jì)算費(fèi)用p=p->nextarc;)mti=rearj;〃將open〃將open表在所有待擴(kuò)展范圍內(nèi)全排序，代價(jià)