人工智能及其应用

第三章 确定性推理

第2章研究的知识表示方法是问题求解所必需的。

从问题表示到问题的解决，有个求解的过程，也就是搜索过程。在这一过程中，采用适当的搜索技术，包括各种规则、过程和算法等推理技术，力求找到问题的解答

3.1 图搜索策略

可把图搜索控制策略看成一种在图中寻找路径的方法
初始节点和目标节点分别代表初始数据库和满足终止条件的目标数据库。求得把一个数据库变换为另一个数据库的规则序列问题就等价于求得图中的一条路径问题

在图搜索过程中涉及到的数据结构除了图本身以外，还需要两个辅助的数据结构，即存放已访问但未扩展结点的$OPEN$表，以及存放已扩展节点的$CLOSED$表
搜索的过程实际是从隐式的状体空间图中不断生成显示的搜索图和搜索树，最终找到路径的过程

为实现这一过程，图中每个节点除了自身的状态信息外，还需存储诸如父节点是谁，由其父节点是通过什么操作可到达该节点，以及节点位于搜索树的深度、从起始节点到该节点的路径代价等信息

图搜索的一般过程如下：

1. 建立一个只含有起始节点$S$的搜索图$G$，把$S$放到一个$OPEN$表中
2. 初始化$CLOSED$表为空表
3. $LOOP$：若$OPEN$表是空表，则失败退出
4. 选择$OPEN$表上的第一个节点，把它从$OPEN$表移出并放进$CLOSED$表中。称此节点为节点$n$
5. 若$n$为一目标节点，则有解并成功退出，此解是追踪图$G$中沿着指针从$n$到$S$这条路径而得到的
6. 扩展节点$n$，生成后继节点集合$M$
7. 对那些未曾在$G$中出现过的$M$成员设置其父节点指针指向$n$并加入$OPEN$表。对已经在$OPEN$或$CLOSED$表中出现过的每一个$M$成员，确定是否需要将其原来的父节点更改为$n$。对已在$CLOSED$表上的每个$M$成员，若修改了其父节点，则将该节点从$CLOSED$表中移出，重新加入$OPEN$表中
8. 按某一任意方式或按某个试探值，重排$OPEN$表
9. $GOLOOP$

此过程生成一个显示的图$G$（称为搜索图）和$G$的一个子集$T$（称为搜索树），树$T$上的每个节点也在图$G$中

搜索过程中使用的$OPEN$表存储的都是当前搜索树的叶子节点，因此也被称为$Fronge$表，即前沿表

在失败终止的情况下，从起始节点出发，一定达不到目标节点

$GRAPHSEARCH$算法同时生成一个节点的所有后继节点。为了说明图搜索过程的某些通用性质，将继续使用同时生成所有后继节点的算法，而不采用修正算法。在修正算法中，一次只生成一个后继节点
从图搜索过程可以看出，是否重新安排$OPEN$表，即是否按照某个试探值重新对未扩展节点进行排序，将决定该图搜索过程是无信息搜索或启发式搜索

3.2 盲目搜索

不需要重新安排$OPEN$表的搜索叫做无信息搜索或盲目搜索，它包括宽度优先搜索、深度优先搜索和等代价搜索等。
盲目搜索只适用于求解比较简单的问题

3.2.1 宽度优先搜索

如果搜索是以接近起始节点的程度依次扩展节点的，那么这种搜素就叫作宽度优先搜索
宽度优先搜索算法如下：

1. 把起始节点放到$OPEN$表中
2. 如果$OPEN$是个空表，则没有解，失败退出；否则继续
3. 把第一个节点从$OPEN$表移出，并把它放入$CLOSED$的扩展节点表中
4. 扩展节点$n$如果没有后继节点，则转向上述第（2）步
5. 把$n$的所有后继节点放到$OPEN$表的末端，并提供从这些后继节点回到$n$的指针
6. 如果$n$的任一个后继节点是个目标节点，则找到一个解答，成功退出；否则转向第（2）步

宽度优先搜索方法在假定每一次操作的代价都相等的情况下，能够保证在搜索树中找到一条通向目标节点的最短途径。在宽度优先搜索中，节点进出$OPEN$表的顺序是先进先出，因此其$OPEN$表是一个队列结构

3.2.2 深度优先搜索

