10

二分木を考えてみましょう:

  1. nが整数の場合、 nはノードです
  2. aとbがノードの場合、 (+ a b ) はノードです。

次の 3 つの操作があります。

  1. (+ a b ) -> (+ b a )
  2. (+ (+ a b ) c ) -> (+ a (+ b c ))
  3. (+ a (+ b c )) -> (+ (+ a b ) c ) -- (2.逆)

これらの操作を使用して、特定のツリーの可能な順列をすべて与えるアルゴリズムが必要です。任意の操作を任意のサブツリーに適用できます。順列とは、まったく同じ葉のセットを持つすべての木を意味します。そんなに難しいことではないのかもしれませんが、私には理解できないようです。

[編集] リーフは名前 (つまり変数) にすることもできるため、整数としてのプロパティに依存することはオプションではありません。木は合計を表します。

[編集 2] この演習のポイントは、フォームAおよび-Aの項を見つけて合計を減らし、それらを削除するためにツリーをサブツリー (+ A -A ) に取得することです。上記の 3 つの操作は私のシステムの公理であり、最後まで使用する必要があります。そうしないと、削減されたツリーが元のツリーと等しいことを証明できません。私はTwelfロジック プログラミング言語を使用しているので、最初に要求したことを実行するアルゴリズムを理解できれば、残りは簡単に実行できますが、別の解決策ももちろん歓迎します。

4

6 に答える 6

2

最も簡単な解決策は、ツリーの深さ優先のトラバーサルで、すべてのノードをリストに収集し、リストのすべての順列を生成し、各順列をバイナリ ツリーにダンプすることです。

したがって、リスト (+ a (+ bc) ) が与えられると、ノード [a; b; c]、次の順列があります。

[a; b; c]
[a; c; b]
[b; a; c]
[b; c; a]
[c; a; b]
[c; b; a]

リストの最初の項目は頭で、次の 2 つの項目は子ノード、次の 4 つの項目は子-子ノードなどです。

バランスの取れたツリーだけでなく、可能なすべてのツリーのリストを作成する必要がある場合、これの複雑さは劇的に増加します。その場合、次のようにグループ化する必要があります。

[a; b; c; d]
[(a; b); c; d]
[(a; b; c); d]
[a; (b; c); d]
[a; (b; c; d)]
[a; b; (c; d)]
[a; b; d; c]
// first permutation
[(a; b); d; c]
[(a; b; d); c]
...

各 n タプルはノードのセットです。いくつかのノードでは、アルゴリズムが完了する前に、ユニバースは熱死を経験します。

于 2009-03-16T18:51:34.253 に答える
1

この問題の解決策には、間違いなくカタロニア語の数字が含まれます。n 個の葉を持つC n -1個の可能な二分木があり、 n !個あります。葉の可能な順序付けなので、n !個あります。* C n -1可能なツリー。ただし、それらを列挙するのは少し面倒です。

于 2009-03-16T18:47:26.587 に答える
1

これらの演算は、閉包、結合性、交換性というプロパティを持つ加算に似ています。一致するノードの場合、それぞれが一連のリーフを同じままにし、再帰的に適用できます。特定のノード x の順列をカウントするには (Haskell と F# の奇妙な組み合わせで)

let count x = match x with
  | LeafNode -> 1
  | TreeNode (a,b) -> 2 * count a * count b
于 2009-03-16T18:47:57.710 に答える
1

結合性と交換性があるため、要素を自由に移動できます。この問題に対する実際的なアプローチは、次のようなものです。

  • 木を片側に梳くと、リストが得られます。

  • リストを並べ替えて、キャンセルする要素が隣り合うようにします。

  • 要素をサブツリーに移動してキャンセルします。

目的の証明を得るには、これらの操作の小さな証明を作成してから組み合わせる必要があります。

または、AC マッチングを調べることもできます。

あなたが提案するようにすべての順列を試すと、組み合わせの爆発が大きくなります。

于 2009-03-16T22:08:38.990 に答える
1

指摘したように、交換性と結合性の公理を実際に持っている場合は、被加数を集めて集合またはリストとして処理するのが最善です。

これで満足できない場合は、次のこととして、実際にはすべての順列が必要ではないように見えますが、単純化するために式を書き直したいと考えています。これは、すべての順列を生成するよりもはるかに効率的です!

ただし、繰り返します:)、交換性と結合性しかない場合は、セット内の項を処理してください。

于 2009-03-17T00:19:45.790 に答える
0

木を減らすという根本的な問題の解決策を発見しました。

  1. ツリーから葉Aと-Aのペアを見つけます。
  2. a）Aと-Aが同じ子にある場合は、繰り返します。
  3. b）「バブル」Aおよび-Aをそれぞれの子の上部に配置します。結果として生じる可能性のあるケースは8つありますが、それらはすべて次のようになります（+（x A）（-A y））。それから（+（+ xy）（+ A -A））に移行するのは簡単です。

提案されているように、それを行う別の方法は、最初にツリーをリストに変換することです：（+ A（+ B（+ ...））X）、次に一致するペアAと-Aを見つけて、それらを一番上に移動します。私は試していませんが、これにより上記のアルゴリズムよりも長い証明（望ましくない）が生成される可能性があると思います。

それでも、元の質問は魅力的だと思います。それに基づくアルゴリズムが上記とどのように比較されるかを試してみたいと思います。

于 2009-03-17T12:34:33.107 に答える