Prolog에서 간단한 그래프 검색

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 == B를 확인해야한다고 생각합니다. 노드에 루프가 없으므로 후자는 결코 일어나지 않을 것입니다. 사례 A == B는 첫 번째 조항에서 처리되므로 두 번째 조항에서 다시 수행하고 싶지 않습니다.

또한 회원의 주장을 거꾸로 얻었으며 Martin이 작성한 것처럼 첫 번째 조항에서 목록을 수정해야합니다.

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

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

Answer 2

여기서 주요 문제는 회원 테스트입니다. 서명은 member(Element,List); 당신은 논쟁이 다른 방법 '라운드라고 가정하는 것 같습니다.

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

이 문제를 해결하면 부정이 결합되지 않은 변수에 대해 잘 작동하지 않기 때문에 완전히 인스턴스화 된 변수에 대해서만 작동 할 수 있습니다.