在深度优先搜索中，首先扩展最新产生的（即最深的）节点
深度相等的节点可以任意排列。定义节点的深度如下：

1. 起始节点（即根节点）的深度为0
2. 任何其他节点的深度等于其父节点深度加1

首先，扩展最深的节点的结果使得搜索沿着状态空间某条单一的路径从起始节点向下进行；只有当搜索到达一个没有后裔的状态时，它蔡考虑另一条替代的路径。替代路径与前面已经试过的路径的不同之处仅仅在于改变最后$n$步，而且保持$n$尽可能小

在搜索过程中可能会出现深度无限深，为了避免考虑太长的路径，往往给出一个节点扩展的最大深度——深度界限，任何节点如果达到了深度界限，那么都将它们作为没有后继节点处理。
但即使使用了这样的方法，所求得的路径也不一定就是最短路径

含有深度界限的深度优先搜索算法如下：

1. 把起始节点$S$放到未扩展节点$OPEN$表中。如果此节点为一目标节点，则得到一个解
2. 如果$OPEN$为一空表，则失败退出
3. 把第一个节点从$OPEN$表移到$CLOSED$表
4. 如果节点$n$的深度等于最大深度，则转向（2）
5. 扩展节点$n$，产生其全部后裔，并把他们放入$OPEN$表的前头。如果没有后裔，则转向（2）
6. 如果后继节点中有任一个为目标节点，则求得一个解；否则转（2）

显然，深度优先算法中节点进入$OPEN$表的顺序是后进先出，$OPEN$表是一个栈

3.2.3 等代价搜索

宽度优先搜索可被推广用来解决这种寻找从起始状态至目标状态的具有最小代价的路径问题，这种推广了的宽度优先搜索算法叫做等代价搜索算法。
如果所有的连接弧线具有相等的代价，那么等代价算法就简化为宽度优先搜索算法。在等代价搜索算法中，不是描述沿着等长度路径断层进行的扩展，而是描述沿着等代价路径断层进行的扩展

在等代价搜索算法中，把从节点$i$到它的后继节点$j$的连接弧线代价记为$c(i,j)$，把从起始节点$S$到任一节点$i$的路径代价记为$g(i)$。
在搜索树上，假设$g(i)$也是从起始节点$S$到节点$i$的最少代价路径上的代价，因为它是唯一的路径。等代价搜索方法以$g(i)$的递增顺序扩展其节点，其算法如下：

1. 把起始节点$S$放到未扩展节点表$OPEN$中。如果此起始节点为一目标节点，则求得一个解，否则令$g(S)=0$
2. 如果$OPEN$是个空表，则没有解而失败退出
3. 从$OPEN$表中选择一个节点$i$，使其$g(i)$为最小。如果有几个节点都合格，那么就要选择一个目标节点作为节点$i$；否则，就从中选择一个作为节点$i$。把节点$i$从$OPEN$表移至扩展节点表$CLOSED$中
4. 如果节点$i$为目标节点，则求得一个解
5. 扩展节点$i$。如果没有后继节点，则转（2）
6. 对于节点$i$的每个后继节点$j$，计算$g(j)=g(i)+c(i,j)$，并把所有后继节点$j$放进$OPEN$表。提供回到节点$i$的指针
7. 转向第（2）步

3.3 启发式搜索

盲目搜索的效率低，耗费过多的计算空间与时间。如果能够找到一种方法用于排列待扩展节点的顺序，即选择最有希望的节点加以扩展，那么搜索效率将会大为提高

3.3.1 启发式搜索策略和估价函数

要在盲目搜索中找到一个解，所需要扩展的节点数目可能是极大的，因为这些节点的扩展次序完全是随意的，且没有利用已解决问题的任何特性。这种结果是组合爆炸的一种表现形式

把进行这种搜索的技术一般需要某些有关具体问题领域的特性的信息，称为启发信息
把利用启发信息的搜索方法叫做启发式搜索方法

利用启发信息来决定哪个是下一步要扩展的节点，总是选择“最有希望”的节点，这种搜索方法叫做有序搜索，也称为最佳优先搜索
用来估算节点“希望”的量度叫做估价函数，估价函数的值越小，意味着该节点位于最优解路径上的“希望”越大，最后找到的最优路径即平均综合指标为最小的路径

估价函数能够提供一个评定候选扩展节点的方法，以确定哪个节点最有可能在通向目标的最佳路径上

