二分木を列挙するためのアルゴリズムの改善

debugcn 投稿 Dev

ガイコーダー

現在、次のブルートフォース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).

ただし、これは非効率的なブルートフォースアルゴリズムです。

ルート化された平面のラベルなし二分木を列挙するためのより効率的なアルゴリズムはありますか？

注：ツリーは、前の2つの反復からのツリーを使用し、フィボナッチ数を考え、単項ブランチまたはバイナリブランチのいずれかを追加することで生成できますが、これによりツリーが重複します。私自身もそのバージョンを実行できました。私が探しているのは、重複することなく最初に効率的な方法でツリーを生成するアルゴリズムです。

注：二分木は、二分木またはK <= 2のK-aryツリーとも呼ばれます。

補足

結果

M（15）のブルートフォースバージョンは1時間27分かかりましたが、M（15）の効率的なバージョンは約2秒かかりました。

明らかに、効率的なアルゴリズムはまさにそれであり、はるかに効率的であり、なぜ私が質問したのか。

モツキン数

Nルート化された平面のラベルなし二分木のノードを持つツリーの数は、モツキン数で与えられます。参照：OEIS A001006

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

ルート化された平面のラベルなし二分木に対してN個の内部ノードを持つツリーの数は、カタラン数で与えられます。カタラン数を使用してルート化された平面二分木を生成するためのより効率的なアルゴリズムがあります。

注：
カタロニア番号に基づいて木の数がないではない単項枝を持っているだけでカウント内部ノードを。

一方

Motzkin番号に基づいて木の数はない単項の支店を持ち、カウントすべてのノードを。

参照：
OEIS A000108
カタロニア番号にトム・デイビスによって

Prologリスト要素をモツキン数に関連付ける

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

参考文献

役立つかもしれないPDFとして無料でダウンロード可能な本は、PhilippeFlajoletとRobertSedgewickによる「AnalyticCombinatorics」です。

カタロニア語タグの参照も参照してください。

モツキン数

BNF

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

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

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

<terminal> ::= 
    "t"

DavidEisenstatによる回答を使用

忘れてから何ヶ月も経ってからまた使う必要がある場合に備えて、これらをメモやパンくずと考えてください。

答えをテストするために、Python 3がインストールされたWSL（Windows Subsystem for Linux）を使用しました

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で、WindowsPrologディレクトリへのシンボリックリンクを作成しました

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

WSLPrologディレクトリに変更されました

$ 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）木。

この1つのツリーは、M（4）ツリーからM（5）に対して2回生成されました。

(b (u t) (u t))

最初に単項ブランチを追加することによって

(b (u t) t)

次に、単項ブランチをに追加します

(b t (u t))

これを行った後、OEIS検索で使用した番号1、2、4、9、21のシーケンスがあり、上位の結果はモツキン数のA001006でした。モツキン数のリストが大きくなった後、Prologコードを使用して、より大きな入力値のカウントを生成しましたが、すべて同意しました。これで、他の人にデモンストレーションするための有効な例を使用して、OEISをプログラミングツールボックスに追加できます。

全体像

これまで読んだことがあるなら、これは、Prologで最初にシステムを構築するという大きな問題の一部であることがわかるでしょう。このシステムは、項の書き換えを使用して、基本的な微積分までの数式を解くことができますが、より重要なのは、実行した手順を示しています。したがって、これは、テストケースとして使用されるバイナリ式ツリーを生成する方法の一部になります。次のステップは、モツキン数で固定するのではなく、単項および2進数のノードの数を個別に設定できるようにすることです。組み合わせのサブセットを正しく生成していることを確認するために、モツキン数のみを使用しました。そのためのパターンができたので、単項ノードの数とバイナリノードの数に1つの引数を受け入れるように変更できます。参照：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.

デビッドアイゼンスタット

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

これは、ウィキペディアで与えられた再発から1つシフトしています。

この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。

侵害の場合は、連絡してください[email protected]

編集2021-05-30

コメントを追加

サインイン

分類Dev

Related 関連記事

記事