
# 第三章 搜索

## 搜索算法基础

> 搜索算法形式化描述：
>
> + **状态**：对智能体和环境当前情形的描述，例如，在最短路径问题中，城市可作为状态。将原问题对应的状态称为初始状态
> + **动作**：从当前时刻所处状态转移到下一时刻所处状态所进行操作。
> + **状态转移**：对智能体选择了一个动作之后，其所处状态的相应变化
> + **路径/代价**：一个状态序列，该状态序列被一系列操作所连接
> + **目标测试**：（每走一步）评估当前状态是否为目标状态

搜索树：用一棵树的数据结构来记录算法探索过的路径

+ 一个标号可能有多个节点与之对应，同一个标号一定表示相同的状态，其含义为智能体当前所在的城市
+ 搜索算法是一个构建搜索树的过程，会时刻记录所有从初始结点出发已经探索过的路径。

![搜索算法的评价指标](./pics/搜索算法的评价指标.png)

## 启发式搜索

在搜索的过程中利用与所求解问题相关的辅助信息，其代表算法为贪婪最佳优先搜索($Greedybest-firstsearch$)和A*搜索

### 贪婪最佳优先搜索

+ key idea：评价函数$f(n)$ = 启发函数$h(n)$

### A*算法

+ 评价函数：$f(n) = g(n) + h(n)$
  + $g(n)$ 表示从起始节点到节点 $n$ 
  + $h(n)$

![A*算法流程](./pics/A*算法流程.png)

## 对抗搜索

> 本课程讨论的是全局可观察的、确定的零和博弈的背景下的对抗搜索

+ 最小最大搜索：计算最优策略的方法
+ Alpha-Beta剪枝搜索：对最小最大搜索算法的优化，剪枝无需搜索的节点
+ 通过采样而非穷举方法来实现搜索

**对抗搜索问题模型**：

![对抗搜索问题模型](./pics/对抗搜索问题模型.png)

### MiniMax算法

注意主要讨论在确定的、全局可观察的、竞争对手轮流行动、**零和游戏(zero-sum)下的对抗搜索**

+ 一定是从左往右搜索
+ 如果有影响，那么我们继续搜索，如果没有影响，则对这个节点下停止搜索，剪枝，然后开始下一个兄弟节点并从最左边的子节点开始搜索。

然后我们现在就是维护两个变量$\alpha$和$\beta$

### 蒙特卡洛树搜索

单一状态的蒙特卡洛规划：多臂赌博机

+ 多笔赌博机问题

我们要明确蒙特卡洛树搜索算法的基本思想：