启发信息用来排列第8步$OPEN$表上的节点，使得搜索沿着那些被认为最有希望的区段扩展。

用函数$f$(估价函数)来排列第8步$OPEN$表上的节点。根据习惯，$OPEN$表上的节点按照它们$f$函数值的递增顺序排列。根据推测，某个具有低的估价值的节点较有可能处在最佳路径上

3.3.2 有序搜索

有序搜索又称为最佳优先搜索，它总是选择最有希望的节点作为下一个要扩展的节点
尼尔逊$(Nillson)$曾提出一个有序搜索的基本算法，该算法的估价函数$f$：一个节点的希望程度越大，其$f$值就越小。被选为扩展的节点，是估价函数最小的节点

有序状态空间搜索算法如下：

1. 把起始节点$S$放到$OPEN$表中，计算$f(S)$并把其值与节点$S$联系起来
2. 如果$OPEN$是个空表，则失败退出，无解
3. 从$OPEN$表中选择一个$f$值最小的节点$i$。如果有几个节点合格，当其中有一个为目标节点时，则选择此目标节点，否则就选择其中任一个节点作为节点$i$
4. 把节点$i$从$OPEN$表中移出，并把它放入$CLOSED$的扩展节点表中
5. 如果$i$是一个目标节点，则成功退出，求得一个解
6. 扩展节点$i$，生成其全部后继节点。对于$i$的每一个后继节点$j$：
   1. 计算$f(j)$
   2. 如果$j$既不在$OPEN$表中，又不在$CLOSED$表中，则用估价函数$f$把它添入$OPEN$表。从$j$加一指向其父节点$i$的指针，以便一旦找到目标节点时记住一个解答路径
   3. 如果$j$已在$OPEN$表或$CLOSED$表中，则比较刚刚对$j$计算过的$f$值和前面计算过的该节点在表中的$f$值。如果新的$f$值较小，则：
      1. 以此新值取代旧值
      2. 从$j$指向$i$，而不是指向它的父节点
      3. 如果节点$j$在$CLOSED$表中，则把它移回$OPEN$表
7. 转向（2）

宽度优先搜索、等代价搜索和深度优先搜索都是有序搜索技术的特例。
宽度优先搜索，选择$f(i)$作为节点$i$的深度。
对于等代价搜索，$f(i)$是从起始节点至节点$i$这段路径的代价

与盲目搜索方法比较，有序搜索的目的在于减少被扩展的节点数
有序搜索的有效性直接取决于$f$的选择，这将敏锐地辨别出有希望的节点和没有希望的节点，但是这种辨别不准确，可能会失去一个最好的解甚至全部的解

如果没有适用的、准确的希望量度，那么$f$的选择将涉及两方面的内容：一方面是一个时间和空间之间的折中方案；另一方面是保证有一个最优的解或任意解

节点希望量度以及某个具体估价函数的合适程度取决于手头的问题情况。根据所要求的解答类型，可以把问题分为3种情况：

1. 假设该状态空间含有几条不同代价的解答路径，其问题是要求得最优解答。这种情况的代表性的例子为算法$A^{\ast }$
2. 与上面的情况相似，但有一个附加条件：此类问题是比较难的，如果按第一种情况加以处理，则搜索过程很可能在找到解答之前就超过了时间和空间界限。在这种情况下，关键问题是：①如何通过适当的搜索试验找到好的解答；②如何夏至搜索试验的范围和所产生的解答与最优解答的差异程度
3. 不考虑解答的最优化；或者只存在一个解，或者任何一个解与其他的解一样好。这时，问题是如何使搜索试验的次数最少，而不像第二种情况那样试图使某些搜索试验和解答代价的综合指标最小

3.3.3 $A^{\ast }$算法

在讨论$A^{\ast }$算法前，先定义几个有用的记号：

• 令$k(n_i,n_j)$表示任意两个相通节点$n_i$和$n_j$之间最小代价路径的实际代价
• 令$h^{\ast }(n)$表示整个目标节点集合{ti}\left\{t_i \right\}{ti​}上所有$k(n,t_i)$中最小的一个，因此$h^{\ast }(n)$就是从$n$到目标节点最小代价路径的代价，而且从$n$到目标节点的代价为$h^{\ast }(n)$的任一路径就是一条从$n$到某个节点的最佳路径
• 引进函数$g^{\ast }$，对所有从$S$开始可达到$n$的路径来说，函数$g^{\ast }$定义为：
  • $g^{\ast }(n)=k(S,n)$
