Получите случайное удовлетворительное решение (или несколько решений) при запуске runSMT.

При запуске следующего кода:

answer = do

    -- elts is a list of the values we're trying to satisfy for
    x <- doSomething

    {- ... constraints and other stuff ... -}

    query $ do cs <- checkSat
               case cs of
                    Sat    -> getValue x
                    Unsat  -> error "Solver couldn't find a satisfiable solution"
                    DSat{} -> error "Unexpected dsat result!"
                    Unk    -> error "Solver returned unknown!"

runSMT answer
-- output: one single satisfying solution

SBV/Z3 возвращает уникальное удовлетворительное решение. Как вместо этого получить список всех (возможно, до n) удовлетворяющих решений? Я знаю о sat по сравнению с allSat при запуске примеров hello-world, но я не уверен, как подключить его к более сложному контексту выше. Я также читал о extractModels (обратите внимание на множественное число), но документации по этому вопросу не так много.

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


person Jivan    schedule 27.10.2020    source источник


Ответы (1)


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

Кстати, именно так allSat работает внутри. В режиме запроса вы должны кодировать эту логику самостоятельно. Документация по взлому поставляется с примером: https://hackage.haskell.org/package/sbv-8.8/docs/src/Documentation.SBV.Examples.Queries.AllSat.html#demo

person alias    schedule 27.10.2020
comment
Когда вы говорите adding an assertion that rejects the previous value, когда значение представляет собой список значений (как в примере из моего другого вопроса, на который вы ответили сегодня), есть ли способ сохранить предыдущее значение как общий результат, или нам нужно вручную добавить ограничение для каждого элемента списка при использовании checkSatAssuming? - person Jivan; 27.10.2020
comment
Вам не нужно (и не следует использовать) checkSatAssuming. Это относится к примеру в документации и здесь не применяется. Вместо этого вам нужно написать, что значит быть другим в данном случае. То есть либо разная длина, либо отличается одним из значений. Это потребует некоторого кодирования, но у вас есть вся необходимая информация из извлеченного значения. Обратите внимание, что SBV позволяет извлекать все виды моделей; например, вы можете запрограммировать получение только списков разной длины или только одной длины, но разных значений; все зависит от того, какие модели вас интересуют. - person alias; 28.10.2020
comment
Я понимаю. А с помощью you need to write what it means to be a "different" in this case можно указать дополнительные constrain $ ... в цикле, верно? или есть другой способ? - person Jivan; 28.10.2020
comment
Правильный; вы просто добавляете новые ограничения по мере прохождения цикла; которые в совокупности ставят вне закона все предыдущие модели. - person alias; 28.10.2020
comment
Понятно. Интересно, что каждая итерация выводит новое (другое) решение, даже если я закомментировал дополнительное ограничение в цикле. Не уверен, почему. - person Jivan; 28.10.2020
comment
Вы вызывали checkSat каждый раз в цикле? - person alias; 28.10.2020
comment
Вы уверены, что результаты отличаются? Этот цикл просто вызовет check-sat без добавления каких-либо новых ограничений, и решатель обязательно вернет ту же модель. Вы можете увидеть, что происходит, запустив runSMTWith z3{verbose=True}, и посмотреть, не происходит ли что-нибудь интересное между двумя последовательными вызовами check-sat. Если ограничений не введено, маловероятно, что z3 предоставит вам новую модель. - person alias; 28.10.2020
comment
по сути, я просто был глуп - моя функция сравнения между двумя списками SState не работала должным образом - person Jivan; 28.10.2020