Search -- State Spaces, Uninformed Search

为了让一个理性的规划智能体能够行动，我们首先需要一种数学化的方式来描述它所处的环境。搜索问题 (Search Problem) 的核心就是：给定智能体当前的状态，如何以最优的方式找到一条路径，到达满足其目标的新状态。

搜索问题的形式化定义

一个搜索问题由以下六个核心要素构成：

状态空间 (State Space)：在一个特定世界中所有可能状态的集合。
行动集合 (Actions)：在每个状态下，智能体可以采取的一系列行动。
转移模型 (Transition Model)：描述了当在当前状态下采取一个特定行动后，会转移到哪个新状态。
行动成本 (Action Cost)：从一个状态转移到另一个状态所产生的代价。
初始状态 (Start State)：智能体最初所处的状态。
目标测试 (Goal Test)：一个函数，用于判断给定的状态是否是目标状态。

状态空间 (State Space)

状态空间 (State Space) 是搜索问题中最重要的概念之一。它定义了在特定世界中所有可能的状态。其中主要区分两种状态空间：世界状态 vs. 搜索状态

世界状态 (World State) 包含了一个状态的所有信息。
搜索状态 (Search State) 只包含对规划必要的信息，这主要是为了节省空间。

状态空间图和搜索树(State Space Graph and Search Tree)

这是理解搜索算法如何工作的两个关键结构。

状态空间图 (State Space Graph)
- 节点是状态，有向边是行动。
- 每个状态在图中只出现一次。
搜索树 (Search Tree)
- 节点不仅代表一个状态，更代表一条从初始状态到达该状态的完整路径 。
- 由于从起点到同一个状态可能有多条路径，因此同一个状态可能在树中出现多次。
- 算法在解决问题时，会按需 (on-demand) 构建搜索树，只存储和扩展当前需要处理的节点（即“前沿”），从而应对其巨大的潜在规模。

无信息搜索 (Uninformed Search)

当智能体对目标状态的位置没有任何先验知识时，它只能采用无信息搜索策略。这些策略都基于上述提到的通用的树搜索 (Tree Search) 框架，即维护一个待扩展节点的前沿 (frontier)，并根据不同策略选择下一个要扩展的节点 。

树搜索框架 (Tree Search)

树搜索不是一次性构建整个搜索树，而是通过维护和扩展前沿来逐步、动态地构建这棵树，这个框架可以被概括为以下几个步骤：

1.初始化前沿：搜索开始时，将包含初始状态的节点（即搜索树的根节点）放入前沿。这是我们探索的起点。

2.循环探索：只要前沿不为空（意味着还有未探索的路径），就继续循环。如果前沿为空，则说明所有可达路径都已探索完毕，但仍未找到目标，因此搜索失败。

3.选择并移除节点：根据预设的策略，从前沿中选择一个节点并将其移除。正是这个选择策略，决定了搜索算法是DFS、BFS还是UCS。

4.目标测试：检查刚刚移除的节点是否包含目标状态。如果是，那么从该节点回溯至根节点的路径就是我们找到的解决方案，搜索成功结束。

5.扩展节点：如果上一步的节点不是目标，我们就对其进行“扩展”。这意味着，我们会考虑从该节点所代表的状态出发，可以执行的所有行动，并为每个行动在原先的节点基础上加上一个新的子节点（代表新的路径和新的状态）。然后，将这些新生成的子节点加入到前沿中，等待未来的探索。

示例

假设我们的目标是从城市 S 到达城市 G。

初始状态: 前沿 (Frontier): [ Node(S) ] , 此时我们的探索列表里只有一个起点。
第 1 轮循环:
- 移除: 算法从前沿中选择并移除 Node(S)。
- 当前前沿: [ ] (暂时为空)
- 目标测试: S 是不是目标 G？不是。
- 扩展: 我们对 Node(S) 进行扩展。假设从 S 可以到达 A 和 B。
- 步骤说明：我们生成了两个新的子节点：Node(S->A) 和 Node(S->B)。
- 加入前沿: 将这两个新节点加入前沿。
- 当前前沿: [ Node(S->A), Node(S->B) ]
第 2 轮循环 (假设使用BFS策略，选择最浅的节点):
- 移除: 算法从前沿中选择并移除 Node(S->A)。
- 当前前沿: [ Node(S->B) ]
- 目标测试: A 是不是目标 G？不是。
- 扩展: 我们对 Node(S->A) 进行扩展。假设从 A 可以到达 C 和 D。
- 步骤说明：我们生成了两个新的子节点：Node(S->A->C) 和 Node(S->A->D)。
- 加入前沿: 将这两个新节点加入前沿。
- 当前前沿: [ Node(S->B), Node(S->A->C), Node(S->A->D) ]
第 3 轮循环 (继续使用BFS策略):
- 移除: 算法从前沿中选择并移除 Node(S->B)。
- 当前前沿: [ Node(S->A->C), Node(S->A->D) ]
- 目标测试: B 是不是目标 G？不是。
- 扩展: 我们对 Node(S->B) 进行扩展。假设从 B 可以到达 E 和 G。
- 步骤说明：我们生成了两个新的子节点：Node(S->B->E) 和 Node(S->B->G)。
- 加入前沿: 将这两个新节点加入前沿。
- 当前前沿: [ Node(S->A->C), Node(S->A->D), Node(S->B->E), Node(S->B->G) ]
第 4 轮循环:
- 移除: 算法从前沿中选择并移除 Node(S->A->C)… 这个过程会继续下去。
- 直到某一次循环，比如第 N 轮：
- 移除: 算法从前沿中选择并移除 Node(S->B->G)。
- 目标测试: G 是不是目标 G？是的！
- 返回结果: 搜索成功，返回 Node(S->B->G)。通过这个节点，我们可以回溯出完整的路径是 S -> B -> G。

