확산 정보에 기반한 branch 선택

스도쿠(Sudoku)는 엄격한 이산 제약 하에서 전역 구조적 사고가 필요한 대표적인 제약 만족 문제입니다. 현재 스도쿠를 해결하는 연구는 주로 두 가지 주요 접근 방식에 집중되어 왔는데, 그것은 전통적인 근거 추론과 깊은 학습 기반 해결사입니다. 그러나 두 가지 상보적인 제약이 존재하는데, 학습 기반 해결사는 강력한 정확성 보장을 하지 못하고 완전한 Symbolic 해결사는 여전히 긴 꼬리 검색에 취약합니다. 이러한 단점을 해결하기 위해, 우리는 branch selection search process를 위한 새로운 Diffusion model-guided 접근 방법, DiBS를 제안합니다. DiBS는 Symbolic 해결사를 완전하게 유지하고 Diffusion model을 branch-ordering guide로 사용합니다. 핵심 방법은 현재 부분 assignments와 가볍게한 consistency signal 아래에서 candidate values를 ranking하는 것입니다. 또한, 우리는 DiBS가 어떻게 작동하고 왜 작동하는지에 대한 심층 이론적 증명을 제공합니다. Royle 17-clue 스도쿠 benchmark에서 수행한 실험은 우리의 DiBS가 강력한 근거 기반 baseline에 비해 search cost를 크게 줄이는 것을 보여주었습니다. 특히 노드, backtracks, 그리고 긴 꼬리 백분율에서 DiBS가 더 좋았습니다. 또한, learned global guidance가 hard instances에서 branch-order mistakes가 가장 비용이 많이 드는 곳에서 효과적인 것을 확인했습니다. 모든 코드는 https://github.com/shanxierdan/DiBS에서 사용할 수 있습니다.