Рис. 7.8. Анализ производительности алгоритмов DPLL и WalkSAT при решении трудных задач: график, на котором показана вероятность того, что случайно сформированное высказывание в форме 3-CNF с количеством символов п=50 окажется выполнимым, как функция от отношения "выражение/символ", m/n (а); график усредненного времени прогона алгоритмов DPLL и WalkSAT применительно к 100 выполнимым сформированным случайным образом высказываниям в форме З-CNFc п=50, который показывает наличие узкого диапазона значений m/n вокруг критической точки (б)

На рис. 7.8, б показано время прогона алгоритмов DPLL и WalkSAT на участке вокруг этой критической точки, где наше внимание ограничивалось только выполнимыми задачами. Изучение приведенных результатов позволяет сделать три вывода: во-первых, задачи, приближающиеся к критической точке, являются гораздо более трудными по сравнению с другими случайно сформированными задачами; во-вторых, даже при решении самых сложных задач алгоритм DPLL является весьма эффективным — он требует выполнения в среднем нескольких тысяч шагов по сравнению со значением количества шагов, которое требуется для перебора истинностной таблицы; в-третьих, во всем этом диапазоне характеристик задач алгоритм WalkSAT работает намного быстрее, чем алгоритм DPLL.

Безусловно, эти результаты относятся только к случайно сформированным задачам. Реальные задачи не обязательно имеют такую же структуру, как случайно сформированные задачи (они могут характеризоваться разными значениями относительного количества положительных и отрицательных литералов, разными плотностями соединений между выражениями и т.д.). Тем не менее на практике алгоритм WalkSAT и подобные ему алгоритмы очень хорошо справляются также с решением реальных задач и часто не уступают самым лучшим алгоритмам специального назначения для этих задач. Такие решатели задач, как Chaff, легко справляются с задачами, состоящими из тысяч символов и миллионов выражений. На основании этих наблюдений можно сделать вывод, что некоторые комбинации эвристики с минимальными конфликтами и поведения со случайным блужданием предоставляют универсальную способность находить решения в большинстве ситуаций, в которых требуется комбинаторное формирование рассуждений.