状态空间搜索.ppt

《状态空间搜索.ppt》由会员分享，可在线阅读，更多相关《状态空间搜索.ppt（180页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、状态空间搜索 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life, there is hope。有生命必有希望。有生命必有希望 基于递归的搜索基于递归的搜索 递归递归 递归搜索递归搜索 模式驱动搜索模式驱动搜索 产生式系统产生式系统 定义与历史定义与历史 产生式系统示例产生式系统示例 产生式系统搜索的控制产生式系统搜索的控制 产生式系统的优点产生式系统的优点 状态空间搜索策略状态空间搜索策略 数据驱动和目标驱动的搜索数据驱动和目标驱动的搜索 状态空间可以从两个方向进行搜索：从实际问题状态空间可以从两个方向进行搜索：从实际问题的

2、给定数据向目标搜索或者从目标到数据进行搜的给定数据向目标搜索或者从目标到数据进行搜索。索。 数据驱动搜索，也称为正向推理。搜索的过程是数据驱动搜索，也称为正向推理。搜索的过程是应用规则从给定的条件产生新的条件，再用规则应用规则从给定的条件产生新的条件，再用规则从新的条件产生更多的新条件。这个过程持续到从新的条件产生更多的新条件。这个过程持续到有一条满足目标要求的路径产生为止。有一条满足目标要求的路径产生为止。 另一种求解方法是：先从欲想达到的目标开始，另一种求解方法是：先从欲想达到的目标开始，看哪些规则或合法移动能产生该目标以及应用这看哪些规则或合法移动能产生该目标以及应用这些规则产生目标时需

3、要哪些条件。这些条件就成些规则产生目标时需要哪些条件。这些条件就成为我们要达到的新目标，即子目标。搜索就通过为我们要达到的新目标，即子目标。搜索就通过反向的、连续的子目标不断地进行，一直到找到反向的、连续的子目标不断地进行，一直到找到问题给定的条件为止。这样就找到了一条从数据问题给定的条件为止。这样就找到了一条从数据到目标的移动或规则组成的链，尽管搜索方向和到目标的移动或规则组成的链，尽管搜索方向和它正好相反。这种方法称为目标驱动的推理或反它正好相反。这种方法称为目标驱动的推理或反向推理。向推理。 在实际的搜索系统中可能两种方法同时使用，即在实际的搜索系统中可能两种方法同时使用，即一方面从数据

4、驱动向目标进行，可能搜索到某一一方面从数据驱动向目标进行，可能搜索到某一个子目标；另一方面又从目标向数据方面进行搜个子目标；另一方面又从目标向数据方面进行搜索，刚好也搜索到该子目标，这时推理也结束，索，刚好也搜索到该子目标，这时推理也结束，即假设的目标正确。即假设的目标正确。 图搜索的实现图搜索的实现 无论是目标还是数据驱动的搜索，其求解问题都无论是目标还是数据驱动的搜索，其求解问题都是要在状态空间图中找到从初态到目标状态的路是要在状态空间图中找到从初态到目标状态的路径。而路径上弧的序列就对应解题的先后步骤。径。而路径上弧的序列就对应解题的先后步骤。若在选择解题路径时能给出绝对可靠的预言或绝若

5、在选择解题路径时能给出绝对可靠的预言或绝对正确的机制，那就不需要搜索了，求解时会一对正确的机制，那就不需要搜索了，求解时会一次成功地穿过空间到达目标，构造出一条求解路次成功地穿过空间到达目标，构造出一条求解路径来。但实际问题中没有绝对可靠的预言，求解径来。但实际问题中没有绝对可靠的预言，求解时必须尝试多条路径直到找到目标为止。回溯是时必须尝试多条路径直到找到目标为止。回溯是一种经常使用的技术。一种经常使用的技术。图搜索的实现（续）图搜索的实现（续） 带回溯的搜索从初始状态出发，不停地寻找路径带回溯的搜索从初始状态出发，不停地寻找路径一直到它到达目标或一直到它到达目标或“不可解端点不可解端点”。

6、若找到目。若找到目标，就退出搜索，返回解题路径，若遇到不可解标，就退出搜索，返回解题路径，若遇到不可解结点，就回溯到路径中最近的父结点上，查看是结点，就回溯到路径中最近的父结点上，查看是否有当前结点的兄弟结点未扩展，并沿这些分支否有当前结点的兄弟结点未扩展，并沿这些分支继续搜索。算法在每个结点上的检查过程遵循下继续搜索。算法在每个结点上的检查过程遵循下面的递归方式：面的递归方式： 图搜索的实现（续）图搜索的实现（续） 若当前状态若当前状态S未到达目标的要求，就对它的第一未到达目标的要求，就对它的第一子状态子状态Schild1递归调用回溯过程。如果在以递归调用回溯过程。如果在以Schild1为根

