第五章启发式搜索课件

1、第5章 搜索求解策略 5.1 搜索的概念搜索的概念 5.2 状态空间的搜索策略状态空间的搜索策略 5.3 盲目的图搜索策略盲目的图搜索策略 5.4 启发式图搜索策略启发式图搜索策略 5.5 与与/或或图搜索策略图搜索策略 例例1 三数码问题（数码问题（3 puzzle problem）。 123312初始棋局目标棋局第5章 搜索求解策略问题求解：问题求解：问题的表示。问题的表示。 选择一种相对合适的求解方法。选择一种相对合适的求解方法。问题求解的基本方法：问题求解的基本方法：搜索法搜索法、归约法、归结法、归约法、归结法、推理法及产生式等。、推理法及产生式等。v状态空间表示法状态空间表示法v搜索

2、策略：搜索策略： （1）盲目搜索：宽度优先搜索、深度优先搜索）盲目搜索：宽度优先搜索、深度优先搜索 （2）启发式搜索：）启发式搜索：A算法和算法和A*搜索；搜索；第5章 搜索求解策略v搜索中需要解决的基本问题：搜索中需要解决的基本问题：（1）是否一定能找到一个解。）是否一定能找到一个解。（2）是否终止运行或是否会陷入一个死循环。）是否终止运行或是否会陷入一个死循环。（3）找到的解是否是最佳解。）找到的解是否是最佳解。（4）时间与空间复杂性如何。）时间与空间复杂性如何。5.1.1 搜索的基本问题与主要过程5.1.1 搜索的基本问题与主要过程搜索的主要过程搜索的主要过程：(1) 从初始或目的状态出

3、发，并将它作为当前状态。从初始或目的状态出发，并将它作为当前状态。(2) 扫描操作算子集，将适用扫描操作算子集，将适用当前状态当前状态的一些操作算子的一些操作算子作用于当前状态而得到作用于当前状态而得到新的状态新的状态，并建立指向其父，并建立指向其父结点的结点的指针指针 。(3) 检查所生成的新状态是否满足检查所生成的新状态是否满足结束状态结束状态，如果满足，如果满足，则得到问题的一个解，并可沿着有关指针从结束，则得到问题的一个解，并可沿着有关指针从结束状态反向到达开始状态，给出一解答路径；否则，状态反向到达开始状态，给出一解答路径；否则，将新状态作为当前状态，返回第将新状态作为当前状态，返回

4、第(2)步再进行搜索步再进行搜索。 5.1.2 搜索策略1. 搜索方向搜索方向： (1) 数据驱动数据驱动：从初始状态出发的正向搜索。：从初始状态出发的正向搜索。 正向搜索正向搜索从问题给出的条件（一个用于状态转换的操从问题给出的条件（一个用于状态转换的操作算子集合）出发。作算子集合）出发。逆向搜索逆向搜索：先从想达到的目的入手，看哪些操作算子能产：先从想达到的目的入手，看哪些操作算子能产生该目的以及应用这些操作算子产生目的时需要哪些条件。生该目的以及应用这些操作算子产生目的时需要哪些条件。 (2) 目的驱动目的驱动：从目的：从目的状态出发的逆向搜索。状态出发的逆向搜索。5.1.2 搜索策略

5、(3) 双向搜索双向搜索 双向搜索双向搜索：从开始状态出发作正向搜索，同时又从目的：从开始状态出发作正向搜索，同时又从目的状态出发作逆向搜索，直到两条路径在中间的某处汇合状态出发作逆向搜索，直到两条路径在中间的某处汇合为止。为止。5.1.2 搜索策略2. 盲目搜索与启发式搜索盲目搜索与启发式搜索:（1）盲目搜索：盲目搜索：在不具有对特定问题的任何有关信在不具有对特定问题的任何有关信息的条件下，按固定的步骤（依次或随机调用操息的条件下，按固定的步骤（依次或随机调用操作算子）进行的搜索。作算子）进行的搜索。 （2）启发式搜索：启发式搜索：考虑特定问题领域可应用的知识考虑特定问题领域可应用的知识，动

