Перечисление бинарных деревьев в Прологе

Я пытаюсь создать правила Prolog для перечисления «двоичных деревьев» в форме списка в Prolog. Я новичок в Prolog.

Дерево с 0 узлами - это пустой список:

[]

Дерево с 1 узлом:

[[],[]]

Дерево с двумя узлами имеет 2 возможности:

[[],[[],[]]]

[[[],[]],[]]

и так далее.

Вот мои правила:

bintree(0,[]).
bintree(1,[[],[]]).
bintree(N,[Lc,Rc]) :-
  N > 1,
  bintree(N1,Lc),
  bintree(N2,Rc),
  N1 >= 0,
  N2 >= 0,
  N3 is N1+N2+1,
  N==N3.

Очевидно, что запросы на 0 и 1 работают. Для N = 2 он печатает одну из возможностей, но выдает ошибку после того, как я ввожу точку с запятой, чтобы получить другую возможность. Запросы для N> 2 напрямую выдают ошибку. Ошибка всегда одна и та же:

ERROR: >/2: Arguments are not sufficiently instantiated

Я читал об этой ошибке на некоторых веб-сайтах, но не могу понять, что здесь вызывает эту ошибку.

Заранее благодарны за Вашу помощь.


instantiation-error prolog logic-programming catalan
person kpjoshi    schedule 26.03.2015    source источник
comment
Нет, это заходит в бесконечный цикл.   -  person kpjoshi    schedule 26.03.2015
comment
Чтобы использовать компаратор выражений в Прологе, все выражения должны быть полностью созданы (значения известны). Вы получили ошибку, потому что N не имело значения, когда вы пытались N > 1. Какой запрос вы пытаетесь удовлетворить? В вашем вопросе совсем не ясно.   -  person lurker    schedule 26.03.2015
comment
Ожидает пару. Первое - положительное целое число, которое представляет собой количество узлов в дереве. Второй - это дерево в заданном формате с таким количеством узлов. Бывший. бинтри (2, А). должен дать A = [[], [[], []]]; A = [[[], []], []], который является представлением двух двоичных деревьев с 2 узлами. Он должен заканчиваться для всех положительных целых чисел, заданных в качестве первого аргумента.   -  person kpjoshi    schedule 26.03.2015
comment
В вашем предложении выражения bintree(N1, Lc) и bintree(N2, Rc) вызываются с N1 и N2 неустановленными переменными. Таким образом, подпоследовательность N > 1 завершится ошибкой при этом сообщении об ошибке.   -  person lurker    schedule 26.03.2015
comment
Я пытаюсь удовлетворить такой тип запроса, как bintree (5, X). Это заставит пролог распечатать представление двоичного дерева с 5 узлами. Каждый пустой список [] подобен NULL-указателю в C. Список с 2 элементами [L, R] - это узел, который имеет два элемента L и R в качестве дочерних. Когда будет предложено поставить точку с запятой, пролог должен вывести все возможные деревья для X с таким количеством узлов, а затем вывести false.   -  person kpjoshi    schedule 26.03.2015
comment
@lurker Хорошо, я изменил порядок на следующий: bintree(N,[Cl,Cr]) :- integer(Nl), integer(Nr), Nl>=0, Nr>=0, Ns is Nl+Nr+1, N==Ns, bintree(Nl,Cl), bintree(Nr,Cr). Теперь я получаю false для всех N ›1. В основном я хочу, чтобы он попытался построить левое и правое поддеревья так, чтобы сумма узлов в них плюс 1 (их родительский элемент) была равна N.   -  person kpjoshi    schedule 26.03.2015
comment
Английское определение моих правил: Двоичное дерево с 0 узлами: пустой список. Пустой список представляет собой ПУСТОЙ указатель. Двоичное дерево с 1 узлом: список, содержащий 2 пустых списка. Представляет узел с двумя указателями NULL в качестве дочерних. [Cl, Cr] - это двоичное дерево с N узлами, если существуют не -ve целых чисел Nl и Nr, такие что Nl + Nr + 1 = N, и Cl - двоичное дерево с Nl узлами, а Cr - двоичное дерево с Nr узлами.   -  person kpjoshi    schedule 26.03.2015
comment
См. это   -  person false    schedule 26.03.2015