7、的子图中没有找到目标，就对它的兄弟为根的子图中没有找到目标，就对它的兄弟Schild2调用此过程。此过程重复进行到某个结点调用此过程。此过程重复进行到某个结点的后裔是目标或者所有子结点都搜索完为止。的后裔是目标或者所有子结点都搜索完为止。 图搜索的实现（续）图搜索的实现（续）算法就是以这种方式执行直到找到目标或遍历了状态空间为止。下图给出的是一个假设的状态空间的深度优先回溯搜索。 1A2B8C10DE36F9GHIJ457一个假设状态空间的深度优先回溯搜索一个假设状态空间的深度优先回溯搜索 图搜索的实现（续） 下面定义一个回溯搜索的算法：算法使用下面定义一个回溯搜索的算法：算法使用3张表保存状

8、张表保存状态空间中的结点。态空间中的结点。 SL状态表列出了当前路径上的状态。如果找到了目标，状态表列出了当前路径上的状态。如果找到了目标，SL就是解题路径上状态的有序集。就是解题路径上状态的有序集。 NSL新状态表，包含了等待评估的结点，其后裔结点还新状态表，包含了等待评估的结点，其后裔结点还未被扩展。未被扩展。DE不可解端点集不可解端点集,列出了找不到解题路径的列出了找不到解题路径的状态。如果在搜索中再遇到它们，就会检测到它们是状态。如果在搜索中再遇到它们，就会检测到它们是DE中的成分而立即将其排除。中的成分而立即将其排除。 为了在最普遍的情况下（是图而不是树）定义回溯算法，为了在最普遍的

9、情况下（是图而不是树）定义回溯算法，有必有必 要检测并删除多次出现的某些状态，以避免造成要检测并删除多次出现的某些状态，以避免造成路径循环。检测可以通过对每一个新生成的状态判断它路径循环。检测可以通过对每一个新生成的状态判断它是否在上述是否在上述3张表中来实现，如果它属于某一张表，就张表中来实现，如果它属于某一张表，就说明它已被搜索过不必再考虑。说明它已被搜索过不必再考虑。 图搜索的实现（续）图搜索的实现（续） 当前正在搜索的结点叫当前正在搜索的结点叫CS，即当前状态。即当前状态。CS总总是等于最近加入是等于最近加入SL中的状态，是当前正在探寻中的状态，是当前正在探寻的解题路径的的解题路径的“

10、前锋前锋”。博弈中走步用的推理。博弈中走步用的推理规则或者其他合适的问题求解操作都可应用于规则或者其他合适的问题求解操作都可应用于CS，得到一些新状态，即得到一些新状态，即CS的子状态的有序集，的子状态的有序集，重新视该集合中第一个状态为当前状态，其余重新视该集合中第一个状态为当前状态，其余的按次序放入的按次序放入NSL中，用于以后的搜索。新的中，用于以后的搜索。新的CS加入加入SL中，搜索就这样继续进行。若中，搜索就这样继续进行。若CS没没有子状态，就要从有子状态，就要从SL，NSL中删除它，将其加中删除它，将其加入入DE，然后回溯查找然后回溯查找NSL中的下一个状态。中的下一个状态。 图搜

