理解分散森林搜索：多轮程序校正的版本空间视角

在多轮程序校正中，提出了最先进的分散森林搜索（SFS）方法，采用蒙特卡罗树搜索（MCTS）以及精心设计的初始种子和基于文本的优化。然而，由于SFS集成了多个组件，因此每个组件对性能和SFS整体行为的影响尚未得到充分分析。在这项工作中，我们从学习理论中版本空间的角度对SFS的细化过程进行了理论分析，并阐明了其行为。首先，作为理论分析的基础，我们引入了顺序自细化方法（Line），该方法从初始程序开始，反复细化生成的程序。此外，当Line在深度方向上进行细化过程时，我们引入了修复指令的迭代细化（IRRI）来捕捉宽度方向上的细化过程，它修复了初始程序并迭代地细化了修复指令。然后我们分析了 Line 和 IRRI，并将 SFS 定位为两者之间的中间方法，对 SFS 进行了理论分析。我们的理论分析表明，SFS 表现出的行为更接近 IRRI，而不是 Line，并且这一理论特征也得到了实验的证实。考虑到计算资源和方法简单性，这些结果表明更简单的方法 IRRI 可以实现类似的细化过程，而不依赖于 SFS 的复杂校正机制。