问题求解智能体的含义

当要采取的正确动作不是很明显时，智能体可能需要提前规划：考虑一个形成通往目标状态路径的动作序列。这样的智能体被称为问题求解智能体。

问题求解智能体使用原子化表示世界状态。因子化和结构化表示世界状态是规划智能体。

智能体求解问题的过程

1. 目标形式化：智能体要做的正确的事情，书中的例子是到达 Bucharest
2. 问题形式化：对问题的抽象化，实现目标所需的状态和动作
3. 搜索：智能体在其模型中模拟一系列动作，并进行搜索，直到找到一个能达到目标的动作序列。可能有解也可能无解。
4. 执行：执行解中的动作，一次执行一个动作

搜索问题的形式化定义

1. 状态空间：可能的环境状态的集合
2. 初始状态：智能体启动时的状态
3. 目标状态：可能是一个或多个
4. 行动：智能体可以采取的行动
5. 转移模型：描述每个动作所起到的作用
6. 动作代价函数：表示从状态 s 经过 a 动作到达 s' 状态的数值代价

如何评价问题形式化时抽象层级是否合适？

抽象能细化为更详细的世界中的解，那么就认为是合理的抽象。好的抽象需要删除尽可能多的细节，同时保留合理性，并确保抽象动作易于执行。

搜索算法

1. 广度优先搜索，内存使用率高。它可采用FIFO（先进先出）队列。
2. 深度优先搜索，内存使用率低。它可采用LIFO（后进先出）队列。
3. 最佳优先搜索：选择让某个评价函数的值最小的节点。评价函数的具体算法不同。它可采用优先队列（priority queue），首先弹出根据评价函数 f 计算得到的代价最小的节点。

在搜索算法中，冗余消除是一个很重要的话题，冗余会导致搜索不能停止。

消除冗余的办法：

1. 记录已经迭代的状态
2. 跟踪父指针链查看路径末端的状态之前是否在存在的路径中出现过。
3. 有些问题可能不会出现冗余情况

图搜索和树搜索的差异

带有检查冗余的算法称为图搜索，否则称为树搜索。

如何评价搜索的性能

1. 完备性：存在解时，算法是否能保证找到解。不存在解时，是否能保证报告失败
2. 代价最优性：它是否找到了所有解中路径代价最小的解
3. 时间复杂性：耗费的时间
4. 空间复杂性：耗费的内存

显式的状态空间：具有确定的顶点，边

隐式的状态空间：状态空间图由初始状态、动作和转移模型隐式地表示

复杂性衡量指标：d（depth）最优解的深度或动作；m，任意路径的最大动作数；b(branching factor)分支因子或后续节点数

无信息搜索策略

广度优先搜索

当所有动作的代价相同（使用广度优先搜索的先决条件），正确的策略是采用广度优先搜索。评价函数是节点的深度，这是获取最优解的关键。

function BreadthFirstSearch(problem) returns 一个解节点或 failure
    node = Node(problem.Inital)
    if(problem.isGlobal(node.State)) then return node
    frontier = FIFO 队列，其中一个元素为 node
    reached = {problem.Inital}
    while not isEmpty(frontier) do
        node = Pop(froniter)
        for each child in Expand(problem, node) do
            s = child.State
            if(problem.isGloabl(s)) then return child
            if s不在reached中 then
            将 s 添加到 reached
            将 child 天假到 frontier
        return failure

Dijkstra 算法或一致代价搜索

Dijkstra（戴可思彻）最佳优先搜索算法，在人工智能界称为一致代价搜索（uniform-cost search）。

深度优先搜索与内存问题

深度优先搜索占用内存比广度优先要少。在此基础上还可以采用回溯搜索算法，一次只生成一个后继，而不是所有后继节点；每个部分扩展的节点会记住下一个要生成的后继节点。回溯通过直接修改当前状态描述而不是为一个全新的状态分配内存来生成后继节点。

深度优先树状搜索已经称为许多人工智能领域的基本工具，其原因是：内存的节约使用。

深度受限和迭代加深搜索

