Поиск листовых узлов в дереве is_a () в Прологе - PullRequest
Новая
       12

Поиск листовых узлов в дереве is_a () в Прологе

0 голосов
/ 29 октября 2018

Я сделал в основном "дерево" в "прологе", используя `is_a (X, Y) '.Что выглядит примерно так: 

is_tree('b', 'a').
is_tree('c', 'a').
is_tree('d', 'b').
is_tree('e', 'b').
is_tree('f', 'c').
is_tree('g', 'c').

       a
  b         c
d   e      f  g

А сейчас я пытаюсь найти все листовые узлы, которые были бы d, e, f, g.До сих пор мне удалось write()'ing из 1-го листа, но я не понимаю, как мне вернуться наверх по дереву, чтобы найти другие узлы, и как я должен написать свой closing clause, чтобы найти значения. 

find_leaf(X, Y):-
    \+is_tree(X, Y).
find_leaf(X, Y):-
    is_tree(A, Y), !,
    find_leaf(Y, A).
find_leaf(X, Y):-
    is_tree(A, X),
    write(Y),
    find_leaf(Y, A).

Как я могу вернуться "снова", чтобы найти другие листья?И что будет правильным «заключительным предложением»?

1 Ответ

0 голосов
/ 29 октября 2018

Большинство предикатов в Прологе не write/1 вещи.Как и в императивном и функциональном программировании, обычно большое количество функций вычисляет вещи, а другие затем "сообщают" вещи (записывая данные на консоль, изменяя пользовательский интерфейс и т. Д.

Поэтому я бы предложил построить предикат find_leaf(X), который объединяет переменную X с листом. Благодаря механизму обратного отслеживания Пролога, мы можем в итоге объединиться со всеми листьями.

Получение узлов из is_tree/2 Предикат

Здесь узлы - если вы не упомянули об этом - можно получить только путем анализа предиката is_tree/2, где первый элемент является «дочерним», а второй - «родительским».Здесь мы знаем, что что-то - это отпуск, если это узел, а не родительский элемент. Поскольку нет других механизмов для определения дерева, узел (вероятно) является дочерним в некотором предикате is_tree.

Мытаким образом, можно реализовать предикат, который находит дочерние элементы с: 

find_leave(X) :-
    is_tree(X, _),
    \+ is_tree(_, X).

Таким образом, первый вызов is_tree(X, _) объединит X с дочерним элементом в дереве, гдетак как второй вызов проверяет, что нет дочернего элемента для X.

Это затем дает: 

?- find_leave(X).
X = d ;
X = e ;
X = f ;
X = g.

Получить листья из данного корня

Мы также можем передатькорень через параметр, например: find_leave(b, X) объединит X со всеми дочерними элементами b.Здесь мы делаем два случая:

  1. R, корень, не является родителем, в этом случае R = X (R это отпуск);и
  2. в противном случае, если есть дети, мы рекурсивно называем find_leave(C, X) с C ребенком.Благодаря обратному отслеживанию в конечном итоге мы получим все листья.

Итак: 

find_leave(R, R) :-
    \+ is_tree(_, R).
find_leave(R, X) :-
    is_tree(C, R),
    find_leave(C, X).

Затем мы получим для разных корней разные листья: 

?- find_leave(a, X).
X = d ;
X = e ;
X = f ;
X = g ;
false.

?- find_leave(b, X).
X = d ;
X = e ;
false.

?- find_leave(R, X).
R = a,
X = d ;
R = a,
X = e ;
R = a,
X = f ;
R = a,
X = g ;
R = b,
X = d ;
R = b,
X = e ;
R = c,
X = f ;
R = c,
X = g ;
false.
...