Пролог CLPFD Транзитивность - PullRequest
Новая
       18

Пролог CLPFD Транзитивность

2 голосов
/ 09 мая 2019

«Очевидное» - это не просто слово, которое часто обсуждают, но почему CLPFD SWI-Prolog правильно решает это: 

?- A+1 #= A*2.
A = 1.

, но не это: 

?- B #= A + 1, B #= A * 2.
A+1#=B,
A*2#=B.

(label и indomain yield Arguments are not sufficiently instantiated.)

Это просто ... решатель не уловил этот случай?(Я уверен, что ожидал, что это применимо к транзитивности.) Или это симптом какой-то более глубокой синтаксической головоломки или что-то в этом роде?

1 Ответ

3 голосов
/ 09 мая 2019

Он пытается решить ограничение из значений в домене каждой переменной!Поскольку область B и A бесконечна и не ограничена, откат по удовлетворению ограничения будет отложен, и программа остановлена.

Это означает, что он пытается найти какое-то решение для ограничения B #= A + 1, но находит много (бесконечные значения для A и B), а также то же самое для второго ограничения.Следовательно, он будет остановлен здесь, поскольку возможные значения A и B бесконечны.Тем не менее, результат не No.Это Yes с 2 задержанными целями.

B = B{-1.0Inf .. 1.0Inf}
A = A{-1.0Inf .. 1.0Inf}
There are 2 delayed goals.

Чтобы решить эту проблему, вам нужно связать хотя бы один из A или B.Например, если вы выполните этот запрос A::1..1000, B#=A+1, B #= A*2., вы получите тот же результат, что и для первого запроса в ваших примерах.Кроме того, в clpfd нет никаких вычетов для разрешения транзитивности, как это используется в методе обратного отслеживания.

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

...