Я иногда очень удивляюсь
https://arxiv.org/pdf/1508.05117 - страница 8, правый столбец.
"∂+i (resp. ∂-i) is the set of clauses satisfied by setting xi = 1 (resp. xi = −1)."
Вроде, мелочь, 0 и -1 перепутали, но позвольте! Эта статья прошла ревю и вычитку самими авторами. Там всюду диапазон значений переменных от нуля до единицы, судя по формулам, и вдруг -1.
Код вот тут: https://github.com/RaffaeleMarino/The-Backtracking-Survey-Propagation-Algorithm-code
Но там настолько исследовательский код, что понять ничего нельзя.
Тем не менее.
Survey Propagation (распространение оценок) выбирает, случайным образом, одно из распространяемых "сообщений," от ограничения (clause) к переменной или от переменной к ограничению, и перевычисляет его. В один прекрасный момент сообщения перестают меняться значительным образом и мы вычисляем ожидаемое значение переменных, в диапазоне от 0 до 1, чем ближе мы к 0 или 1, тем выше "уверенность" в значении переменной. Далее мы упорядочиваем переменные по уверенности в их значении, присваиваем некоторым из них наиболее близкое значение, упрощаем задачу (распространяя константы) и снова запускаем распространение оценок. Если у нас нет достаточно определённых переменных, мы считаем, что задача уже довольно проста и можем запустить тот или иной алгоритм перебора.
В статье по первой ссылке иногда производится переоценка уверенности переменных с выбранным значением, и если она, для каких-то из них, упала сравнительно с тем, когда мы выбирали значение переменной, мы можем снова выбрать для них случайные значения и вернуть их в алгоритм распространения оценок. Это и есть "откат" (backtracking), основная идея статьи.
Так вот, код по ссылке работает как угодно, но не так, как описано в статье. ;)
Ничего он в поиск не возвращает. ;)
Заметно более понятная реализация распространения оценок:
https://github.com/antoniomanuelfr/Survey-Propagation
Насколько я понял из чтения литературы, распространение оценок использует перемещение в поле, своего рода, потенциальной энергии, нигде полностью не выраженной. И вместо использования интегрирования, они делают что-то неописуемое, физически (по-моему).
Тем не менее, это работает для случайных задач вблизи фазового перехода, работает лучше, чем другие методы. Это удивительно.
"∂+i (resp. ∂-i) is the set of clauses satisfied by setting xi = 1 (resp. xi = −1)."
Вроде, мелочь, 0 и -1 перепутали, но позвольте! Эта статья прошла ревю и вычитку самими авторами. Там всюду диапазон значений переменных от нуля до единицы, судя по формулам, и вдруг -1.
Код вот тут: https://github.com/RaffaeleMarino/The-Backtracking-Survey-Propagation-Algorithm-code
Но там настолько исследовательский код, что понять ничего нельзя.
Тем не менее.
Survey Propagation (распространение оценок) выбирает, случайным образом, одно из распространяемых "сообщений," от ограничения (clause) к переменной или от переменной к ограничению, и перевычисляет его. В один прекрасный момент сообщения перестают меняться значительным образом и мы вычисляем ожидаемое значение переменных, в диапазоне от 0 до 1, чем ближе мы к 0 или 1, тем выше "уверенность" в значении переменной. Далее мы упорядочиваем переменные по уверенности в их значении, присваиваем некоторым из них наиболее близкое значение, упрощаем задачу (распространяя константы) и снова запускаем распространение оценок. Если у нас нет достаточно определённых переменных, мы считаем, что задача уже довольно проста и можем запустить тот или иной алгоритм перебора.
В статье по первой ссылке иногда производится переоценка уверенности переменных с выбранным значением, и если она, для каких-то из них, упала сравнительно с тем, когда мы выбирали значение переменной, мы можем снова выбрать для них случайные значения и вернуть их в алгоритм распространения оценок. Это и есть "откат" (backtracking), основная идея статьи.
Так вот, код по ссылке работает как угодно, но не так, как описано в статье. ;)
Ничего он в поиск не возвращает. ;)
Заметно более понятная реализация распространения оценок:
https://github.com/antoniomanuelfr/Survey-Propagation
Насколько я понял из чтения литературы, распространение оценок использует перемещение в поле, своего рода, потенциальной энергии, нигде полностью не выраженной. И вместо использования интегрирования, они делают что-то неописуемое, физически (по-моему).
Тем не менее, это работает для случайных задач вблизи фазового перехода, работает лучше, чем другие методы. Это удивительно.