SWI/CLP(FD)의 연결 가능성 제약

Question

노드와 호의 존재에 대한 제약 조건(예: 이진 변수)을 해결하여 유향 그래프의 모양을 결정하려고 합니다. V1V2 ~이다 1 노드로부터 호가 있는 경우 V1 에게 V2.예를 들어 그래프가 연결되어야 하거나 특정 노드에서 다른 노드로의 경로가 있어야 한다는 등의 도달 가능성 제약 조건을 표현하고 싶습니다(또는 전이적 폐쇄 찾기).

나는 SICStus Prolog가 fd_closure 이 목적을 위해 SWI Prolog에서 비슷한 것을 찾을 수 없었습니다.사용해야 할까요? CHR?호/경로 일관성 예제를 살펴봤지만 올바른 방향을 보고 있는지 잘 모르겠습니다.

Answer 1

SICStus' fd_closure/2 SWI-Prolog와 매우 유사합니다. term_attvars/2.이는 속성을 통해 전이적으로 도달할 수 있는 모든 변수를 제공합니다(그리고 SWI의 CLP(FD)는 속성을 사용하여 제약 조건을 저장합니다).

일반적으로 ~ 아니다 이러한 술어가 필요합니다.예를 들어 잔여 목표를 얻기 위해 최상위 수준에서 사용됩니다.

이러한 조건자를 사용하지 않고도 유한 도메인 제약 조건이 있는 그래프를 표현할 수 있습니다.예를 들어 유한 도메인 변수를 사용하십시오. B_i_j 1입니다 iff 노드에서 호가 있습니다 나 노드로 제이.

더 강한 속성이 필요하다면 더 강한 속성이 필요할 것입니다. 제약.예를 들어, circuit/1 SICStus 및 SWI에서 사용할 수 있으며 해밀턴 회로를 설명합니다.다른 속성의 경우 전용 필터링 알고리즘을 구현할 수 있습니다.

Answer 2

와 함께 copy_term/3 그리고 term_variables/2 당신은 얻을 수 있어야합니다 (편집 :거의)와 같은 효과 fd_closure/2.

점에 유의하시기 바랍니다 fd_closure SICStus에서는 FD 제약 조건에만 작동합니다.변수 간의 다른 연결은 고려되지 않습니다.

편집하다:이렇게 하면 내부 변수의 복사본만 얻을 수 있습니다. 이는 모양을 결정하는 데 충분할 것입니다.그러나 나중에 @mat의 솔루션이 해당 변수를 참조하고 싶을 수도 있습니다.