蒙特卡洛树搜索的主要流程是

蒙特卡洛树搜索的主要流程是

蒙特卡洛树搜索的主要流程是：选择、扩展、卜桐模拟、回传。

1、利用CPOP算法求出DAG图的关键路径。

2、选择阶段：设定搜索树的根节点为S0，从根节点S0开始，每经过一个结点，开始判断经过的这个结点是否扩展完。

3、扩展阶段：若当前为扩展任务结点，则从待调度的任务队列中选择一个任务，添加到搜索树上，作为新的任务结点。

4、模拟咐衫阶段：从扩展结点开始，在每一个位置Si，使用随机策略交替选择任务和处理器，并将同一状态下选择的任务调度到处理器上，直到模拟到全部任务都被调度到处理器上为止，最后会得到一个makespan值。

5、回传阶段：当模拟结束后，获得搜索树中各节型简坦点的信息，同时根据makespan值，将搜索后所得最新结点由叶子结点回传到根节点上进行更新。

6、重复执行以上步骤直到DAG图的最后一个任务结点被调度到处理器上为止，并最后根据结果找到一条能使makespan值最小的调度顺序。

蒙特卡洛树搜索的含义：

蒙特卡洛树搜索又称随机抽样或统计试验方法，属于计算数学的一个分支，它是在上世纪四十年代中期为了适应当时原子能事业的发展而发展起来的。

传统的经验方法由于不能逼近真实的物理过程，很难得到满意的结果，而蒙特卡洛树搜索方法由于能够真实地模拟实际物理过程，故解决问题与实际非常符合，可以得到很圆满的结果。

这也是以概率和统计理论方法为基础的一种计算方法，是使用随机数（或更常见的伪随机数）来解决很多计算问题的方法。将所求解的问题同一定的概率模型相联系，用电子计算机实现统计模拟或抽样，以获得问题的近似解。