人工智能之迷宫.doc

精品文档，仅供学习与交流，如有侵权请联系网站删除
【精品文档】第 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)点，则向上移动一步

为求得最佳路径，可使用A*算法。
A*算法f 函数定义 f(n) ＝ g(n) ＋h(n)
设：每一步的耗散值为1（单位耗散值）
定义：g(n) ＝d(n) 从初始节点s到当前节点n的搜索深度
h(n) ＝| Xg－Xn | ＋ | Yg－Yn | 当前节点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)
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中)
精品文档，仅供学习与交流，如有侵权请联系网站删除
【精品文档】第 2 页
④ if f(n,ml) ＜ f(ml) then f(ml) ← f(n,ml)，标记ml到n的指针(ml在 CLOSED中)
ADD(ml,OPEN)，把ml放回到OPEN中
7、OPEN中的节点按照f值升序排列
8、GO LOOP
A*。
。
迷宫搜索结果示意图
详细设计
（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）。
精品文档，仅供学习与交流，如有侵权请联系网站删除
【精品文档】第 3