Главная arrow Знания и рассуждения arrow Определение выполнимости
Как начинался компьютер
Компьютерная революция
Двоичный код
Разработки военных лет
Интегральные микросхемы
Микрокомпьютер
Персоны
Сеть
Язык компьютера
Развитие ПО
Гибкие системы
Средства разработки
Информатика
Вычислительная наука
Операционные системы
Искусственный интеллект
Предыстория
Поиск
Знания и рассуждения
Логика
Робототехника
 

 
Определение выполнимости Печать

Теперь рассмотрим, какие показатели производительности демонстрируют алгоритмы DPLL и WalkSAT на практике. Нас особенно интересуют трудные задачи, поскольку легкие могут быть решены с помощью любого старого алгоритма. В предыдущем разделе мы ознакомились с некоторыми удивительными открытиями в области решения задач определенного типа.

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

Если речь идет о решении задач проверки выполнимости, представленных в конъюнктивной нормальной форме, то среди них недостаточно ограниченными можно считать такие задачи, которые содержат относительно немного выражений, ограничивающих значения переменных. Например, ниже представлено выработанное случайным образом высказывание в форме 3-CNF с пятью символами и пятью выражениями.

(¬D v ¬B v C) ^ (B v ¬A v ¬C) ^ (¬C v ¬B v E) ^ (E v ¬D v B) ^ (B v E v ¬C)

Моделями этого высказывания являются 16 из 32 возможных вариантов присваивания, поэтому в среднем для поиска модели потребуются только две случайно выбранных гипотезы.

Так где же найти сложные задачи? Можно предположить, что если количество выражений будет увеличено, притом что количество символов останется постоянным, то задача станет более ограниченной и поиск решений окажется более затруднительным.

На рисунке показана вероятность того, что случайно сформированное высказывание в форме 3-CNF является выполнимым, как функция от отношения "выражение/символ", m/n, при постоянном значении n, равном 50. Как и следовало ожидать, при малых значениях m/n эта вероятность близка к 1, а при больших значениях m/n вероятность близка к 0. На кривой вероятности начинается довольно резкий спад приблизительно после достижения значения m/n=4.3. Высказывания в форме CNF, приближающиеся к этой критической точке, можно назвать "почти выполнимыми, или "почти невыполнимыми. Можно ли считать, что именно здесь находятся трудные задачи?

Image

 

 

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

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

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

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