87.4. フィボナッチの例のデシジョン (再帰および競合解決)

フィボナッチの例のデシジョンセットでは、デシジョンエンジンが再帰をどのように使用してルールの実行競合を順番に解決していくのかを例示します。この例では、ルールで定義可能な顕著性の値を使用して競合を解決することにフォーカスします。

以下は、フィボナッチの例の概要です。

フィボナッチ数は、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 フィールドは、その数列の位置のフィボナッチオブジェクトの値を示します。-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 コンソールウィンドウに表示されます。

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" ルールは、値が -1 の、アサートされた各 Fibonacci オブジェクトを照合して、現在の値よりも数列が 1 つ小さい Fibonacci オブジェクトを新たに作成し、アサートします。数列フィールドが 1 に相当するオブジェクトが存在しない場合に、フィボナッチオブジェクトが追加されると毎回、このルールは再度照合され、実行されます。メモリーにフィボナッチオブジェクト 50 個がすべて存在する場合は、not 条件要素を使用して、ルールの合致を停止します。また、"Bootstrap" ルールを実行する前に Fibonacci オブジェクト 50 個をすべてアサートする必要があるため、このルールには salience の値も含まれます。

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 → Show View)) に読み込みます。

この例では、監査ビュー に、sequence フィールドが 50 に指定された、Fibonacci の元のアサーションが表示されます。これは Java コードで実行されています。これ以降、監査ビュー で、ルールの再帰が継続して行われ、アサートされた Fibonacci オブジェクトにより、"Recurse" ルールがアクティベートされて、再度実行されます。

図87.7 監査ビューでのルール "Recurse"

sequence フィールドが 2 の Fibonacci オブジェクトがアサートされると、"Bootstrap" ルールが一致し、"Recurse" ルールとともにアクティベートされます。フィールド sequence には複数の制約があり、1 または 2 と同等かをテストしている点に注目してください。

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" ルールは実行していません。

図87.8 アジェンダビュー 1 でのルール "Recurse" および "Bootstrap"

sequence が 1 の Fibonacci オブジェクトがアサートされると、"Bootstrap" ルールが再度一致し、このルールに含まれる 2 つのルールがアクティベートされます。sequence が 1 の Fibonacci オブジェクトが存在すると、すぐに not 条件要素でルールが一致しなくなるため、"Recurse" ルールの照合やアクティベーションはされません。

図87.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 オブジェクトの値を計算できます。

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 オブジェクトに値が設定されるまで継続されます。

図87.10 監査ビューのルール