Reteアルゴリズム(1)

今日はルールエンジンの代表的なアルゴリズムReteアルゴリズムを。
ルールエンジンのアルゴリズム
にも書いたように、ルールエンジンは、

1.ワーキングメモリ(短期記憶)に入ったデータ(ファクト)の集合に対して、たくさんあるルールの条件部分をひとつひとつファクトとマッチングさせて、マッチしたルールとデータのカップルを列挙しておく。
2.カップルの中からひとつを選んで実行する。
3.実行によってワーキングメモリ(短期記憶)のファクトが書き換えられる場合もあるので、再度1.のカップリングを行う。
4.1~3を繰り返してマッチするルールがなくなったところで実行が終了する。

といったサイクルをもって実行が進んでいきます。
さてこのサイクルの 1.に注目してみましょう。ここでは論理上常にルールとファクトの組を全部マッチングさせるはずです。これを真っ正直に行っていたら誰が考えても驚くほどの時間がかかってしまうのは明らかでしょう。
というわけで、このあと一生をReteアルゴリズムに捧げる(?)こととなる Charles Forgyは考えました。「確かに論理上は、ルールとファクトの組を全部マッチングさせようとするはずだが、ルールはサイクルあたりひとつしか実行されないのでワーキングメモリの内容の変更分もたかだか一つのルールで変更された分しか変わらないはず」
・・・
「ということは、最初にまとめてルールとファクトのマッチングをチェック・結果を保持しておき後は各サイクルでのワーキングメモリの差分のみをチェック・更新していけば十分なのではないだろうか」

そして彼は、このアイデアを1979年にReteアルゴリズムとしてまとめました。
(続く)

コメント

  1. […] Terminalノード if-thenルールのthen部分にあたるノード。ここまで到達したファクト(の組)がthen部分と合わさって実行候補のリストに登録される(前回の記事の1.で言う「マッチしたルールとデータのカップルを列挙」したリストに登録されるということ) […]

タイトルとURLをコピーしました