人工智能 第三版 第二章笔记

空间状态图

状态空间图（state-space graph）是对问题的一种表示方法。

其中有两种特殊类型的节点。其中一种是表示问题起始状态（start state）的起始节点（start node）。另一种特殊类型的节点对应于问题的终点或终止状态。

问题的状态空间树包含了问题可能出现的所有状态以及这些状态之间所有可能的转换。事实上，由于回路或者说环经常出现，因此这样的结构通常被称为状态空间图。问题的解通常需要在这个结构中进行搜索（无论它是树还是图），搜索始于起始节点，止于终点或目标状态（goal state）。

微型假币问题

有6枚硬币，已知其中一枚是假的或伪造的，但是不知道这枚假币比真币轻还是重。普通的天平可以用于确定任何两组硬币的质量是否相等，或者一组硬币比另一组硬币轻还是重。

生成-测试范式

先给出可能的解，再检查每个可能的解，看是否有候选解能够构成问题的解。

如果这个生成器给出了每个可能的解，那么该生成器就是完备的（complete）。

如果某个给出的解被拒绝，那么这个解就不会再次被给出（事实上，即使是成功的解也只能给出一次）。换句话说，一个好的生成器应该是非冗余（noredundant）的。

如果生成器有一些信息，允许其对给出的解做出一些限制，那么这个生成器就是知情的（informed）。

过程如下：
{While没有找到解，但仍有候选方案

`[生成可能的解`

​ 测试其是否满足所有的问题约束条件]

End While}

IF找到某个解，则宣布成功，并输出此解

Else宣布没有找到解

n皇后问题

将n个皇后放置在一个n×n的棋盘上，使得任何两个皇后都不互相攻击。也就是说，任何两个皇后都不占据相同的行、列或对角线。

回溯法

完全枚举法（exhaustive enumeration）解的情况下，还可能从部分解开始进一步往后搜索。

回溯法（backtracking）是对完全枚举法的一种改进。

如果问题的约束条件得到满足，那么搜索将进行到下一步。如果任何选择都得不到可行的部分解，那么搜索将回溯到前一步，撤销前一步的选择，继续下一个可能的选择结果。

贪心算法（greedy algorithm）

贪心算法总是包含一个必须优化（即最大化或最小化）的目标函数（objective function）。典型的目标函数可以是旅行距离、开销或持续时间。

在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解 。

使用贪心算法求解问题的效率很高，但遗憾的是，计算机科学中的一些问题并不能使用这种范式来求解。

盲目搜索算法

盲目搜索算法是不使用问题域知识的不知情搜索算法。它们不使用启发式估计（如果使用启发式估计，那么搜索将沿着最有希望得到解的路径前进。），目标是找出给定问题的某个解。

问题求解性能的衡量指标

• 完备性：当问题存在解时，如果搜索算法可以保证找到一个解，就说这个算法是完备的（complete）

• 最优性：如果搜索算法能提供所有解中那个开销最低的解，则认为这个算法是最优的（optimal）。

• 时间复杂度：搜索算法的时间复杂度（time complexity）关注的是找到解需要花费的时间。这里可以根据搜索期间生成（或扩展）的节点数量来衡量时间。

• 空间复杂度：搜索算法的空间复杂度（space complexity）关注的是内存开销。我们必须确定存储到内存中的最大节点数目。

  AI中的复杂度是用如下3个参数表示的。

  1. 节点的分支因子（branching factor，记为b），指的是从节点出发的分支数。
  2. 参数d给出的是最浅目标节点的深度。
  3. 参数m给出的是状态空间中所有路径的最大长度。

深度优先搜索（DFS）

试图尽可能快地深入树中进行搜索。每当搜索方法可以做出选择时，就选择最左（或最右）分支（通常选择最左分支）。

在下列情况下，优选深度优先搜索。

• 树很深。
• 分支因子不太大，并且
• 解出现在树中的位置相对较深。

广度优先搜索（BFS）

使用BFS，从树的顶部到树的底部，按照从左到右（或从右到左，不过从左到右更常见）的方式，可以逐层访问节点。必须首先访问第i层的所有节点，然后才能访问第i +1层的节点。

BFS的时间复杂度T(n) = b + b^2 + b^3 + ... +(b^(d−1)– b) = O(b^(d+1))

对BFS而言，最尖锐的批评来自其指数级的空间复杂度S(n) = T(n)+1.

即使问题的规模不太大，BFS也很快就变得不可行。

如果是以下情况，优选广度优先搜索。

• 搜索树的分支因子不太大（一个适度的b值）。当整棵树的分支因子实际上很大时，BFS会因为有过多的路径需要探索而不堪重负。
• 解出现在树中的位置在合理的深度（一个适度的d值），并且
• 所有路径都不是特别深。

迭代加深的深度优先搜索（DFS-ID）

结合DFS的中等存储空间需求，去除寻找长路径的倾向，可以得到迭代加深的DFS，即DFS-ID（DFS With Iterative Deepening）。

DFS-ID执行一个DFS算法，其状态空间的深度的界为0，如果没有找到目标，就执行另一个DFS算法，此时深度的界为1。继续以这种方式搜索，在每次迭代中，深度的界都会增加1。在每次迭代中，一个完备的DFS都要执行到当前深度。在每次迭代中，搜索都要重新开始。

DFS-ID的时间复杂度是O(b^d)。

空间复杂度为O(b*d)，这与DFS相同。

当分支因子有限时，与BFS一样，DFS-ID是完备的。当路径开销是节点深度的非递减函数时，DFS-ID是最优的。