6、态地确定调用操作算子的步骤，优先选择较，动态地确定调用操作算子的步骤，优先选择较适合的操作算子，尽量减少不必要的搜索，以求适合的操作算子，尽量减少不必要的搜索，以求尽快地到达结束尽快地到达结束状态。状态。5.1.2 搜索策略3.人工智能的主要搜索策略：人工智能的主要搜索策略：求求任一解任一解的搜索策略：的搜索策略： 爬山法（爬山法（Hill Climbing）；）； 深度优先法（深度优先法（Depth-first search）；）； 限定范围搜索法（限定范围搜索法（Beam Search）；）； 回溯法（回溯法（Back-tracking）；）； 最好优先法（最好优先法（Best-first

7、 search）；）；5.1.2 搜索策略3.人工智能的主要搜索策略：人工智能的主要搜索策略：求求最佳解最佳解的搜索策略：的搜索策略： 大英博物馆法（大英博物馆法（British museum）；）； 宽度优先法（宽度优先法（Breadth-first search）；）； 分支界定法（分支界定法（Branch and Bound）；）； 最佳图搜索法（最佳图搜索法（A*）；）； 动态规划法（动态规划法（Dynamic Programing）；）；5.1.2 搜索策略3.人工智能的主要搜索策略：人工智能的主要搜索策略：求求与或关系解图与或关系解图的搜索法：的搜索法： 一般的与或图关系解的搜索法

8、；（一般的与或图关系解的搜索法；（AO*） 极大极小法（极大极小法（Minimax）；）； - 剪枝法剪枝法（ - Pruning）；）； 启发式剪枝法（启发式剪枝法（Heuristic Pruning）第5章 搜索求解策略 5.1 搜索的概念搜索的概念5.2 状态空间知识表示方法状态空间知识表示方法 5.3 盲目的图搜索策略盲目的图搜索策略 5.4 启发式图搜索策略启发式图搜索策略 5.5 与与/或或图搜索策略图搜索策略5.2 状态空间知识表示方法5.2.1 状态空间表示法状态空间表示法5.2.2 状态空间的图描述状态空间的图描述5.2.1 状态空间表示法n 状态空间表示法：知识表示的一种方

9、法状态空间表示法：知识表示的一种方法n 状态：表示系统状态、事实等叙述型知识的一组变量或数状态：表示系统状态、事实等叙述型知识的一组变量或数组：组： qi：状态变量：状态变量,nqqqQ21 ,mfffF21 操作：表示引起状态变化的过程型知识的一组关系或函数：操作：表示引起状态变化的过程型知识的一组关系或函数： 操作符（算子，操作算子）：走步，过程，规则，数学算操作符（算子，操作算子）：走步，过程，规则，数学算子，运算符或逻辑符子，运算符或逻辑符5.2.1 状态空间表示法 状态空间：利用状态变量和操作符号，表示系统或状态空间：利用状态变量和操作符号，表示系统或问题的有关知识的符号体系，状态空

