9.4. フィボナッチの例のデシジョン (再帰および競合解決)
フィボナッチの例のデシジョンセットでは、デシジョンエンジンが再帰をどのように使用してルールの実行競合を順番に解決していくのかを例示します。この例では、ルールで定義可能な顕著性の値を使用して競合を解決することにフォーカスします。
以下は、フィボナッチの例の概要です。
-
名前:
フィボナッチ
-
Main クラス: (
src/main/java
内の)org.drools.examples.fibonacci.FibonacciExample
-
モジュール:
drools-examples
- タイプ: Java アプリケーション
-
ルールファイル: (
src/main/resources
内の)org.drools.examples.fibonacci.Fibonacci.drl
- 目的: ルールの顕著性を使用した再帰や競合解決を例示します。
フィボナッチ数は、0 または 1 で開始する数列です。0、1、1、2、3、5、8、13、21、34、55、89、144、233、377、610、987、1597、2584、4181、6765、10946 などのように、2 つの先行する数を足すことにより、次にくるフィボナッチ数が求められます。
フィボナッチの例では、Fibonacci
のファクトクラスを 1 つ使用し、このクラスに以下の 2 つのフィールドが含まれています。
-
sequence
-
value
sequence
フィールドは、フィボナッチ数列のオブジェクトの位置を示します。value
フィールドは、その数列の位置のフィボナッチオブジェクトの値を示します。-1
は、計算する必要がある値という意味です。
フィボナッチクラス
public static class Fibonacci { private int sequence; private long value; public Fibonacci( final int sequence ) { this.sequence = sequence; this.value = -1; } ... setters and getters go here... }
この例を実行するには、IDE で Java アプリケーションとして org.drools.examples.fibonacci.FibonacciExample
クラスを実行します。
実行後に、以下の出力が IDE コンソールウィンドウに表示されます。
IDE コンソールでのフィボナッチの例の出力
recurse for 50 recurse for 49 recurse for 48 recurse for 47 ... recurse for 5 recurse for 4 recurse for 3 recurse for 2 1 == 1 2 == 1 3 == 2 4 == 3 5 == 5 6 == 8 ... 47 == 2971215073 48 == 4807526976 49 == 7778742049 50 == 12586269025
Java でこの動作を実現するには、sequence フィールドに 50
を指定して、Fibonacci
オブジェクトを挿入します。この例では、次に再帰ルールを使用して、他の 49 個の Fibonacci
オブジェクトを挿入します。
PropertyChangeSupport
インターフェイスを実装して動的ファクトを使用する代わりに、この例では MVEL 方言の modify
キーワードを使用して、ブロックセッターアクションを有効にしてデシジョンエンジンに変更を通知しています。
フィボナッチの例の実行
ksession.insert( new Fibonacci( 50 ) ); ksession.fireAllRules();
この例では、以下の 3 つのルールを使用します。
-
"Recurse"
-
"Bootstrap"
-
"Calculate"
"Recurse"
ルールは、値が -1
の、アサートされた各 Fibonacci
オブジェクトを照合して、現在の値よりも数列が 1 つ小さい Fibonacci
オブジェクトを新たに作成し、アサートします。数列フィールドが 1
に相当するオブジェクトが存在しない場合に、フィボナッチオブジェクトが追加されると毎回、このルールは再度照合され、実行されます。メモリーにフィボナッチオブジェクト 50 個がすべて存在する場合は、not
条件要素を使用して、ルールの合致を停止します。また、"Bootstrap"
ルールを実行する前に Fibonacci
オブジェクト 50 個をすべてアサートする必要があるため、このルールには salience
の値も含まれます。
ルール "Recurse"
rule "Recurse" salience 10 when f : Fibonacci ( value == -1 ) not ( Fibonacci ( sequence == 1 ) ) then insert( new Fibonacci( f.sequence - 1 ) ); System.out.println( "recurse for " + f.sequence ); end
この例の実行フローをさらに理解するには、target/fibonacci.log
の監査ログファイルを IDE デバッグビュー (または Audit View が利用できる場合は Audit View (例: IDE の Window
この例では、監査ビュー に、sequence
フィールドが 50
に指定された、Fibonacci
の元のアサーションが表示されます。これは Java コードで実行されています。これ以降、監査ビュー で、ルールの再帰が継続して行われ、アサートされた Fibonacci
オブジェクトにより、"Recurse"
ルールがアクティベートされて、再度実行されます。
図9.7 監査ビューでのルール "Recurse"
sequence
フィールドが 2
の Fibonacci
オブジェクトがアサートされると、"Bootstrap"
ルールが一致し、"Recurse"
ルールとともにアクティベートされます。フィールド sequence
には複数の制約があり、1
または 2
と同等かをテストしている点に注目してください。
ルール "Bootstrap"
rule "Bootstrap" when f : Fibonacci( sequence == 1 || == 2, value == -1 ) // multi-restriction then modify ( f ){ value = 1 }; System.out.println( f.sequence + " == " + f.value ); end
IDE で Agenda View を使用して、デシジョンエンジンアジェンダの状態を調査できます。"Recurse"
の顕著性の値のほうが高いため、"Bootstrap"
ルールは実行していません。
図9.8 アジェンダビュー 1 でのルール "Recurse" および "Bootstrap"
sequence
が 1
の Fibonacci
オブジェクトがアサートされると、"Bootstrap"
ルールが再度一致し、このルールに含まれる 2 つのルールがアクティベートされます。sequence
が 1
の Fibonacci
オブジェクトが存在すると、すぐに not
条件要素でルールが一致しなくなるため、"Recurse"
ルールの照合やアクティベーションはされません。
図9.9 アジェンダビュー 2 でのルール "Recurse" および "Bootstrap"
"Bootstrap"
ルールは、sequence
が 1
と 2
のオブジェクトの値を 1
に設定します。値が -1
でない Fibonacci
オブジェクトが 2 つあるため、"Calculate"
ルールの照合が可能になります。
この例のある時点で、ワーキングメモリーに 50 近くの Fibonacci
オブジェクトが存在します。3 つ選択してそれぞれを乗算し、順番に各値を計算する必要があります。フィールドの制約なしに、ルールで 3 つの Fibonacci パターンを使用してクラス積候補を絞り込む場合に、考えられる組み合わせとして 50x49x48 通りあり、約 12 万 5000 のルールを実行できるにもかかわらず、その大半が誤っていることになります。
"Calculate"
ルールは、フィールドの制約を使用して正しい順番にフィボナッチパターンを 3 つ評価します。この手法は cross-product matching と呼ばれます。
最初のパターンでは、値が != -1
の Fibonacci
オブジェクトを検索して、このパターンとフィールド両方をバインドします。2 番目の Fibonacci
オブジェクトが実行する内容は同じですが、別のフィールド制約を追加して、シーケンスが f1
にバインドされている Fibonacci
オブジェクトより 1 つ大きくなるようにします。このルールが初めて実行されると、シーケンスが 1
と 2
にだけ、値 1
が割り当てられていることが分かります。また、この 2 つの制約で、f1
がシーケンス 1
を参照し、f2
がシーケンス 2
を参照するようにします。
最後のパターンでは、値が -1
と等しく、シーケンスが f2
よりも大きい Fibonacci
オブジェクトを検索します。
フィボナッチの例のこの時点で、3 つの Fibonacci
オブジェクトが利用可能なクロス積から正しく選択され、f3
にバインドされている 3 番目の Fibonacci
オブジェクトの値を計算できます。
ルール "Calculate"
rule "Calculate" when // Bind f1 and s1. f1 : Fibonacci( s1 : sequence, value != -1 ) // Bind f2 and v2, refer to bound variable s1. f2 : Fibonacci( sequence == (s1 + 1), v2 : value != -1 ) // Bind f3 and s3, alternative reference of f2.sequence. f3 : Fibonacci( s3 : sequence == (f2.sequence + 1 ), value == -1 ) then // Note the various referencing techniques. modify ( f3 ) { value = f1.value + v2 }; System.out.println( s3 + " == " + f3.value ); end
modify
ステートメントにより、f3
にバインドされた Fibonacci
オブジェクトの値が更新されます。つまり、値が -1
以外の Fibonacci
オブジェクトが新たに存在するということで、"Calculate"
ルールにより、再度合致があるか検索して次のフィボナッチ番号を算出することができます。
IDE のデバッグビューまたは 監査ビュー では、最後の "Bootstrap"
ルールが実行されることで Fibonacci
オブジェクトが変更され、"Calculate"
ルールに合致し、次に、別の Fibonacci
オブジェクトが変更され、この "Calculate"
ルールに再度合致できていることが分かります。このプロセスは、すべての Fibonacci
オブジェクトに値が設定されるまで継続されます。
図9.10 監査ビューのルール