深度首先搜索是设置深度界限，超过界限上的所有节点视为其不存在的后继节点。因为人为设置了深度界限。那么可能导致无法获取解。

迭代加深搜索与深度受限的差异是，在深度界限的基础上，迭代加深搜索会不断的增加界限深度。

双向搜索

其形式很像有一个数组，需要查找到一个内容，这时候就可以同数组的两端向中间查找。双向搜索是从初始状态正向搜索和从目标状态反向搜索，直到这两个搜索相遇。

当只存在唯一的解，很容易处理相遇。这里另外一个问题是从目标状态反向搜索，它使用的评价函数和正向搜索使用的是不一样的。

有信息（启发式）搜索策略

信息以启发式函数的形式出现记为 h(n)，h(n) = 从节点 n 的状态到目标状态的最小代价路径的代价估计值

贪心最佳优先搜索

贪心最佳优先搜索是最佳优先搜索的一种形式，它首先扩展 h(n)值最小的节点（看起来和目标最接近的节点）。这时候评价函数f(n) = h(n)。

贪心最佳优先搜索在有限状态空间中是完备的，但是在无限状态空间中时不完备的。所有要介绍 A* 搜索。

A* 搜索

A* 搜索是一种最佳优先搜索，它的评价函数 f(n) = g(n) + h(n)

h(n): 从节点 n 到目标状态的最短路径代价

g(n): 从节点 n 到后继节点的路径代价

A* 搜索是完备的，它是否是代价最优，取决于启发函数的某些性质。关键性质是可容许性。

• 可容许性：可容许的启发式永远不会高估到达目标的代价。它给出的估计是“乐观的”——实际代价要么等于估计，要么比估计更大。
• 一致性：如果对于每个节点n以及由动作 a 生成的 n 的每个后继节点 n' 有以下条件，则启发式函数 h(n) 是一致的： h(n) <= c(n, a, n') + h(n')。三角不等式（两边之和大于第三边）。一致的启发式函数都是可容许的，反过来不一定成立。

启发函数和评价函数的关系

评价函数 = 启发函数（在贪心最佳优先搜索中）

评价函数 = 代价函数 + 启发函数（在 A* 中）

启发函数是一个领域相关的知识，需要设计者根据问题提供（例如曼哈顿距离、错位数等）。

评价函数是算法内部的排序准则，它可能包含启发函数，也可能包含其他项（如已付出代价、随机扰动等，例如模拟退火的能量函数）。

搜索等值线

等值线：

一种可视化的方法是在状态空间中绘制等值线。A* 搜索从初始节点扇形地向外扩展，以 g(n)+h(n) 值递增的同心带状方式添加节点。这说明 A* 搜索的重要特性：不会盲目的向所有方向扩展。

满意搜索

内存受限搜索

因为内存的占用主要在 reached 表和 frontier 状态表中，所以要想个办法可以删掉没有用的 reached 表中的节点，可以减少内存占用。

这里的实现更像垃圾回收机制中的 引用计数法。维护引用计数——到达某一状态的次数，并且在再也没有路径可以到达该状态时将其从 reached 表中删除。

束搜索，想象苕帚的形状，束搜索就是对边界进行限制。只保留具有最优评价函数值的 K 个节点，放弃扩展其他节点。

迭代加深A搜索（IDA） 每次迭代中，新的截断值为超过上一次迭代截断值的节点中最小的f代价。也就是说每次迭代都会彻底搜索一个 f 等值线。

启发式函数

启发式函数如何影响性能

有效分支因子（b*）是一种描述启发式函数质量的方法。书中通过 A* 搜索算法给出了 b* 的说明：A* 搜索生成的总结点数是 n，解的深度是 d，b* 就是深度为 d 的均衡树要包含 n+1 个节点所必需的分支因子

有效深度也是一种影响性能的评价指标

启发式函数如何构建

从松弛问题出发生成启发式函数，松弛问题是指减少了对动作的限制条件的问题。

从子问题出发生成启发式函数，可容许的启发式函数可以由给定问题的子问题的解代价推导得到。

从经验中学习生成启发式函数。