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

< 人工智能 > 实 验 报 告 4

一、实验目的：

掌握深度优先搜索求解算法的基本思想。

二、实验要求：

用C语言实现城市交通图的代价树深度优先搜索求解

三、实验语言环境：

C语言

四、设计思路：

解法：采用 代价树的深度优先搜索理论： 1. 首先根据交通图，画出代价图代价图 2. 开始搜索 open表存放刚刚生成的节点。 closed表存放将要扩展的节点或已经扩展过的节点。

背景：如图是5城市之间交通路线图，A城市是出发地，E城市是目的地，两城市间的交通费用(代价)如图中数字所示，求从A到E的最小费用路线。

. 专业 专注 .

. . .. . .

解法：采用 代价树的广度优先搜索 理论：

1. 首先根据交通图，画出代价图 代价图 如图

2. 开始搜索

oepn表存放刚刚生成的节点。

closed表存放将要扩展的节点或已经扩展过的节点。 open表结构： [代价]|[节点]|[父节点] closed表结构： [序号]|[节点]|[父节点] 1) 把A放入 open表 open表： 0| A | 0

. 专业 专注 .

. . .. . .

Closed表： 空

2) 把A从open表放入closed表 open表： 空 closed表： 1 | A | 0

3) 扩展A，得C1，B1，放入open表 C1的代价：3 B1的代价：4 Open表： 3 | C1 | A 4 | B1 | A closed表： 1 | A | 0 4 | B1 | A closed表： 1 | A | 0 2 | C1 | A

C1不是目标节点，于是继续扩展 5) 把C1扩展得到 D1，放入open表 D1的代价：3+2=5 B1的代价：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不是目标节点，于是继续扩展 7) 扩展B1得D2，E1，放入Open表 D2的代价：4+4=8 E1的代价：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不是目标节点，于是继续扩展

9) 把D1扩展得到E2，B2，放入open表 E2的代价：3+2+3=8 B2的代价：3+2+4=9 D2的代价：8 E1的代价：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 是目标节点，搜索结束。 则搜索路径 A - C1 - D1 -E2 即：A - C - D - E 五、实验代码：

#include

. 专业 专注 .

. . .. . .

#include

#define INF 32767 /*INF表示∞*/

typedef int InfoType; typedef char Vertex; #define MAXV 6

/*以下定义邻接矩阵类型*/ typedef struct

/*图的定义*/

/*最大顶点个数*/

{ InfoType edges[MAXV][MAXV]; /*邻接矩阵*/ int n,e;

/*顶点数，弧数*/ /*存放顶点信息*/ /*图的邻接矩阵类型*/

Vertex vexs[MAXV];

} MGraph;

/*以下定义邻接表类型*/

typedef struct ANode /*弧的结点结构类型*/ {

int adjvex; /*该弧的终点位置*/

/*指向下一条弧的指针*/

struct ANode *nextarc;

InfoType info; /*该弧的相关信息,这里用于存放权值*/ } ArcNode;

typedef struct Vnode

/*邻接表头结点的类型*/

. 专业 专注 .

. . .. . .

{ Vertex data; /*顶点信息*/

/*指向第一条弧*/

ArcNode *firstarc; } VNode;

typedef VNode AdjList[MAXV]; /*AdjList是邻接表类型*/ typedef struct {

AdjList adjlist; /*邻接表*/

int n,e; /*图中顶点数n和边数e*/ } ALGraph;

typedef struct

{ char vi,vj;

/*图的邻接表类型*/

int info;

typedef struct CLOSEDList {

int id;

//记住矢量

}etype;

int datan; int cost;

int dad; //记住父节点 回溯用

}closed; //open表和close表都用这个类型

. 专业 专注 .

. . .. . .

