Survey Propagation http://arxiv.org/abs/cs/0212002 昔読んだ時はよく分からなかったけど、ふと読み返したら理解できたので実装してみた。 https://github.com/msakai/toysolver/blob/e895362308ff954db998bb367f97b7bb64ee21c6/src/ToySolver/SAT/MessagePassing/SurveyPropagation.hs
とりあえず、Survey Propagation の結果で、変数の初期値と変数の優先順位の初期値を決めてDPLL/CDCLで探索すると、Random K-Sat では探索が短くなっているような気はする。