Ответы (2)


arrow_upward
3
arrow_downward

Использование библиотеки CLPFD поможет дать чистое решение для создания размеров. Тогда вам не нужен предикат wonky (;)) integer/1, который может быть проблематичным:

:- use_module(library(clpfd)).

bintree(0,[]).
bintree(1,[[],[]]).
bintree(N, [L, R]) :-
    N #> 1,
    N #= N1 + N2 + 1,
    N1 #>= 0, N2 #>= 0,
    bintree(N1, L), bintree(N2, R).

Или проще (благодаря предложению @ repeat):

bintree(0,[]).
bintree(N, [L, R]) :-
    N #> 0,
    N #= N1 + N2 + 1,
    N1 #>= 0, N2 #>= 0,
    bintree(N1, L), bintree(N2, R).

?- bintree(4, L).
L = [[], [[], [[], [[], []]]]] ;
L = [[], [[], [[[], []], []]]] ;
L = [[], [[[], []], [[], []]]] ;
L = [[], [[[], [[], []]], []]] ;
L = [[], [[[[], []], []], []]] ;
L = [[[], []], [[], [[], []]]] ;
L = [[[], []], [[[], []], []]] ;
L = [[[], [[], []]], [[], []]] ;
L = [[[], [[], [[], []]]], []] ;
L = [[[], [[[], []], []]], []] ;
L = [[[[], []], []], [[], []]] ;
L = [[[[], []], [[], []]], []] ;
L = [[[[], [[], []]], []], []] ;
L = [[[[[], []], []], []], []] ;
false.

?-

CLPFD - хороший декларативный способ выражения числовых ограничений.

person lurker    schedule 26.03.2015
comment
Спасибо. Возможно ли это, используя только чистый пролог, без этой библиотеки? - person kpjoshi; 26.03.2015
comment
Эта библиотека чиста. Попробуйте, например, GNU Prolog или B Prolog, где вам не нужно импортировать какую-либо библиотеку для использования такой элементарной функции, как ограничения конечной области. Отличное решение, +1! - person mat; 26.03.2015

arrow_upward
0
arrow_downward

Я знаю, что разместил этот вопрос год назад, но мне удалось решить его позже, не используя никаких библиотек. Вот мое решение:

%binary tree generator
bintree(0,[]). %0 nodes - empty list
bintree(1,[[],[]]). %1 node - list containing 2 empty lists
bintree(N,[Cl,Cr]) :-
    N>=2, %check only if at least 2 nodes
    between(0,N,Nl), %let Nl be in [0,N]
    between(0,N,Nr), %similarly for Nr
    Ns is Nl+Nr+1, %total no. of nodes should add up correctly
    N==Ns, %so check for that
    bintree(Nl,Cl), %children should also be valid binary trees
    bintree(Nr,Cr).
person kpjoshi    schedule 16.02.2017
comment
Это очень плохой генератор. Например, попробуйте самый общий запрос: ?- bintree(N, Tree). Он дает два решения, а затем говорит: ERROR: Arguments are not sufficiently instantiated. Я настоятельно рекомендую вам использовать ограничения CLP (FD), чтобы рассуждать о целых числах, как в программе lurker. Это сделает ваше решение более общим, применимым во всех направлениях, как мы и ожидаем от отношения. В вашем решении и формулировка (проверка), и поведение очень императивны, и ваш код работает только в очень ограниченном наборе режимов использования. В качестве другого примера попробуйте ?- bintree(N, [_,_]). и сравните их! - person mat; 16.02.2017