• 定义函数$f^{\ast }$，使得在任一节点$n$上其函数值$f^{\ast }(n)$就是从节点$S$到节点$n$的一条最佳路径的实际代价，加上从节点$n$到某目标节点的一条最佳路径的代价之和，即
  • $f^{\ast }(n)=g^{\ast }(n)+h^{\ast }(n)$
• 估价函数$f$是$f^{\ast }$的一个估计，此估计可由下式给出：
  • $f(n)=g(n)+h(n)$
    • 其中：$g$是$g^{\ast }$的估计；$h$是$h^{\ast }$的估计；
    • $h^{\ast }(n)$的估计$h(n)$依赖于有关问题的领域的启发信息，$h$叫做启发函数

$A^{\ast }$算法是一种有序搜索算法，其特点在于对估价函数的定义上
对于一般的有序搜索，总是选择$f$值最小的节点作为扩展节点。因此，$f$是根据需要找到一条最小代价路径的观点来估算节点的

可考虑每个节点$n$的估价函数值为两个分量：从起始节点到节点$n$的代价以及节点$n$到达目标节点的代价

先有以下定义：

1. 在$GRAPHSEARCH$过程中，如果第8步的重排$OPEN$表是依据$f(x)=g(x)+h(x)$进行的，则称该过程为$A$算法
2. 在$A$算法中，如果对所有的$x$存在$h(x)\le h^{\ast }(x)$，则称$h(x)$为$h^{\ast }(x)$的下界，它表示某种偏于保守的估计
3. 采用$h^{\ast }(x)$的下界$h(x)$为启发函数的$A$算法，称为$A^{\ast }$算法。当$h=0$时，$A^{\ast }$算法就变为等代价搜索算法

$A^{\ast }$算法：

1. 把$S$放入$OPEN$表，记$f=h$，令$CLOSED$为空表
2. 重复下列过程，直至找到目标节点为止。若$OPEN$表为空，则失败
3. 选取$OPEN$表中未设置过的具有最小$f$值的节点为最佳节点$(BESTNODE)$，并移入$CLOSED$表
4. 若最佳节点为一目标节点$(SUCCESSOR)$，则成功求得一解
5. 若最佳节点不是目标节点，则扩展结点，产生后继节点
6. 对每个后继节点，进行下列过程：
   1. 建立从后继节点返回最佳节点的指针
   2. 计算$g(SUC)=g(BES)+g(BES,SUC)$
   3. 如果$SUCCESSOR\in OPEN$，则称此节点为$OLD$，并添加至$BESTNODE$的后继节点表中
   4. 比较新旧路径代价。如果$g(SUC)<g(OLD)$，则重新确定$OLD$的父节点为$BESTNODE$，记下较小代价$g(OLD)$，并修正$f(OLD)$值
   5. 若至$OLD$节点的代价较低或一样，则停止扩展节点
   6. 若$SUCCESSOR$不在$OPEN$表中，则看其是否在$CLOSED$表中
   7. 若$SUCCESSOR$在$CLOSED$表中，则比较新旧路径代价。如果$g(SUC)<g(OLD)$，则重新确定$OLD$的父节点$BESTNODE$，记下较小代价$g(OLD)$，修正$f(OLD)$值，并将$OLD$从$CLOSED$表中移出，移入$OPEN$表
   8. 若$SUCCESSOR$既不在$OPEN$表中，又不在$CLOSED$表中，则把它放入$OPEN$表中，并添入$BESTNODE$后裔表，然后转第7步
7. 计算$f$值
8. $GOLOOP$

$A^{\ast }$算法中估价函数的定义是非常重要的，尤其是其中的启发函数$h(n)$，由于启发信息在算法中就是通过$h(n)$体现，如果在估价函数的定义中恰好令$h(n)=h^{\ast }(n)$，则可以看到搜索树将只扩展出最佳路径，也就是最理想的情况，但一般情况下必须满足$h(n)$不超过$h^{\ast }(n)$算法才能保证找到最优解，$h(n)$的这种特性称为可纳性，即$h(n)$的定义必须满足可纳性才能保证算法的最优性