总之, 这里的移除一个节点，并不是把它丢弃或忘记，而是把它从“待办事项”列表（前沿）中拿出来，准备对其进行处理。

而扩展一个节点，就是基于当前路径，探索所有下一步的可能性, 例如查看状态A所有可能的行动（比如可以去B、C、D），然后为每一个行动生成一个新的子节点。

# pseudocode for tree search
function TREE-SEARCH(problem, frontier) return a solution or failure
    frontier ← INSERT(MAKE-NODE(INITIAL-STATE[problem]), frontier)
    while not IS-EMPTY(frontier) do
        node ← POP(frontier)
        if problem.IS-GOAL(node.STATE) then
            return node
        end
        for each child-node in EXPAND(problem, node) do
            add child-node to frontier
        end
    end
    return failure

function EXPAND(problem, node) yields nodes
    s← node.STATE
    for each action in problem.ACTIONS(s) do
        s′ ← problem.RESULT(s, action)
    end
    yield NODE(STATE=s′, PARENT=node, ACTION=action)

三种核心策略

对于每种策略，我们也将介绍其一些基本性质，从以下几个方面进行说明：每种搜索策略的完备性————如果搜索问题存在解，该策略是否在无限计算资源下保证能找到解？每种搜索策略的最优性————如果搜索问题存在解，该策略是否能找到最优解？每种搜索策略的时间和空间复杂度 分支因子 b - 每次从前沿队列中取出一个节点并用其子节点替换时，前沿节点数量增加的量是 O(b)。在搜索树的深度 k 处，存在 O(b^k)个节点。

深度优先搜索 (Depth-First Search - DFS)
- 描述：总是选择最深的前沿节点进行扩展。
- 前沿表示：使用后进先出 (LIFO) 栈，因为它总是优先处理最新加入的节点（即更深的节点）。
- 性质：
  - 完备性：不完备。如果状态空间图中存在环路，搜索树可能会无限深，导致DFS陷入死循环。
  - 最优性：不最优。它找到的是搜索树中“最左侧”的解，不考虑路径成本。
- 时间复杂度：O(b^m)，其中 b 是分支因子，m 是最大深度。
- 空间复杂度：O(bm)。这是它的主要优势，因为它只需要存储一条路径上的节点。 > 一条路径的最大长度是 m。在这条路径上的每个节点，最多在生成的时候扩展了 b-1 个兄弟节点存储在前沿（栈）中，等待当前路径探索失败后回溯时使用。因此，总共需要存储的节点数大约是 (b − 1) * m
广度优先搜索 (Breadth-First Search - BFS)
- 描述：总是选择最浅的前沿节点进行扩展。
- 前沿表示：使用先进先出 (FIFO) 队列，以保证按层级顺序访问节点。
- 性质：
  - 完备性：完备。因为它保证会搜索到最浅的解所在的有限深度 s 。
  - 最优性：当所有行动成本相同时，它是最优的，因为它找到的是深度最浅的解。
- 时间复杂度：O(b^s)，其中 s 是最浅解的深度。
- 空间复杂度：O(b^s)。这是它的主要缺点，前沿需要存储整层的节点。
一致成本搜索 (Uniform Cost Search - UCS)
- 描述：UCS 是 BFS 的一个重要泛化，它从“找到步数最少的路径”升级为“找到成本最低的路径”, 其总是选择从初始状态到当前节点路径成本最低的前沿节点进行扩展。
  - UCS 的策略与著名的 Dijkstra 算法完全相同。主要区别在于，UCS 在找到第一个目标状态时就停止，而 Dijkstra 算法会继续运行，直到找到从起点到图中所有节点的最短路径。
- 前沿表示：使用基于堆的优队列 (Priority Queue)，节点的优先级由其路径成本决定。
  - 每个节点被放入优先队列时，它的优先级被设定为其从初始状态到该节点的路径成本。
  - 优先队列的特性保证了成本最低的节点总是位于队列的“顶部”。
  - 当算法需要选择下一个节点时，它只需从队列顶部取出一个即可。
  - 当新的子节点被加入队列时，优先队列会自动根据它们的路径成本进行内部排序（“重新洗牌”），以确保成本最低的节点始终在最前面。
- 性质：
  - 完备性：完备（只要存在有限成本的解）。
  - 最优性：最优（只要行动成本非负）。因为它按路径成本递增的顺序扩展节点。
    - 负成本问题：如果存在负成本的边，UCS 的最优性保证就会失效，因为它可能先找到一条看起来成本低的路径，但之后却发现另一条更长的路径因为有负成本边而总成本更低。
- 时间复杂度：O(b^{C^*/ϵ})
  - C^*：最优解的路径成本。
  - ϵ：任意两个节点之间最小的行动成本（必须大于0）。
  - C^*/ϵ：这个比值可以理解为最优路径的“有效深度”。它粗略地告诉我们，要凑够最优成本 C^*，在最理想的情况下（即每一步都走成本最低的 ϵ 路径），大约需要走多少步。如果所有行动成本都是1，那么 ϵ = 1，C^* = s，这个比值就等于最浅解的深度 s，复杂度就退化为 BFS 的 O(b^s)
  - 这个“有效深度”的概念，将 UCS 的行为与 BFS 统一了起来。BFS 是在探索一个“深度圈”，而 UCS 是在探索一个“成本圈”。C^*/ϵ 就是这个成本圈的半径的近似度量。
- 空间复杂度：O(b^{C^*/ϵ})
  - 和 BFS 类似，UCS 的空间瓶颈在于前沿 (frontier) 的大小。在即将找到成本为 C^* 的最优解时，前沿中会包含大量路径成本约等于 C^* 的节点。