第三章 通过搜索进行问题求解

树搜索和图搜索的区别：

树搜索和图搜索均可以对有向图进行搜索。树搜索允许遍历重复状态，无记忆性；图搜索不允许遍历重复状态，通常会维护一个队列来记录已探索过的状态以防止重复。

无信息搜索

  • 宽度优先搜索
    当每一步的行动代价都相等时宽度优先搜索是最优的。
  • 一致代价搜索
    与宽度优先搜索类似，能保证对任何单步代价函数都是最优的。
  • 深度优先搜索
  • 深度受限搜索
    限制深度界限的深度优先搜索，可以解决无穷路径问题。
  • 迭代加深的深度优先搜索
    不断增加深度限制的深度受限搜索。
  • 双向搜索

启发式搜索

  • 贪婪最佳优先搜索
  • A*搜索

保证A*算法最优性的条件

可采纳性和一致性（单调性）：

可采纳性指的是A*算法中的启发式函数h(n)h(n)不会过高估计到达目标的代价；

一致性是指从节点nn到目标的估计代价不大于从nn到n′n'的单步代价与n′n'到达目标的估计代价之和。即：

h(n)≤c(n,a,n′)+h(n′)h(n)\leq c(n,a,n')+h(n')

证明一致性可推出可采纳性：

使用数学归纳法证明。设h∗h^*为实际代价。对任意的节点nn，设ll为从nn到目标节点n′n'的最短路径，假如ll上nn与n′n'的距离为1则有：

