5

目前，我可以使用以下蛮力 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 <=2 的K-ary 树。

补充

结果

我的 M(15) 的蛮力版本需要 1 小时 27 分钟，而 M(15) 的高效版本大约需要 2 秒。

显然，有效的算法就是这样，效率更高，也是我问这个问题的原因。

莫茨金数

具有根平面未标记二叉树节点的树的数量N由 Motzkin 数给出。参见：OEIS A001006

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

对于有根平面未标记二叉树，具有 N 个内部节点的树的数量由加泰罗尼亚数给出。有一种更有效的算法可以使用加泰罗尼亚数生成有根平面二叉树。

注意：
基于加泰罗尼亚数字的树数没有一元分支，只计算内部节点。

尽管

基于 Motzkin 数的树数确实具有一元分支并计算所有节点。

请参阅：汤姆戴维斯的
OEIS A000108
加泰罗尼亚语数字

将 Prolog 列表元素与 Motzkin 数相关联

% 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.

参考

Philippe Flajolet 和 Robert Sedgewick 所著的“Analytic Combinatorics”是一本可能有帮助的可免费下载的 pdf 书

另请参阅加泰罗尼亚语标签中的参考资料。

莫茨金数

BNF

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

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

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

<terminal> ::= 
    "t"

使用David Eisenstat 的回答

对我来说，将这些视为笔记或面包屑，以防在我忘记它的几个月后需要再次使用它。

为了测试答案，我使用了安装了 Python 3 的WSL（适用于 Linux 的 Windows 子系统）

motzkin.py使用 Windows 10 我在目录中创建了一个名为

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 Prolog 目录

$ cd Prolog

然后开始 Python3

~/Prolog$ python3

并导入 Python 代码

>>> import motzkin

并以 ubtrees 为 Motzkin 数的参数运行以下命令

>>> 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)

并检查 Motzkin 数

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()

重复注释

我了解 Motzkin 数的方法是用笔和纸手动枚举树，并通过使用将一元分支添加到前面的树 M(N-1) 和二进制分支到前面的 M(N -2）树木。

这棵树从 M(4) 棵树中为 M(5) 生成了两次

(b (u t) (u t))

第一个通过添加一元分支到

(b (u t) t)

其次通过添加一元分支到

(b t (u t))

完成此操作后，我得到了用于 OEIS 搜索的数字序列 1、2、4、9、21，最上面的结果是Motzkin 数字的A001006。一旦我有了更大的 Motzkin 数字列表，我就使用 Prolog 代码为更大的输入值生成计数，他们都同意了。现在，您可以将 OEIS 添加到您的编程工具箱中，并通过一个有效的示例向其他人演示。

更大的图景

如果你已经读到这里，那么你可能会看到这是一个更大的问题的一部分，它首先在 Prolog 中构建一个系统，可以使用术语重写来解决数学表达式直到基本微积分，但更重要的是显示所采取的步骤。因此，这为生成用作测试用例的二元表达式树提供了一部分方法。下一步是能够单独设置一元和二元节点的数量，而不是让它们由 Motzkin 数固定。我只使用 Motzkin 数字来验证我是否正确生成了组合的子集。现在我有了模式，我可以修改它以接受一个参数用于一元节点的数量，一个用于二进制节点。请参阅：如何使用具有 CLP(FD) 和多个约束的 DCG 枚举组合

只有当我遇到困难时，我才会提出与此相关的问题，所以不要指望看到所有必要的面包屑。

序言输出

?- 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.
4

3 回答 3

5

除了已经发布的解决方案之外，我还想为该任务提供以下Prolog解决方案。

首先，这是对此类树的声明性描述：

e（数字）-> []。
e(u(Arg)) --> [_], e(Arg)。
e(b(左,右)) --> [_,_], e(左), e(右)。

我也在使用。但是，我将它用于与问题不同的目的：就我而言，我仅描述一个列表以限制解决方案的深度。将非终结符视为说明应用规则肯定会消耗多少“令牌” 。另请注意，我使用复合术语来自然地描述此类树。

示例查询，使用迭代深化：

?- 长度（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, 计数) :-
        长度（[_|Ls]，M），
        findall(., 短语(e(_), Ls), Sols),
        长度（溶胶，计数）。

这里还有一些解决方案：

?- 长度（_，M），
   时间（es_count（M，计数）），
   描绘子句（m_count（M，Count）），
   错误的。
% 7 次推断，0.000 CPU 在 0.000 秒内（64% CPU，636364 唇）
% 28 次推理，0.000 CPU 在 0.000 秒内（81% CPU，1120000 Lips）
m_count(1, 1)。
% 29 次推理，0.000 CPU 在 0.000 秒内（31% CPU，1318182 唇）
m_count(2, 1)。
% 33 次推理，0.000 CPU 在 0.000 秒内（76% CPU，1736842 唇）
m_count(3, 2)。
% 41 次推理，0.000 CPU 在 0.000 秒内（81% CPU，1952381 唇）
m_count(4, 4)。
% 61 次推理，0.000 CPU 在 0.000 秒内（88% CPU，2178571 唇）
m_count(5, 9)。
% 109 次推理，0.000 CPU 在 0.000 秒内（91% CPU，2595238 唇）
m_count(6, 21)。
% 230 次推理，0.000 CPU 在 0.000 秒内（93% CPU，2948718 唇）
m_count(7, 51)。
% 538 推论，0.000 CPU 在 0.000 秒内（97% CPU，3221557 唇）
m_count(8, 127)。
% 1,337 次推理，0.000 CPU 在 0.000 秒内（99% CPU，3293103 唇）
m_count(9, 323)。
% 3,434 次推理，0.001 秒内 0.001 CPU（99% CPU，3400000 唇）
m_count(10, 835)。
% 9,000 次推理，0.003 秒内 0.003 CPU（94% CPU，3301541 唇）
m_count(11, 2188)。
% 23,908 推理，0.007 CPU 在 0.024 秒内（31% CPU，3300387 唇）
m_count(12, 5798)。
% 64,158 推理，0.019 CPU 在 0.024 秒内（79% CPU，3387792 唇）
m_count(13, 15511)。
% 173,579 次推理，0.051 CPU 在 0.062 秒内（83% CPU，3397448 唇）
m_count(14, 41835)。
% 472,853 推理，0.139 CPU 在 0.152 秒内（92% CPU，3393690 唇）
m_count(15, 113634)。

Prolog 是一种很好的语言，可以根据声明性描述详尽地生成解决方案！

于 2017-03-06T19:02:25.680 回答
3

正如@DavidEisenstat 所建议的那样，在 Prolog 中对递归关系进行编码：

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 ;
...
于 2017-03-06T20:26:49.967 回答
1

在 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},

它与维基百科中给出的重复出现了一个。

于 2017-03-06T15:30:17.713 回答