Улучшение алгоритма для перечисления бинарных деревьев

Question

Улучшение алгоритма для перечисления бинарных деревьев

В настоящее время я могу перечислить укорененные плоские непомеченные двоичные деревья, используя следующий код Prolog методом грубой силы.

e --> u | b | t.
u --> ['[op(u),['], e, [']]'].
b --> ['[op(b),['], e, [','], e, [']]'].
t --> ['number(n)'].

Примечание: см. Выходные листинги ниже.

и выводить их в увеличенном размере, используя

es(S) :-
    length(Ls, _),
    phrase(e, Ls),     % or e(Ls,[]),
    atomic_list_concat(Ls,S).

Однако это неэффективный алгоритм перебора.

Существует ли более эффективный алгоритм перечисления корневых плоских немеченых бинарных деревьев?

Примечание. Деревья можно сгенерировать, используя деревья из предыдущих двух итераций, подумайте о числах Фибоначчи и добавив либо унарную ветвь, либо двоичную ветвь, однако это приводит к дублированию деревьев. Я сам мог бы сделать эту версию, и я искал алгоритм, который эффективно генерирует деревья в первый раз без дубликатов.

Примечание. Бинарное дерево также называется деревом бинарных выражений или K-арным деревом с K <=2.

дополнение

Результаты

Моя версия грубой силы для M(15) заняла 1 час и 27 минут, в то время как эффективная версия для M(15) заняла около 2 секунд.

Очевидно, что эффективный алгоритм гораздо эффективнее, и поэтому я задал вопрос.

Числа Моцкина

Количество деревьев, которые имеют N узлы для корневых плоских немеченых бинарных деревьев задаются числами Моцкина. Смотрите: OEIS A001006

Nodes  Trees
1      1
2      1
3      2
4      4
5      9

Количество деревьев, которые имеют N внутренних узлов для корневого планарного бинарного дерева без меток, задается каталонскими числами. Существует более эффективный алгоритм генерации корневых бинарных деревьев с использованием каталонских чисел.

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

в то время как

число деревьев, основанных на числах Моцкина , имеет одинарные ветви и считает все узлы.

Увидеть:
OEIS A000108
Каталонские числа Тома Дэвиса

Привязка элементов списка Пролога к числу Моцкина

% M is Motzkin number, N is number of  list elements passed to atomic_list_concat\2
m_to_n(1,1).
m_to_n(2,3).
m_to_n(M,N) :-
    M > 2,
    N is (M*2)-1.

es_m(M,S) :-
    m_to_n(M,N),
    length(Ls,N),
    e(Ls,[]),
    atomic_list_concat(Ls,S).

Статистика с неэффективной грубой силой

es_c(M,Count) :-
    aggregate_all(count, es_m(M,_), Count).

?- time(es_c(1,Count)).
% 57 inferences, 0.000 CPU in 0.000 seconds (?% CPU, Infinite Lips)
Count = 1.

?- time(es_c(2,Count)).
% 141 inferences, 0.000 CPU in 0.000 seconds (?% CPU, Infinite Lips)
Count = 1.

?- time(es_c(3,Count)).
% 571 inferences, 0.000 CPU in 0.000 seconds (?% CPU, Infinite Lips)
Count = 2.

?- time(es_c(4,Count)).
% 2,740 inferences, 0.000 CPU in 0.000 seconds (?% CPU, Infinite Lips)
Count = 4.

?- time(es_c(5,Count)).
% 13,780 inferences, 0.000 CPU in 0.001 seconds (0% CPU, Infinite Lips)
Count = 9.

?- time(es_c(6,Count)).
% 70,072 inferences, 0.000 CPU in 0.002 seconds (0% CPU, Infinite Lips)
Count = 21.

?- time(es_c(7,Count)).
% 357,358 inferences, 0.016 CPU in 0.012 seconds (136% CPU, 22870912 Lips)
Count = 51.

?- time(es_c(8,Count)).
% 1,824,082 inferences, 0.063 CPU in 0.056 seconds (111% CPU, 29185312 Lips)
Count = 127.

?- time(es_c(9,Count)).
% 9,313,720 inferences, 0.297 CPU in 0.290 seconds (102% CPU, 31372531 Lips)
Count = 323.

