가족 관계 프롤로그 거리

Question

나는 다음과 같은 조건을 가지고 말할 수 있습니다. 예를 들어 부모 사이의 거리는 2이고 형제 (형제) 간의 거리는 1입니다. 나는 다음을 시도했다 (그러나 그것은 작동하지 않았다) : 일반적으로

parent(X,Y) :- 
    father(X,Y); 
    mother(X,Y). 

sibling(X,Y):- 
    parent(Z,X), !, parent(Z,Y), 
    not(X=Y). 

not_in_list(_,[]). 
not_in_list(X,[Y|L]):- 
    not(X=Y), 
    not_in_list(X,L). 

edge(X,Y):- 
    (parent(X,Y); 
    parent(Y,X); 
    sibling(X,Y)). 

list_length(0,[]). 
list_length(N,[_|Ys]):- 
    list_length(N1,Ys), 
    N is N1+1. 

travel_graph(X,X,_). 
travel_graph(From,To,[From|Path]):- 
    edge(From,Next), 
    not_in_list(Next,Path), 
    travel_graph(Next,To,Path). 

degree(X,Y,N):- 
    travel_graph(X,Y,L), 
    list_length(N,L). 

Answer 1

당신이 가장 짧은 경로를 할 때 당신은 폭 우선 검색을 할 수 있습니다. 여기에 몇 가지 토론이 있습니다 : Breadth-First in Prolog

프롤로그는 먼저 깊이를 찾기 위해 노력할 것이므로 추론의 특정 라인이 얼마나 걸릴 수 있는지 보려합니다. 최단 경로를 원한다면 Prolog는 모든 첫 번째 옵션을 시도한 다음 솔루션에서 찾을 때까지 각각의 옵션을 바깥쪽으로 반복합니다. 이렇게하면 가장 먼저 찾을 수있는 첫 번째 솔루션이됩니다. 무한한 솔루션 (예 : 단계를 백업하고 되돌릴 수있는 미로 걷기)이있는 경우 이동하는 유일한 방법입니다.

너비 넓이 우선 검색을하기 위해 뒤집을 수있는 마법 스위치가 없으므로 구현해야합니다. O'Keefe는 정상적인 프롤로그 검색을 아직 시도하지 않은 것들의 "열린 세트"를 사용하여 명시적인 깊이 우선 검색으로 변환하는 방법을 먼저 설명하고 The Craft of Prolog에서 이것을 매우 명쾌하게 설명합니다. 열린 우선 순위를 나타내는 목록의 순서를 변경하여 폭 우선 동작을 대신 수행하는 방법.