1.1 盲目搜索

预备知识

状态空间和搜索问题

为了创建一个理性计划agent，我们需要一种方法来对agent存在的环境进行数学表达。为此，我们必须正式表达一个搜索问题（search problem）——给定agent的当前状态（state，它在环境中的配置），我们如何尽可能最好地达到一个满足目标的新状态？讲一个问题公式化需要四个前提：

下面的概念尽量贴近MDP中的表述

状态空间（state space）：在给定世界中所有可能的状态
后续函数（successor function）：读入状态和动作，并计算该操作的代价以及后续状态，即函数\(f\)满足：\((r,s') = f(s,a)\)。
起始状态（start state）和目标状态（goal state），目标状态不见得是唯一一个，所以可以写成一个function，读入某个状态并判断是否为goal state。

而搜索问题的解，就是从start state到goal state的一个动作序列。

（世界状态和搜索状态的区别） 世界状态（world state）包含了环境中事无巨细的信息。而搜索状态（search state）只包含了计划所需要的部分细节，从而降低空间复杂度。例如，对Pacman（吃豆人）游戏来说，如果只是进行路径规划，那么只需要知道pacman当前的位置；如果是pacman的经典模式（吃掉所有豆子），那么状态还要考虑每个豆子是否被吃掉的bool值，同时successor func还要更新豆子的bool值。两种玩法的目标状态也不一样，前者是Bool值\(\{x,y\} == END\)，后者是“所有的豆子都处于false状态”。

世界状态往往很大，还是以pacman为例，假定： - 棋盘大小：10×12，即120个潜在坐标 - 吃豆人动作集：东南西北，4种情况 - 恶灵位置：两个恶灵，每一种都可能在12个不同的坐标，且分布互相独立 - 豆子分布：30个，位置固定，状态只有被吃（false）和没被吃（true）两种

那么： 1. 那么，根据简单计数原理，世界状态的空间有：\(120\times 4 \times 12^2 \times 2^{30}\)种。 2. 如果Pacman只是路径规划，那么此时搜索状态只包含了其位置：120种。 3. 如果Pacman要清空豆子，那么此时搜索状态包含了位置和豆子状态：\(120 \times 2^{30}\)种。

状态空间图和搜索树

盲目搜索方法

深度优先搜索 DFS

广度优先搜索 BFS

一致代价搜索 UCS

Next episode

下一部分将考虑有信息搜索，如A* 搜索、启发式搜索等，移步[[Section1.2 A_star Search and Heuristics]]。