DiBS：扩散通知分支选择

arXiv:2606.06518v1 公告类型：new 摘要：数独是一个典型的约束满足问题，需要在严格离散约束下进行全局结构推理。现有的数独求解工作主要集中在两种主要方法，即传统启发式求解器和深度学习求解器。然而，它们面临两个互补的限制：基于学习的求解器缺乏严格的正确性保证，而完整的符号求解器仍然容易出现长尾搜索。为了解决这些缺点，我们提出了一种新颖的扩散模型引导方法，称为 DiBS，用于分支选择搜索过程。具体来说，DiBS 保持符号求解器的完整性，并使用扩散模型作为分支排序指南。核心方法是在当前部分分配和轻量级一致性信号下对候选值进行排序。此外，我们提供了深入的理论证明来揭示它的工作原理和原因。对具有挑战性的 Royle 17-clue Sudoku 基准的实验表明，相对于强启发式基线，我们的 DiBS 大大降低了搜索成本，特别是在节点、回溯和长尾百分位数方面。此外，这些结果证实了学习的全局指导对于分支顺序错误代价最高的困难情况是有效的。所有代码均可在 https://github.com/shanxierdan/DiBS 获取。