Chapter 3 Uninformed Search¶
- 对应于 "Artificial Intelligence - A Modern Approach (3rd Edition)" 中的 Chapter 3
- SOLVING PROBLEMS BY UNINFORMED SEARCHING (3.1~3.4)
问题形式化¶
一个问题可以用5个组成部分形式化描述，以寻路问题为例:
-
Agent的初始状态: 𝐼𝑛(𝐴𝑟𝑎𝑑)
-
行动ACTION(𝑠): ACTION(𝐼𝑛(𝐴𝑟𝑎𝑑)) = {𝐺𝑜(𝑆𝑖𝑏𝑖𝑢), 𝐺𝑜(𝑇𝑖𝑚𝑖𝑠𝑜𝑎𝑟𝑎), 𝐺𝑜(𝑍𝑒𝑟𝑖𝑛𝑑)}
-
转移模型 RESULT(𝑠, 𝑎):
- RESULT(𝐼𝑛(𝐴𝑟𝑎𝑑), 𝐺𝑜(𝑍𝑒𝑟𝑖𝑛𝑑)) = 𝐼𝑛(𝑍𝑒𝑟𝑖𝑛𝑑)
- 后继状态 𝑆(𝑠): 从给定状态出发通过单步行动可到达的状态集合，𝑆(𝑠) = 𝑠’|∀𝑎 ∈ ACTION 𝑠 , 𝑠’ = RESULT(𝑠,𝑎)
-
目标测试: {𝐼𝑛(𝐵𝑢𝑐h𝑎𝑟𝑒𝑠𝑡)}
-
路径消耗(累加): 用公里数表示的路径长度。𝑐(𝑠, 𝑎, \(s^{,}\)) 是在状态 𝑠 执行动作 𝑎 到达状态 \(s^,\) 的单步消耗
-
问题的解就是从初始状态到目标状态的一组行动序列
- 解的质量由路径消耗函数度量，路径消耗值最小的解即为最优解
问题求解Agent¶
一个简单的问题求解Agent首先形式化目标和问题，然后搜索解决问题的行动序列，最后逐个执行这些行动
这是离线求解问题的方法(是无信息的或具有完全知识); 在 线问题求解涉及的是没有完全知识的行动
问题类型¶
- 确定的，完全可观察的 ⟹ 单状态问题
- Agent确切知道它将处于哪个状态; 问题的解是一个序列
- 不可观察的 ⟹ 一致性问题
- Agent可能不知道它在哪里;问题的解(如果有)是一个序列
- 不确定性的 and/or 部分可观察的 ⟹ 偶然性问题
- 感知提供有关当前状态的新信息
- 问题的解是一个偶然计划或策略
- 经常交错进行搜索和执行(试错)
- 未知状态空间 ⟹ 探索问题 (“在线”)
问题的形式化: 抽象¶
- (抽象)状态 = 真实状态的子集
- (抽象)行动 = 实际行动的复杂组合
每个抽象行动都应比原始问题 “更容易”
常规搜索策略¶
搜索策略
策略是通过选择扩展结点的顺序来定义的
根据以下维度评估策略:
- 完备性——当问题有解时，是否总能找到解?
- 最优性——是否总能找到最优解(消耗最少的解)? • 时间复杂度——生成/扩展的结点数(搜索代价)
- 空间复杂度——内存中的最大结点数
时间复杂度和空间复杂度由下面三个来度量:
- 𝑏：搜索树的最大分支因子 (任何结点的最多后继数)
- 𝑑：最优解 (消耗最少的解) 的深度，根结点到目标状态的步数
- 𝑚：状态空间中任何路径的最大长度 (可以为∞)
树搜索¶
基本思路: 离线，通过生成已经探索过的状态的继任者（不需要去重）模拟搜索状态空间，又称扩展状态
不能检测到重复状态会导致冗余路径问题
图搜索¶
使用探索集(也称closed表)记录已扩展过的结点，以实现去重功能
图搜索算法: 树搜索算法 + 探索集
图搜索算法构造的搜索树中 每个状态只出现一次 ，可以直接 在状态空间中生成一棵树
“边缘” 将状态空间分为已探索区域和未被探索区域，因此从初始状态出发至任意一个未被探索状态的路径都必须通过边缘中的结点
状态 vs. 结点¶
- 状态是一种物理配置(表示)，比如八皇后中“当前棋盘上的摆放方式”，属于物理意义层
- 结点是构成搜索树一部分的数据结构，包括父结点、子结点、深度或 路径消耗𝑔(𝑥)。(可记录达到目标状态的路径)
- 状态没有父结点、子结点、深度或路径消耗!
实际操作
EXPEND函数创建新结点: 填充各个区域，并使用SUCCESSOR函数创建相应的状态
无信息搜索策略¶
- 宽度优先搜索 Breadth-first search (BFS)
- 一致代价搜索 Uniform-cost search
- 深度优先搜索 Depth-first search (DFS)
- 深度受限搜索 Depth-limited search (DLS)
- 迭代加深的深度优先搜索 Iterative deepening search (IDS)
宽度优先搜索Breadth-first search (BFS)¶
思想：
扩展深度最浅的未扩展结点
实现方式:
将边缘组织成先进先出(FIFO)队列，即新结点加入到 队列尾，意味着浅层的老结点会在深层结点之前被扩展
性质：
- 完备性: 是 (如果最大深度𝑑和最大分支因子𝑏均是有限的)
- 最优性:否，仅当路径消耗是结点深度的非递减函数时才 是最优的; 通常不是最优的。
- 时间复杂度: ...
- 空间复杂度: 𝑂(\(b^d\)) (将每个结点存在内存中) 大问题!
一致代价搜索Uniform-cost search¶
思想：
扩展 路径消耗𝑔(𝑛) 最小的未扩展结点，此处的路径消耗是指“所选节点到初始节点路径长度总和”
实现方式：
边缘=按路径消耗排序的队列，最低优先（如果每一步的代价全部相等，则相当于宽度优先）
性质：
- 完备性: 是，如果每一步的代价𝑐𝑜𝑠𝑡 > 𝜀 > 0(死循环)
- 最优性: 是——结点以路径消耗𝑔(𝑛)的递增顺序扩展
- 时间复杂度：...
- 空间复杂度：...
深度优先搜索Depth-first search (DFS)¶
思想：
扩展最深的的未扩展结点
实现方式:
边缘是后进先出(LIFO)队列，即新的后继排在前面
性质:
- 完备性:否，在无限深度空间(带有循环的空间)中会失败。修改以避免在路径上重复状态 ⟶ 在有限空间中完备。
- 最优性:否
- 时间复杂度：...
- 空间复杂度：...
深度受限搜索Depth-Limited Search (DLS)¶
思想：
- 如果状态空间中路径的最大长度 𝑚 ⟶ ∞ ，则DFS永不终止
- 深度受限搜索DLS = 深度限制为𝑙的深度优先搜索DFS，即 深度为𝑙的结点没有后继结点
性质：
- 完备性: 如果深度限制 𝑙 < 𝑑 (最优解的深度)，则不完备，即找不到解; 否则完备
- 最优性: 通常不是最优的 (即使𝑙 > 𝑑)
两种终止条件:
- 失败(failure): 原问题本身无解
- 中断(cutoff): 在深度界限内无解
迭代加深的深度优先搜索IDS¶
思想：
- 逐渐增大深度限制，迭代调用深度受限搜索DLS
- 重复生成状态似乎很浪费，但实际上不是，因为绝大多数结点在底层，所以重复生成上层结点影响不大
- 结合了宽度优先搜索BFS和深度优先搜索DFS的优势
迭代加深的深度优先搜索仅使用线性空间，并且不比其它无信息搜索算法花费更多时间
性质：
- 完备性: 是
- 最优性: 是
双向搜索Bidirectional Search¶
双向搜索的思想是：
同时运行两个搜索，也就是一个 从初始状态向前 搜索，同时另一个 从目标状态向后 搜索，希望它们在中间某点相遇，此时搜索终止