11、索的实现（续）图搜索的实现（续） Function backtrack (回溯算法）回溯算法） begin SL:=Start; NSL:= Start; DE := ; CS :=Start; /*初始化初始化*/ while NSL /*还有未检查的状态还有未检查的状态*/ do begin if CS = 目标（或符合目标的要求）目标（或符合目标的要求） then return (SL); /*成功，返回路径状态的表成功，返回路径状态的表*/ if CS没有子状态（不包括没有子状态（不包括DE，SL和和NSL中已有的中已有的状态）状态） then begin while(SL非空）非空）

12、and(CS = SL中第一个元素中第一个元素) 图搜索的实现（续）图搜索的实现（续） do begin 将将CS加入加入DE；/*标明此状态不可解标明此状态不可解*/ 从从SL中删除第一个元素；中删除第一个元素；/*回溯回溯*/ 从从NSL中删去第一个元素；中删去第一个元素； CS：=NSL中第一个元素；中第一个元素； end; 将将CS加入加入SL； end else begin 将将CS子状态（不包括子状态（不包括DE、SL、NSL中有的）加入中有的）加入NSL； 图搜索的实现（续）图搜索的实现（续） CS：=NSL中第一个元素；中第一个元素； 将将CS加入加入SL； end end;

13、return FAIL end. 假设状态空间的深度优先回溯搜索中的回溯轨迹假设状态空间的深度优先回溯搜索中的回溯轨迹如下：如下： 初值：初值：SL = A；NSL= A；DE= ；CS=A； 图搜索的实现（续）图搜索的实现（续） 重复重复 CS SL NSL DE 0 A A A 1 B BA BCDA 2 E EBA EFBCDA 3 H HEBA HIEFBCDA 4 I IEBA IEFBCDA H 5 F FBA FBCDA EIH 6 J JFBA JFBCDA EIH 7 C CA CDA BFJEIH 8 G GCA GCDA BFJEIH 1A 2B8C10D 3E6F9G

14、4H5I7J 一个假想的状态空间的深度优先回溯搜索一个假想的状态空间的深度优先回溯搜索 状态空间的一般搜索过程 一个问题的状态空间是一个三元组，即 S,F,G，其中S是问题所有可能的状态的集合，F是操作的集合，G是目标状态的集合一般，如果问题的状态空间不太大的话，可以用显式的方式画出其状态空间图，否则用隐式的方法画出其状态空间图对状态空间的搜索就是从图中某个初始状态出发，寻求一条到达目标状态的路径状态空间的一般搜索过程 对状态空间的搜索过程用到两张表：OPEN表和CLOSED表，它们的结构如下： Open表 状态节点父节点 Closed表 编号状态节点父节点 状态空间的一般搜索过程 其中ope

15、n表存放刚生成的节点，对于不同的搜索策略，节点在open表中的排列顺序是不同的例如对宽度优先搜索是先生成的节点排在前面，而对深度优先搜索则是后生成的节点排在前面 Closed表用于存放将要扩展或者已经扩展的节点搜索的一般过程如下：状态空间的一般搜索过程 (1)把初始节点S0放进open表，并建立只包含S0的图，记为 (2)检查open表是否为空，若为空则问题无解，退出 (3)把open表的第一个节点取出放入closed表，并记该节点为n. (4)考察节点n是否为目标节点，若是，则求得了问题的解，退出 (5)扩展节点n，生成一组子节点把其中不是状态空间的一般搜索过程 节点n的先辈的那些子节点记作

16、集合，并把这些子节点作为节点n的子节点加入中 (6)针对中子节点的不同情况，分别进行如下处理： )对那些未曾在中出现过的成员设置一个指向父节点（即节点n）的指针，并把它们放入open表 )对于那些先前已在中出现的成员，确定是否需要修改它指向父节点的指针 )对于那些先前已在中出现并且已经扩展状态空间的一般搜索过程 了的成员，确定是否是需要修改其后继节点指向父节点的指针 (7)按某种搜索策略对open表中的节点进行排序 (8)转第步 说明：上面对状态空间的搜索过程具有通用性，后面讨论的各种搜索策略都可看作是它的一个特例各种搜索策略的主要区别仅在于open表中节点的排序准则不同例如在宽度优先搜索中是

17、先生成的节点排在前，在深度优先搜索中是后生成的节点排在前等状态空间的一般搜索过程 一个节点经一个算符操作后一般只生成一个子节点，但适用于一个节点的算符可能有多个，此时就会生成一组子节点在这些子节点中可能有些是当前扩展节点(即节点n)的父节点，祖父节点等，此时不能把这些先辈节点作为当前扩展节点的子节点余下的子节点记作集合，并加入图中 一个新生成的节点，它可能是第一次被生成的节点，也可能是先前已作为其它节点的后继节点被生成过，当前又作为另一个节点的后继节状态空间的一般搜索过程 点被再次生成此时，它应该作为哪一个节点的后继呢？一般由原始节点到该节点上所付出的代价来决定，哪条路径付出的代价小，相应的节

18、点就作为它的父节点 深度和广度优先搜索深度和广度优先搜索 深度优先搜索、广度优先搜索、有界深度优先搜索及最好优先搜索都与backtrack方法类似，所不同的是，它们实现了另外一些搜索策略，为求解提供了更灵活的手段。 广度优先搜索采取的是先横后纵的搜索策略，而深度优先搜索采取的是先纵后横的搜索策略。 A BCD EFGHIJ KLMNOPQR STU 用于深度和广度优先搜索的例图 深度和广度优先搜索深度和广度优先搜索 例如在上面的深度和广度优先搜索图中，深度优例如在上面的深度和广度优先搜索图中，深度优先搜索的顺序是：先搜索的顺序是： A，B，E，K，S，L，T，F，M，C，G，N，H，O，P，U

19、，I，Q，J，R 而在广度优先搜索中结点的顺序是：而在广度优先搜索中结点的顺序是： A，B，C，D，E，F，G，H，I，J，K，L，M，N，O，P，Q，R，S，T，U 算法中设有两个表：算法中设有两个表：OPEN表和表和CLOSED表。表。 OPEN表中放的是未扩展的结点，表中放的是未扩展的结点， CLOSED表表中放的是已扩展的结点。中放的是已扩展的结点。深度和广度优先搜索深度和广度优先搜索 可以看出这里的可以看出这里的open表与回溯算法中的表与回溯算法中的NSL相似，相似，而而closed表则是回溯算法中表则是回溯算法中SL和和DE的合并的合并. 当对解的先验信息有所了解时（比如知道解可