?- time(es_c(10,Count)).
% 47,561,878 inferences, 1.469 CPU in 1.467 seconds (100% CPU, 32382555 Lips)
Count = 835.

?- time(es_c(11,Count)).
% 242,896,160 inferences, 7.672 CPU in 7.665 seconds (100% CPU, 31660599 Lips)
Count = 2188.

?- time(es_c(12,Count)).
% 1,240,493,974 inferences, 38.797 CPU in 38.841 seconds (100% CPU, 31974069 Lips)
Count = 5798.

?- time(es_c(13,Count)).
% 6,335,410,822 inferences, 206.047 CPU in 213.116 seconds (97% CPU, 30747425 Lips)
Count = 15511.

?- time(es_c(14,Count)).
% 32,356,235,848 inferences, 1016.156 CPU in 1018.955 seconds (100% CPU, 31841792 Lips)
Count = 41835.

?- time(es_c(15,Count)).
% 165,250,501,417 inferences, 5231.766 CPU in 5268.363 seconds (99% CPU, 31585991 Lips)
Count = 113634.

BNF

<expression> ::= 
      <unary expression>
    | <binary expression>
    | <terminal>

<unary expression> ::= 
    "(u" <expression> ")"

<binary expression> ::= 
    "(b" <expression> " " <expression> ")"

<terminal> ::= 
    "t"

Используя ответ Дэвида Эйзенстата

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

Чтобы проверить ответ, я использовал WSL (Windows Subsystem for Linux) с установленным Python 3

Используя Windows 10, я создал файл с именем motzkin.py в каталоге

C:\Users\Eric\Documents\Prolog

с кодом Python

def ubtrees(n):
    if n == 1:
        yield 't'
    elif n > 1:
        for t in ubtrees(n - 1):
            yield '(u {})'.format(t)
        for i in range(1, n - 1):
            for t1 in ubtrees(i):
                for t2 in ubtrees(n - 1 - i):
                    yield '(b {} {})'.format(t1, t2)

затем в WSL я создал символическую ссылку на каталог Windows Prolog

$ ln -s "/mnt/c/Users/Eric/Documents/Prolog" /home/eric/Prolog

и перешел в каталог прологов WSL

$ cd Prolog

потом запустил Python3

~/Prolog$ python3

и импортировал код Python

>>> import motzkin

и запустил следующее с аргументом к ubtrees, являющимся числом Моцкина

>>> for value in ubtrees(1):
...   print(value)
...
t

>>> for value in ubtrees(2):
...   print(value)
...
(u t)

>>> for value in ubtrees(3):
...   print(value)
...
(u (u t))
(b t t)

>>> for value in ubtrees(4):
...   print(value)
...
(u (u (u t)))
(u (b t t))
(b t (u t))
(b (u t) t)

>>> for value in ubtrees(5):
...   print(value)
...
(u (u (u (u t))))
(u (u (b t t)))
(u (b t (u t)))
(u (b (u t) t))
(b t (u (u t)))
(b t (b t t))
(b (u t) (u t))
(b (u (u t)) t)
(b (b t t) t)

и проверить числа Моцкина

def m_count(m):
    count = sum(1 for x in ubtrees(m))
    print("Count: ", count)

>>> m_count(1)
Count:  1
>>> m_count(2)
Count:  1
>>> m_count(3)
Count:  2
>>> m_count(4)
Count:  4
>>> m_count(5)
Count:  9
>>> m_count(6)
Count:  21
>>> m_count(7)
Count:  51
>>> m_count(8)
Count:  127
>>> m_count(9)
Count:  323
>>> m_count(10)
Count:  835
>>> m_count(11)
Count:  2188
>>> m_count(12)
Count:  5798
>>> m_count(13)
Count:  15511
>>> m_count(14)
Count:  41835
>>> m_count(15)
Count:  113634

Для выхода из интерактивного Python используйте

quit()

Заметки на дубликаты

То, как я узнал о числах Моцкина, было вручную перечислять деревья ручкой и бумагой и находить дубликаты, используя метод добавления унарной ветви к предыдущим деревьям M(N-1) и двоичных ветвей к предыдущей предшествующей M(N-2) деревья.

