人工智能之迷宫学习资料

人工智能之迷宫

问题描述

迷宫图从入口到出口有若干条通路，求从入口到出口最短路径的走法

(1,1)(4,4)

图i.i迷宫示意图

设计原理

图i.i为一简单迷宫示意图的平面坐标表示。以平面坐标图来表示迷宫 的通

路时，问题的状态以所处的坐标位置来表示，即综合数据库定义为｛ | 1 < x, y < 4 ｝，则迷宫问题归结为求解从 (1,1) 到(4, 4)的最短路 径。

迷宫走法规定为向东、南、西、北前进一步，由此可得规则集简化形式如下

(x, y)

右移 R1: if(x, y) then (x+1, y) 步

下移 R2: if(x, y) then (x,y -1) 步

左移 R1: if(x, y) then (x -1,y) 步

上移 R2: if(x, y) then (x, y+1)

.rH. .rH. .rH.

如果当前在(x, y)点，则向右移动

如果当前在(x, y)点，则向下移动

如果当前在(x, y)点，则向左移动

如果当前在(x, y)点，则向上移动

步

.rH.

给出其状态空间如图2.1所示

A*算法f函数定义f(n) = g(n) + h(n) 设：每一步的耗散值为1 (单位耗散值)

定义：g(n) = d(n) 从初始节点s到当前节点n的搜索深度

h(n) 离

其中：(X g, Y g)目标节点g坐标 (X n, Y n )当前节点n坐标 显然满足：h(n)

⑴按照f值升序排列

= | Xg— X. | + | 丫 g — Yn |

当前节点n与目标节点间的坐标距

⑵如果f值相同，则深度优先 A*算法的搜索过程如下：

1、 OPE比(s) , f(s)=g(s)+h(s)

2、 LOOP if OPEN = ( ) then EXIT(FAIL) 3、 n J FIRST(OPEN)

4、 if GOAL(n) THEN EXIT(SUCCESS) 5、 REMOVE(n,OPEN)ADD(n,CLOSED) 6、 ｛m I J EXPAND(n)

① 计算f(n,m i)=g(n,m i)+h(mi),(自s过n, m到目标节点的耗散值) ② ADD(m,OPEN),标记 m到 n 的指针(m 不在 OPENS CLOSE中) ③ if f(n,m

k

) v f(m k) then f(m

k

) J f(n,m k)，标记 m到 n 的

指针(mk在OPEN中) ④ if f(n,m l) v f(m l) then f(m

指针(m在CLOSED中)

ADD(mOPEN),扌巴 m放回至U OPEN中

7、 OPEN中的节点按照f值升序排列 8、 GO LOOP

l

) J f(n,m l)，标记 m到 n 的

A*算法的搜索图示如图2.2所示。