20、能当对解的先验信息有所了解时（比如知道解可能落在最右分枝或最左分枝上时）深度优先搜索的落在最右分枝或最左分枝上时）深度优先搜索的速度还是很快的，如果弄错了方向可能会使搜索速度还是很快的，如果弄错了方向可能会使搜索落入陷阱中，补救的措施是采用定界的方法落入陷阱中，补救的措施是采用定界的方法有有界深度优先搜索。其思想是定一个界界深度优先搜索。其思想是定一个界d，这个界这个界d可以是深度可以是深度 ，也可以是一个代价。也可以是一个代价。 以上几种搜索方法都是盲目搜索的典型代表。以上几种搜索方法都是盲目搜索的典型代表。宽度优先搜索宽度优先搜索 宽度优先搜索的过程如下： 、把初始节点放入open表 、如

21、果open表为空，则问题无解，退出 、把open表的第一个节点(记为n)取出放入closed表 、考察节点n是否为目标节点，若是则求得了问题的解，退出。 、若节点n不可扩展，则转第步 、扩展节点n将其子节点放入open表的尾部宽度优先搜索宽度优先搜索 并为每一个子节点配置指向父节点指针，然后转其图示如p265的图所示 例：重排九宫问题在一个的方格棋盘上放置分别标有数字1,2,3,4,5,6,7,8的张牌，初始状态为S0目标状态为Sg即： S0为：Sg为： 宽度优先搜索宽度优先搜索 可使用的算符有，空格左移，右移，上移，下移 宽度优先搜索的图示如p267页的图深度优先搜索 深度优先搜索的过程如下

22、： 、把初始节点放入open表 、如果open表为空，则问题无解，退出 、把open表的第一个节点(记为n)取出放入closed表 、考察节点n是否为目标节点，若是则求得了问题的解，退出。 、若节点n不可扩展，则转第步 、扩展节点n将其子节点放入open表的首部深度优先搜索 深度优先搜索和宽度优先搜索的区别仅在于：宽度优先搜索是把节点n的子节点放入到open表的尾部，而深度优先搜索则是将节点n的子节点放入open表的首部深度优先搜索重排九宫的例子见p268页的图有界深度优先搜索 为了解决深度优先搜索不完备的问题，避免搜索过程陷入无穷分支的死循环，提出了有界深度优先搜索方法其过程如下： 、把初始

23、节点放入open表，置S0深度d(S0)=0 、如果open表为空，则问题无解，退出 、把open表的第一个节点(记为n)取出放入closed表有界深度优先搜索 、考察节点n是否为目标节点，若是则求得了问题的解，退出。 、若节点n的深度d(n)=dm则转 、若节点n不可扩展，转 、扩展节点n将其子节点放入open表的首部，并为其配置指向父节点的指针，转 如果问题有解，且其路径长度dm，则上述搜索过程一定能求得解，若解的路径长度dm则上述搜索过程就得不到解即界的选择很重要的不是越大就越好有界深度优先搜索 有界深度优先搜索的例子见p269的 图代价树的宽度优先搜索 在上面的搜索中都没有考虑代价的问

24、题，即假设各边上的代价是相同的，如果不是这样，边上是附有不同的数字的即代价（这样的树称为代价树）在代价树中如果用g(x)表示从初始节点S0到节点x的代价，用c(x1,x2)表示从父节点x1到子节点x2的代价，则有： g(x2)=g(x1)+c(x1,x2) 代价宽度优先搜索的基本思想就是每次从open表中选择节点往closed表传送时总是选择代价最小的节点也就是说open表中的节点在任一时刻都是按代价从小到大排序的代价树的宽度优先搜索 其搜索过程如下： 、把初始节点放入open表，置S0的代价g(S0)=0 、如果open表为空，则问题无解，退出 、把open表的第一个节点(记为n)取出放入c

25、losed表 、考察节点n是否为目标节点，若是则求得了问题的解，退出。 5、若节点n不可扩展，转代价树的宽度优先搜索 6、扩展节点n将其子节点放入open表中，并为其配置指向父节点的指针，计算各子节点的代价，并按代价对open表中的全部节点按从小到大的顺序排序，转 搜索过程见p270页的图 书上例.7给出了求城市间交通图，现要求从城市到城市的最小费用交通路线求解该问题时首先要把图转换成代价树代价树的宽度优先搜索 A4B 44 C2D5 3E 交通图代价树的宽度优先搜索 转化成代价树 A 34 C1B1 245 D1D2E1 3423 E2B2C2E35E4 交通图的代价树代价树的宽度优先搜索

