Intro to AI: Searching

Searching

• Searching Problem 的组成部分
  1. state space
  2. successor function (包含 action 和 cost/reward，例如路径)
  3. start state 和 goal state
• 搜索问题的解决方法：a sequence of action which transforms start state into goal state

于是可以表示为图论问题

• 节点：代表 state
• 有向边：代表 state transformation
• 目标：从一个节点走到另一个节点

这张图是全局的，包含所有 state 的信息和转移。如果我们只关注从某一个 state (例如 start state) 出发的可能性（即局部的），则得到搜索树

• ……但是子树结构大量重复
• ……可能有环，导致树高无限高
• 解决方案：只保留正在考虑的部分子树，其余的全部扔掉

DFS

令一个状态可以拓展到 $b$ 个状态，最多 $m$ 层，则

• 树中节点数量：$O(b^m)$
• 原图无环时，DFS 搜索树是有穷的
• 不一定 Optimal，因为只往 leftmost 方向走

BFS

• 到达一个状态，所探明的节点数量为 $O(b^s)$，$s$ 为当前所处在的深度
• 必然是 complete 的
• 不一定 optimal，除非 cost 均为 $1$