Публикации по теме 'satisfiability'
Проблема булевой выполнимости подвергается подлому осуждению.
Проблема булевой выполнимости. Начальный план (со спамом в комментариях).
Здесь я предлагаю несколько совершенных приемов создания отличных инструментов для логических операций. Извинения: кто-то взломал статью, чтобы не поделиться этой технологией.
Проблема логической выполнимости (SAT) - это проблема определения, существует ли интерпретация, удовлетворяющая заданной булевой формуле. Учитывая, что логическая переменная - это переменная, которая может принимать только два..
SAT-кодирование: обход направленного графа в глубину
В этом посте я опишу, как закодировать задачу обхода (поиска) в глубину (DFT/DFS) ориентированного графа как задачу SAT. Он будет следовать тому же потоку, что и пост, описывающий как закодировать обход (поиск) в ширину (BFT/BFS) ориентированного графа как задачу SAT .
Проблема
Учитывая ориентированный граф и узел n в графе, обход в глубину графа посещает все еще не посещенные узлы, достижимые из дочернего узла узла, прежде чем посетить другой дочерний узел узла.
Начиная обход..
Кодирование SAT: Введение
Пока я копался в материале для преподавания курса по решению SAT, я хотел выделить свое понимание кодирования SAT - процесса преобразования проблемы в проблему SAT - в форме, доступной для читателей с базовыми знаниями логики высказываний. Кроме того, вместо простого теоретического изложения, я хотел предоставить исполняемые примеры того, как хорошо известные проблемы информатики могут быть механически закодированы как задачи SAT и решены с помощью стандартных решателей SAT.
В этом..
Вопросы по теме 'satisfiability'
Можно ли использовать программу SAT для поиска всех решений?
Я написал ответ на то, что, как мне казалось, было довольно интересный вопрос , но, к сожалению, вопрос был удален его автором до того, как я смог опубликовать. Я публикую здесь краткое изложение вопроса и свой ответ на тот случай, если он может...
4136 просмотров
schedule
12.04.2022
Проверить комбинаторные кодировки CNF SAT?
Я пытаюсь решить комбинаторную проблему с помощью SAT Solver .
Это включает в себя следующие шаги:
Закодируйте проблему как набор логических выражений.
Переведите сочетание выражений в CNF / DIMACS (используя собственные...
555 просмотров
schedule
06.05.2022
Разобрать строку с пропозициональной формулой в CNF в список вложенных целых чисел DIMACS в haskell
Я хотел бы проанализировать строку с пропозициональной формулой в CNF для DIMACS, таким образом, вложенный список int в haskell. Формат подходит для привязок haskell picosat, которые кажутся более производительными, чем другие варианты решения SAT....
672 просмотров
schedule
09.04.2022
экземпляры SAT в реальном мире
Я разрабатываю и внедряю решатель SAT. Было бы особенно хорошо, если бы все предложения имели вид
a AND b = c
a OR b = c
a XOR b = c
a = NOT b
В литературе они используют форму CNF, которая, я думаю, будет менее эффективным представлением...
711 просмотров
schedule
26.01.2023
Теорема Кука (на простом английском языке)
Я прочитал книгу Гэри и Джонсона Computers and Intractability — A Guide to the Theory of NP-Completeness для курса по алгоритмам; однако, просматривая материал год спустя, я понял, что никогда по-настоящему не понимал теорему Кука.
Что касается...
451 просмотров
schedule
06.11.2022
CNF против Horn Выполнимость
Я знаю, что легче доказать, что формула рога выполнима. Мой вопрос: почему с рупорной формулой проще, чем с обычным CNF?
677 просмотров
schedule
25.09.2022
Полиномиальный алгоритм для алгоритма, относящегося к 2-SAT
Я читал много алгоритмов для поиска проблемы 2-SAT, т.е. данное выражение выполнимо или нет, которое может быть решено за полиномиальное время. пример ( алгоритм ). Для процедура Крома ( Wikipedia ), я строю граф, из которого могу легко...
306 просмотров
schedule
22.04.2022
Можно ли уменьшить набор, независимый от K, до 2-SAT
Это вопрос домашнего задания для начала. Перед тем, как я начну, у меня есть несколько вопросов.
Наша проблема:
«Сократите k-независимое множество до 2-SAT следующим образом. Для графа G с n вершинами формируется n предложений, по одному на...
1218 просмотров
schedule
12.05.2022
Процедура алгоритма DPLL
Я пытаюсь понять процедуру DPLL, прежде чем ее кодировать.
Например, у меня есть такие пункты:
C1 : {c, !d, !b}
C2 : {d, a}
C3: {b, !d, !a}
C4: {d, c, b, a}
C5: {c, !d, !b}
C6: {d, c, b}
C7: {c}
Теперь я принимаю...
498 просмотров
schedule
21.03.2022
нахождение максимального числа чисел в z3 с использованием SMTLIB2
У меня есть 7 чашек, в которых есть немного воды. Мне нужно запрограммировать эти чашки на разное количество воды. Как только это будет сделано, мне нужно измерить чашку, в которой больше всего воды, а затем удалить некоторое количество (скажем, 2...
254 просмотров
schedule
13.12.2023
Несовместимая выполнимость между ctx-solver-simplify и ctx-simplify Z3
Я пытаюсь сделать z3 (я использую z3py), чтобы проверить, выполнима ли формула или нет, и если она выполнима, то упростить ее.
Сначала я использовал Z3 ctx-solver-simplify . Однако, поскольку я постоянно делаю много звонков, использование этой...
72 просмотров
schedule
05.02.2023
Это нормально, что решатель Z3 не может решить 2 ^ x = 4?
Я попытался решить 2 ^ x = 4 с помощью Z3, разместив на веб-сайте Z3 следующее: https://rise4fun.com/z3/tutorial .
(declare-const x Real)
(declare-const y Real)
(declare-const z Real)
(assert (=(^ 2 x) 4))
(check-sat)
(get-model)
Z3...
98 просмотров
schedule
13.03.2024