26、从起始节点开始，把与它直接相邻的节点作为它的子节点，若一个节点已经作为某个节点的直系先辈，则不能再作为该节点的子节点为了区别一个节点可能在代价树中的多次出现，用下标1,2,标出例如，E1,E2等都是图中的节点广度优先搜索的结果是：ACDE 代价树的深度优先搜索类似宽度优先搜索，只是把代价当作深度限制搜索的过程对与对与/或图的搜索或图的搜索 对与对与/或图的搜索与一般图的回溯相比，要求保或图的搜索与一般图的回溯相比，要求保留更多的记录。对属于或结点的后裔结点的检留更多的记录。对属于或结点的后裔结点的检查与回溯算法中一样；一旦找到一条从初始状查与回溯算法中一样；一旦找到一条从初始状态沿或结点通向目

27、标的路径，问题就解决了，态沿或结点通向目标的路径，问题就解决了，除非这条路径被证明是失败的，算法就要回溯，除非这条路径被证明是失败的，算法就要回溯，探索另一分支。但检查与结点时，要证明父结探索另一分支。但检查与结点时，要证明父结点为真，必须证明它所有的子结点为真。点为真，必须证明它所有的子结点为真。 如果在代价树中计算与结点的代价时，有两种如果在代价树中计算与结点的代价时，有两种计算方法：和代价法，最大代价法。具体使用计算方法：和代价法，最大代价法。具体使用见下图例。见下图例。对与对与/或图的搜索（续）或图的搜索（续） 和代价法：取与结点逐子结点的代价之和作为该和代价法：取与结点逐子结点的代价

28、之和作为该与结点的代价。与结点的代价。 最大代价法：取逐子结点中代价最大的作为该与最大代价法：取逐子结点中代价最大的作为该与结点的代价。结点的代价。 S a1b1解树A解树Ba2a3a4a5a6b2tttb3b4b55624434424573t与与/或树的搜索（续）或树的搜索（续） 上图中原始问题上图中原始问题S可以分解成解树可以分解成解树A或解树或解树B，即只要即只要解决其中一个原始问题解决其中一个原始问题S即可解。哪一个花费的代价更即可解。哪一个花费的代价更少，当然就是我们希望的那个分支。少，当然就是我们希望的那个分支。 1、按和代价计算的结果：、按和代价计算的结果：A树为树为25；B树为

29、树为23 2、按最大代价法计算结果：、按最大代价法计算结果：A树为：树为：14；B树为树为18 所以规定好计算方法取代价花费小的即可。所以规定好计算方法取代价花费小的即可。启发式优先搜索启发式优先搜索 前面我们介绍的搜索均是盲目搜索的情形，即在寻求前面我们介绍的搜索均是盲目搜索的情形，即在寻求下一步应扩展结点时，对解的先验信息一点都不知道。下一步应扩展结点时，对解的先验信息一点都不知道。 启发（启发（heuristic)式优先搜索就是从状态空间中选择最式优先搜索就是从状态空间中选择最有希望到达问题解的路径。它在选择待扩展结点时利有希望到达问题解的路径。它在选择待扩展结点时利用启发式函数用启发式

30、函数f(x)对对OPEN表中的结点进行计算并排序表中的结点进行计算并排序,然后再进行扩展的原则。而不同问题的启发式函数也然后再进行扩展的原则。而不同问题的启发式函数也不同，启发式函数是影响搜索效率的一个关键。不同，启发式函数是影响搜索效率的一个关键。 启发式函数：启发式函数：f(x)=g(x)+ h(x) 其中其中g(x)是从初始结点到结点是从初始结点到结点x已经付出的代价，已经付出的代价，h(x) 是从结点是从结点x到目标结点将要付出代价的估计值。一般影到目标结点将要付出代价的估计值。一般影响响f(x)的主要因素是的主要因素是h(x)。 启发式优先搜索启发式优先搜索 算法算法 速度比较快的一

31、种搜索是局部择优（也称瞎子速度比较快的一种搜索是局部择优（也称瞎子爬山爬山 （hill climbing)法）搜索法）搜索. 它的特点也是其缺点，是省略了一个它的特点也是其缺点，是省略了一个OPEN表，表，速度提高了，但由于它没有保留所走过的信息，速度提高了，但由于它没有保留所走过的信息，所以它不能修正错误的路径，可能导致它陷入所以它不能修正错误的路径，可能导致它陷入无穷尽地搜索中。无穷尽地搜索中。 瞎子爬山法在单峰单值的情况，搜索速度较快，瞎子爬山法在单峰单值的情况，搜索速度较快，可能找到一个最佳解；但在多峰多值的情况下可能找到一个最佳解；但在多峰多值的情况下只能找到较好解但不是最好解。只能

32、找到较好解但不是最好解。 人工智能中人工智能中Samuel的跳棋程序最早应用的跳棋程序最早应用的就是该方法。的就是该方法。 跳棋程序中根据几个不同启发值的总合跳棋程序中根据几个不同启发值的总合来估算棋局的状态。来估算棋局的状态。启发式优先搜索算法启发式优先搜索算法 最好优先搜索法（有序搜索法）最好优先搜索法（有序搜索法） 在最好优先搜索法中也利用两张表在最好优先搜索法中也利用两张表OPEN表和表和CLOSED表来记录已生成而未扩展的结点和已扩展的结点。算法表来记录已生成而未扩展的结点和已扩展的结点。算法中有一步是根据启发函数，按结点距离目标结点的长度中有一步是根据启发函数，按结点距离目标结点的