Это одно дерево было сгенерировано дважды для M(5) из M(4) деревьев

(b (u t) (u t))

первый, добавив унарную ветвь к

(b (u t) t)

а во-вторых, добавив одинарную ветвь к

(b t (u t))

После этого у меня была последовательность чисел 1,2,4,9,21, которую я использовал при поиске в OEIS, и лучшим результатом был A001006 для чисел Моцкина. Получив больший список чисел Моцкина, я использовал код Пролога, чтобы сгенерировать счетчики для больших входных значений, и все они согласились. Теперь вы можете добавить OEIS в свой инструментарий программирования с действительным примером для демонстрации другим.

Большая картина

Если вы прочитали это далеко, то, вероятно, увидите, что это является частью более серьезной проблемы, которая заключается в создании системы сначала в Прологе, которая может использовать переписывание терминов для решения математических выражений вплоть до базового исчисления, но, что более важно, показывает предпринятые шаги. Таким образом, это дает одну часть пути к созданию деревьев двоичных выражений, которые будут использоваться в качестве тестовых случаев. Следующим шагом будет возможность индивидуально установить количество унарных и двоичных узлов вместо того, чтобы фиксировать их по числу Моцкина. Я использовал только числа Моцкина, чтобы убедиться, что я правильно генерировал подмножество комбинаций. Теперь, когда у меня есть шаблон для этого, я могу изменить его так, чтобы он принимал один аргумент для числа унарных узлов и один для двоичных узлов. См.: Как перечислять комбинации с использованием DCG с CLP(FD) и несколькими ограничениями

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

Пролог выходной

?- length(Ls, N), phrase(e, Ls).
Ls = ['number(0)'],
N = 1 ;
Ls = ['[op(u),[', 'number(0)', ']]'],
N = 3 ;
Ls = ['[op(u),[', '[op(u),[', 'number(0)', ']]', ']]'],
N = 5 ;
Ls = ['[op(b),[', 'number(0)', ',', 'number(0)', ']]'],
N = 5 ;
Ls = ['[op(u),[', '[op(u),[', '[op(u),[', 'number(0)', ']]', ']]', ']]'],
N = 7 ;
Ls = ['[op(u),[', '[op(b),[', 'number(0)', ',', 'number(0)', ']]', ']]'],
N = 7 ;
Ls = ['[op(b),[', '[op(u),[', 'number(0)', ']]', ',', 'number(0)', ']]'],
N = 7 ;
Ls = ['[op(b),[', 'number(0)', ',', '[op(u),[', 'number(0)', ']]', ']]'],
N = 7 ;

?- es(S).
S = 'number(0)' ;
S = '[op(u),[number(0)]]' ;
S = '[op(u),[[op(u),[number(0)]]]]' ;
S = '[op(b),[number(0),number(0)]]' ;
S = '[op(u),[[op(u),[[op(u),[number(0)]]]]]]' ;
S = '[op(u),[[op(b),[number(0),number(0)]]]]' ;
S = '[op(b),[[op(u),[number(0)]],number(0)]]' ;
S = '[op(b),[number(0),[op(u),[number(0)]]]]' ;
S = '[op(u),[[op(u),[[op(u),[[op(u),[number(0)]]]]]]]]' ;
S = '[op(u),[[op(u),[[op(b),[number(0),number(0)]]]]]]' ;
S = '[op(u),[[op(b),[[op(u),[number(0)]],number(0)]]]]' ;
S = '[op(u),[[op(b),[number(0),[op(u),[number(0)]]]]]]' ;
S = '[op(b),[[op(u),[[op(u),[number(0)]]]],number(0)]]' ;
S = '[op(b),[[op(u),[number(0)]],[op(u),[number(0)]]]]' ;
S = '[op(b),[[op(b),[number(0),number(0)]],number(0)]]' ;
S = '[op(b),[number(0),[op(u),[[op(u),[number(0)]]]]]]' ;
S = '[op(b),[number(0),[op(b),[number(0),number(0)]]]]' ;

?- es_m(1,E).
E = 'number(n)' ;
false.

