Что делает аннотация поиска влияния в MiniZinc?

Чтобы понять выбор переменной на основе impact, вы должны понять first_fail. В программировании с ограничениями мы обычно хотим сначала решить самую сложную подзадачу, быстро терпя неудачу, если решение не может быть найдено. Проблема с first_fail заключается в том, что он не принимает во внимание количество ограничений, в которых участвует переменная, больше будет означать, что решение для переменной «жестче», или влияние, которое выбор на переменную оказал на другие части. дерева поиска.

Кстати, dom_w_deg можно рассматривать как компромисс между first_fail и impact, при котором ограничения учитываются, а предыдущее решение - нет.

Предполагается, что выбор переменной impact является улучшением по сравнению с first_fail, где учитываются не только размеры домена, но также ограничения, в которые он вовлечен, и то, какое «влияние» оказали исторические выборы. Переменной с наибольшим влиянием, как ожидается, будет труднее всего присвоить правильное значение с учетом всей этой информации.

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

Для получения идей о возможных реализациях эвристики, основанной на воздействии, я бы посоветовал прочитать статью «Об эффективности эвристики, основанной на воздействии» Марко Коррейи и Педро Бараоны. Вы также можете проверить свой конкретный решатель MiniZinc/FlatZinc на предмет реализации эвристики.