人工智能 第三章.ppt

第三章搜索策略? 控制策略分类?控制策略分为两类:不可撤回的方式和试探方式?不可撤回的方式:选择一条适用的规则并应用它时, 不必为以后重新考虑做准备。?试探方式:选择一条适用的规则执行,但需为以后应用另一条规则做准备。?试探方式也可分为两种:回溯式和图搜索式?回溯式:在选择一条规则时要建立一个回溯点,当计算遇到困难,不能得到一个解时,使状态返回原来的回溯点上,从那里改选另一条可应用规则。?图搜索:同时记住几个规则序列及其产生的结果。? 不可撤回方式?这种方式是利用问题给出的局部知识来决定如何选取规则,不必考虑撤回已用的规则。这种控制策略的优点是控制简单。? 爬山法?爬山法就是利用高度随位置变化的函数引导爬山。?爬山法只有在登单峰的山时才有效,如遇到多峰、山脊或平顶时,并不总是有效。?我们以八数码游戏为例加以说明。?在3×3的棋盘上,有八个将牌和一个空格, 每一个将牌都标有 1—8 中的某一个数码, 空格周围的将牌可向空格移动,求解的问题是:有一个初始布局和一个目标布局, 问如何移动将牌,从初始布局达到目标。?综合数据库:我们用二维数组来表示 3×3 的棋盘。?初始状态目标状态 217 86 345 187 26 345 ?规则集合:可用四条产生式规则代表四种走法: ?空格左移、空格上移、空格右移、空格下移?设用 B ij表示表中第 i行第 j列的数码, u、v 表示空格所在的行列数,空格用 0 表示,则空格左移的规则定义如下: ? IF v-1 ≧1 THEN B uv︰=B u(v-1) ∧B u(v-1) =0 ?搜索策略: ?不在位将牌个数:当前状态与目标状态对应位置逐一比较后有差异的将牌个数。?我们定义一个描述状态的函数-W(n) ,其中, n 表示任一状态, W(n) 的值为不在位将牌个数。?初始状态的函数值为-4,目标状态的函数值为 0。爬山法选取规则的原则:选取使用规则后生成的新状态的函数值有最大增长的规则,如没有使函数值增长的规则,则选取使函数值不减少的规则,若这种规则也没有,则过程停止。?使用爬山法过程如下: ? 2 8 3 ? 1 6 4 ? 7 5 ? 2 8 3 ? 1 4 ? 7 6 5 ? 2 3 2 8 3 8 1 3 1 8 4 1 4 2 4 ? 7 6 5 7 6 5 7 6 5 ? 2 3 8 3 1 3 ? 1 8 4 2 1 4 8 2 4 ? 7 6 5 7 6 5 7 6 5 ? 1 2 3 8 3 1 3 8 4 2 1 4 8 2 4 ? 7 6 5 7 6 5 7 6 5 ? 1 2 3 8 1 3 1 2 3 ? 8 4 2 4 8 4 ? 7 6 5 7 6 5 7 6 5 ?从上述过程可知,用不可撤回方式(爬山策略) 可找到通往目标的路径,控制简单是其优点, 缺点是对任何状态不是总能选得最优解,并且具有一定的局限性,例如: ?初始状态目标状态? 八数码题的爬山局部极大值?初始状态处于局部极大值,无法搜索。 18 276 543 18 276 345