《Rollout算法及其相关技术解析》
1. 确定性Rollout算法
在算法执行k步后，会得到一个从初始状态$x_0$开始，到状态$x_k$结束的轨迹。接着会生成所有可能的下一个状态集合，例如图中的$x_{k + 1}^1$，$x_{k + 1}^2$，$x_{k + 1}^3$，$x_{k + 1}^4$。使用基础启发式方法对这些状态进行“评估”，并选择其中一些进行“扩展”，也就是生成它们的下一个状态$x_{k + 2}$，再用基础启发式方法评估，如此继续下去。最终会得到一个具有选择性深度的下一个状态树，以及从树的叶子节点得到的基础启发式成本。选择性深度前瞻Rollout算法会选择对应最小总成本的状态$x_{k + 1}$。对于具有大量阶段的问题，还可以截断Rollout轨迹，并添加一个终端成本函数近似来补偿由此产生的误差。
下面用mermaid流程图展示确定性Rollout算法的主要流程：
graph TD A[开始] --> B[执行k步算法得到轨迹] B --> C[生成所有可能下一个状态集合] C --> D[用基础启发式评估状态] D --> E{选择部分状态扩展?} E -- 是 --> F[生成下一个状态并评估] F --> E E -- 否 --> G[得到选择性深度树和成本] G --> H[选择最小总成本状态] H --> I[结束]
