Algoritmo Rete

El algoritmo Rete es un algoritmo de reconocimiento de patrones eficiente para implementar un sistema de producción de reglas. Fue creado por el Dr. Charles L. Forgy en la Carnegie Mellon University. Su primera referencia escrita data de 1974, y apareció de forma más detallada en su tesis doctoral (en 1979) y en un artículo científico de 1982. Rete es hoy en día la base de muchos sistemas expertos muy famosos, incluyendo CLIPS, Jess, Drools, y Soar.

Ventajas

Una implementación simple de un sistema experto basado en reglas comprobaría cada regla con los hechos de la base de conocimiento activando la regla si corresponde, y pasando a evaluar la siguiente. Este algoritmo, incluso para un número bajo de reglas y hechos, tiene un tiempo de ejecución muy alto (haciéndolo inadecuado para sistemas de producción reales).

El algoritmo Rete (cuya pronunciación suele ser 'REET', 'REE-tee' o, en Europa, 're-tay' que viene de su pronunciación en latín, dado que 'rete' significa red en latín) es la base de diversas implementaciones más eficientes de sistemas expertos. Un sistema experto basado en Rete construye una red de nodos, donde cada uno de ellos (excepto el nodo raíz) representa un patrón que aparece en la parte izquierda (el condicional) de una regla. Por lo tanto, el camino desde el nodo raíz a una hoja define la parte condicional entera de una regla. Cada nodo tiene una memoria de hechos que satisfacen su patrón. Esta estructura es, básicamente, un Trie.

A medida que se añaden o modifican hechos, se propagan los cambios por la red, haciendo que los nodos que se activan con el patrón se activen. Cuando un hecho o un conjunto de ellos hace que todos los patrones de una regla se satisfagan, se llega a un nodo hoja y la regla es activada.

Básicamente, el algoritmo Rete sacrifica memoria para incrementar velocidad de procesamiento. En la mayoría de los casos el incremento de velocidad comparado con la implementación simple es de varios órdenes de magnitud (porque teóricamente el rendimiento de Rete es independiente del número de reglas del sistema). En sistemas expertos muy grandes, sin embargo, Rete suele presentar problemas por su gran cantidad de consumo memoria. Existen otros algoritmos tanto basados en él como independientes, que necesitan menos memoria.

Referencias

Charles Forgy, "A network match routine for production systems." Working Paper, 1974.
Charles Forgy, "On the efficient implementation of production systems." Ph.D. Thesis, Carnegie-Mellon University, 1979.
Charles Forgy, "Rete: A Fast Algorithm for the Many Pattern/Many Object Pattern Match Problem", Artificial Intelligence, 19, pp 17-37, 1982

Datos: Q2002217