机器人第六章 迷宫比赛与搜索算法.ppt

机器人第六章 迷宫比赛与搜索算法
你现在浏览的是第一页，共110页
本章内容
1. 迷宫比赛简介
2. 搜索的基本知识
3. 状态空间的搜索策略
4. 与/或树的搜索策略
5. 搜索策略性能的评价
你现在浏览的是第二页，共1用A(i,j)及B(i,j)表示：
A(i,j)表示把A盘从第i号杆移到第j号杆上;
B(i,j)表示把B盘从第i号杆移到第j号杆上。
则，算符共有12个。
A(1,2),　A(1,3),　A(2,1),　A(2,3),　A(3,1),　A(3,2)
B(1,2),　B(1,3),　B(2,1),　B(2,3),　B(3,1),　B(3,2)
你现在浏览的是第二十三页，共110页
2、2 状态空间表示法(举例)
二阶汉诺塔问题
由9种可能的状态和12个算符, 二阶汉诺塔问题的状态空间图如下：
从(1,1)到(2,2)或(3,3)的任何一条通路都是问题的一个解。
你现在浏览的是第二十四页，共110页
2、2 状态空间表示法(举例)
猴子和香蕉
在一个房间内有一只猴子、一个箱子和一束香蕉。香蕉挂在天花板下方，但猴子的高度不足以碰到它。那么这只猴子怎样才能摘到香蕉呢?
你现在浏览的是第二十五页，共110页
2、2 状态空间表示法(举例)
猴子和香蕉
用一个四元表列(W,x,Y,z)来表示这个问题的状态，
其中　　W－猴子的水平位置　　x－当猴子在箱子顶上时取x=1；否则取x=0　　Y－箱子的水平位置　　z－当猴子摘到香蕉时取z=1；否则取z=0 。
你现在浏览的是第二十六页，共110页
2、2 状态空间表示法(举例)
猴子和香蕉
全部可能的状态有13种, 可表示如下：
S0=(a,0,b,0), S1=(a,0,c,0) , S2=(a,0,a,0),
S3=(c,0,b,0) , S4=(c,0,c,0), S5=(c,0,a,0), S6=(b,0,b,0), S7=(b,0,c,0), S8=(b,0,a,0),
S9=(a,1,a,0), S10=(b,1,b,0), S11=(c,1,c,0),
S12=(c,1,c,1)
问题的初始状态集合为S={S0},目标状态集合为G={S12}。
你现在浏览的是第二十七页，共110页
2、2 状态空间表示法(举例)
猴子和香蕉
算符用下面的表示：
(1) goto(U)猴子走到相邻的水平位置U
(2) pushbox(V)猴子把箱子推到相邻的水平位置V
(3) climbbox猴子爬上箱顶
(4) godownbox猴子爬下箱子
(5) grasp猴子摘到香蕉
则，算符共有11个，包括猴子移动的4个，箱子移动的4个，猴子爬上箱子1个、爬下箱子1个，猴子摘到香蕉1个。
你现在浏览的是第二十八页，共110页
2、2 状态空间表示法(举例)
猴子和香蕉
由13种可能的状态和11个算符, 猴子和香蕉问题的状态空间图如下：
你现在浏览的是第二十九页，共110页
2、2 状态空间表示法
需要定义状态、算符。
问题的求解过程，是一个不断把算符作用于状态的过程。
问题的解是从初始状态到目标状态所用算符构成的序列。
使用算符最少的解是最优解。
对一个状态选取哪个算符操作，取决于搜索策略。不同的搜索策略，操作顺序不一定相同。(重点讨论的问题)
你现在浏览的是第三十页，共110页
2、3 与/或树表示法
与/或树表示法
用于表示问题及其求解过程的一种方法，通常用于表示比较复杂问题的求解。
对于一个复杂问题，直接求解往往比较困难，可以对其进行简化。
简化使用的两个操作：分解、等价变换
你现在浏览的是第三十一页，共110页
2、3 与/或树表示法
分解
把一个复杂问题分解为若干个较为容易求解的子问题。每个子问题又可继续分解。不断重复，直到不需要或者不能再分解为止。
复合各子问题的解就得到原问题的解。
你现在浏览的是第三十二页，共110页
2、3 与/或树表示法
分解
P
P1
P2
P3
与树
分解形成“与”树
你现在浏览的是第三十三页，共110页
2、3 与/或树表示法
等价变换
把一个原问题变换为若干个较为容易求解的新问题。
若新问题中有一个可求解，则就得到了原问题的解。
你现在浏览的是第三十四页，共110页
2、3 与/或树表示法
等价变换
等价变换形成“或”树
P
P1
P2
P3
或树
你现在浏览的是第三十五页，共110页
2、3 与/或树表示法
分解、等价变换结合使用