До сих пор в данной книге было представлено несколько алгоритмов локального поиска, включая алгоритмы Hill-Climbing и Simulated-Annealing. Эти алгоритмы могут непосредственно применяться для решения задач проверки выполнимости, при условии, что будет выбрана правильная функция оценки. Поскольку цель состоит в том, чтобы найти присваивание, обеспечивающее выполнение каждого выражения, для этой цели может использоваться любая функция оценки, которая подсчитывает количество невыполненных выражений. Фактически именно этот критерий и применяется в алгоритме Min-Conf licts для задач CSP (с. 227). Все эти алгоритмы делают шаги в пространстве полных присваиваний, каждый раз меняя на противоположное (инвертируя) истинностное значение одного символа. Это пространство обычно содержит много локальных минимумов, для выхода из которых требуются различные формы рандомизации. В последние годы было проведено множество экспериментов с тем, чтобы можно было найти приемлемый компромисс между стремлением к "жадному" выбору наилучшего преемника и необходимостью выходить из локальных минимумов с помощью случайного выбора очередного преемника.

Одним из простейших и наиболее эффективных алгоритмов, которые были созданы в результате всей этой работы, является алгоритм, получивший название WalkSAT (листинг 7.8). При каждой итерации этот алгоритм выбирает одно невыполненное выражение, а в этом выражении выбирает один символ для инвертирования. В данном алгоритме происходит случайным образом переключение между двумя способами выбора символа для инвертирования его истинностного значения: во-первых, этап с "минимизацией конфликтов", в котором минимизируется количество невыполненных выражений в новом состоянии, и, во-вторых, этап "случайного передвижения", в котором один из символов выбирается случайным образом.

Листинг 7.8. Алгоритм WalkSAT для проверки выполнимости путем инвертирования значений переменных случайным образом. Существует много версий этого алгоритма