第四章 搜索策略 4-3 状态空间的启发式搜索.

Presentation on theme: "第四章 搜索策略 4-3 状态空间的启发式搜索."— Presentation transcript:

1 第四章 搜索策略 4-3 状态空间的启发式搜索

2 利用问题自身的特性信息和经验与知识引导搜索的方法称为启发式搜索。
启发性信息：与具体问题求解过程有关的，并可指导搜索过程朝着最有希望方向前进的控制信息。如：帮助确定扩展节点的信息；帮助决定哪些后继节点应被生成的信息；能决定在扩展一个节点时哪些节点应从搜索树上删除的信息。 估价函数：评价节点重要性的函数。 估价函数f(n)=g(n)+h(n)

3 估价函数：评价节点重要性的函数。 估价函数f(n)=g(n)+h(n)
其中：g(n)是从初始节点S0到节点n的实际代价，可以由父节点的代价和父节点到子节点的代价决定，如：g(n)可以定义为是从初始节点S0到节点n的有向路上边的代价和。 h(n)是从节点n到目标节点Sg的最优路径的估计代价，需要根据问题自身的特性、经验和知识决定。 例4-8 八数码难题 估价函数f(n)=d(n)+W(n) d(n)是从初始节点S0到节点n的深度；W(n)表示节点n中不在位的数码个数。 p.117，图4-17

4 4-3-2 A算法 利用估价函数对Open表中的节点排序。 全局择优搜索
当有新的子节点放入Open表或Open的节点估价函数值被改变后，立即对Open表中的全部节点按估价函数值从小到大重新排序。 例4-9 八数码难题 全局择优搜索 p.117，图4-17 局部择优搜索 从新生成的子节点中选一个估价函数值最小的节点扩展。

5 4-3-3 A*算法 A*算法对A算法的估价函数加了一些限制 A算法的估价函数f(n)=g(n)+h(n)
设f*(n)是从初始节点S0经节点n到目标节点的最小代价值，则f*(n)=g*(n)+h*(n)，其中： g*(n)是从初始节点S0到节点n的最小代价值， h*(n) 是从节点n到目标节点的最小代价值。 因此， g(n) ≥ g*(n)。 A*算法限制： （1） g(n) ≥ 0； （2） h(n) ≤ h*(n)。 A*算法的特性 例4-10

6 4-5 与/或树的启发式搜索 与/或树搜索就是寻找解树的过程。 与/或树启发式搜索就是利用启发性信息寻找最优解树的过程。
4-5 与/或树的启发式搜索 与/或树搜索就是寻找解树的过程。 与/或树启发式搜索就是利用启发性信息寻找最优解树的过程。 最优解树是指代价最小的解树。

7 4-5-1 解树的代价与希望树 解树的代价：根节点的代价。 终止节点n的代价h(n)=0; 端节点n的代价h(n)=∞；

8

9 例4-13 P 2 2 4 6 5 3 2 1 t t t t

10 左解树 P 2 4 6 2 t t

11 右解树 P 2 5 3 1 t t

12 左解树：与节点和代价法 P 14 2 12 4 6 2 2 t t

13 右解树：与节点和代价法 P 11 2 9 5 3 1 1 t t

14 左解树：与节点最大代价法 P 10 2 8 4 6 2 2 t t

15 右解树：与节点最大代价法 P 8 2 6 5 3 1 1 t t

16 希望树 在搜索过程中最有希望成为最优树一部分的子树。 希望树T： （1）初始节点在T中； （2）或节点的最小代价子节点；
（3）与节点的所有子节点。

17 与/或树的启发式搜索过程 与/或树的启发式搜索过程就是不断选择、修改希望树的过程。 搜索过程如下：
（1）把初始节点S0放入Open表中，计算h(S0)； （2）计算希望树T； （3）依次从Open表中取出T的端节点放入Closed表，并记该节点为n；

18 与/或树的启发式搜索过程 （4）如果节点n为终止节点，则做下列工作： 标记节点n为可解节点；
在T上应用可解标记过程，对n的先辈节点中的所有可解节点进行标记； 如果初始节点S0能够被标记为可解节点，则T就是最优解树，成功退出； 否则，从Open表中删去具有可解先辈的所有节点； 转（2）。

19 与/或树的启发式搜索过程 （5）如果节点n不是终止节点，但可扩展，则做下列工作： 扩展节点n，生成n的所有子节点；
把这些子节点都放入Open表中，并为每一个子节点设置指向父节点n的指针； 计算这些子节点及其先辈节点的h值； 转（2）。

20 与/或树的启发式搜索过程 （6）如果节点n不是终止节点，且不可扩展，则做下列工作： 标记节点n为不可解节点；
在T上应用不可解标记过程，对n的先辈节点中的所有不可解节点进行标记； 如果初始节点S0能够被标记为不可解节点，则问题无解，失败退出； 否则，从Open表中删去具有不可解先辈的所有节点； 转（2）。

21 4-6 博弈树的启发式搜索 双人完备信息博弈（例如：中国象棋） 当任何一方行动时，都是选择对自己最为有利，而对对方不利的行动方案。
4-6 博弈树的启发式搜索 双人完备信息博弈（例如：中国象棋） 当任何一方行动时，都是选择对自己最为有利，而对对方不利的行动方案。 在一方看来，可供自己选择的那些行动方案之间是或的关系，可供对方选择的那些行动方案之间是与的关系。 博弈树： 博弈的初始状态是初始节点； 或节点和与节点逐层交替出现； 在一方看来，自己获胜的终局对应的节点是终止节点，对方获胜的终局对应的节点是不可解节点。

22 极大极小过程 估价函数 极大极小原则：在最不利情况下，取最有利。 极大极小原则假设对手不出错，是保守的策略。 例4-14

23 极大 MAX MAX 极小 极小 MIN MIN MIN MIN

24 剪枝 不扩展差的枝。 作业： 4-8，4-11，4-15