овеществленные и полувещественные предикаты

Question

Недавно я обратил внимание на то, что одна из последних версий FlatZincподдерживает полуварифицированные предикаты:

Половосстановленные предикаты по сути представляют собой ограничения, которые подразумеваются логической переменной, а не эквивалентны ей.

источник: документы

Вопрос:

• все ли глобальные предикаты имеют_reif версия сейчас?
• все ли глобальные предикаты имеют_imp версия тоже?

Глядя на содержание share/minizinc/ Я вижу это внутри std только nosets.mzn использует _imp предикаты, поэтому у меня сложилось впечатление, что поддержка _impпредикаты. Q: Это правильно?

Посмотрев документы, я обнаружил следующее:

Поэтому библиотеки решателей должны по возможности предоставлять обновленные версии ограничений. Библиотека содержит файлыfzn__reif.mzn для этого.

источник: документы

Если я правильно интерпретирую, то поддерживать _reif предикаты, потому что они уже переопределены в share/minizinc(хотя это может быть полезно для производительности). Q: Это правильно?

Answer 1

Чаще всего предикаты (звонки), R(...), используются как фактическое ограничение: constraint R(...). Вопрос при обработке выраженияR(...) теперь, если он может быть передан непосредственно решающей программе или если у него есть переопределение, которое необходимо оценить.

Если предикат используется в более сложном выражении B \/ R(...), то мы не можем просто позвонить решателю R(...) потому что мы не хотим применять R(...). Вместо этого мы хотим знать, есть ли отношения, описанныеR(...)держит. Это то, что мы называем овеществлением.

По этой причине должен быть R_reif(..., r) предикат, который заставляет r <-> R(...). По сути, это дает истинное значениеR(...). Опять же, когда компилятору дается выражениеR_reif(...,r), затем он проверит, можно ли передать его непосредственно решающей программе или доступно ли переопределение. Если оба из них недоступны, компилятор попытается сгенерировать переопределение из переопределенияR(...). Если и это не удается, компилятор останавливает компиляцию.

Если мы посмотрим на наш пример, B \/ R(...), то можно заметить, что использование r <-> R(...)больше, чем нужно. ЕслиR(...) ложно, тогда нам все еще нужно B быть true и если B является false мы все еще хотим заставить R(...); однако мы знаем, что ничто не заставитR(...) становиться false. Мы говоримR(...)находится в положительном контексте. В данном случае это означает, что имеяr -> R(...)достаточно. Это называется полувеществом.

В MiniZinc можно ввести R_imp(..., r)предикат для предоставления отдельного полувещественного предиката. Это опять же может быть что-то, что напрямую передается в решатель или переопределение. Если компилятор должен преобразовать выражениеR(...) и видит, что он находится в положительном контексте, тогда он сначала попытается увидеть, сможет ли он найти R_imp(..., r) и в противном случае вернуться к R_reif(..., r). Обратите внимание, что если сгенерировано переопределение, то контекст вызова распространяется внутрь, и при переопределении все еще могут возникать половинные реификации.

Подводя итоги и прямо отвечая на ваши вопросы:

• Все глобальные предикаты могут быть овеществлены. Новое определение_reif могут быть определены явно или могут быть сгенерированы путем генерации из их переопределения.
• Ни один из глобалов не является наполовину овеществленным. В этом нет необходимости, поскольку полувещества все еще могут запускаться при генерации переопределений реификаций, и в настоящее время нет известных случаев, когда явное полувещественное определение работает лучше.
• В настоящее время не существует полурефицированных предикатов, для которых требуется поддержка решателя. Однако обратите внимание, что любой_reif предикат, который может быть реализован как _imp решателем (включая встроенные функции FlatZinc).
• Не требуется поддержка каких-либо глобальных _reifпредикаты; однако требуется несколько_reifпредикаты во встроенных командах FlatZinc, которые действительно нуждаются в поддержке. Если эти предикаты не переопределяются или не реализуются решателем, решающая программа не может поддерживать сгенерированный FlatZinc.