h(n)≤c(n,a,n′)+h(n′)=c(n,a,n′)+0=h∗(n)\begin{aligned} h(n) & \leq c(n,a,n')+h(n')\\ &= c(n,a,n')+0\\ &= h^*(n) \end{aligned}

假设与目标节点n′n'在最短路径上距离kk的所有节点nn均满足h(n)≤h∗(n)h(n)\leq h^*(n)，则对于距离为k+1k+1的节点：

h(n)≤c(n,a,n′)+h(n′)=c(n,a,n′)+h∗(n′)=h∗(n)\begin{aligned} h(n) &\leq c(n,a,n')+h(n') \\ &=c(n,a,n')+h^*(n')\\ &=h^{*}(n) \end{aligned}

根据数学归纳法，原命题成立。

证明A*算法的最优性

首先证明如果h(n)h(n)是一致的，那么沿着任何路径的f(n)f(n)值就是非递减的：

f(n′)=g(n′)+h(n′)=g(n)+c(n,a,n′)+h(n′)≥g(n)+h(n)=f(n)f(n')=g(n')+h(n')=g(n)+c(n,a,n')+h(n')\geq g(n)+h(n)=f(n)

然后证明当A*算法选择扩展节点nn时就已经找到了到达nn的最佳路径。

否则，在到达节点nn的最优路径上一定会存在另一个节点n′n'。由于任何路径上ff都是非递减的，因此n′n'的ff代价会比nn小，因此n′n'会被优先选择。

由于每一步都会扩展最优节点，因此A*算法一定会找到最优解。

第四章 超越经典搜索

局部搜索算法

局部搜索算法不关心解的路径，旨在根据目标函数找到最佳状态。

对于离散状态空间：

  • 爬山法搜索
    每次选择相邻的最优状态。
  • 模拟退火搜索
    与爬山法类似，但是不选择最佳移动，选择的是随机移动，根据状态的“好坏”动态调整接受该移动的概率。
  • 局部束搜索
    记录kk个最优状态而不是11个。遗传算法是局部束搜索的变形。

对于连续空间，可以离散化，也可以使用梯度下降法求解。

不确定动作的搜索

即某个动作可能导致多个状态的产生。该类问题的解为一颗树（可以理解为if else语句或者决策树）。使用与或搜索树进行搜索可以得到解。

使用部分可观察信息的搜索

无观察信息的搜索

如果Agent感知不到任何信息，称之为无传感问题。（感知不到状态，但是可以明确做出动作产生的结果）求解无传感问题需要在信念状态空间搜索而不是在实际状态空间搜索。信念状态是指整个信念状态空间包含物理状态的每个可能集合。信念状态满足目标当且仅当其中所有物理状态满足目标。用无观察信息的搜索可以解决无感知的吸尘器问题，但是不能解决无感知的八数码问题。

有观察信息的搜索

  • 预测阶段与无感知信息问题相同。给定状态bb的活动aa，预测的信念状态为b^=PREDICT(b,a)\hat{b}=\text{PREDICT}(b,a);
  • 观测阶段确定预测信念状态里可观察到的感知oo的集合：

POSSIBLE-PERCEPTS(b^)={o:o=PERCEPT(s)且s∈b^}\text{POSSIBLE-PERCEPTS}(\hat{b})=\{o:o=\text{PERCEPT}(s)\text{且}s\in\hat{b}\}

  • 更新阶段对于每个可能的感知信息确定可能得到的信念状态。新的信念状态b0b_0是b^\hat{b}中可能产生该感知状态的集合：

bo=UPDATE(b^,o)={s:o=PERCEPT(s)且s∈b^}b_o=\text{UPDATE}(\hat{b},o)=\{s:o=\text{PERCEPT(s)}\text{且}s\in\hat{b}\}

联机搜索

联机搜索Agent通过交替地计算和行动来完成任务。它先采取某种行动然后观察环境变化，再通过计算采取下一行动。这对于未知环境很有必要。
竞争比是指联机搜索中Agent实际旅行经过的路径开销实际的最短路径的比值。在很多情况下竞争比可能无穷大（比如陷入死路）。可以通过联机深度优先搜索来进行探索和搜索。与一般的DFS不同的是，OnlineDFS需要Agent实际回溯到状态，因此需要构建一个回溯节点列表。

联机局部搜索

爬山法本质上是一种联机搜索算法。但是这种形式的联机搜索用处不大，因为当陷入局部极大值时，Agent无法重启搜索。因此考虑用随机行走取代随机重启。但是这种方式时间复杂度较高。考虑增加爬山法的内存解决该问题。

第五章 对抗搜索

初始状态、ACTION函数和RESULT函数定义了游戏的博弈树，其中节点是状态，边是移动。

MINIMAX算法

给定一颗博弈树，最优策略可以通过检查每个结点的极小极大值来决定。记为MINMAX(n)\text{MINMAX}(n)。假设两个游戏者始终按照最优策略行棋，那么对于最大化效用值的玩家来说，结点的极小极大值就是对应状态的效用值。

MINIMAX算法思想：对于MAX玩家，总是在后续节点中选择收益最大的节点，MIN玩家则正好相反。通过找出极小极大值或极大极小值来递归得到当前状态的最优选择。MINMAX算法在搜索树有限的情况下是完备的，当对手是理性的时，得到的结果是最优的。

Alpha-Beta剪枝搜索

在MINIMAX\text{MINIMAX}算法中减少所搜索的搜索树节点数。

Alpha-Beta剪枝搜索中的α\alpha值表示MAX节点目前得到的最高收益。β\beta值表示MIN节点目前可给对手的最小收益。假设nn是MIN节点，如果nn的一个后续节点可提供的收益小于α\alpha，则nn及其后续节点可以被剪枝。假设nn是MAX节点，如果nn的一个后续节点可提供的收益大于β\beta，则nn及其后续节点可以被剪枝。

IBM推出的深蓝就是用的此策略来提高效率。

引入评估函数

即使引入了Alpha-Beta剪枝，在很多情况下待搜索的状态数目仍然很大。因此，可以设置搜索截断，引入启发式评估函数对搜索中的状态进行效用值估计。而评估函数的设计是需要相关领域知识的，当然也可以使用机器学习相关技术来学习得到。

截断搜索

评估函数只适用于静态棋局，即，评估值不会很快出现大的摇摆变化的棋局。非静态棋局可以扩展直到变成静态棋局，这种额外的搜索成为静态搜索。
单步延伸指的是在给定棋局中一种棋招要“明显好于”其他棋招。一旦在搜索某处发现单步延伸，牢记它。当搜索达到指定深度界限，算法会检验单步延伸是否合法；如果是，算法会考虑此棋招。这样做可能会超过深度限制，但是由于单步延伸很少，不会增加太多开销。

第7章 逻辑Agent

基于知识的Agent的核心部件是知识库（KB），知识库是一个语句的集合。必须有将新语句添加到知识库以及查询目前所知内容的方法。完成这些任务的分别是TELL（告诉）和ASK（询问）。这两个任务可能涉及到推理，即从原有语句推导出新语句。
每次调用Agent程序，它会做三件事：

  • Agent告诉知识库它感知到的内容；
  • Agent询问知识库应该执行什么行动；
  • Agent告诉知识库它所选择的行动并执行该行动。

命题逻辑

命题逻辑是应用一套形式化规则对以符号表示的描述性陈述进行推理的系统。在命题逻辑中，一个或真或假的描述性陈述称为原子命题，在对原子命题的内部结构不做任何解析。若干原子命题可通过逻辑运算符来构成复合命题。

逻辑等价：给定命题pp和qq，如果pp和qq在所有情况下都具有相同的真假结果，那么pp和qq在逻辑上等价。
模型：如果语句α\alpha在模型mm中为真，称mm满足α\alpha，也称mm是α\alpha的一个模型。
有效性：一个模型是有效的，如果在所有模型中它都为真。如p∧¬pp\land\neg p是有效的。有效语句也被称为重言式
可满足性：如果一个语句在某些模型中为真，那么这个语句是可满足的。

Horn子句和限定子句

限定子句是指恰好只含一个正文字的析取式。如¬L∨¬breeze∨B\neg L \lor \neg breeze \lor B就是限定子句。而¬L∨breeze∨B\neg L \lor breeze \lor B则不是。

Horn子句是指至多只有一个正文字的析取式；如果对两个Horn子句进行归结，结果依然是Horn子句。

只包含限定子句的知识库的好处：

  1. 每个限定子句都可以写成蕴含式，蕴含式更容易理解；
  2. 使用Horn子句的推理可以使用前向链接和反向链接算法；
  3. 使用Horn子句判定蕴含需要的时间与知识库大小呈线性关系。

推理是从旧语句生成新语句的过程，可靠的推理算法只生成被蕴涵的语句；完备的推理算法生成所含有被蕴涵的语句。

第八章 一阶逻辑

命题逻辑，连接的是命题符号和预定义的相应真值，而一阶逻辑包含对象及其解释。关系是相互关联的对象的元组集合。

一阶逻辑的基本句法元素是表示对象、关系和函数的符号。这些符号分为三类：表示对象的常量符号，表示关系的谓词符号，表示函数的函词。其中，谓词返回的是真或假，而函词返回的是一个对象。

一阶逻辑的模型包括对象集和解释，解释把常量符号映射到对象，谓词符号映射成对象之间的关系，函词映射成对象上的函数。

含糖语法是标准语法的扩展或缩写，它不改变语句的语义。任何使用含糖语法的语句可以“脱糖”，生成一个普通一阶逻辑的等价语句。

第九章 一阶逻辑的推理

一阶逻辑可以退化到命题逻辑进行推理，对于一阶逻辑的推理是完备的，但是是半可判定的，即对于知识库蕴含的语句，推理算法一定可以证明出来，但是对于知识库不蕴涵的语句，通过推理并不能判断其是否为知识库蕴含的语句。这是因为程序可以一直执行下去，但是程序并不知道证明是否陷入循环当中还是快要证明出结果了。