蒙特卡洛树搜索（MCTS）

MCTS也是一种使用颇多的路径生成算法，结合了BFS、DFS的优势，并且还可以结合神经网络和强化学习进行更进一步的探索。
MCTS优势在于，一个设计良好的估计函数可以让MCTS最大限度模拟人类的路径规划得出贴近人类思维的路径，这点在地图情况未知的开放型寻路中较有优势；其算法可以朴素地实现，但因每步的计算量较A大，故其效率相较于传统的A更低。

因此，MCTS适用于复杂地理环境寻路、动态环境寻路、未知环境寻路（如机器人寻路）等场合，不适用于高效率寻路、已知路径点寻路、静态寻路等场合。

Tesla之前使用的就是MCTS和神经网络来进行轨迹生成，通过构建目标点，使用神经网络进行目标点打分，然后选择分数较高的进行另一个神经网络的轨迹生成，最终结合约束和代价，筛选出final trajectory；
主要区别是在：MCTS通过一个权重表（取决于具体的实现）来决定每次搜索的试探方向：到底是探向更深的一层，还是停留在当前层试探其他节点。

树搜索的算法有很多，如果树的层数比较浅，我们可以穷举计算每个节点输赢的概率，那么可以使用一种最简单的策略，叫做minmax算法。基本思路是这样的，从树的叶子结点开始看，如果是本方回合就选择max的，如果是对方回合就是min的，实际上这也是假设对方是聪明的也会使用minmax算法，这样在博弈论里面就达到一个纳什均衡点。