33、长度大小重排大小重排OPEN表中结点的顺序。扩展时（或循环时）表中结点的顺序。扩展时（或循环时）只考虑只考虑OPEN表中状态最好的结点，这就是最好优先搜表中状态最好的结点，这就是最好优先搜索法。它既不是广度优先中的先进先出，也不是深度中索法。它既不是广度优先中的先进先出，也不是深度中的后进先出而是一个按启发函数计算的大小为序的一个的后进先出而是一个按启发函数计算的大小为序的一个表，有时称为表，有时称为“优先队优先队”。 最好优先搜索的算法描述如下：最好优先搜索的算法描述如下：最好优先搜索法（续）启动把S0放入OPEN表计算f(x)OPEN=NIL取OPEN表最前面的结点N放入CLOSED表并冠

34、以顺序编号nN=Sg?N可扩展？失败是否成功是扩展N并用f(x)估计每个子结点Ni及配上指向N的返回指针，将Ni并入OPEN表，利用f(x)对OPEN表重新排序（小的在前）是否否启发式函数的实现 前面我们介绍过启发式优先搜索的关键是启发式函数的前面我们介绍过启发式优先搜索的关键是启发式函数的制定上，不同的问题有不同的启发式函数。下面介绍的制定上，不同的问题有不同的启发式函数。下面介绍的是处理重排九宫问题时制定启发式函数的原则。是处理重排九宫问题时制定启发式函数的原则。 2 8 3 1 6 4 5 6 0 7 5 2 8 3 1 2 31 4 3 4 0 8 4 7 6 5 7 6 52 8 3

35、1 6 4 5 6 07 5 位置不符将牌距离总和二倍将牌逆转数目标启发式函数的实现启发式函数的实现2131238484756765目标九宫问题的目标状态及有两个逆转位置的状态1和2，5和6下面给出重排九宫问题的两个启发式函数：下面给出重排九宫问题的两个启发式函数：f1(x)= p(x)+w(x)其中其中p(x)是是x结点和目标结点相比将牌不相符的数目，结点和目标结点相比将牌不相符的数目， w(x)是结点是结点x和目标结点相比每个将牌的距离之和。和目标结点相比每个将牌的距离之和。 启发式函数的实现启发式函数的实现f2(x)= p(x)+3s(x)其中其中p(x)是是x结点和目标结点相比每个将牌

36、结点和目标结点相比每个将牌“离家离家”的最的最短距离之和；短距离之和；s(x)是这样计算的：每个将牌和目标相比，是这样计算的：每个将牌和目标相比，若该将牌的后继和目标中该将牌的后继不同，则该将若该将牌的后继和目标中该将牌的后继不同，则该将牌得牌得2分，相同则该将牌得分，相同则该将牌得0分，中间位置有将牌得分，中间位置有将牌得1分，分，没将牌得没将牌得0分。显然分。显然f2(x)的启发强度要比的启发强度要比f1(x)大。对于大。对于给定的格局和目标请大家按两种启发式函数给出搜索给定的格局和目标请大家按两种启发式函数给出搜索的状态空间图。的状态空间图。 2 8 3 1 2 31648475765初

37、始状态目标状态博弈树的启发式搜索策略博弈树的启发式搜索策略 下棋、打牌、战争等竞争性智能活动称为博弈。其中最下棋、打牌、战争等竞争性智能活动称为博弈。其中最简单的一种称为二人零和非偶然性全信息博弈。简单的一种称为二人零和非偶然性全信息博弈。 所谓二人零和、全信息非偶然性搏弈是指：所谓二人零和、全信息非偶然性搏弈是指： （1）对垒的双方）对垒的双方A、B轮流采取行动，博弈的结果只有轮流采取行动，博弈的结果只有三种情况：三种情况：A胜，胜，B败；败；B胜胜A败；和局。败；和局。 （2）对垒的双方都了解当前的格局和过去的历史。）对垒的双方都了解当前的格局和过去的历史。 （3）任何一方在采取行动之前，

38、都要根据当前的实际）任何一方在采取行动之前，都要根据当前的实际情况进行得失分析，选取对自己最为有利而对对方最不情况进行得失分析，选取对自己最为有利而对对方最不利的对策，不存在碰运气的偶然因素。利的对策，不存在碰运气的偶然因素。博弈树的启发式搜索策略博弈树的启发式搜索策略 在博弈过程中，任何一方都希望自己获得胜利。因此，在博弈过程中，任何一方都希望自己获得胜利。因此，在在A方有多个行动方案可供选择时，他总是选对自己方有多个行动方案可供选择时，他总是选对自己有利而对有利而对B方不利的方案，站在方不利的方案，站在A方的立场看问题，供方的立场看问题，供A方选择的方案之间是一种或的关系，因为主动权操方选