?- es_m(2,E).
E = '[op(u),[number(n)]]' ;
false.

?- es_m(3,E).
E = '[op(u),[[op(u),[number(n)]]]]' ;
E = '[op(b),[number(n),number(n)]]' ;
false.

?- es_m(4,E).
E = '[op(u),[[op(u),[[op(u),[number(n)]]]]]]' ;
E = '[op(u),[[op(b),[number(n),number(n)]]]]' ;
E = '[op(b),[[op(u),[number(n)]],number(n)]]' ;
E = '[op(b),[number(n),[op(u),[number(n)]]]]' ;
false.

?- es_m(5,E).
E = '[op(u),[[op(u),[[op(u),[[op(u),[number(n)]]]]]]]]' ;
E = '[op(u),[[op(u),[[op(b),[number(n),number(n)]]]]]]' ;
E = '[op(u),[[op(b),[[op(u),[number(n)]],number(n)]]]]' ;
E = '[op(u),[[op(b),[number(n),[op(u),[number(n)]]]]]]' ;
E = '[op(b),[[op(u),[[op(u),[number(n)]]]],number(n)]]' ;
E = '[op(b),[[op(u),[number(n)]],[op(u),[number(n)]]]]' ;
E = '[op(b),[[op(b),[number(n),number(n)]],number(n)]]' ;
E = '[op(b),[number(n),[op(u),[[op(u),[number(n)]]]]]]' ;
E = '[op(b),[number(n),[op(b),[number(n),number(n)]]]]' ;
false.

5

algorithm language-agnostic binary-tree oeis motzkin-numbers

Источник

user1243762 06 мар '17 в 13:43

3 ответа

Решение

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

Во-первых, вот декларативное описание таких деревьев:

е (число) -> [].
e(u(Arg))        -> [_], e(Arg).
e (b (слева, справа)) -> [_, _], e(слева), e (справа).

Я также использую DCG. Однако я использую его для другой цели, чем в вопросе: в моем случае я описываю только список, чтобы ограничить глубину решения. Думайте о нетерминалах как о том, сколько "жетонов" определенно будет использовано при применении правила. Обратите внимание, что я использую сложные термины для естественного описания таких деревьев.

Пример запроса с использованием итеративного углубления:

? - длина (Ls, _), фраза (e(E), Ls).
Ls = [],
E = число;
Ls = [_5710],
E = u(число);
Ls = [_5710, _5716],
E = u(u(число));
Ls = [_5710, _5716],
E = b(число, число);
Ls = [_5710, _5716, _5722],
E = u(u(u(число))).

Теперь я могу рассчитывать решения следующим образом:

es_count (M, Count): -
        длина ([_|Ls], М),
        findall (., фраза (e(_), Ls), Sols),
        длина (Sols, Count).

Вот еще несколько решений:

? - длина (_, M), 
    время (es_count (M, Count)), 
    portray_clause (m_count (М, граф)), 
    ложный.
% 7, 0,000 CPU за 0,000 секунд (64% CPU, 636364 Lips)
% 28, 0,000 CPU за 0,000 секунд (81% CPU, 1120000 губ)
m_count (1, 1).
% 29 выводов, 0,000 CPU за 0,000 секунд (31% CPU, 1318182 Lips)
m_count (2, 1).
% 33 выводов, 0,000 CPU за 0,000 секунд (76% CPU, 1736842 Lips)
m_count(3, 2).
% 41 вывод, 0,000 CPU за 0,000 секунд (81% CPU, 1952381 Lips)
m_count(4, 4).
% 61 вывод, 0,000 CPU за 0,000 секунд (88% CPU, 2178571 Lips)
m_count (5, 9).
% 109 выводов, 0,000 CPU за 0,000 секунд (91% CPU, 2595238 Lips)
m_count(6, 21).
% 230 выводов, 0,000 CPU за 0,000 секунд (93% CPU, 2948718 Lips)
m_count(7, 51).
% 538 выводов, 0,000 CPU за 0,000 секунд (97% CPU, 3221557 Lips)
m_count (8, 127).
% 1,337 логических выводов, 0,000 CPU за 0,000 секунд (99% CPU, 3293103 Lips)
m_count (9, 323).
% 3434 выводов, 0,001 ЦП за 0,001 секунды (99% ЦП, 3400000 губ)
m_count (10, 835).
% 9,000 выводов, 0,003 ЦП за 0,003 секунды (94% ЦП, 3301541 Гипс)
m_count (11, 2188).
% 23,908 выводов, 0,007 ЦП за 0,024 секунды (31% ЦП, 3300387 губ)
m_count(12, 5798).
% 64,158 выводов, 0,019 ЦП за 0,024 секунды (79% ЦП, 3387792 Lips)
m_count (13, 15511).
% 173 579 выводов, 0,051 ЦП за 0,062 секунды (83% ЦП, 3397448 губ)
m_count(14, 41835).
% 472 853 выводов, 0,139 ЦП за 0,152 секунды (92% ЦП, 3393690 губ)
m_count(15, 113634).

