프롤로그에서 간단한 그래프 검색

Question

SWI-Prolog에서 간단한 그래프 검색을 코딩하려고합니다. 나는 다음 프로그램을 생각해 냈다.

adjacent(1,4). adjacent(4,2). adjacent(3,6). 
adjacent(6,4). adjacent(7,10). adjacent(4,9). 
adjacent(5,10). adjacent(7,10). adjacent(7,12). 
adjacent(6, 11). adjacent(13,11). adjacent(9,14). 
adjacent(14,12). adjacent(10,15). adjacent(9,12). 

connected(X,Y) :- adjacent(X,Y); adjacent(Y,X). 

path(A,B,[A|B]) :- 
    connected(A,B). 
path(A,B,[A|R]) :- 
    \+member(R,A), 
    connected(A,C), 
    A \== C, 
    path(C,B,R). 

그러나이 프로그램은 스택 오버플로를 일으킨다. 내가 뭘 잘못하고 어떻게 고칠 수 있니?

Answer 1

반환 된 경로를 루프 방지를위한 검사로 사용하려고합니다. 경로가 아직 부정으로 인스턴스화되지 않았기 때문에 경로를 검색 할 때 작동하지 않습니다.

가장 간단한 해결책은 이미 방문한 노드를 수집하고 반복을 피하기 위해이를 확인하는 또 다른 입력 인수를 추가하는 것입니다.

또한 A \ == C 대신 A를 확인해야한다고 생각합니다. 노드에는 루프가 없으므로 후자는 절대 발생하지 않습니다. case A == B는 첫 번째 절에서 처리되므로 두 번째 절에서 다시 수행하지 않으려 고합니다.

마틴 (Martin)이 작성한 것처럼 멤버의 주장을 거꾸로하고 첫 번째 절에서 목록을 수정해야합니다.

추가 인수없이 무한 루프를 피하는 고급 방법은 부정에 동결/2를 사용하는 것입니다.

또한 Prolog에서 디버깅이 어떻게 작동하는지 살펴보고 더 잘 이해하는 데 도움이 될 수 있습니다.

Answer 2

주요 문제는 회원 테스트입니다. 서명은 member(Element,List)입니다. 당신은 논쟁이 다른 방향이라고 생각하는 것 같습니다.

또한 첫 번째 경로 조건자는 두 요소 목록을 테스트하기위한 것이지만 B는 실제로 나머지 목록과 통합됩니다 (연결되지 않은 경우).

이 값을 수정하면 언 바운드 변수에 부정이 잘 적용되지 않으므로 완전히 인스턴스화 된 변수에서만이 값을 사용할 수 있습니다.