❶ 常见算法有哪些
模拟
拟阵
暴力
贪心
二分法
整体二
三分法
一般动规与递推
斯坦纳树
动态树分治
2-SAT
并查集
差分约束
最短路
最小割
费用流
最大流
有上下界网络流
虚树
矩阵树定理
最小生成树
点分治
树链剖分
prufer编码
哈夫曼树
拉格朗日乘数法
BSGS
博弈论
矩阵乘法
高斯消元
容斥原理
抽屉原理
模线性方程组
莫比乌斯反演
快速傅里叶变换
扩展欧几里得算法(
裴蜀定理
dfs序
深度搜索
迭代深搜
广度搜索
双向广搜
启发式搜索
dancing link
回文自动机
KMP
字典树
后缀数组
AC自动机
后缀自动机
manacher
凸包
扫描线
三角剖分
旋转卡壳
半平面交
cdq分治
莫队算法
爬山算法
分数规划
模拟退火
朱刘算法
随机增量法
倍增算法
❷ MCTS方法在强化学习和组合优化中的调研
MCTS是一种古老的解决对抗搜索的方法。与Min-max 搜索不同，其可以做单智能体的任务。
1928年，John von Neumann的minimax定理提出了关于对手树搜索的方法，这成为了计算机科学和人工智能决策制定的基石。
其思路为，如果树的层数较浅，我们可以穷举计算每个节点的输赢概率，可以使用minmax算法，从叶子节点开始看，本方回合选择max，对方回合选择min，从而在博弈论中达到纳什均衡点。
流程如上图所示。当然，我们可以使用alpha-beta对这个搜索树剪枝。
但如果每一层的搜索空间都很大，这种方法就极其低效了，以围棋为例，围棋每一步的所有可能选择都作为树的节点，第零层只有1个根节点，第1层就有361种下子可能和节点，第2层有360种下子可能和节点，这是一颗非常大的树。如果我们只有有限次评价次数，minimax方法就是不可行的（往往只能跑2-3层，太浅了）
1940年代，Monte Carlo方法形成，这个方法由于在摩纳哥的蒙特卡洛赌场被发明而得名。其思想类似于18世纪的谱丰投针。
这种方法可以用到树搜索上。以围棋为例，围棋的每一步所有可能选择都作为树的节点，第零层只有1个根节点，第1层就有361种下子可能和节点，第2层有360种下子可能和节点，但是如果我们不断地尝试随机选择往下模拟5步，拿有限的尝试次数给当前层的每个动作算个期望，我们就可以选择相对最优的动作。
值得注意的是，这种方法可以应用到单人游戏上，所以在model-free强化学习中，也有这样的蒙特卡洛方法。
蒙特卡罗强化学习(Monte Carlo reinforcement learning)：指在不清楚 MDP 状态转移概率的情况下，直接从经历完整的状态序列 (episode) 来估计状态的真实价值，并认为某状态的价值等于在多个状态序列中以该状态算得到的所有return 的平均，记为期望值。
2006年，Kocsis和Szepesvári将此观点形式化进UCT算法。UCT=MCTS+UCB。UCB是在多臂老虎机问题中的不确定性估计方法。这种方法的思路是蒙特卡洛方法的动作选择之间具有不确定性，基于选择次数可以估计一个确定性值，以辅助价值评估。
UCT算法为，在原有的基础上，拓展作为确定性上界。t是选择这个动作的次数，T是当前状态的选择动作总次数。最后根据这个公式来选择给定状态的动作。这个确定性上界的推导是Chernoff-Hoeffding Bound定理得出的。
其实确定性上界有很多，由于推导过程认为选择次数会足够多。这个上界满足的是。后续很多工作只是把这一项当作了启发式，给第二项加了个系数。
这样，MCTS的过程就进化为了以下四个步骤。
再重新回到根节点，重复上述过程。
我们可以发现，这里的Simulation过程如果搜不到结束状态，对当前状态估值就是一个很重要的学问。我们将利用过往经验训练的神经网络对其估价就是一个可信的优秀方法。
Alphago Lee：接下来我会讲一下这个基本的方法之后于深度学习的结合，分别是在围棋和组合优化。MCTS的组合优化应用大概也是Alphago的功劳。
这是第一篇Alphago文章。
总的来说，这篇工作一共使用了3种技术：监督学习，强化学习和MCTS（UCT）。
下图展示了两个训练阶段。
这里的监督学习输入是状态的表示，我不会下围棋，所以不清楚这里的capture是什么。总体来说就是一个48 * 360 * 360的张量。
训练了两个类似的网络，只是大小不同。loss是CE loss。这些数据都是来自于一个数据集KGS，大小为100,000。
相比于上来就强化学习，这样相当于训练baseline，会更加稳定。
这个学完的效果是不好的。文章拿这个网络不加蒙特卡洛搜索对比了其他方法，只能赢11%-12%的对局。
强化学习的目的有两个。一是继续学习：数据集过小了，和minst差不多大（60,000），胜率太低了。二是获得估值：监督学习就好比图片分类，在输入棋盘后只会学习输出最优答案，而不是每个位置的胜率。
继续学习
获得估值
在提升策略网络性能的同时，RL另外训练了一个价值网络来估计棋盘的胜率 loss是MSE。输出由动作概率变为一个标量值，用来表示状态s的胜率。注意到胜率其实就是上文中的reward对动作序列的期望。
这之后的MCTS是一个独立的步骤，文章先评价了每个方法的效果。
正如上文提到，MCTS分为四个步骤，最终会得到一个训练好的MCTS。这个过程网络都是fixed的。
Alphago的MCTS流程如下。
上文提到这个最大确定上界u可以很灵活，对照前文表示方法，这里的[公式]。
值得强调的是，最终Alphago在运行时选择动作的依据不是Q，而是u。
这是最终的结果。看得出超过了所有人类高手和已有方法。
这页很有意思。
可以看出设备很足……
Alphazero
一年后，原班人马提出了升级版，motivation是原有的监督学习数据会导致容易陷入局部最优而且不优雅。
两者最大的不同是，本文仅仅使用self-play强化学习，从随机play开始，不用任何监督学习。
作者的意思是，rollout只是网络不行的一个替代解决方案。这里的U有一个微调，改回了原始版本[公式]。
注意，这里不是一个神经网络，而是一组，Alphazero维护的神经网络为[公式]，两者分别是根据奖励和选择次数（u）策略梯度更新和根据奖励MSE更新，最终加权估计这个Q。也就是说，在Alphazero中，不需要一套额外的计数器去记录Q和u了。在训练时，这两个函数被记录去训练两个网络，在训练完成后，整个决策就会完全根据网络输出，[公式]代替argmax Q+U选择动作。
这篇文章的潜能更高当然train得更慢。
组合优化：
后续有很多文章致力于用MCTS做TSP，基本思想也是建模成四个流程模仿Alphago。
众所周知，强化学习组合优化一般是两种思路，一个是一位一位得输出解，这个过程是端到端的，称为Learn to construct。
Learn to Construct methods
对于end-to-end的L2C思路，2016年就有一位学者发表了论文Application of monte-carlo tree search to traveling salesman problem，但这篇文章怎么也搜不到了。
后来2020年有这样一篇文章。
这篇文章里，蒙特卡洛树搜索被建模为每层选解。以TSP20为例，第一层就是20个选择，第二层是19个...
依然是四个阶段。
选择动作如下式子。
在提前训练这个网络的时候也是reward拟合剩下的半部分，用的是值函数逼近 训练方法（L2 loss + 正则化，但是没有搞target network）。
他这里介绍的reward有一处错误，[公式]应该是[公式]，下边是训练方法。
这里的随机选择我不理解，我的理解是这样学习网络的价值就不大了。文章结果比不过不加MCTS。这个directly use也有点不规范……
这篇文章还有升级版，采用了类似的奖励设置，投稿ICLR2021获得了455的分数，叫做：
这篇文章就是按照Alphazero的思路搞出来两个网络，拟合v和[公式]，然后险胜S2V-DQN的原始方法。
这两篇文章和所有在这个角度的文章最大的贡献应当是证明了，基于构造（L2C）的组合优化蒙特卡洛方法不可行。我的理解是，这个方法是根据对弈产生的，其奖励的和自然可以代表胜率。两者都把这个最关键的奖励设置为人为构造的新东西。构造排名得分是个不错的想法，但是这样转化根据结果看不是一个好的转化方法，导致这套理论就无法发挥作用。
Openreview的意见认为，这种方法发展到大规模会比较好。传统的端到端学习基本只能拟合值函数或者policy之一，Alphazero框架需要同时拟合两者，这需要一定的创新。
Learn to Improve methods
这个方向是比较成功的，有一篇AAAI21的文章。这个方向上的第一篇文章是：
但是被ICLR拒了。这个方法完全是AAAI文章的一部分（也是同一个课题组搞得）。本文使用的提升算子为k-opt。这篇文章不是learning-based的，而是一种启发式，每次重新跑一遍MCTS，所以被拒了。
这个MCTS的结构就比较特别了，后边会提到。同样是四个阶段。
k-opt的动作选择可以用一个序列表示[公式]代表。对应删除边[公式]，连接[公式]在选择时我们认为一个TSP序列是有向环路，所以我们只需要选择k个不同的a即可。在每次选择一个b后，对于一个n个结点的图下一个点是这样决定的，还是用T代表当前层总访问次数[公式]这里就看出来了，这其实是一个算子迭代树，这里的MCTS也不是为了快速求解而是辅助启发式的。
result：
最后这篇文章是AAAI21，我曾经做过一个论文复盘 论文复盘：Generalize a Small Pre-trained Model to Arbitrarily Large TSP Instances-AAAI2021大规模tsp监督学习方法。他就是在这个操作前监督学习train了小网络并且拼接得到热图来生成初始解。
但是读了前一篇文章我对这个结果就有点不解了...
总结一下：MCTS是一个解决游戏问题很好的方法，取自MAB，但是对于优化问题有一定的限制。MCTS的核心是rollout和simulation时用到的UCB评价，前者来自于赌场经验，后者来自于MAB的理论。这两个单独的构建分别在RL方法里被发展成了两个分支，这说明了这两个点对于强化学习的重要性。例如DDPG也是一个价值网络和一个策略网络，这两个部件可以对应到之前讲到的基线估计方法TD3、SAC和curiosity好奇心。