지시 된 그래프의 잎 노드 -Prolog

Question

프롤로그에서 잎 노드 목록을 얻는 방법을 아는 사람이 있습니까?

이 지시 된 가장자리에 의해 설명 된 간단한 지시 그래프가 있습니다.

de(0,1).
de(0,2).
de(2,3).
de(2,4).
de(3,4).
de(4,5).

이제 그래프를 재귀 적으로 탐색하고 2 개의 잎 노드 (노드 1 & 5)의 목록을 작성하는 방법은 무엇입니까?

답변 주셔서 감사합니다!

편집하다:

글쎄, 나는 첫 번째 술어 서면 및 작업이 있습니다.

isLeaf(Node) :-
not(de(Node,_)).

그러나 지금, 나는 그래프를 가로 지르고 잎 노드의 출력 목록을 작성하는 방법을 모른다. 나는 매우 쉽지만 이런 생각과 프로그래밍 방식에 대한 경험이 없습니다.

Answer 1

술어를 정의해야합니다 is_leaf/1 그것은 발전기, 즉 입력 변수를 가능한 솔루션으로 인스턴스화합니다.

이 같은:

% Directed graph
de(0,1).
de(0,2).
de(2,3).
de(2,4).
de(3,4).
de(4,5).

% If Node is ground,
%         then test if it is a child node that is not a parent node.
% If Node is not ground,
%         then bind it to a child node that is not a parent node.
is_leaf(Node) :-
    de(_, Node),
    \+ de(Node, _).

사용 예제 :

?- is_leaf(Node).
Node = 1 ;
Node = 5.

?- is_leaf(Node), writeln(Node), fail ; true.
1
5
true.

?- findall(Node, is_leaf(Node), Leaf_Nodes).
Leaf_Nodes = [1, 5].

솔루션이 즉시 전화를합니다 not. (BTW, SWI-PROLOG는 사용하는 것이 좋습니다 \+ 대신에 not.)

isLeaf(Node) :-
    not(de(Node,_)).

이것은 당신을 의미합니다 isLeaf/2 아닙니다 발전기: 그것은 실패하거나 성공하며 (한 번) 입력 인수가 변수 인 경우 결코 바인딩하지 않습니다. 또한 입력이 리프라는 것을 테스트하지는 않지만 부모 노드가 아닌 경우 테스트합니다.

% Is it false that 1 is a parent? YES
?- isLeaf(1).
true.

% Is it false that blah is a parent? YES
?- isLeaf(blah).
true.

% Is it false that 2 is a parent? NO
?- isLeaf(2).
false.

% Basically just tests if the predicate de/2 is in the knowledge base,
% in this sense quite useless.
?- isLeaf(Node).
false.

Answer 2

당신이 그 반대의 일을 생각하십시오. 즉, 노드가 분기인지 알 수있는 술어를 공식화하십시오.

그로부터 현재 노드가 리프 인 경우 그래프, 인쇄 및 역 추적을 가로 지르는 술어를 쓸 수 있어야합니다.