Трудные задачи определения выполнимости
Теперь рассмотрим, какие показатели производительности демонстрируют алгоритмы DPLL и WalkSAT на практике. Нас особенно интересуют трудные задачи, поскольку легкие могут быть решены с помощью любого старого алгоритма. В главе 5 мы ознакомились с некоторыми удивительными открытиями в области решения задач определенного типа. Например, задача с п ферзями (которая когда-то рассматривалась как чрезвычайно сложная) при ее решении с помощью алгоритмов поиска с возвратами оказалась тривиально простой для методов локального поиска, таких как метод с минимальными конфликтами. Это связано с тем, что решения этой задачи распределены в пространстве присваиваний очень плотно и для любого начального присваивания гарантируется, что решение находится недалеко. Таким образом, задача с п ферзями является простой потому, что она недостаточно ограниченна.
Если речь идет о решении задач проверки выполнимости, представленных в конъюнктивной нормальной форме, то среди них недостаточно ограниченными можно считать такие задачи, которые содержат относительно немного выражений, ограничивающих значения переменных. Например, ниже представлено выработанное случайным образом12 высказывание в форме 3-CNF с пятью символами и пятью выражениями.
(—iD v —iB v С) л (В v -лA v -iC) л (-iC v —>В v E) л (I? v —iD v В) л (В v E v —iC)
Моделями этого высказывания являются 16 из 32 возможных вариантов присваивания, поэтому в среднем для поиска модели потребуются только две случайно выбранных гипотезы.
Отношение "выражение/символ", т/п Отношение "выражение/символ", т/п
а) б)
Рис. 7.8. Анализ производительности алгоритмов DPLL и WalkSAT при решении трудных задач: график, на котором показана вероятность того, что случайно сформированное высказывание в форме 3-CNF с количеством символов п=50 окажется выполнимым, как функция от отношения "выражение/символ", m/n (а); график усредненного времени прогона алгоритмов DPLL и WalkSAT применительно к 100 выполнимым сформированным случайным образом высказываниям в форме 3-CNFc п=50, который показывает наличие узкого диапазона значений m/n вокруг критической точки (б)
На рис. 7.8, б показано время прогона алгоритмов DPLL и WalkSAT на участке вокруг этой критической точки, где наше внимание ограничивалось только выпол-
Так где же найти сложные задачи? Можно предположить, что если количество выражений будет увеличено, притом что количество символов останется постоянным, то задача станет более ограниченной и поиск решений окажется более затруднительным. Допустим, что т — количество выражений, а п — количество символов. На рис. 7.8, а показана вероятность того, что случайно сформированное высказывание в форме 3-CNF является выполнимым, как функция от отношения "выражение/символ", т/п, при постоянном значении п, равном 50. Как и следовало ожидать, при малых значениях т/п эта вероятность близка к 1, а при больших значениях т/п вероятность близка к 0. На кривой вероятности начинается довольно резкий спад приблизительно после достижения значения ш/л=4 . 3. Высказывания в форме CNF, приближающиеся к этой критической точке, можно назвать "почти выполнимыми'1, или "почти невыполнимыми1'. Можно ли считать, что именно здесь находятся трудные задачи?
Изучение приведенных результатов позволяет сделать три вывода: во-первых, задачи, приближающиеся к критической точке, являются гораздо более трудными по сравнению с другими случайно сформированными задачами; во-вторых, даже при решении самых сложных задач алгоритм DPLL является весьма эффективным — он требует выполнения в среднем нескольких тысяч шагов по сравнению со значением количества шагов 250=1015, которое требуется для перебора истинностной таблицы; в-третьих, во всем этом диапазоне характеристик задач алгоритм WalkSAT работает намного быстрее, чем алгоритм DPLL.
Безусловно, эти результаты относятся только к случайно сформированным задачам. Реальные задачи не обязательно имеют такую же структуру, как случайно сформированные задачи (они могут характеризоваться разными значениями относительного количества положительных и отрицательных литералов, разными плотностями соединений между выражениями и т.д.). Тем не менее на практике алгоритм WalkSAT и подобные ему алгоритмы очень хорошо справляются также с решением реальных задач и часто не уступают самым лучшим алгоритмам специального назначения для этих задач. Такие решатели задач, как Chaff, легко справляются с задачами, состоящими из тысяч символов и миллионов выражений. На основании этих наблюдений можно сделать вывод, что некоторые комбинации эвристики с минимальными конфликтами и поведения со случайным блужданием предоставляют универсальную способность находить решения в большинстве ситуаций, в которых требуется комбинаторное формирование рассуждений.