搜索算法综述

启发式搜索

关于搜索算法的具体介绍见 遍历与启发式搜索。

搜索算法的形式化描述：状态、动作、状态转移、路径、测试目标

启发式搜索（有信息搜索）

搜索过程中利用辅助信息，代表有贪婪最佳优先搜索和A*搜索。

以城市最短路径问题为例：可以利用的信息为城市之间的直线距离作为启发函数。

辅助信息、评价函数（如何寻找下一个节点）、启发函数（节点到目标节点的路径的最小代价值）

贪婪最佳优先搜索

(Greedy Best First Search, GBFS)：评价函数=启发函数

从当前节点出发，寻找下一个邻接节点，邻接节点选择的依据（评价函数）为使得启发函数值最最小的节点。

不足之处：1.不是最优解，2.启发函数最小化这一目标对于错误的起点比较敏感，有可能进入死循环（不完备）3.最坏情况下复杂度很高为$O(b^m)$，b为节点分支因子数、m为搜索空间的最大深度

需要设计一个良好的启发函数

A*算法

评价函数$f(n)=g(n)+h(n)$

g(n)为起始节点到当前节点n的开销代价，h(n)表示从节点n到目标节点路径所估算的开销代价值（启发函数）。

即评估函数=当前最小开销代价+后续最小开销代价

要求：

可容：需要启发函数<=实际开销

一致性：$h(n)<=c(n,n’) + h(n’)$，即n到目标的启发式距离不大于n到$n’$的距离加$n’$到目标的距离。

以直线距离作为启发函数h(n)，则一定是可容的和一致的。

性质：

A*算法中，如果$h(n)$是一致的，则如果$f(n)$是非递减的。

如果A*算法将节点n作为最小代价开销的路径中一个节点，则n一定是最优路径中的一个节点

对抗搜索

最小最大搜索

时间复杂度为$O{(b^m)}$，m为游戏树的最大深度，b为每个节点存在的有效走法数

最小最大算法的最大弱点是它需要展开整个博弈树。对于有高分支因子的博弈（例如围棋或国际象棋），该算法将导致巨大的博弈树，使得计算无法进行。

Alpha-Bata剪枝搜索

在极小极大算法中通过剪枝减少搜索的节点数。

α为max节点目前得到的最高收益，β为min节点可以给对手的最小收益 。

蒙特卡洛搜索

蒙特卡洛树搜索

通过采样而不是穷举的方式实现

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

上限置信区间策略

蒙特卡洛树搜索

单一状态蒙特卡洛规划

序列决策问题，再利用和探索之间保持平衡

利用：保证再过去决策中获取最佳回报

探索：未来能够获得更大的回报

上限置信区间（UCB）

使$\overline{X_{i,T_i(t-1)}}$记录第i个赌博机（共k个）在过去t-1时刻内的平均奖励，选择具有最佳上限置信区间的赌博机：

$$I_t = \max_{i\in \{1,\cdots,k\}}\{\overline{X_{i,T_i(t-1)}}+c_{t-1,T_i(t-1)} \}$$

其中$c_{t,s}$定义如下：

$$c_{t,s} = \sqrt{\frac{2\ln t}{s}}$$

$T_i(t) = \sum_{s=1}^t if(I_s=i)$为从初始时刻到t时刻时，选择第i个赌博机的次数。

$I_t$中第一项表示不同赌博机过去的奖励均值，则为了最大化$I_t$，倾向于选取之前平均收益最大的赌博机，代表利用。第二项大小与该赌博机被选择的次数有关，次数越多，则$c_{t,s}$中的s越大，则$c_{t,s}$越小，更倾向于选择之前被选次数更少的赌博机，代表探索。

简化表示：

$$UCB= \overline X_j + c\sqrt{\frac{2\ln n}{n_j}}$$

$\overline X_j$为第j个赌博机过去获得的奖励的均值，$n_j$为第j个赌博机被选择的次数，c为平衡因子。

首先把所有的赌博机选择一次，从第二次选择开始，每次从1一直遍历到k个赌博机，选取其中能够使UCB1（UCB最大）的一个j。

蒙特卡洛树搜索

将UCB应用于游戏树的搜索方式，包括选择、扩展、模拟、反向传播四个步骤。每个节点有2个值，代表选择这个节点的胜利次数和模拟的总次数。

选择：

从根节点向下递归选择，一直到一个叶子节点。选择方式为用UCB选择最优潜力的后续节点

节点分成三类：

未访问：节点没有被遍历过

为完全展开：节点访问过，而子节点没有被全部访问过

完全展开：所有子节点都被访问过

扩展：

将选择的叶子节点添加一个为（0，0）的叶子节点。然后开始模拟。

模拟：

随机走一个棋子，直到分出胜负。

反向传播:

从子节点，沿着刚才向下的路径返回去，沿途更新每个祖先节点的状态。

整个过程包括2种策略学习方法：

搜索树策略：从已有的搜索树选择或者创建一个叶子节点（选择和扩展步骤）

模拟策略：从扩展出的节点出发，模拟游戏，得到游戏最终胜负结果。

搜索过程为：首先至少模拟一次，得出部分节点状态，然后从根节点出发，基于上次的节点状态，选择子节点，当不存在子节点时，创建出一个状态为（0，0）的子节点，开始模拟，模拟的结果回溯更新祖先节点。

假设以黑棋的角度，以上述的搜索树为例，则第一行表示黑棋选择，第二行表示白棋选择，依次交替。每个节点有2个状态（A/B），A表示选择该节点黑棋胜利次数或者白棋失败次数，B表示选择该节点的总次数。已经模拟了21次，第22次时从根节点出发。比如根节点（12/21）表示总共模拟了21次，黑棋胜利12次。第一行第一个节点表示，该节点被走过10次，其中黑棋7次胜利。

当第22次时，根节点处，黑棋开始选择，黑棋有三个子节点，分别为7/10，5/8，0/3。使用UCB1公式(平衡因子c=$\frac{\sqrt{2}}{2}$)计算分别为：

$$7/10：\frac{7}{10}+\sqrt{\frac{\ln 21}{10}} = 1.252 \\ 5/8：\frac{5}{8}+\sqrt{\frac{\ln 21}{8}} = 1.243 \\ 0/3：\frac{0}{3}+\sqrt{\frac{\ln 21}{3}} = 1.007$$

因此，从根节点，选择7/10这个子节点。接下来，白棋从7/10开始选择子节点。由于状态A/B中第一项A为白棋失败次数，计算时应该使用1-A。

$$2/4:1-\frac{2}{4}+\sqrt{\frac{\ln 21}{4}} = 1.372 \\ 5/6:1-\frac{5}{6}+\sqrt{\frac{\ln 21}{6}} = 0.879$$

因此，白棋选择2/4节点。接下来黑棋选择1/1节点，此时到达了叶子节点，需要进行扩展。

扩展的新节点被置为0/0，然后以此节点开始模拟。假设经过一系列的仿真，最终白棋获胜，则将扩展节点置为0/1，并且沿着选择路径回溯到根节点，沿途所有祖先节点的A值不变，B值加一。