39、择的方案之间是一种或的关系，因为主动权操在在A方的手里，他或者选择这个方案或这者选择另一方的手里，他或者选择这个方案或这者选择另一个方案。个方案。 但是，若但是，若B方也有可供选择的若干方案，则对方也有可供选择的若干方案，则对A方来说方来说这些方案之间是与的关系，因为这时主动权操在这些方案之间是与的关系，因为这时主动权操在B手手里，这些可供选择的方案中任何一个都可能被里，这些可供选择的方案中任何一个都可能被B选中，选中，A方必须考虑到对自己最不利的情况发生。站在任何方必须考虑到对自己最不利的情况发生。站在任何一方的立场上画出来的博弈树都是一棵与或结点交替一方的立场上画出来的博弈树都是一棵与或结

40、点交替产生的与产生的与/或树或树称为博弈树。称为博弈树。博弈树的启发式搜索策略博弈树的启发式搜索策略 博弈树的特点如下：博弈树的特点如下： （1 1）博弈的初始格局是初始结点。）博弈的初始格局是初始结点。 （2 2）在博弈树中）在博弈树中“或或”结点和结点和“与与”结点是逐层交替结点是逐层交替出现的。自己一方扩展的结点之间是或关系，对方扩展出现的。自己一方扩展的结点之间是或关系，对方扩展结点之间是与关系。双方轮流扩展结点。结点之间是与关系。双方轮流扩展结点。 （3 3）所有使自己获胜的终局都是本原问题，相应的结）所有使自己获胜的终局都是本原问题，相应的结点是可解结点；所有使对方获胜的终局都是不

41、可解结点。点是可解结点；所有使对方获胜的终局都是不可解结点。博弈树的启发式搜索策略博弈树的启发式搜索策略 极大极小分析法：极大极小分析法： 在二人博弈问题中，为了从众多可供选择的方案中选在二人博弈问题中，为了从众多可供选择的方案中选出一个对自己有利的行动方案就需要对当前情况及将出一个对自己有利的行动方案就需要对当前情况及将要发生的情况进行分析，从中选出最优者。最常用的要发生的情况进行分析，从中选出最优者。最常用的方法是极大极小分析法。其基本思想是：方法是极大极小分析法。其基本思想是： （1）设博弈的一方是）设博弈的一方是A，另一方是另一方是B。极大极小分析极大极小分析就是为其中的一方（例如就是

42、为其中的一方（例如A方）寻找最优行动方案的方）寻找最优行动方案的方法。方法。 （2）为了找到当前的最优行动方案，需要对各个方案）为了找到当前的最优行动方案，需要对各个方案可能产生的后果进行比较。具体地说就是，就是要考可能产生的后果进行比较。具体地说就是，就是要考虑每一方案实施后对方可能采取的所有行动，并计算虑每一方案实施后对方可能采取的所有行动，并计算可能的得分。可能的得分。博弈树的启发式搜索策略博弈树的启发式搜索策略 （3）计算得分，需要根据问题的特性信息定义一个估）计算得分，需要根据问题的特性信息定义一个估计函数，用来估算当前博弈树端结点的得分。此时估算计函数，用来估算当前博弈树端结点的得

43、分。此时估算出来的得分称为静态估值。出来的得分称为静态估值。 （4）当端结点的估值计算出来后，再推算父结点的得）当端结点的估值计算出来后，再推算父结点的得分。推算的方法是对分。推算的方法是对“或或”结点，选其子结点中最大的结点，选其子结点中最大的得分作为父结点的得分，这是为了使自己在可供选择的得分作为父结点的得分，这是为了使自己在可供选择的方案中选一个对自己最有利的方案；对方案中选一个对自己最有利的方案；对“与与”结点，选结点，选其子结点中一个最小的得分作为父结点的得分，这是立其子结点中一个最小的得分作为父结点的得分，这是立足于最坏的情况。这样计算出来的父结点的得分称为倒足于最坏的情况。这样计

44、算出来的父结点的得分称为倒退估值。退估值。 （5）如果一个行动方案能获得较大的倒退估值，则它）如果一个行动方案能获得较大的倒退估值，则它是当前最好的方案。是当前最好的方案。博弈树的启发式搜索策略博弈树的启发式搜索策略 在博弈问题中，每一个格局可供选择的行动方案都有很在博弈问题中，每一个格局可供选择的行动方案都有很多，因此会产生十分庞大的博弈树，例如，西洋跳棋完多，因此会产生十分庞大的博弈树，例如，西洋跳棋完整的博弈树约有整的博弈树约有1040 个结点。试图用完整的博弈树来进个结点。试图用完整的博弈树来进行极大极小分析是很困难的。可行的办法是生成一定深行极大极小分析是很困难的。可行的办法是生成一

