Мне кажется, что ответ должен быть
Z in 1..99
Как вы можете быть настолько уверены, что вы правы? Это одно из приятных свойств ограничений: в этом легко убедиться:
?- X in 1..7, Y in -3..100, Y #> X, Z #\= 0, Z #= Y -X.
X in 1..7,
Z+X#=Y,
X#=<Y+ -1,
Z in -5.. -1\/1..99,
Y in 2..100.
?- X in 1..7, Y in -3..100, Y #> X, Z #\= 0, Z #= Y -X, Z #< 0.
false.
Хорошо, теперь я верю тому, что ты сказал.
Итак, вы обнаружили здесь непоследовательность, которая присутствует также в родном library(clpfd) SICStus, а также в library(clpz). Во-первых, обратите внимание, что данный ответ не был неправильным! Он сказал: Да, есть решения, если X in 1..7, Z+X#=Y, X#=<Y+ -1, Z in -5.. -1\/1..99, Y in 2..100. верно. Хелас, это неправда.
Так что этот ответ немного похож на юридический язык во многих страховых договорах, где говорится, что да, мы заплатим, при условии, что весь этот крошечный нечитаемый шрифт сохранится, но на самом деле вы можете заменить эту стену микротекста большим жирным false.
В общем, такие несоответствия неизбежны, поскольку CLP(FD)/CLP(Z) в том виде, в каком они определены в приведенных выше системах, позволяют формулировать неразрешимые проблемы. Таким образом, независимо от того, насколько развит ваш решатель ограничений, у нас есть гарантия, что всегда будут случаи, которые мы не сможем решить. Это научный, математический закон, гораздо более надежный, чем эмпирические законы, такие как гравитация или ограничение скорости.
Несоответствие здесь фактически является инженерным компромиссом. Пока никто не жалуется и не будет убедительного варианта использования, разработчики таких систем не увидят смысла улучшаться. В конце концов, такое улучшение может замедлить существующие варианты использования.
- Как именно (или приблизительно) CLP распространяет свои ограничения?
На самом деле, для любой проблемы реалистичного размера никто не знает. Но и это не обязательно. В случае CLP(FD) фундаментальным элементом являются домены, связанные с логическими переменными. Вы видите их как (in)/2 целей, таких как Z in -5.. -1\/1..99. Между ними связаны фактические ограничения. В вашем случае Y #> X и Z #= Y-X. Эти ограничения теперь видят только домены переменных и пытаются поддерживать согласованность между ними. В еще более грубом приближении домены видны как интервалы, таким образом, Z in -5 .. 99 вместо приведенного выше. Чего (большинство из них) не видят, так это других ограничений. В этом случае прямой связи между Y #> X и Z #= Y-X нет. Отсюда и нестыковка. Такие ограниченные проверки непротиворечивости гораздо проще реализовать, они довольно быстрые и часто превосходят более полные алгоритмы. С открытием лучших алгоритмов все меняется. Хорошим примером является all_distinct/1, который поддерживает согласованность между всеми переменными с помощью алгоритма Регина, тогда как all_different/1 поддерживает согласованность только между каждой парой переменных. Но в любом случае: эти вещи развиваются, и немного удивительно, что это экзаменационный вопрос.
- Есть ли способ заставить CLP(FD) правильно применять ограничение...?
?- X in 1..7, Y in -3..100, Y #> X, Z #\= 0, Z #= Y -X, clpfd:contracting([X,Y,Z]).
X in 1..7,
Z+X#=Y,
X#=<Y+ -1,
Z in 1..99,
Y in 2..100.
Но большинство проигнорируют эту проблему и просто добавят labeling([],[X,Y])
- Что такое домен
Z?
Это неоднозначный вопрос. Дайте оба в качестве ответа.
person
false
schedule
09.01.2020
