Влияние порядка ввода на производительность решателя ограничений - PullRequest
0 голосов
/ 27 мая 2020

Упорядочивает ли ввод (логические и арифметические c уравнения) решатели ограничений, такие как Gecode и SMT, такие как Microsoft Z3 ?? Если да, то какой из этих двух будет работать лучше при условии, что я могу воспользоваться некоторыми заранее известными эвристиками с помощью функции ветвления в Gecode?

(Примечание: я не знаю, существует ли функция, аналогичная branch () в Gecode, в Z3)

1 Ответ

1 голос
/ 27 мая 2020

Теоретически нет; порядок не имеет значения. Порядок утверждений не должен иметь значения. Но на практике они могут иметь влияние, поскольку эвристика может в конечном итоге тратить много времени в тупик. Решатели SMT обычно работают как черные ящики, т. Е. Трудно увидеть, как они продвигаются, если вы не знаете их точное внутреннее устройство. Однако вы можете увеличить подробность (используйте флаг z3 -v) и можете посмотреть на вывод, чтобы увидеть, не обнаружите ли вы какое-либо расхождение в поведении.

Как и в случае с любым общим вопросом «производительность решателя SMT», это невозможно ответить абстрактно. Каждый экземпляр проблемы имеет определенные характеристики c, и могут быть разные способы его кодирования, чтобы упростить его решателю. Если вы опубликуете конкретные c проблемы, вы сможете получить лучшие предложения.

...