DiBS: 拡散モデルに基づく分枝選択

ニュース概要

数独は厳密な離散制約の下での全体的な構造推論を必要とする制約充足問題の代表例である。既存の数独求解アプローチは従来的ヒューリスティックと深層学習ソルバーの2つが主流だが、学習ベースのソルバーは厳密性の保証が欠け、完全な記号的ソルバーは長尾探索に弱いという補完的な限界を抱えている。これらの問題に対処するため、分枝選択探索プロセスのガイドとして拡散モデルを活用したDiBSと呼ばれる新しいアプローチを提案する。DiBSは記号的ソルバーの完全性を維持しながら、拡散モデルを分枝順序付けの指針として使用する。核心的な手法は現在の部分割当と軽量の一貫性信号の下で候補値をランク付けすることである。さらに、その動作原理と有効性に関する詳細な理論的証明を提供する。困難なRoyle 17ヒント数独ベンチマークの実験結果は、DiBSが特に探索ノード数、バックトラック回数、長尾パーセンタイルにおいて強力なヒューリスティックベースラインと比較して探索コストを大幅に削減することを示している。また、分枝順序の誤りが最も高くつく困難なインスタンスにおいて、学習された全体的ガイダンスが有効であることが確認されている。