盲目搜索算法

实验一：盲目搜索算法—、实验目的：掌握深度优先搜索求解算法的基本思想。二、 实验要求：用C语言实现城市交通图的代价树深度优先搜索求解三、 实验语言环境：C语言、设计思路:解法：采用代价树的深度优先搜索理论：1.首先根据交通图,画出代价图代价图2.开始搜索open表存放刚刚生成的节点。closed表存放将要扩展的节点或已经扩展过的节点。背景：如图是5城市之间交通路线图，A城市是出发地，E城市是目的地，两城市间的交通费用（代价）如图中数字所示，求从A至UE的最小费用路线。图1 图2解法：采用代价树的广度优先搜索理论：首先根据交通图1,画出代价图代价图如图2开始搜索oepn表存放刚刚生成的节点。closed表存放将要扩展的节点或已经扩展过的节点。open表结构：［代价］I［节点］I［父节点］closed表结构：［序号］I［节点］I［父节点］1） 把A放入open表open表：0|A|0Closed表：空2） 把A从open表放入closed表open 表 :空closed表：IA|03） 扩展A,得Cl,Bl,放入open表Open表：|Cl|A|Bl|Aclosed表：IA|04|Bl|Aclosed表：IA|0|Cl|ACl不是目标节点，于是继续扩展5）把Cl扩展得到D1,放入open表D1的代价：3+2=5B1的代价：4open表：|B1|A|D1|Clclosed表：|A|0ClACl的代价：3Bl的代价：4 6）把Bl从open放入closed表open表：5|DI|Clclosed表：|A|0|Cl|A|Bl|ABl不是目标节点，于是继续扩展7） 扩展Bl得D2,E1,放入Open表D2的代价:4+4=8E1的代价：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不是目标节点，于是继续扩展9）把D1扩展得到E2,B2,放入open表E2的代价：3+2+3=8B2的代价：3+2+4=9D2的代价：8E1的代价：9open表：8|E2|D18|D2|Bl9|B2|D19|E1|B1closed表：1A02|ClAclosed表：3|BlA1A04IDICl2ClA10)把E2从open表放入closed3BlA表4DICl5E2DIopen表：E2是目标节点，搜索结束。8|D2Bl则搜索路径A-Cl-DI-E29B2DI即：A-C-D-E9|E1Bl五、实验代码:#iiiclude<stdio.h>#iiiclude<malloc.h>^defineINF32767/*INF表示8*/typedefintInfbType;typedefcharVertex;#defineMAXV6/*最大顶点个数*//*以下定义邻接矩阵类型*/typedefstmct( IiifoT^eedges[MAXV][MAXV];/*邻接矩阵*/intii,e;Vertexvexs[MAXV];}MGraph;/*图的定义*//*顶点数，孤数*//*存放顶点信息*//*图的邻接矩阵类型*//*以卜定义邻接表类型*/typedefstmctANode(intadjvex;/*弧的结点结构类型*//*该孤的终点位置*//*指向下一条弧的指针*//*/*指向下一条弧的指针*//*该孤的相关信息，这里用于存放权值*//*邻接表头结点的类型*//*顶点信息*//*指向第一条弧*//*AdjList是邻接表类型*//*邻接表*//*图中顶点数11和边数e*//*图的邻接表类型*/InfoTypeiiifb;}ArcNode;typedefstructVnode(Vertexdata;AicNode*fkstaic;)VNode;typedefVNodeAdjListfMAXV];typedefstmct(AdjListadjlist;mtn,e;}ALGraph;typedefstmct{chatmtinfb;}etype;typedefstructCLOSEDList{mtid; 〃记住矢量intdatan;intcost;nitdad;〃记住父节点回溯用Jclosed;//open表和close表都用这个类型voidMatToList(MGraphg^ALGraph*&G)/*将邻接矩阵g转换成邻接表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转换成邻接矩阵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;〃深度优先遍历hitvisited[10];〃深度优先遍历/*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) //广度优先搜索，v是出发结点序号，dest是目标节点序号closedop[20];//定义open表大小closedcl[20];〃定义closed表大小

intftontjear;〃定义指针hitcreai--l;mtcost=0; 〃定义费用变量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表表首节点,crear为closed表的尾指针cl[crear]=op[front];〃放入close表if(cl[crear].dataii==dest)//判断是目标结点,回溯输出访问路径(chaitoprt[MAXV];pimtfC'\ii找到目标，搜索路径为：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扩展结点//fiisttobe扩展结点〃若不是目标节点，则对其扩展,p=G->adjlist[cl[crear].datan].fiistarc;wliile(p!=NULL)并将扩展结果放入open表表尾部rear-H-；op[rear].id=rear;rear-H-；op[rear].id=rear;op[rear].dad=crear;后来回溯op[rear].datan=p->adjvex;//open新节点位置〃记录父节点在close表中的位置，方便〃是哪个字符，即位置op[iear].cost=cl[creai].cost+p->infb;//计算费用p=p->nextarc;)mti=rearj;〃将open〃将open表在所有待扩展范围内全排序，代价