пролог в математике - поиск уровня узла в прологе

Question

Предполагается, что это двоичное дерево поиска и задано правило, что above(X,Y) - X находится непосредственно над Y. Также я создал правило root(X) - X не имеет родителя.

Затем я пытался выяснить, что такое глубина узла в этом дереве. Предположим, что корневой узел дерева «r». Итак, я получил факт level(r,0). Чтобы реализовать правило level(N,D) :-, я подумал, что здесь должна быть рекурсия. Таким образом, я попытался

level(N,D): \+ root(N), above(X,N), D is D+1, level(X,D). 

Так что, если N не является корнем, то есть узел X выше N и уровень D плюс один, то рекурсии. Но когда я тестировал это, он просто работает для условия корня. Когда я создал больше фактов, таких как node «s», это левый элемент узла «r», My query - level (s, D). Он возвращает мне «нет». Я проследил запрос, он показывает мне

1 1 Call: level(s,_16) ? 
    1 1 Fail: level(s,_16) ? 

Я просто запутанным, почему он терпит неудачу, когда я называю level(s,D)?

Answer 1

Есть некоторые проблемы с вашим запросом:

• В Прологе вы не можете написать что-то вроде D is D+1, потому что переменная может быть назначен только один значение;
• в данный момент, вы позвоните: D is D+1, D еще не был создан экземпляр, так что это может привести к ошибке; и
• Вы не указываете (по крайней мере, не в видимом коде), что level/2 корня 0.

Решение состоит в том, чтобы первое состояние, что уровень любого корня 0:

level(N,0) :- 
    root(N). 

Теперь мы должны определить индуктивный случай: сначала мы действительно ищем родитель, используя above/2 предикат. Выполнение проверки, что N не является root/1, не обязательно, строго говоря, потому что это противоречило бы с тем, что есть above/2. Далее мы определяем уровень этого родителя LP и, наконец, мы вычисляем уровень нашего узла, указав, что L is LP+1 где L является уровень N и LP уровень операционного P:

level(N,L) :- 
    above(P,N), 
    level(P,LP), 
    L is LP+1. 

Или положить все это вместе:

level(N,0) :- 
    root(N). 
level(N,L) :- 
    above(P,N), 
    level(P,LP), 
    L is LP+1. 

Поскольку вы не предоставили образец дерева, у меня нет средств проверить, ведет ли этот предикат себя так, как вы ожидаете.

---

О root/1

Обратите внимание, что при написании root/1, вы приведете дублирования данных: вы можете просто написать:

root(R) :- 
    \+ above(_,R).