¿Qué es Rete?

El algoritmo Rete es un algoritmo de coincidencia de patrones diseñado por el Dr. Charles L. Forgy de la Universidad Carnegie Mellon. Rete es una palabra latina que significa red [1]. Es un algoritmo muy eficiente para coincidir hechos con los patrones en las reglas. Comprender el algoritmo Rete facilitará la comprensión de por qué escribir reglas de una manera es más eficiente que escribirlas de otra manera.

Reglas, Conjunto de Reglas y Hechos

Un conjunto de reglas no es más que una base de conocimiento que consta de una o más reglas comerciales (o simplemente reglas). Cada regla en el conjunto de reglas representa algún conocimiento. Las reglas suelen estar en forma de si-entonces o condición-acción. Como las reglas si-entonces son adecuadas para el algoritmo Rete, se llaman reglas Rete. Aquí hay una regla Rete simple

Si la edad > 60 entonces asignar estado = "Adulto mayor"

Donde si , entonces y asignar son palabras clave. La parte si representa la condición y la parte entonces representa la acción. Puede haber más de una condición y, en ese caso, las condiciones deben unirse con operadores lógicos. La parte entonces representa una o más acciones. Claramente, la regla de ejemplo anterior significa que si la edad de una persona es mayor de 60 años, entonces es un adulto mayor. Si queremos verificar si una persona es adulta mayor o no, necesitamos un dato que es la edad de la persona y este dato se llama hecho. A medida que aumenta el número de variables o definiciones únicas, también lo hace el número de hechos. Por ejemplo,

Si la edad > 60 e ingreso-anual < 12000 entonces asignar bono-mensual = 2000

Para ejecutar la regla anterior necesitamos dos datos o hechos: uno para la edad y otro para el ingreso-anual. Para verificar el bono de dos personas necesitamos dos pares de datos, y así sucesivamente. Este es un caso simple y en situaciones de la vida real podemos tener miles de hechos en los que la regla debe operar. Y también podemos tener miles de reglas diferentes.

Necesidad del Algoritmo Rete

Un conjunto completo de reglas debe ser proporcionado al motor de reglas para su posterior procesamiento. El motor de reglas empareja cada regla (es decir, condición) en el conjunto de reglas con los hechos dados para decidir si disparar (o ejecutar) la regla o no. Este proceso se llama proceso de coincidencia de patrones y se repite. En cada ciclo, la lista de hechos puede modificarse: nuevos hechos pueden agregarse a la lista o los hechos antiguos pueden eliminarse de la lista. Estos cambios pueden hacer que los patrones previamente insatisfechos se satisfagan. Además, durante cada ciclo, el conjunto de reglas satisfechas debe mantenerse y actualizarse. En la mayoría de los casos, las acciones de las reglas solo cambian algunos hechos en la lista. Esto se llama redundancia temporal. Si un motor de reglas verifica cada regla para dirigir la búsqueda de todos los hechos incluso si la mayoría de ellos no se modifican, entonces ralentizará el proceso. Esta computación innecesaria se puede evitar recordando lo que ya ha coincidido de ciclo a ciclo y luego calculando solo los cambios necesarios para los hechos recién agregados o eliminados. El algoritmo Rete hace este trabajo perfectamente.

Algoritmo Rete: Implementación

El algoritmo Rete se implementa construyendo una red de nodos. Está diseñado de tal manera que guarda el estado del proceso de coincidencia de ciclo a ciclo y vuelve a calcular los cambios solo para los hechos modificados. El estado del proceso de coincidencia solo se actualiza a medida que se agregan y eliminan hechos. Si los hechos agregados o eliminados son menos en número, entonces el proceso de coincidencia será más rápido.

El Ciclo de Inferencia

Cada regla tiene un ciclo de inferencia que consta de tres fases: coincidencia, selección y ejecución. En la fase de coincidencia, las condiciones de las reglas se emparejan con los hechos para determinar qué reglas deben ejecutarse. Las reglas cuyas condiciones se cumplen se almacenan en una lista llamada agenda para disparar. De la lista de reglas, se selecciona una regla para ejecutar o disparar. La estrategia de selección puede depender de la prioridad, recencia de uso, especificidad de la regla, u otros criterios. La regla seleccionada de la lista se ejecuta llevando a cabo las acciones en el lado derecho de la regla. La acción puede ser una afirmación, ejecutar una función definida por el usuario o incorporada o ejecutar una tabla de decisiones, o de otra manera. Tenga en cuenta que el motor de tablas de decisiones se utiliza para ejecutar tablas de decisiones.