10、间是一个四元问题的有关知识的符号体系，状态空间是一个四元组：组： ),(0GSOS ：状态集合。：状态集合。 ：操作算子的集合。：操作算子的集合。 ：包含问题的初始状态是：包含问题的初始状态是S 的非空子集。的非空子集。 ：若干具体状态或满足某些性质的路径信息描述：若干具体状态或满足某些性质的路径信息描述。O0SGS5.2.1 状态空间表示法 求解路径求解路径：从从S0结点到结点到G结点的路径。结点的路径。 GSSSkOOOO321210kOO,1：状态空间的一个解。：状态空间的一个解。 状态空间的一个解：一个有限的状态空间的一个解：一个有限的操作算子序列操作算子序列。v例如下棋、迷宫及各种游

11、戏。例如下棋、迷宫及各种游戏。 例例1 三数码问题（数码问题（3 puzzle problem）。 5.2.1 状态空间表示法状态空间表示法状态集状态集 ：所有摆法：所有摆法S操作算子：操作算子：将空格向上移将空格向上移Up将空格向左移将空格向左移Left将空格向下移将空格向下移Down将空格向右移将空格向右移Right123312初始棋局目标棋局解法解法1：123123123312312312初始棋局目标棋局downrightupleftdown5.2.1 状态空间表示法状态空间表示法5.2.2 状态空间的图描述（状态）（状态）（操作算子）（操作算子）状态空间的有向图描述状态空间的有向图描述

12、第5章 搜索求解策略 5.1 搜索的概念搜索的概念 5.2 状态空间知识表示方法状态空间知识表示方法5.3 盲目的图搜索策略盲目的图搜索策略 5.4 启发式图搜索策略启发式图搜索策略 5.5 与与/或或图搜索策略图搜索策略5.3 盲目的图搜索策略5.3.1 回溯策略回溯策略5.3.2 宽度优先搜索策略宽度优先搜索策略5.3.3 深度优先搜索策略深度优先搜索策略5.3.1 回溯策略 带回溯策略的搜索：带回溯策略的搜索：（走不通就回头）（走不通就回头）u 从初始状态出发，不停地、试探性地寻找路径，从初始状态出发，不停地、试探性地寻找路径，直到它到达目的或直到它到达目的或“不可解结点不可解结点”，即

13、，即“死胡同死胡同”为止。为止。u 若它遇到不可解结点就回溯到路径中若它遇到不可解结点就回溯到路径中最近的父结最近的父结点点上，查看该结点是否还有其他的子结点未被扩展上，查看该结点是否还有其他的子结点未被扩展。u若有，则沿这些子结点继续搜索；如果找到目标，若有，则沿这些子结点继续搜索；如果找到目标，就成功退出搜索，返回解题路径。就成功退出搜索，返回解题路径。5.3.1 回溯策略1 AB 2E 3J 57 K9 G6 F10 H11 D8 C回溯搜索示意图回溯搜索示意图5.3.1 回溯策略回溯搜索算法的几张表：回溯搜索算法的几张表：(1) PS（path states）表：保存当前搜索路径上的状

14、态。）表：保存当前搜索路径上的状态。如果找到了目的，如果找到了目的，PS就是解路径上的状态有序集。就是解路径上的状态有序集。 (2) NPS（new path states）表：新的路径状态表。它包）表：新的路径状态表。它包含了等待搜索的状态，其后裔状态还未被搜索到，含了等待搜索的状态，其后裔状态还未被搜索到，即未被生成扩展即未被生成扩展 。(3) NSS（no solvable states）表：不可解状态集，列出）表：不可解状态集，列出了找不到解题路径的状态。如果在搜索中扩展出的了找不到解题路径的状态。如果在搜索中扩展出的状态是它的元素，则可立即将之排除，不必沿该状状态是它的元素，则可立即

15、将之排除，不必沿该状态继续搜索。态继续搜索。 回溯搜索示意图的回溯轨迹：回溯搜索示意图的回溯轨迹： 初值：初值：PS=A； NPS=A； NSS= ； CS=A。 5.3.1 回溯策略1 AB 2E 3J 57 K9 G6 F10 H11 D8 C5.3.1 回溯策略图搜索算法（深度优先、宽度优先、最好优先搜索等）图搜索算法（深度优先、宽度优先、最好优先搜索等）的回溯思想：的回溯思想：（1）用未处理状态表（用未处理状态表（NPS）使算法能返回（回溯）到其）使算法能返回（回溯）到其 中任一状态。中任一状态。 （2）用一张）用一张“死胡同死胡同”状态表（状态表（NSS）来避免算法重新搜索）来避免算

16、法重新搜索 无解的路径。无解的路径。 （3）在）在PS 表中记录当前搜索路径的状态，当满足目的时可表中记录当前搜索路径的状态，当满足目的时可 以将它作为结果返回。以将它作为结果返回。 （4）为避免陷入死循环必须对新生成的子状态进行检查，）为避免陷入死循环必须对新生成的子状态进行检查， 看它是否在该三张表中看它是否在该三张表中 。5.3.2 宽度优先搜索策略宽度优先搜索宽度优先搜索：以接近起始结点的程度为依据进行逐层扩展：以接近起始结点的程度为依据进行逐层扩展的搜索方法。（用队列的存储结构，类似于树的按层次遍历的搜索方法。（用队列的存储结构，类似于树的按层次遍历的过程。的过程。特点：逐层搜索；高

17、价搜索：若解存在，必能找到。特点：逐层搜索；高价搜索：若解存在，必能找到。 例例2 通过搬动积木块，希望从初始状态达到一个目通过搬动积木块，希望从初始状态达到一个目的状态，即三块积木堆叠在一起。的状态，即三块积木堆叠在一起。 BCAABC(a) 初始状态初始状态(b) 目的状态目的状态 积木问题积木问题5.3.2 宽度优先搜索策略 操作算子为操作算子为MOVE（X，Y）：把积木）：把积木X搬到搬到Y（积（积木或桌面）上面。木或桌面）上面。MOVE（A，Table）：）：“搬动积木搬动积木A到桌到桌面上面上”。 操作算子可运用的先决条件：操作算子可运用的先决条件：（1）被搬动积木的顶部必须为空。

18、）被搬动积木的顶部必须为空。（2）如果）如果 Y 是积木，则积木是积木，则积木 Y 的顶部也必须为空。的顶部也必须为空。（3）同一状态下，运用操作算子的次数不得多于一次。）同一状态下，运用操作算子的次数不得多于一次。5.3.2 宽度优先搜索策略ABABACCBACCCBABCABACBAABCBCBCCABAMOVE(A,TABLE)MOVE(A,TABLE)MOVE(C,AMOVE(C,A) )MOVE(A,CMOVE(A,C) )MOVE(B,A)MOVE(B,A)MOVE(B,C)MOVE(B,C) MOVE(C,AMOVE(C,A) )MOVE(C,B)MOVE(C,B) MOVE(C

19、,B)MOVE(C,B)MOVE(A,BMOVE(A,B) )0S1S2S3S4S5S6S7S8S9S10S没有后裔，失败退出 积木问题的宽度优先搜索树积木问题的宽度优先搜索树5.3.2 宽度优先搜索策略5.3.2 宽度优先搜索策略vopen表（表（NPS表）：已经生成出来但其子状态未被搜索的状表）：已经生成出来但其子状态未被搜索的状态。态。vclosed表（表（ PS表和表和NSS表的合并）：记录了已被生成扩展过表的合并）：记录了已被生成扩展过的状态。的状态。 重复重复OPEN表表CLOSE表表0S0 1234。重复重复OPEN表表CLOSE表表0S0 1S1，S2，S3S0234。重复重复

20、OPEN表表CLOSE表表0S0 1S1，S2，S3S02S2，S3，S4，S5，S6，S7S1，S034。重复重复OPEN表表CLOSE表表0S0 1S1，S2，S3S02S2，S3，S4，S5，S6，S7S1，S03S3，S4，S5，S6，S7S2，S1，S04。重复重复OPEN表表CLOSE表表0S0 1S1，S2，S3S02S2，S3，S4，S5，S6，S7S1，S03S3，S4，S5，S6，S7S2，S1，S04S4，S5，S6，S7，S8S3，S2，S1，S0。5.3.3 深度优先搜索策略0S12345678910111213KK 深度优先搜索法中状态的搜索次序深度优先搜索法中状态

21、的搜索次序0S12345678910111213KK深度优先搜索深度优先搜索：首先扩展最新产生的节点，深度相等的节：首先扩展最新产生的节点，深度相等的节点可以任意排列的搜索方法。点可以任意排列的搜索方法。（用堆栈的数据结构）（用堆栈的数据结构）特点：搜索沿着状态空间的某单一路径沿着起始点向下进特点：搜索沿着状态空间的某单一路径沿着起始点向下进行下去，仅当搜索到达一个没有后裔的状态时，才选择另行下去，仅当搜索到达一个没有后裔的状态时，才选择另一条替代路径。一条替代路径。5.3.3 深度优先搜索策略v深度优先搜索并不能保证第一次搜索到的某个状态时的路径深度优先搜索并不能保证第一次搜索到的某个状态时

22、的路径是到这个状态的最短路径，为防止搜索过程沿着无益的路径是到这个状态的最短路径，为防止搜索过程沿着无益的路径扩展下去，给出一个节点扩展的最大深度扩展下去，给出一个节点扩展的最大深度深度界限深度界限。v为了保证找到解，应选择合适的深度限制值，或采取不断加为了保证找到解，应选择合适的深度限制值，或采取不断加大深度限制值的办法，反复搜索，直到找到解。大深度限制值的办法，反复搜索，直到找到解。 v与宽度优先搜索根本的不同点：将扩展的后继节点放在与宽度优先搜索根本的不同点：将扩展的后继节点放在OPEN表的最前端。表的最前端。 例例3 3 卒子穿阵问题卒子穿阵问题，要求一卒子从顶部通过下图所要求一卒子从

23、顶部通过下图所示的阵列到达底部。卒子行进中不可进入到代表敌示的阵列到达底部。卒子行进中不可进入到代表敌兵驻守的区域（标注兵驻守的区域（标注1），并不准后退。假定深度），并不准后退。假定深度限制值为限制值为5。 000100100100000121342134行列图5.10阵列图000100100100000121342134行列图5.10阵列图 阵列图阵列图 5.3.3 深度优先搜索策略0S1S)1 ,1(2S)2,1(3S)2,2(4S)1 ,2(5S)1 ,3(6S)2,3(7S)3,2(8S)3,1(9S)2,1(14S)4,1(10S)2,2(11S)1 ,2(12S)1 ,3(13S

24、)3,2(15S)4,2(16S)4,3(17S)4,4(18S)4,1(死死解 0S1S)1 ,1(2S)2,1(3S)2,2(4S)1 ,2(5S)1 ,3(6S)2,3(7S)3,2(8S)3,1(9S)2,1(14S)4,1(10S)2,2(11S)1 ,2(12S)1 ,3(13S)3,2(15S)4,2(16S)4,3(17S)4,4(18S)4,1(死死死死深度限制深度限制解open表：S17、S18closed表：S0S16 卒子穿阵的深度优先搜索树卒子穿阵的深度优先搜索树5.3.3 深度优先搜索策略死死死死000100100100000121342134行列图5.10阵列图0

25、00100100100000121342134行列图5.10阵列图S20(2,4)S19(2,4)S21(4,4)最优解5.3.2 宽度优先搜索策略重复重复OPEN表表CLOSE表表0S0 1S1，S2，S8，S18S02S2，S8，S18S1，S03S3，S8，S18S2，S1，S04S4，S7，S8，S18S3，S2，S1，S05S5，S7，S8，S18S4，S3，S2，S1，S06S6，S7，S8，S18S5，S4，S3，S2，S1，S07S8，S18S7，S6，S5，S4，S3，S2，S1，S0。 。5.3.3 深度优先搜索策略一般情况下，深度优先搜索法占内存少但速度较一般情况下，深度

26、优先搜索法占内存少但速度较慢，广度优先搜索算法占内存多但速度较快，在慢，广度优先搜索算法占内存多但速度较快，在距离和深度成正比的情况下能较快地求出最优解距离和深度成正比的情况下能较快地求出最优解。因此在选择用哪种算法时，要综合考虑。决定取因此在选择用哪种算法时，要综合考虑。决定取舍。舍。深度搜索和宽度搜索深度搜索和宽度搜索 深度搜索与宽度搜索的控制结构和产生系统很深度搜索与宽度搜索的控制结构和产生系统很相似，唯一的区别在于对扩展节点选取上。相似，唯一的区别在于对扩展节点选取上。 由于其保留了所有的前继节点，所以在产生后由于其保留了所有的前继节点，所以在产生后继节点时可以去掉一部分重复的节点，从

27、而提继节点时可以去掉一部分重复的节点，从而提高了搜索效率。高了搜索效率。 这两种算法每次都扩展一个节点的所有子节点这两种算法每次都扩展一个节点的所有子节点，而不同的是，深度搜索下一次扩展的是本次，而不同的是，深度搜索下一次扩展的是本次扩展出来的扩展出来的子节点子节点中的一个，而广度搜索扩展中的一个，而广度搜索扩展的则是本次扩展的节点的的则是本次扩展的节点的兄弟节点兄弟节点。 在具体实现上为了提高效率在具体实现上为了提高效率,所以采用了不同的所以采用了不同的数据结构。数据结构。第5章 搜索求解策略 5.1 搜索的概念搜索的概念 5.2 状态空间知识表示方法状态空间知识表示方法 5.3 盲目的图搜

28、索策略盲目的图搜索策略5.4 启发式图搜索策略启发式图搜索策略 5.5 与与/或或图搜索策略图搜索策略盲目图搜索策略特点：盲目图搜索策略特点：v1）不需要重排）不需要重排OPEN表；表；v2）没有启发信息的一种搜索形式；）没有启发信息的一种搜索形式；v3）一般只适用于求解简单的问题。）一般只适用于求解简单的问题。5.4 启发式图搜索策略5.4 启发式图搜索策略5.4.1 启发式策略启发式策略5.4.2 启发信息和估价函数启发信息和估价函数5.4.3 A搜索算法搜索算法5.4.4 A*搜索算法及其特性分析搜索算法及其特性分析 为什么需要启发式搜索？为什么需要启发式搜索？盲目搜索的不足：盲目搜索的

29、不足：l 效率低，耗费过多的计算时间和空间；效率低，耗费过多的计算时间和空间；l 可能产生组合爆炸；可能产生组合爆炸； 什么可以做启发信息？什么可以做启发信息？ 用来简化搜索过程有关用来简化搜索过程有关具体问题领域的特性信息具体问题领域的特性信息叫做启发信叫做启发信息；息； 利用利用启发式信息启发式信息进行搜索的方法就是启发式搜索方法进行搜索的方法就是启发式搜索方法特点：重排特点：重排OPEN表，选择表，选择最有希望的节点最有希望的节点加以扩展；加以扩展； 种类：种类：A算法，算法，A*算法等算法等5.4 启发式图搜索策略5.4.1 启发式策略运用启发式策略的两种基本情况运用启发式策略的两种基

30、本情况： （1）一个问题由于在问题陈述和数据获取方面固有）一个问题由于在问题陈述和数据获取方面固有 的模糊性，的模糊性，可能可能会使它会使它没有一个确定的解。没有一个确定的解。 （2）虽然一个问题可能有确定解，但是其）虽然一个问题可能有确定解，但是其状态空间状态空间 特别大，特别大，搜索中生成扩展的状态数会随着搜索搜索中生成扩展的状态数会随着搜索 的深度呈指数级增长。的深度呈指数级增长。5.4.1 启发式策略 “启发启发”（heuristic）：关于发现和发明操作算）：关于发现和发明操作算子及搜索方法的研究。子及搜索方法的研究。 在状态空间搜索中，启发式被定义成一系列在状态空间搜索中，启发式被

31、定义成一系列操操作算子作算子，并能从状态空间中选择最有希望到达，并能从状态空间中选择最有希望到达问题解的路径。问题解的路径。 启发式策略：利用与问题有关的启发信息进行启发式策略：利用与问题有关的启发信息进行搜索。搜索。 例例4 4 一字棋一字棋。在九宫棋盘上，从空棋盘开始，双方轮流在棋盘上在九宫棋盘上，从空棋盘开始，双方轮流在棋盘上摆各自的棋子摆各自的棋子 或或 （每次一枚），谁先取得三子一线（一行（每次一枚），谁先取得三子一线（一行、一列或一条对角线）的结果就取胜。、一列或一条对角线）的结果就取胜。 5.4.1 启发式策略 和和 能够在棋盘中摆成的各种不同的棋局就是问题空间能够在棋盘中摆成的

32、各种不同的棋局就是问题空间中的不同状态。中的不同状态。 9个位置上摆放个位置上摆放空，空， ， 有有 39 种棋局。种棋局。 可能的走法可能的走法 ： 9！。！。赢的几率赢的几率赢的几率图5.12 启发式策略的运用赢的几率赢的几率赢的几率图5.12 启发式策略的运用 启发式策略的运用启发式策略的运用5.4.1 启发式策略图5.13启发式搜索下缩减的状态空间启发式搜索下缩减的状态空间启发式搜索下缩减的状态空间5.4.1 启发式策略5.4.2 启发信息和估价函数 求解问题中能利用的大多求解问题中能利用的大多是非完备的启发信息是非完备的启发信息：（1）求解问题系统不可能知道与实际问题有关的全）求解问

33、题系统不可能知道与实际问题有关的全部信息，因而无法知道该问题的全部状态空间，也部信息，因而无法知道该问题的全部状态空间，也不可能用一套算法来求解所有的问题。不可能用一套算法来求解所有的问题。（2）有些问题）有些问题在理论上虽然存在着求解算法，但是在理论上虽然存在着求解算法，但是在工程实践中，这些算法不是效率太低，就是根本在工程实践中，这些算法不是效率太低，就是根本无法实现。无法实现。一字棋：一字棋：9！，西洋跳棋：！，西洋跳棋：1078，国际象棋：，国际象棋：10120，围棋：，围棋：10761。假设每步可以搜索一个棋局，用极限并行速度（假设每步可以搜索一个棋局，用极限并行速度（10-104年

34、年/步）来步）来处理，搜索一遍国际象棋的全部棋局也得处理，搜索一遍国际象棋的全部棋局也得1016年即年即1亿亿年才可以亿亿年才可以算完！算完！ 5.4.2 启发信息和估价函数启发信息按运用的方法分类：启发信息按运用的方法分类： （1）陈述性启发信息：更准确地描述状态）陈述性启发信息：更准确地描述状态 （2）过程性启发信息：一系列操作算子）过程性启发信息：一系列操作算子 （3）控制性启发信息：控制策略）控制性启发信息：控制策略5.4.2 启发信息和估价函数 估价函数：任务是估价函数：任务是估计待搜索结点的估计待搜索结点的“有希望有希望”程度程度，并依，并依次给它们排定次序（在次给它们排定次序（在

35、open表中）。表中）。 估价函数估价函数f (n) ：从初始结点经过：从初始结点经过n结点到达目的结点到达目的 结点的路结点的路径的最小代价估计值，其一般形式是径的最小代价估计值，其一般形式是 f (n)= g(n) + h (n) g(n)：从初始节点到节点：从初始节点到节点n的的实际代价实际代价h(n)： 从节点从节点n到目标节点的到目标节点的最优路径最优路径的估计代价的估计代价一般地，在一般地，在f(n)中，中， g(n)的比重越大，越倾向于宽度优先搜索的比重越大，越倾向于宽度优先搜索方式，而方式，而 h (n)的比重越大，表示启发性能越强。的比重越大，表示启发性能越强。 设初始节点设

36、初始节点S0和目标节点和目标节点Sg分别如下图的初始分别如下图的初始棋局和目标棋局所示。棋局和目标棋局所示。2831647512384765初始状态目标状态例例5 八数码的估价函数八数码的估价函数设计方法有多种，并且不同的估价函数对求解八数码问题有不设计方法有多种，并且不同的估价函数对求解八数码问题有不同的影响。同的影响。 最简单的估价函数：取一格局与目的格局相比，其位置不最简单的估价函数：取一格局与目的格局相比，其位置不符的数码数目符的数码数目:f(S0)=5 较好的估价函数：各数码移到目的位置所需移动的距离的较好的估价函数：各数码移到目的位置所需移动的距离的总和总和:f(S0)=6 第三种

37、估价函数：对每一对逆转数码乘以一个倍数。第三种估价函数：对每一对逆转数码乘以一个倍数。f(S0)=0 第四种估价函数：克服了仅计算数码逆转数目策略的局限第四种估价函数：克服了仅计算数码逆转数目策略的局限，将位置不符数码数目的总和与，将位置不符数码数目的总和与3倍数码逆转数目相加。倍数码逆转数目相加。f(S0)=0. 5.4.2 启发信息和估价函数5.4.2 启发信息和估价函数 估价函数：设计一个好的估价函数有相当的难度估价函数：设计一个好的估价函数有相当的难度，是一个，是一个经验问题经验问题，判断和直觉是很重要的因素。，判断和直觉是很重要的因素。设计估价函数的目标是利用有限的信息做出精确设计估

38、价函数的目标是利用有限的信息做出精确的估价的估价衡量估计函数的好坏最终标准取决于具体应用时衡量估计函数的好坏最终标准取决于具体应用时的搜索效果。的搜索效果。5.4.3 A搜索算法搜索算法 启发式图搜索法启发式图搜索法A算法和算法和A*算法算法 爬山法爬山法：（Pearl，1984）在搜索过程中先扩展当前的状态）在搜索过程中先扩展当前的状态，然后再评估他的孩子，而后选择最佳的孩子做进一步扩，然后再评估他的孩子，而后选择最佳的孩子做进一步扩展，展，不保留不保留他的兄弟姐妹和双亲，当搜索遇到比其孩子更他的兄弟姐妹和双亲，当搜索遇到比其孩子更佳的状态则停止。佳的状态则停止。 最佳优先搜索：最佳优先搜索

39、：对对OPEN表的状态进行排序，排序的依据表的状态进行排序，排序的依据是是按状态与目标按状态与目标“接近程度接近程度”的某种启发式的某种启发式估计，每一轮估计，每一轮循环考虑循环考虑OPEN表中最有希望的状态。表中最有希望的状态。 A算法：算法：使用估价函数的最佳优先搜索。使用估价函数的最佳优先搜索。5.4.3 A搜索算法搜索算法 A算法的基本特点：算法的基本特点： 如何寻找并设计一个与问题有关的如何寻找并设计一个与问题有关的 h(n) 及构出及构出 f(n)= h(n)+ g(n) ， 然后以然后以f(n) 的大小来排列待扩的大小来排列待扩展状态的次序，每次选择展状态的次序，每次选择f(n)

40、 值值最小者最小者进行扩展进行扩展。 open表：保留所有已生成而未扩展的状态。表：保留所有已生成而未扩展的状态。 closed表：记录已扩展过的状态。表：记录已扩展过的状态。 进入进入open表的状态是根据其估值的大小插入到表中合适表的状态是根据其估值的大小插入到表中合适的位置，每次的位置，每次从表中优先取出启发估价函数值最小的状态加从表中优先取出启发估价函数值最小的状态加以扩展。以扩展。 A算法流程图算法流程图开始开始把把S0放入放入OPEN表中表中,计算计算f(S0) OPEN=NIL? 选取选取OPEN表中表中f最小的节点最小的节点i放入放入CLOSED表中表中 i=G ? 扩展扩展i

41、得后继节点得后继节点j,计算计算f(j),提供返回提供返回i的指针的指针,把把节点节点j送回送回OPEN表，利用表，利用f(j)对对OPEN表进行重表进行重排，调整亲子关系和指针。排，调整亲子关系和指针。失败失败成功成功5.4.3 A搜索算法搜索算法YNYN5.4.3 A搜索算法搜索算法 例例6 6 利用利用A搜索算法求解八数码问题的搜索树，其搜索算法求解八数码问题的搜索树，其估价函数定义为估价函数定义为 f (n)= d(n) + w (n) ：状态的深度，每步为单位代价。：状态的深度，每步为单位代价。 ：节点：节点n的数码格局同目标节点相比，的数码格局同目标节点相比，数码数码不同的位置个数

42、不同的位置个数。 w( (S0)=4)=4)(nd)(nw 设初始节点设初始节点S0和目标节点和目标节点Sg分别如下图的初始分别如下图的初始棋局和目标棋局所示。棋局和目标棋局所示。2831647512384765初始状态目标状态5.4.3 A搜索算法搜索算法2 8 31 6 47 52 8 31 47 6 52 8 31 6 4 7 52 8 31 6 47 52 31 8 47 6 52 8 3 1 47 6 52 8 31 47 6 52 8 37 1 4 6 5 8 32 1 47 6 5 2 31 8 47 6 52 31 8 47 6 51 2 3 8 47 6 51 2 38 47

43、 6 51 2 37 8 4 6 5s(4)A(1+5)B(4)C(6)D(2+3)E(5)F(6)G(3+3)H(7)I(5)J(7)K(5)L(5)M(7)目标目标123456 open表和表和closed表内状态排列的变化情况表内状态排列的变化情况 5.4.3 A搜索算法搜索算法重重复复OPEN表表CLOSE表表0S(4) 1B(4)，A(6), C(6)S(4)2D(5)，E(5), A(6), C(6),F(6)S(4)，B(4)3E(5), A(6), C(6),F(6), G(6),H(7)S(4)，B(4), D(5)4I(5), A(6), C(6),F(6), G(6),H

44、(7), J(7)S(4)，B(4), D(5), E(5)5K(5), A(6), C(6),F(6), G(6),H(7), J(7)S(4)，B(4), D(5), E(5), I(5)6L(5), A(6), C(6),F(6), G(6),H(7), J(7), M(7) S(4)，B(4), D(5), E(5), I(5), K(5)7A(6), C(6),F(6), G(6),H(7), J(7), M(7)S(4)，B(4), D(5), E(5), I(5), K(5), L(5)L为目的状态，成功推出，结束搜索为目的状态，成功推出，结束搜索 假设假设f*(n)为从初始节点

45、为从初始节点S0出发，约束经过节点出发，约束经过节点n到达目标节到达目标节点的最小代价值。估价函数点的最小代价值。估价函数f(n)则是则是f*(n)的估计值。的估计值。 f*(n)由以下两部分所组成：由以下两部分所组成： 一部分是从初始节点一部分是从初始节点S0到节点到节点n的最小代价，记为的最小代价，记为g*(n)； 另一部分是从节点另一部分是从节点n到目标节点的最小代价，记为到目标节点的最小代价，记为h*(n)，因，因此有此有 f*(n)=g*(n) +h*(n)5.4.4 A*搜索算法搜索算法 A*算法算法1）OPEN表中的节点按着估价函数表中的节点按着估价函数f(n)=g(n)+h(n)的值的值从小到大排序从小到大排序2）g(n)是对是对g*(n)的最优估价；的最优估价；3）h(n)是是h*(n)的下界：的下界：h(n) h*(n)g*(n):初始节点到节点初始节点到节点n的最小代价的最小代价h*(n)：节点：节点n到目标节点到目标节点的最小代价；的最小代价；（一定存在）一定存在）5.4.4 A*搜索算法搜索算法 A*算法就是对估价函数加上一些限制后得到的一算法就是对估价函数加上一些限制后得到的一种启发式搜索算法。种启发式搜索算法。 如果某一问题有