人工智能之迷宫
一、问题描述
迷宫图从入口到出口有若干条通路，求从入口到出口最短路径的走法。
图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, 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) ＝| X
g －X
n
| ＋ | Y
g
－Y
n
| 当前节点n与目标节点间的坐标距离
其中：( X
g , Y
g
) 目标节点g坐标 ( X
n
, Y
n
)当前节点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)
6、{m
i
﹜← EXPAND(n)
①计算f(n,m
i )=g(n,m
i
)+h(m
i
)，(自s过n，m
i
到目标节点的耗散值)
② ADD(m
j ,OPEN)，标记m
j
到n的指针(m
j
不在OPEN和CLOSED中)
③ if f(n,m
k ) ＜ f(m
k
) then f(m
k
) ← f(n,m
k
)，标记m
k
到n的指
针
(m
k
在 OPEN中)
④ if f(n,m
l ) ＜ f(m
l
) then f(m
l
) ← f(n,m
l
)，标记m
l
到n的指
针(m
l
在 CLOSED中)
ADD(m
l ,OPEN)，把m
l
放回到OPEN中
7、OPEN中的节点按照f值升序排列
8、GO LOOP
A*算法的搜索图示如图2.2所示。
则其搜索结果如图2.3所示。
`
出口入口
（4,4）
（1,1）
图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},
{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代表代表评价函数值，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=(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 *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*算法
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代表两个节点之间没有线，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)+abs((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(!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;
}
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 { p=open.top(); open.pop(); for(int j=i+1;j { q=open.top(); open.pop(); if(q->f { 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=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=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+1 { d->g=a->g+1; d->f=b[i]->g+h(b[i]); d->parent=a; } } else if(Nclosed(b[i])) { if(a->g+1 { b[i]->g=a->g+1; b[i]->f=b[i]->g+h(b[i]); b[i]->parent=a; open.push(b[i]); } } } } } } void printmaze() //输出迷宫 { cout<<" (4,4) "< { if(i==6) cout<<"入口→"; else cout<<" "; if(i%2==0) { for(int j=0;j<7;j++) { if(Maze[i][j]==3) cout<<"●"; else if(Maze[i][j]==1) cout<<"─"; else if(Maze[i][j]==5) cout<<"←"; else if(Maze[i][j]==6) cout<<"→"; else cout<<" "; } if(i==0) cout<<"→出口"; cout< } else { for(int j=0;j<7;j++) { if(Maze[i][j]==1) cout<<"│"; else if(Maze[i][j]==7) cout<<"↑"; else if(Maze[i][j]==8) cout<<"↓"; else cout<<" "; } cout< } } cout<<" (1,1)"< } void printpath(Data *a)//输出搜索结果{ int b,c; stack 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][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<<"("< q.pop(); } cout< printmaze(); } int A() //A*算法 { Data s={6,0,0,0,NULL}; Data *n=&s; open.push(n); while(1) { if(open.empty()) { cout<<"不存在路径!"< return 0; } else { n=open.top(); if(n->x==0&&n->y==6) { cout<<"最短路径长度为:"< cout<<"最短路径为:"; printpath(n); return 1; } else { open.pop(); closed.push(n); Expand(n); //扩展n节点 sort(); //open中节点按照f值升序排列 } } } } void main()//主函数 { cout<<"迷宫如下图:"< printmaze(); A(); } 四、设计结果及分析 （1）实验结果 （2）实验分析 从上面的图中可以看出程序运行结果与分析结果一致，程序运行正确。 五、实验心得与体会 通过本次课程设计的训练，增加了我学习算法的兴趣，对A*算法有了更深刻的理解，虽然还不是很明白其中的具体内容，但已发现算法分析与程序设计的乐趣，而且还熟练使用C语言编程的能力。虽然还有很多复杂的问题是我们的能力所不及的，但我相信通过一次次实际的训练操作会使我们的解决问题的能力一步步有所提高。这次程序设计让我们学到了好多知识，但也暴露了我们在程序设计中的不足。总之，所以我相信通过此次课程设计会提高我们分析设计能力和编程能力，为后续课程的学习及实践打下良好的基础