나는 Prolog와 함께 a logic puzzle을 풀기 위해 노력하고있다. 나는 GNU Prolog 유한 도메인 해석기를 사용하여 문제를 올바르게 매핑했다고 생각한다.Prolog가 일치하면 성공하지만 출력을 레이블링하라는 메시지가 나타나면 실패합니다.
해결 함수를 실행할 때 Prolog는 예와 변수 목록을 모두 0..1 범위로 제한합니다 (부울 값은 너무 제한되어 있음). 문제는 fd_labeling (Solution) 절을 추가하려고 할 때 얼굴에 대한 프롤로그와 침을 뱉어내는 것입니다.
내가이 언어에 새로운 해요 모든 것이 실제로 답을 레이블을 요청할 때까지 작동하는 것 같다 왜 알아 내기 위해 공격의 과정을 찾을 수 없습니다 ...
분명히, 당신을 변수에 레이블을 붙이려고 할 때 "no"를 얻으므로 FD에 문제를 "올바르게"매핑하지 않았습니다.
제약 논리 프로그래밍에서는 도메인이있는 변수 (도메인 [0,1]의 부울 값)와 이러한 변수 사이에 여러 제약 조건이있는 제약 조건 모델을 설정합니다. 각 제한 조건에는 제한 조건이 게시되는 변수의 도메인에 대해 일관성을 유지하려고하는 전파 규칙이 있습니다. 일관성이없는 값은 도메인에서 제거됩니다. 일관성에는 몇 가지 유형이 있지만 공통점이 있습니다. 제약 조건은 일반적으로 전체 솔루션을 제공하지 않으며 제약 조건 솔루션이 있는지 여부를 알려주지 않습니다.
예를 들어 두 변수 X와 Y (도메인 [1..10] 및 제약 조건 X < Y)가 있다고 가정하면 전파 규칙은 Y의 도메인에서 값 1을 제거하고 제거합니다 10 도메인의 X에서. 그때 그것은 도메인이 이제 일관성이 있기 때문에 중지됩니다 : 한 도메인의 각 값에 대한 다른 도메인에 값이 존재하므로 제약 조건이 충족됩니다.
모든 변수가 값에 바인딩되는 솔루션을 얻으려면 변수에 레이블을 지정해야합니다. 각 레이블링은 레이블이 지정된 변수에 첨부 된 제한 조건을 깨우고 또 다른 전파 단계를 트리거합니다. 이것은 솔루션 (모든 변수는 값에 응답, 대답 : 예) 또는 실패 (검색 트리의 각 분기에서 일부 변수는 빈 도메인으로 끝남, 대답 : 아니오)로 이어집니다.
각 제약 조건은 그것이 게시 된 변수의 영역의 일관성을 목표로 제약 조건의 조합으로 인해 발생하는 불가 능성이 전파 단계에서 감지되지 않을 수도 있습니다. 예를 들어 도메인 [1. 2]이있는 세 개의 변수 X, Y, Z 및 쌍 단위의 부등식 제약 조건. 이것은 귀하의 제약 조건 모델에서 발생한 것 같습니다.
퍼즐에 대한 해결책이 있어야한다고 확신하면 제약 조건 모델에 일부 실행 불가능 성이 있습니다. 어쩌면 구속 조건을 예리하게 들여다 보아도 충분할 것입니다.
명백한 실행 불가능 성 (예 : 위의 불평등 예제와 같은 모순되는 제약 조건)이없는 경우 프로그램을 디버깅해야합니다. 가능한 경우 내장 레이블 지정 술어를 사용하지 말고 직접 작성하십시오. 그런 다음 어떤 변수가 인스턴스화되었는지 그리고 이것이 발생시킨 부울 결정 변수가 어떤 변화를 일으켰는지 추적 할 수있는 출력 술어를 추가 할 수 있습니다.
당신이 당신이 돌아갈 것은 대답이다 프롤로그에 쿼리를 입력하면
을 (@twinterer 이미 설명을했다, 내 대답은 다른 각도에서 그것을 가지고하려고합니다).답변에 솔루션이 포함되어있는 경우가 많으며 때로는 여러 솔루션이 포함되어 있으며 때로는 솔루션이 전혀 포함되지 않는 경우가 있습니다. 종종이 두 개념은 혼란 스럽다. 의는 GNU 프롤로그와 예를 살펴 보자 : 여기
| ?- length(Vs,3), fd_domain_bool(Vs).
Vs = [_#0(0..1),_#19(0..1),_#38(0..1)]
yes
을, 우리는 8 개 솔루션을 포함하는 대답이있다. 즉,
| ?- length(Vs,3), fd_domain_bool(Vs), fd_labeling(Vs).
Vs = [0,0,0] ? ;
Vs = [0,0,1] ? ;
...
Vs = [1,1,1]
yes
이제 다른 쿼리입니다. 이것이 인용 된 @twinterer의 예입니다.
| ?- length(Vs,3), fd_domain_bool(Vs), fd_all_different(Vs).
Vs = [_#0(0..1),_#19(0..1),_#38(0..1)]
yes
답변은 이전과 같습니다. 그러나 더 이상 해결책이 없습니다.
| ?- length(Vs,3), fd_domain_bool(Vs), fd_all_different(Vs), fd_labeling(Vs).
no
조금 덜 신비하게 만드는 또 다른 방법은 관련된 실제 제약 조건을 표시하는 것입니다. SWI이 작업을 수행합니다 :
이?- length(Vs,3), Vs ins 0..1, all_different(Vs).
Vs = [_G565,_G568,_G571],
_G565 in 0..1,
all_different([_G565,_G568,_G571]),
_G568 in 0..1,
_G571 in 0..1.
?- length(Vs,3), Vs ins 0..1, all_different(Vs), labeling([], Vs).
false.
그래서 SWI는 당신에게 구체적인 솔루션을 얻을 만족하는 모든 제약 조건을 보여줍니다. SWI의 답을 다음과 같이 읽으십시오 : 예, 해결책이 있습니다. 아아, 작은 글씨는 거짓입니다.
이 문제를 해결하는 또 다른 방법은보다 일관성있는 all_different/1 구현을 얻는 것입니다. 그러나 이것은 특정 경우에만 작동합니다.
?- length(Vs,3), Vs ins 0..1, all_distinct(Vs).
false.
는 일반적인 경우에 당신은 시스템이 글로벌 일관성을 유지하기 위해 기대할 수 없다. 이유 :
일관성 유지는 매우 비쌉니다. 그러한 결정을 라벨링에 위임하는 것이 종종 더 좋습니다. 사실 단순한 all_different/1은 종종 all_distinct/1보다 빠릅니다.
더 나은 일관성 알고리즘은 종종 매우 복잡합니다.
일반적으로 글로벌 일관성을 유지하는 것은 결정할 수없는 문제입니다.
감사합니다. 훌륭한 설명입니다. – CptOatmeal