Пролог - хороший язык для генерации решений, основанных на декларативных описаниях!

5

Источник

user1613573 06 мар '17 в 19:02

Кодирование в Прологе рекуррентного отношения, как предлагает @DavidEisenstat:

motzkin_numbers(0, 1).
motzkin_numbers(1, 1).
motzkin_numbers(N, M) :-
    N>1,
    N1 is N-1,
    motzkin_numbers(N1, M1),
    N2 is N-2,
    aggregate_all(sum(MiP), (
              between(0, N2, I),
              motzkin_numbers(I, M_i),
              I_n1i is N-2-I,
              motzkin_numbers(I_n1i, M_n1i),
              MiP is M_i * M_n1i), Ms),
       M is M1 + Ms.

мы получаем

?- length(_,N), time(motzkin_numbers(N,M)).
...
N = 14,
M = 113634 ;
% 4 inferences, 0.000 CPU in 0.000 seconds (89% CPU, 115724 Lips)
% 1,863,722 inferences, 1.107 CPU in 1.107 seconds (100% CPU, 1683529 Lips)
N = 15,
M = 310572 ;
% 4 inferences, 0.000 CPU in 0.000 seconds (88% CPU, 129232 Lips)
% 4,499,430 inferences, 2.645 CPU in 2.646 seconds (100% CPU, 1700821 Lips)
N = 16,
M = 853467 
...

но SWI-Prolog недавно добавил таблинг: просто добавив эту декларацию

:- table motzkin_numbers/2.

мы получаем

...
% 310 inferences, 0.001 CPU in 0.001 seconds (99% CPU, 591031 Lips)
N = 14,
M = 113634 ;
% 331 inferences, 0.001 CPU in 0.001 seconds (100% CPU, 457731 Lips)
N = 15,
M = 310572 ;
% 352 inferences, 0.001 CPU in 0.001 seconds (100% CPU, 310880 Lips)
N = 16,
M = 853467 ;
% 373 inferences, 0.001 CPU in 0.001 seconds (100% CPU, 703349 Lips)
N = 17,
M = 2356779 ;
...

3

Источник

user874024 06 мар '17 в 20:26

Другие вопросы по тегам algorithm language-agnostic binary-tree oeis motzkin-numbers

user2144669 06 мар '17 в 15:30 2017-03-06 15:30 · Accepted Answer · 2017-03-06 15:30

В Python 3:

def ubtrees(n):
    if n == 1:
        yield 't'
    elif n > 1:
        for t in ubtrees(n - 1):
            yield '(u {})'.format(t)
        for i in range(1, n - 1):
            for t1 in ubtrees(i):
                for t2 in ubtrees(n - 1 - i):
                    yield '(b {} {})'.format(t1, t2)

Эта процедура рекурсивного перечисления соответствует повторению

M_1 = 1
M_n = M_{n-1} + sum_{i=1}^{n-2} M_i M_{n-1-i},

который сдвинут от повторения, данного в Википедии одним.

Улучшение алгоритма для перечисления бинарных деревьев

дополнение

Результаты

Числа Моцкина

Привязка элементов списка Пролога к числу Моцкина

Статистика с неэффективной грубой силой

Рекомендации

BNF

Используя ответ Дэвида Эйзенстата

Заметки на дубликаты

Большая картина

Пролог выходной

3 ответа