人工智能之迷宫互联网

《人工智能之迷宫互联网》由会员分享，可在线阅读，更多相关《人工智能之迷宫互联网（16页珍藏版）》请在装配图网上搜索。

1、 一、 问题描述 迷宫图从入口到出口有若干条通路，求从入口到出口最短路径的走法。 图1.1 迷宫示意图 二、 设计原理 图1.1为一简单迷宫示意图的平面坐标表示 。以平面坐标图来表示迷宫的通路时，问题的状态以所处的坐标位置来表示，即综合数据库定义为｛(x, y) | 1≤x, y ≤ 4 ｝，则迷宫问题归结为求解从 (1, 1) 到 (4, 4)的最短路径。 迷宫走法规定为向东、南、西、北前进一步，由此可得规则集简化形式如下。 右移 R1：if(x, y) then (x+1, y) 如果当前在(x, y)点，则向右移动一步 下移 R2：if(x,

2、 y) then (x,y -1) 如果当前在(x, y)点，则向下移动一步 左移 R1: if(x, y) then (x -1,y) 如果当前在(x, y)点，则向左移动一步 上移 R2：if(x, y) then (x, y+1) 如果当前在(x, y)点，则向上移动一步 给出其状态空间如图2.1所示 为求得最佳路径，可使用A*算法。 A*算法f 函数定义 f(n) ＝ g(n) ＋h(n) 设：每一步的耗散值为1（单位耗散值） 定义：g(n) ＝d(n) 从初始节点s到当前节点n的搜索深度 h(n) ＝| Xg－Xn | ＋ | Yg－Yn

3、| 当前节点n与目标节点间的坐标距离 其中：( Xg, Yg) 目标节点g坐标 ( Xn, Yn )当前节点n坐标 显然满足： h(n) ≤h*(n) OPEN表节点排序 ⑴ 按照f 值 升序排列 ⑵ 如果f 值相同，则深度优先 A*算法的搜索过程如下： 1、OPEN＝(s)， f(s)=g(s)+h(s) 2、LOOP：if OPEN＝( ) then EXIT(FAIL) 3、n ← FIRST(OPEN) 4、if GOAL(n) THEN EXIT(SUCCESS) 5、REMOVE(n,OPEN)，ADD(n,CLOSED)

4、 6、{mi﹜← EXPAND(n) ①计算f(n,mi)=g(n,mi)+h(mi)，(自s过n，mi到目标节点的耗散值) ② ADD(mj,OPEN)，标记mj到n的指针(mj不在OPEN和CLOSED中) ③ if f(n,mk) ＜ f(mk) then f(mk) ← f(n,mk)，标记mk到n的指针(mk在 OPEN中) ④ if f(n,ml) ＜ f(ml) then f(ml) ← f(n,ml)，标记ml到n的指针(ml在 CLOSED中) ADD(ml,OPEN)，把ml放回到OPEN中 7、OPEN中的节点按照

5、f值升序排列 8、GO LOOP A*算法的搜索图示如图2.2所示。 则其搜索结果如图2.3所示。 图2.3 迷宫搜索结果示意图 三、 详细设计 （1）数据结构设计 ①为了在程序中表示迷宫图，定义了一个6*6的二维整型数组 int Maze[7][7]={{3,1,3,1,3,0,3}, {0,4,1,4,1,4,1}, {3,1,3,0,3,1,3}, {1,4,1,4,1,4,1}, {3,0,3,1,3,0,3}, {1,4,1,4,1,4,1},

6、 {3,0,3,1,3,1,3}}; 其中数字3代表坐标点，1代表两个坐标点之间存在路径，0代表两个坐标点之间不存在路径，数字4没有意义。 从这个二维整型数组抽象出来的迷宫如下所示： ② 每个坐标点的数据结构如下: struct Data { int x; int y; int g; int f; struct Data *parent; }; 其中x代表数组的第几行对应实际坐标的y值，y代表数组的第几列对应实际坐标的x值，g代表从入口到该坐标点的耗散值，f代表代表评

7、价函数值，parent代表路径上的该坐标点的前一个坐标点。 ③程序中对应入口坐标为（6，0）也就是实际中的入口（1,1），实际中每走一步对应程序中是x+2或x-2或y+2或y-2。程序中对应的出口坐标为（0,6）实际对应着出口（4,4）。 ④实际中的h函数对应程序中的h(n) ＝|x－0|/2＋| y－6 |/2。 ⑤因为实际坐标与程序中坐标不对应，所以需要一个转换公式， 如下: 实际坐标的x值等于程序中坐标点的y值除以2再加1 实际坐标的y值等于5减去程序中坐标点的x值除以2再减1 ⑥判断两个坐标点a,b之间是否存在路径： p=(a->x+b->x)/2; q=

8、(a->y+b->y)/2; 如果Maze[p][q]==1,则说明a，b之间存在路径，Maze[p][q]==0，则说明不存在路径。为了将搜索结果图形输出，则又设置了Maze[p][q]==5，代表“←”, Maze[p][q]==6，代表“→”，Maze[p][q]==7，代表“↑”，Maze[p][q]==8，代表“↓”。 ⑦为了满足open表中节点如果f 值相同，则深度优先，使用一个栈来表示open表，closed表也是用一个栈来表示。 （2）函数说明 bool bound(Data *a) 函数功能:判断一个坐标点是否越过边界，返回值bool值 int h(Data

9、*a) 函数功能:h函数 Data* Nopen(Data *a) 函数功能:在open表中搜索结点a.若找到则返回结点a的地址，否则返回0 Data* Nclosed(Data *a) 函数功能: 在closed表中搜索结点a.若找到则返回结点a的地址，否则返回0 void sort() 函数功能:对open表中节点按照f值升序排列 void Expand(Data *a) 函数功能: 扩展当前结点a void printmaze() 函数功能:输出迷宫 void printpath(Data *a) 函数功能:输出搜索结果 int A() 函数功能: A*

10、算法 void main() 函数功能:主函数 （3）详细程序设计 #include #include using namespace std; int Maze[7][7]={{3,1,3,1,3,0,3}, {0,4,1,4,1,4,1}, {3,1,3,0,3,1,3}, {1,4,1,4,1,4,1}, {3,0,3,1,3,0,3}, {1,4,1,4,1,4,1}, {3,0,3,1,3,1,3}};//3代表节点，1代表两个节点之间有线，0代表两个节点之间没有线

11、，4无意义 struct Data { int x; int y; int g; int f; struct Data *parent; };//坐标点结构体 stack open; //open表 stack closed; //close表 bool bound(Data *a) //边界函数 { return (a->x<=6)&&(a->x>=0)&&(a->y<=6)&&(a->y>=0); } int h(Data *a) //h函数 { return abs((a->x-0)/2)+ab

12、s((a->y-6)/2); } Data* Nopen(Data *a)//在open表搜索a坐标点 { Data *b,*d; stack c; while(!open.empty()) { b=open.top(); if(b->x==a->x&&b->y==a->y) { while(!c.empty()) { d=c.top(); c.pop(); open.push(d); } return b; } open.pop(); c.push(b); } while(!

