1、搜索策略与归结原理 第三讲13.1 图搜索策略1、基本概念搜索 是人工智能研究领域中基本问题之一，在过去几十年，人们已对搜索技术进行了大量研究，取得了一定的成果。搜索 ：根据问题的实际情况 不断寻找可用的知识， 从而构造一条 代价较少的推理方法，使问题得到 圆满解决 的过程称为搜索。搜索技术分为 盲目搜索 和 启发式搜索 。22、图搜索策略(1) 定义 ：图搜索策略可以看作一种在图中 寻找路径 的方法。初始节点和目标节点分别代表初始数据库和满足条件的终止数据库。求将一个数据库变换成另一个数据库的规则序列问题就等价于求得图中的一条路径问题。(2) 图搜索 (Graph Search)的一般过程
2、建立一个只含有起始节点 S的搜索图 G，把 S放到一个叫做 OPEN的 未扩展节点表中 。 建立一个叫做 CLOSED的 已扩展节点表，其初始为空表。3 LOOP：若 OPEN表是空表，则失败退出。 选择 OPEN表上的第一个节点，把它从 OPEN表移出并放进 CLOSED表中。称此节点为节点 n。 若 n为一目标节点，则有解并成功退出，此解是追踪图 G中沿着指针从 n到 S这条路径而得到的 (指针第 7步设置 )。 扩展节点 n，同时生成不是 n的祖先的那些后继节点的集合 M。把 M的这些成员作为 n的后继节点添入图 G中。 对那些未曾在 G中出现过的 (既未曾在 OPEN表上或CLOSED
3、表上出现过的 )M成员设置一个通向 n的指针。把 M的这些成员加进 OPEN表。对已经在 OPEN或CLOSED表上的每一个 M成员，确定是否需要更改通到 n的指针方向。对已在 CLOSED表上的每个 M成员，确定是否需要更改图 G中通向它的每个后裔节点的指针方向。 按某一任意方式或按某个探试值，重排 OPEN表。 GO LOOP。 4开始把 S放入 Open表 Open为空表？ 失败把第一个节点 (n)从 Open表移到 Closed表n为目标节点？ 成功把 n的后继节点 n放入 Open表的末端 ,提供返回节点 n的指针修改指针方向重排 Open表是是否否5(3)图搜索方法的分析图搜索过程
4、的第 8步对 OPEN表上的节点进行排序，以便能够从中选出一个 “最好 ”的节点作为第 4步扩展用。这种排序可以是任意的即 盲目的 (属于 盲目搜索 )，也可以用以后要讨论的各种 启发 思想或其它准则为依据 (属于 启发式搜索 )。每当被选作扩展的节点为目标节点时，这一过程就宣告成功结束。这时，能够重现从起始节点到目标节点的这条成功路径，其办法是从目标节点按指针向 S返回追溯。当搜索树不再剩有未被扩展的端结点时，过程就以失败告终 (某些节点最终可能没有后继节点，所以 OPEN表可能最后变成空表 )。在失败终止的情况下，从起始节点出发，一定达不到目标结点。 63.2 盲目搜索策略主要介绍两种典型
5、的盲目搜索技术，即广度优先搜索 技术和 深度优先搜索 技术。一、基于状态空间知识描述的一般搜索过程1、问题 一个复杂问题的状态空间一般都是十分庞大的。例如 64阶樊塔问题 （园片的数目称为梵塔问题的阶），共有364=0.941030个不同的状态，若把它们都存到计算机中去，需占据 大量的存储空间 ，并且 很难实现 。另外把所有的状态都存到计算机中也是 不必要 的，因为与问题的解相关的状态可能只是其中的一部分。但是，对于一个问题，如何生成它所需的那部分状态从而实现对问7题进行求解呢？通过 搜索技术可解决 这一问题。2、对 Open表和 Closed表数据结构进行说明Open表 用来存放刚刚生成的节
6、点。对不同的搜索策略，节点在 Open表中的排列顺序是不同的。 Closed表 用来存放将要扩展和已经扩展的节点。 所谓对一个节点的扩展 是指：用合适的算符对该节点进行操作，生称一组子节点。状 态节 点 父 节 点Open表 Closed表编 号 状 态节 点 父 节 点83、搜索的一般过程(1)把初始节点 S0放入 Open表中，并建立目前只包含 S0的图，记为 G。(2)检查 Open表是否为空，若为空则问题无解，退出。(3)把 Open表的 第一个节点 取出放入Closed表，并记该节点为节点 n(4)考察节点 n是否为目标节点。若是，则求得了问题的解，退出。(5)扩展节点 n，生成一组子节点。把其中不是节点 n先辈的那些子 节点记作集合 M，并把这些子节点作为 n的子节点加入 G中9(6)针对 M中子节点的不同情况 ，分别进行如下处理： 对于那些未曾在 G中出现过的 M成员，设置一个指向父节点 (即节点 n)的指针，并把它们放入 Open 对于那些先前已在 G中出现过的 M成员，确定是否需要修改其后继节点指向父亲节点的指针。 对于那些先前已在 G中出现并且已经扩展了的 M成员，确定是否需要修改其后继节点指向父节点的指针。(7)按某种搜索策略对 Open表中的节点进行排序。(8)转到第 (2)步。10