void MatToList(MGraph g,ALGraph *&G) /*将邻接矩阵g转换成邻接表G*/ {

for (i=0;iint i,j,n=g.n; ArcNode *p;

G=(ALGraph *)malloc(sizeof(ALGraph)); for (i=0;iG->adjlist[i].firstarc=NULL; G->adjlist[i].data=g.vexs[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;

void ListToMat(ALGraph *G,MGraph &g) /*将邻接表G转换成邻接矩阵g*/ { }

void DispMat(MGraph g)

int i,j,n=G->n; ArcNode *p; for(i=0;ifor(j=0;jg.edges[i][j]=INF;

for (i=0;ig.vexs[i]=G->adjlist[i].data; p=G->adjlist[i].firstarc;

while (p!=NULL) }

g.n=n;g.e=G->e;

{

g.edges[i][p->adjvex]=p->info;

p=p->nextarc; }

. 专业 专注 .

. . .. . .

/*输出邻接矩阵g*/ { }

void DispAdj(ALGraph *G) /*输出邻接表G*/ {

int i; ArcNode *p; for (i=0;in;i++) {

p=G->adjlist[i].firstarc; int i,j;

for (i=0;ifor (j=0;jif (g.edges[i][j]==INF)

printf(\"%3s\∞\");

else

printf(\"%3d\

printf(\"\\n\");

printf(\"\\n%3d %c : \

. 专业 专注 .

. . .. . .

}

}

while (p!=NULL) { }

printf(\"\\n\");

printf(\"-->%d(%d)\p=p->nextarc;

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;kfor(i=0;ifor(j=0;jg.edges[i][j]=INF;

for(k=0;kwhile(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;

void creatlink(ALGraph *&G,char vex[],int n,etype edge[],int e) //建立邻接表 {

ArcNode *p;

G=(ALGraph *)malloc(sizeof(ALGraph)); G->n=n;G->e=e; int k,i,j;

for (i=0;ifor(k=0;ki=0;

G->adjlist[i].firstarc=NULL; G->adjlist[i].data=vex[i];

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;

//char dfsv[10]; char bfsv[10]; int k;

int visited[10];

/*void DFS(ALGraph *G,int v) {

ArcNode *p; int w;

//深度优先遍历

. 专业 专注 .

. . .. . .

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; } }*/

//**********************************************************************************************************************

void BFS(ALGraph *G,int v,int dest) //广度优先搜索 ,v是出发结点序号，dest是目标节点序号 {

closed op[20];

//定义open表大小

closed cl[20]; //定义closed表大小

int front,rear; //定义指针 int crear=-1;

int cost=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(frontfront++; crear++; cl[crear]=op[front];

//取出open表表首节点,crear为closed表的尾指针 //放入close表

if(cl[crear].datan==dest)//判断是目标结点，回溯输出访问路径 {

char toprt[MAXV];

printf(\"\\n找到目标，搜索路径为：\\n\"); int ii = crear; int to=0; while(ii!=-1) { }

for(int j=to-1;j>=0;j--) {

printf(\"%c-->oprt[to]=G->adjlist[ii].data; ii=cl[ii].dad; to++;

. 专业 专注 .

. . .. . .

}

}

printf(\"%c\\n\//printf(\"Least cost: %d\\n\\n\return;

p=(ArcNode *)malloc(sizeof(ArcNode));

p=G->adjlist[cl[crear].datan].firstarc; //first tobe 扩展结点

//若不是目标节点，则对其扩展，

while(p!=NULL)

并将扩展结果放入open表表尾部 {

rear++;

op[rear].id=rear;

//open新节点位置

//记录父节点在close表中的位

op[rear].dad=crear;

置，方便后来回溯

op[rear].datan=p->adjvex;

//是哪个字符，即位置

op[rear].cost=cl[crear].cost+p->info;//计算费用 p=p->nextarc;

}

int i=rear,j;

bool exchange=true;

//将open表在所有待扩展范围内

全排序，代价小的在上面。排序方法：冒泡

closed temp;

. 专业 专注 .

. . .. . .

while(exchange) {

exchange=false;

for(j=front+1;j{ } i--;

temp=op[j+1]; op[j+1]=op[j]; op[j]=temp; exchange=true;

}

} }

//********************************************************************************************************************** //以下为主函数； void main() {

MGraph g; char vex[]=\"abcde\";

. 专业 专注 .

. . .. . .

etype edge[]={{'a','b',4}, {'a','c',3}, {'c','d',2},{'d','b',4},{'d','e',3},{'b','e',5}};

ALGraph *G;

creatmat(g,vex,5,edge,6); printf(\"\\n\");

printf(\" 有向图G的邻接矩阵:\\n\"); DispMat(g);

creatlink(G,vex,5,edge,6);

printf(\" 图G的邻接矩阵转换成邻接表:\\n\"); DispAdj(G); int i;

/*for(i=0;ivisited[i]=0;

DFS(G,0);*/

for(i=0;iBFS(G,0,4);

. 专业 专注 .