Почти всё понял
https://www.cs.cornell.edu/~kroc/pub/surveyPropUAI07b.pdf и https://arxiv.org/pdf/1508.05117 - про "распространение мнений," survey propagation, алгоритм, что может вычислять решения случайных k-SAT задач в областях, близких к фазовому переходу.
Вторая ссылка попроще будет, первая рассматривает сжатие решений через покрытия (cover). В покрытиях, помимо определённых значений 0 и 1, используется признак "не важно" (*). Это позволяет рассматривать несколько решений, как одно, например, если у нас есть решения 1110 и 1000, то мы можем смотреть на них, как на решение 1**0.
Вот тут код для второй статьи: https://github.com/RaffaeleMarino/The-Backtracking-Survey-Propagation-Algorithm-code
На структурных задачах всё равно не работает. ;)
Вторая ссылка попроще будет, первая рассматривает сжатие решений через покрытия (cover). В покрытиях, помимо определённых значений 0 и 1, используется признак "не важно" (*). Это позволяет рассматривать несколько решений, как одно, например, если у нас есть решения 1110 и 1000, то мы можем смотреть на них, как на решение 1**0.
Вот тут код для второй статьи: https://github.com/RaffaeleMarino/The-Backtracking-Survey-Propagation-Algorithm-code
На структурных задачах всё равно не работает. ;)