45、定深度的博弈树，然后进行极大极小化分析找出当前最好的度的博弈树，然后进行极大极小化分析找出当前最好的行动方案。如此进行下去，直到找到胜败的结果为止。行动方案。如此进行下去，直到找到胜败的结果为止。每次生成博弈树的深度，根据实际情况而定。每次生成博弈树的深度，根据实际情况而定。 下面是一个比较简单的二人零和全信息非偶然性博弈的下面是一个比较简单的二人零和全信息非偶然性博弈的例子。例子。 博弈树的启发式搜索策略博弈树的启发式搜索策略 例：一字棋游戏，在一个例：一字棋游戏，在一个3*3的方格棋盘中，由的方格棋盘中，由A、B两两人对弈，轮到谁走棋谁就往空格上放上自己的一只棋子，人对弈，轮到谁走棋谁就往

46、空格上放上自己的一只棋子，谁先使自己的棋子构成三子一线，谁就取得了胜利。设谁先使自己的棋子构成三子一线，谁就取得了胜利。设A的棋子用的棋子用a表示，表示，B的棋子用的棋子用b表示，假设每次仅扩展表示，假设每次仅扩展两层。估计函数定义如下：两层。估计函数定义如下： 设棋局为设棋局为P，估计函数为估计函数为e(P) (1)若若P是是A必胜的棋局，则必胜的棋局，则e(P)=+ （2）若若P是是B必胜的棋局，则必胜的棋局，则e(P)= - （3）若若P是胜负未定的棋局，是胜负未定的棋局， 则则e(P)=e(+P) - e(-P) 其中，其中， e(+P)表示棋局表示棋局P上有可能使上有可能使a成为三子

47、一线的数成为三子一线的数目。目。 e(-P)表示棋局表示棋局P上有可能使上有可能使b成为三子一线的数目。成为三子一线的数目。 博弈树的启发式搜索策略博弈树的启发式搜索策略 例如对于右面的棋局例如对于右面的棋局 ： b e(P) = 6-4 =2 a 假定具有对称性的两个棋局假定具有对称性的两个棋局 算作一个棋局，还假定算作一个棋局，还假定A先走棋先走棋 我们站在我们站在A的立场上。下图给出了的立场上。下图给出了A的第一招走棋生成的第一招走棋生成的博弈树。图中结点旁的数字分别表示相应结点的静的博弈树。图中结点旁的数字分别表示相应结点的静态估值或倒推值。从图中可以看出对于态估值或倒推值。从图中可以

48、看出对于A来说最好的来说最好的一着棋是一着棋是S3，因为因为S3比比S2和和S1有较大的倒推值。有较大的倒推值。 在在A走走S3这一着棋后，这一着棋后，B的最优选择是的最优选择是S4，因为这一着因为这一着棋的静态估值较小，对棋的静态估值较小，对A不利。不管不利。不管B选择选择S4或或S5，A都要运用极大极小化分析法产生深度为都要运用极大极小化分析法产生深度为2的博弈树，的博弈树，以决定下一步应该如何走棋，其过程与上面类似。以决定下一步应该如何走棋，其过程与上面类似。一字棋博弈树的启发式搜索博弈树的启发式搜索aS0S1S2S3aaababababab1010-1-1-21ba-1ba0abab-

49、10ab-2ba1S4b a2S5最佳走步一字棋的极大极小搜索博弈树的启发式搜索博弈树的启发式搜索 从上面的讨论当中可以看出上面例子中定义的启发式函从上面的讨论当中可以看出上面例子中定义的启发式函数考虑的因素太少了，实际上只给出了路的概念（即整数考虑的因素太少了，实际上只给出了路的概念（即整行、整列、整对角线），并且没有对一条路上已有几个行、整列、整对角线），并且没有对一条路上已有几个棋子站位的情况加以区分，仅仅考虑自己站位的情况。棋子站位的情况加以区分，仅仅考虑自己站位的情况。下面定义的一个启发式函数就比较精确。为此，引入以下面定义的一个启发式函数就比较精确。为此，引入以下概念：下概念： 0

50、阶路：一条路上没有任何棋子站位。阶路：一条路上没有任何棋子站位。0阶路即可属于阶路即可属于A方也可属于方也可属于B方，对得分没有影响，在估值时不予考虑。方，对得分没有影响，在估值时不予考虑。 1阶路：如果一条路上仅有阶路：如果一条路上仅有A方（或方（或B方）的一个棋子站方）的一个棋子站位，则称是留给位，则称是留给A方（或方（或B方）的一阶路。方）的一阶路。 2阶路：如果一条路上仅有阶路：如果一条路上仅有A方（或方（或B方）的两个棋子站方）的两个棋子站位，则称是留给位，则称是留给A方（或方（或B方）的二阶路。方）的二阶路。博弈树的启发式搜索博弈树的启发式搜索 一个比较好的启发函数一个比较好的启发