프롤로그의 길 찾기

Question

나는 프롤로그를 가르치려고하고있다. 아래, 나는 무차별 그래프에서 노드 사이의 모든 경로를 반환해야한다고 생각하는 코드를 작성했습니다 ... 그러나 그렇지 않습니다. 왜이이 특정 코드가 작동하지 않는지 이해하려고합니다. (이 질문은 비슷한 프롤로그 길 찾기 게시물과 구분됩니다). 나는 이것을 SWI-Prolog에서 운영하고있다. 모든 단서?

% Define a directed graph (nodes may or may not be "room"s; edges are encoded by "leads_to" predicates). 
room(kitchen). 
room(living_room). 
room(den). 
room(stairs). 
room(hall). 
room(bathroom). 
room(bedroom1). 
room(bedroom2). 
room(bedroom3). 
room(studio). 
leads_to(kitchen, living_room). 
leads_to(living_room, stairs). 
leads_to(living_room, den). 
leads_to(stairs, hall). 
leads_to(hall, bedroom1). 
leads_to(hall, bedroom2). 
leads_to(hall, bedroom3). 
leads_to(hall, studio). 
leads_to(living_room, outside). % Note "outside" is the only node that is not a "room" 
leads_to(kitchen, outside). 

% Define the indirection of the graph. This is what we'll work with. 
neighbor(A,B) :- leads_to(A, B). 
neighbor(A,B) :- leads_to(B, A). 

IFF의 A -> B -> C -> D가

path(A, D, [B, C]) 

참이어야 후, 루프 - 프리 경로이다. 즉, 세 번째 인수는 중간 노드를 포함합니다. 그러나

% Base Rule (R0) 
path(X,Y,[]) :- neighbor(X,Y). 

% Inductive Rule (R1) 
path(X,Y,[Z|P]) :- not(X == Y), neighbor(X,Z), not(member(Z, P)), path(Z,Y,P). 

,

?- path(bedroom1, stairs, P). 

은 false입니다. 왜? 우리는

?- neighbor(bedroom1, hall). 
true. 

?- not(member(hall, [])). 
true. 

?- path(hall, stairs, []). 
true . 

이후

X = bedroom1 
Y = stairs 
Z = hall 
P = [] 

과 R1에 일치하지할까요? 사실

, 내가

?- path(A, B, P). 

을 평가하는 경우가 난 단지 길이-1 솔루션을 얻을.

Answer 1

Prolog에 오신 것을 환영합니다! 문제는 본질적으로 R1에서 not(member(Z, P))에 도달 할 때 P은 평가를 아직 정의하지 않았기 때문에 path(Z, Y, P)이 아니기 때문에 여전히 순수 변수라는 점입니다. 프롤로그에 대한 놀라운 아직 영감을주는 것들 중 하나는 member(Ground, Var)가 Ground를 포함하고 Var으로 그들을 통합 목록을 생성하는 것입니다 :

?- member(a, X). 
X = [a|_G890] ; 
X = [_G889, a|_G893] ; 
X = [_G889, _G892, a|_G896] . 

이가는 uninstantiated 목록에서 값을 확인 항상 성공하는 혼란 부작용이있다 이는 not(member(Z, P))이 항상 실패하여 R1이 항상 실패하게 만듭니다. 모든 R0 솔루션과 R1 솔루션을 얻지 못한다는 사실은 R1의 무언가가 항상 실패하는 원인이라는 단서입니다. 결국 R0가 작동한다는 것을 알게됩니다.

이 두 가지 목표를 교환 할 경우, 당신은 당신이 원하는 첫 번째 결과 얻을 것이다 :

다른 솔루션을 요구하는 경우에

path(X,Y,[Z|P]) :- not(X == Y), neighbor(X,Z), path(Z,Y,P), not(member(Z, P)). 

?- path(bedroom1, stairs, P). 
P = [hall] 

, 당신은 스택 오버 플로우를 얻을 수 있습니다합니다. 변경 후 가능한 한 빨리 사이클을 사용하여 path(Z,Y,P)을 사용하여 행복하게 솔루션을 생성하고 이후에만 not(member(Z, P))으로 폐기해야하기 때문입니다. (덧붙여 말하자면 약간의 효율성을 얻으려면 대신에 memberchk/2으로 전환 할 수 있습니다. 물론 잘못된 것을 빨리하는 것은별로 도움이되지 않습니다. :)

나는 이것을 폭 우선 검색으로 변환하려고합니다. Prolog에서는 아직 시도하지 않은 솔루션을 포함하는 "열린 세트"인수를 추가하고 각 노드에서 먼저 열린 세트에서 무언가를 시도한 다음 해당 노드의 가능성을 열린 세트의 끝에 추가합니다. 오픈 세트가 꺼질 때, 당신은 당신이 도달 할 수있는 모든 노드를 시도했습니다. 어쨌든 깊이 찾는 첫 번째 검색보다 더 나은 솔루션입니다.시도 할 수있는 또 다른 방법은 방문한 컴포넌트와 미래의 컴포넌트로 경로를 분리하고 방문한 컴포넌트 만 확인하는 것입니다. 현재 단계에서 사이클을 생성하지 않는 한 전혀 생성하지 않아도되므로 향후 단계에 대해 걱정할 필요가 없습니다.

당신이 질문에 말한 방식은 당신에게 완전한 해결책, 힌트를 원하지 않는다고 믿게 만듭니다. 그래서 나는 이것이 당신이 필요로하는 전부라고 생각합니다. 그것이 옳지 않다면 알려주세요.