13、c.empty()) { d=c.top(); c.pop(); open.push(d); } return 0; } Data* Nclosed(Data *a) 在closed表搜索a坐标点 { Data *b,*d; stack c; while(!closed.empty()) { b=closed.top(); if(b->x==a->x&&b->y==a->y) { while(!c.empty()) { d=c.top(); c.pop(); closed.push(d); } return b

14、; } closed.pop(); c.push(b); } while(!c.empty()) { d=c.top(); c.pop(); closed.push(d); } return 0; } void sort() 对open表中坐标点排序 { Data *p,*q,*r; stack c; int b=open.size(); for(int i=0;i

15、.pop(); if(q->ff) { r=p; p=q; q=r; } open.push(q); } c.push(p); } while(!c.empty()) { q=c.top(); c.pop(); open.push(q); } } void Expand(Data *a)//扩展a坐标点 { int p,q; Data *d; struct Data *b[4]; for(int i=0;i<4;i++) b[i]=(struct Data*)malloc(sizeof(Data)); b[0]->x=

16、a->x+2; b[0]->y=a->y; b[1]->x=a->x; b[1]->y=a->y-2; b[2]->x=a->x-2; b[2]->y=a->y; b[3]->x=a->x; b[3]->y=a->y+2; for(i=0;i<4;i++) { if(bound(b[i])) { p=(b[i]->x+a->x)/2; q=(b[i]->y+a->y)/2; if(Maze[p][q]==1) { if(Nopen(b[i])==0&&Nclosed(b[i])==0) { b[i]->g=a->g+1; b[i]->f=

17、b[i]->g+h(b[i]); b[i]->parent=a; open.push(b[i]); } else if(Nopen(b[i])) { d=Nopen(b[i]); if(a->g+1g) { d->g=a->g+1; d->f=b[i]->g+h(b[i]); d->parent=a; } } else if(Nclosed(b[i])) { if(a->g+1g) { b[i]->g=a->g+1; b[i]->f=b[i]->g+h(b[i]);

18、b[i]->parent=a; open.push(b[i]); } } } } } } void printmaze() //输出迷宫 { cout<<" (4,4) "<

19、=1) cout<<"─"; else if(Maze[i][j]==5) cout<<"←"; else if(Maze[i][j]==6) cout<<"→"; else cout<<" "; } if(i==0) cout<<"→出口"; cout<

20、se cout<<" "; } cout< q; while(!a->parent==NULL) { q.push(a); b=(a->parent->x+a->x)/2; c=(a->parent->y+a->y)/2; if(a->parent->x==a->x) { if(a->parent->y>a->y) Maze[b]

21、[c]=5; else Maze[b][c]=6; } else { if(a->parent->x>a->x) Maze[b][c]=7; else Maze[b][c]=8; } a=a->parent; } q.push(a); while(!q.empty()) { cout<<"("<y/2+1<<","<<5-(q.top()->x/2+1)<<") "; q.pop(); } cout<

22、={6,0,0,0,NULL}; Data *n=&s; open.push(n); while(1) { if(open.empty()) { cout<<"不存在路径!"<x==0&&n->y==6) { cout<<"最短路径长度为:"<f<

23、ed.push(n); Expand(n); //扩展n节点 sort(); //open中节点按照f值升序排列 } } } } void main()//主函数 { cout<<"迷宫如下图:"<