DiBS：擴散模型引導的分支選擇
針對數獨求解中學習型求解器缺乏正確性保證、符號求解器易陷入長尾搜尋的問題，研究人員提出了一種擴散模型引導的分支選擇方法DiBS。該方法在保持符號求解器完備性的同時，利用擴散模型對候選值進行排序，顯著降低了搜尋成本。在Royle 17線索數獨基準測試上，DiBS減少了節點數、回溯次數和長尾百分位，證明了全域性學習引導在困難例項上的有效性。
數獨是一種經典的約束滿足問題，要求求解器在嚴格的離散約束下進行全域性結構推理。目前主流方法分為兩類：傳統啟發式演算法和深度學習求解器。然而，兩者各有缺陷：學習型求解器雖然速度快，但無法保證輸出結果的正確性，可能給出錯誤答案；而完備的符號求解器雖然能保證正確性，但在處理複雜例項時容易陷入長尾搜尋，即大部分求解時間花費在少數極端困難的搜尋分支上。這種互補性侷限嚴重製約了數獨求解的效率和可靠性。
為了解決這一矛盾，來自多所機構的研究人員提出了一種名為DiBS（Diffusion-Informed Branch Selection）的創新方法。其核心思想是將符號求解器的完備性與擴散模型的引導能力有機融合。具體來說，DiBS保持符號求解器的完整搜尋框架，但利用擴散模型作為分支排序的智慧指南。在每一步部分賦值中，DiBS透過輕量級的一致性訊號對候選值進行排序，從而優先探索最有希望的分支，避免在錯誤方向上浪費計算資源。
研究團隊不僅提出了方法，還提供了深入的理論證明，揭示了擴散模型為何能有效指導分支選擇的內在機理。在極具挑戰性的Royle 17線索數獨基準測試上，實驗結果表明，DiBS相比強啟發式基線顯著降低了搜尋成本，尤其是在節點數、回溯次數和長尾百分位等關鍵指標上表現突出。這些結果有力地證實了，在分支順序錯誤代價極高的困難例項上，學習到的全域性指導具有顯著優勢。
此外，研究團隊已將DiBS的全部程式碼在GitHub上開源，為後續研究提供了堅實的基礎。這項工作不僅為數獨求解開闢了新路徑，也為其他約束滿足問題中融合符號推理與神經網路技術提供了重要參考，有望推動人工智慧在組合最佳化領域的進一步發展。