Ограничение достижимости в SWI/CLP(FD)

Question

Я пытаюсь определить форму ориентированного графа, решив ограничения на наличие узлов и дуг, например, двоичную переменную. V1V2 является 1 если есть дуга из узла V1 к V2.Я хотел бы выразить ограничение достижимости (или, альтернативно, найти транзитивное замыкание), например, потребовать, чтобы граф был связным или чтобы существовал путь от одного заданного узла к другому заданному узлу.

Я видел, что SICStus Prolog имеет fd_closure для этой цели, но в SWI Prolog мне не удалось найти ничего подобного.Должен ли я использовать ЧР?Я просматривал примеры согласованности дуг/путей, но не уверен, что ищу в правильном направлении.

Answer 1

SICStus' fd_closure/2 очень похож на SWI-Prolog term_attvars/2.Он предоставляет вам все переменные, к которым можно транзитивно получить доступ через атрибуты (а CLP (FD) SWI использует атрибуты для хранения ограничений).

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

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

Если вам нужны более сильные свойства, вам, вероятно, понадобятся более сильные свойства. ограничения.Например, circuit/1 доступен в SICStus и SWI и описывает гамильтонову схему.Для других свойств вы можете реализовать специальные алгоритмы фильтрации.

Answer 2

С copy_term/3 и term_variables/2 вы должны быть в состоянии получить (редактировать:почти) тот же эффект, что и fd_closure/2.

Обратите внимание, что fd_closure в SICStus работает только для FD-ограничений.Другие связи между переменными не учитываются.

Редактировать:Таким образом вы получите только копии внутренних переменных — этого должно быть достаточно для определения формы.Однако вы, возможно, захотите обратиться к этим переменным позже, и в этом случае это решение @mat.