クラスでは、3 つの要素 (a、b、c) をソートするための単純な決定木が与えられました。
(ソース: brpreiss.com )
これを見ていると、なんとなく腑に落ちます。フォローできました。
ただし、4 つの要素 (a、b、c、d) の決定木を作成する必要があり、葉の数は 24 まで増えました。
私は、各ブランチで比較していると思われる要素を追跡するのに役立つ整然とした方法で決定木にアプローチするのに苦労しています。
より大きな決定木を構築するための系統的な方法は何ですか? 方法を知っていれば、可能性のあるリーフ構造を吐き出すプログラムを喜んで書きます。
S orting Networksを調べるとよいでしょう。与えられた数の入力に対して最適なソートネットワークを決定木に変換できるはずです。
または、特定の並べ替えアルゴリズムを使用してステップ実行し、比較のたびに新しい分岐を作成することもできます。
最後に、これを逆に実行することもできます。たとえば、マージ ソート タイプのアプローチを使用します。24 の可能なすべてのソート順をツリーの一番下に配置します。比較を選択し、結果に基づいてリーフを 2 つのセットに分割します。ブランチごとにリーフが 1 つになるまで、ブランチごとに再帰的に繰り返します。
アルゴリズムの種類はCharlesForgyによって説明されています。Reteアルゴリズムを参照してください。（申し訳ありませんが、WPの記事は確かに簡単な答えではありませんが、良いスタートになるかもしれません）
