Определение выполнимости

Привет, мой друг, тебе интересно узнать все про определение выполнимости, тогда с вдохновением прочти до конца. Для того чтобы лучше понимать что такое определение выполнимости , настоятельно рекомендую прочитать все из категории Логика.

Теперь рассмотрим, какие показатели производительности демонстрируют алгоритмы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. Об этом говорит сайт https://intellect.icu . Как и следовало ожидать, при малых значениях m/n эта вероятность близка к 1, а при больших значениях m/n вероятность близка к 0. На кривой вероятности начинается довольно резкий спад приблизительно после достижения значения m/n=4.3. Высказывания в форме CNF, приближающиеся к этой критической точке, можно назвать "почти выполнимыми, или "почти невыполнимыми. Можно ли считать, что именно здесь находятся трудные задачи?

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

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

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

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

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