人工智能-实验四-城市交通图的代价树深度优先搜索

人工智能实验报告4一、实验目的：掌握深度优先搜索求解算法的基本思想。二、实验要求：用C语言实现城市交通图的代价树深度优先搜索求解三、实验语言环境：C语言四、设计思路：解法：采用代价树的深度优先搜索理论：1.首先根据交通图，画出代价图代价图2.开始搜索open表存放刚刚生成的节点。closed表存放将要扩展的节点或已经扩展过的节点。背景：如图是5城市之间交通路线图，A城市是出发地，E城市是目的地，两城市间的交通费用(代价)如图中数字所示，求从A到E的最小费用路线。解法：采用代价树的广度优先搜索理论：1.首先根据交通图，画出代价图代价图如图2.开始搜索oepn表存放刚刚生成的节点。closed表存放将要扩展的节点或已经扩展过的节点。open表结构：[代价]|[节点]|[父节点]closed表结构：[序号]|[节点]|[父节点]1)把A放入open表open表：0|A|0Closed表：空2)把A从open表放入closed表open表：空closed表：1|A|03)扩展A，得C1，B1，放入open表C1的代价：3B1的代价：4Open表：3|C1|A4|B1|Aclosed表：1|A|04|B1|Aclosed表：1|A|02|C1|AC1不是目标节点，于是继续扩展5)把C1扩展得到D1，放入open表D1的代价：3+2=5B1的代价：4open表：4|B1|A5|D1|C1closed表：1|A|02|C1|A6)把B1从open放入closed表open表：5|D1|C1closed表：1|A|02|C1|A3|B1|AB1不是目标节点，于是继续扩展7)扩展B1得D2，E1，放入Open表D2的代价：4+4=8E1的代价：4+5=9open表：5|D1|C18|D2|B19|E1|B1closed表：1|A|02|C1|A3|B1|A8)把D1从open表放入closed表open表：8|D2|B19|E1|B1closed表：1|A|02|C1|A3|B1|A4|D1|C1D1不是目标节点，于是继续扩展9)把D1扩展得到E2，B2，放入open表E2的代价：3+2+3=8B2的代价：3+2+4=9D2的代价：8E1的代价：9open表：8|E2|D18|D2|B19|B2|D19|E1|B1closed表：1|A|02|C1|A3|B1|A4|D1|C110)把E2从open表放入closed表open表：8|D2|B19|B2|D19|E1|B1closed表：1|A|02|C1|A3|B1|A4|D1|C15|E2|D1E2是目标节点，搜索结束。则搜索路径A-C1-D1-E2即：A-C-D-E五、实验代码：#includestdio.h#includemalloc.h#defineINF32767/*INF表示∞*/typedefintInfoType;typedefcharVertex;#defineMAXV6/*最大顶点个数*//*以下定义邻接矩阵类型*/typedefstruct/*图的定义*/{InfoTypeedges[MAXV][MAXV];/*邻接矩阵*/intn,e;/*顶点数，弧数*/Vertexvexs[MAXV];/*存放顶点信息*/}MGraph;/*图的邻接矩阵类型*//*以下定义邻接表类型*/typedefstructANode/*弧的结点结构类型*/{intadjvex;/*该弧的终点位置*/structANode*nextarc;/*指向下一条弧的指针*/InfoTypeinfo;/*该弧的相关信息,这里用于存放权值*/}ArcNode;typedefstructVnode/*邻接表头结点的类型*/{Vertexdata;/*顶点信息*/ArcNode*firstarc;/*指向第一条弧*/}VNode;typedefVNodeAdjList[MAXV];/*AdjList是邻接表类型*/typedefstruct{AdjListadjlist;/*邻接表*/intn,e;/*图中顶点数n和边数e*/}ALGraph;/*图的邻接表类型*/typedefstruct{charvi,vj;intinfo;}etype;typedefstructCLOSEDList{intid;//记住矢量intdatan;intcost;intdad;//记住父节点回溯用}closed;//open表和close表都用这个类型voidMatToList(MGraphg,ALGraph*&G)/*将邻接矩阵g转换成邻接表G*/{inti,j,n=g.n;ArcNode*p;G=(ALGraph*)malloc(sizeof(ALGraph));for(i=0;in;i++){G-adjlist[i].firstarc=NULL;G-adjlist[i].data=g.vexs[i];}for(i=0;in;i++)for(j=n-1;j=0;j--)if(g.edges[i][j]!=INF){p=(ArcNode*)malloc(sizeof(ArcNode));p-adjvex=j;p-info=g.edges[i][j];p-nextarc=G-adjlist[i].firstarc;G-adjlist[i].firstarc=p;}G-n=n;G-e=g.e;}voidListToMat(ALGraph*G,MGraph&g)/*将邻接表G转换成邻接矩阵g*/{inti,j,n=G-n;ArcNode*p;for(i=0;in;i++)for(j=0;jn;j++)g.edges[i][j]=INF;for(i=0;in;i++){g.vexs[i]=G-adjlist[i].data;p=G-adjlist[i].firstarc;while(p!=NULL){g.edges[i][p-adjvex]=p-info;p=p-nextarc;}}g.n=n;g.e=G-e;}voidDispMat(MGraphg)/*输出邻接矩阵g*/{inti,j;for(i=0;ig.n;i++){for(j=0;jg.n;j++)if(g.edges[i][j]==INF)printf(%3s,∞);elseprintf(%3d,g.edges[i][j]);printf(\n);}}voidDispAdj(ALGraph*G)/*输出邻接表G*/{inti;ArcNode*p;for(i=0;iG-n;i++){p=G-adjlist[i].firstarc;printf(\n%3d%c:,i,G-adjlist[i].data);while(p!=NULL){printf(--%d(%d),p-adjvex,p-info);p=p-nextarc;}printf(\n);}}voidcreatmat(MGraph&g,charvex[],intn,etypeedge[],inte)//建立邻接矩阵{g.n=n;g.e=e;intk,i,j;for(k=0;kn;k++)g.vexs[k]=vex[k];for(i=0;in;i++)for(j=0;jn;j++)g.edges[i][j]=INF;for(k=0;ke;k++){i=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].info;}}voidcreatlink(ALGraph*&G,charvex[],intn,etypeedge[],inte)//建立邻接表{ArcNode*p;G=(ALGraph*)malloc(sizeof(ALGraph));G-n=n;G-e=e;intk,i,j;for(i=0;in;i++){G-adjlist[i].firstarc=NULL;G-adjlist[i].data=vex[i];}for(k=0;ke;k++){i=0;while(G-adjlist[i].data!=edge[k].vi)i++;j=0;while(G-adjlist[j].data!=edge[k].vj)j++;p=(ArcNode*)malloc(sizeof(ArcNode));p-adjvex=j;p-info=edge[k].info;p-nextarc=G-adjlist[i].firstarc;G-adjlist[i].firstarc=p;p=(ArcNode*)malloc(sizeof(ArcNode));p-adjvex=i;p-info=edge[k].info;p-nextarc=G-adjlist[j].firstarc;G-adjlist[j].firstarc=p;}}//chardfsv[10];charbfsv[10];intk;intvisited[10];/*voidDFS(ALGraph*G,intv)//深度优先遍历{ArcNode*p;intw;dfsv[k]=G-adjlist[v].data;k++;visited[v]=1;p=G-adjlist[v].firstarc;while(p!=NULL){w=p-adjvex;if(visited[w]==0)DFS(G,w);p=p-nextarc;}}*///**********************************************************************************************************************voidBFS(ALGraph*G,intv,intdest)//广度优先搜索,v是出发结点序号，dest是目标节点序号{closedop[20];//定义open表大小closedcl[20];//定义closed表大小intfront,rear;//定义指针intcrear=-1;intcost=0;//定义费用变量ArcNode*p;front=rear=-1;k=0;rear++;op[rear].id=0;op[rear].datan=0;op[rear].cost=0;op[rear].dad=-1;while(frontrear){front++;crear++;//取出open表表首节点,crear为closed表的尾指针cl[crear]=op[front];//放入close表if(cl[crear].datan==dest)//判断是目标结点，回溯输出访问路径{chartoprt[MAXV];printf(\n找到目标，搜索路径为：\n);intii=crear;intto=0;while(ii!=-1){toprt[to]=G-adjlist[ii].data;ii=cl[ii].dad;to++;}for(intj=to-1;j=0;j--){printf(%c--,toprt[j]);}printf(%c\n,G-adjlist[cl[crear].datan].data);//printf(Leastcost:%d\n\n,cl[crear].cost);return;}p=(ArcNode*)malloc(sizeof(ArcNode));p=G-adjlist[cl[crear].datan].firstarc;//firsttobe扩展结点while(p!=NULL)//若不是目标节点，则对其扩展，并将扩展结果放入open表表尾部{rear++;op[rear].id=rear;//open新节点位置op[rear].dad=crear;//记录父节点在close表中的位置，方便后来回溯o