Newtonpedia EN
Inicio › Informática › Algoritmo Rete
Algoritmo Rete
Imagen: Wikimedia Commons
Informática · 1982

Algoritmo Rete

Algoritmo de reconocimiento de patrones que permite aplicar muchas reglas a muchos hechos de forma eficiente en los sistemas expertos.

Año
1982
Protagonistas
Charles Forgy
Sección
Informática

Historia

Los sistemas expertos son programas que toman decisiones a partir de una base de conocimiento formada por hechos y reglas del tipo «si se cumplen estas condiciones, entonces haz esto». El problema es que, con muchas reglas y muchos hechos, comprobar una a una cada regla frente a todos los hechos resulta extremadamente lento. El algoritmo Rete, ideado por Charles L. Forgy, ofrece una alternativa mucho más eficiente para resolver ese problema.

Antes de Rete, la forma habitual de aplicar reglas era la comprobación secuencial: se revisaba cada regla, se disparaba si sus condiciones se cumplían y se pasaba a la siguiente, volviendo al principio al terminar. Este método, aunque sencillo, se volvía impracticable incluso con bases de conocimiento de tamaño moderado. Forgy presentó la idea por primera vez en un documento de trabajo en 1974, la desarrolló en su tesis doctoral de 1979 en la Carnegie Mellon University y la publicó de forma detallada en un artículo de 1982.

La clave de Rete es construir una red de nodos en la que cada nodo, salvo la raíz, representa una condición que aparece en la parte izquierda de una regla, es decir, la parte que describe cuándo debe activarse. El camino desde la raíz hasta una hoja describe por completo las condiciones de una regla. Cada nodo guarda en memoria los hechos que cumplen su condición, de modo que, cuando se añade o modifica un hecho, solo se propagan los cambios por la red en lugar de volver a evaluar todo el conjunto. Cuando un hecho, o una combinación de ellos, satisface todas las condiciones de una regla, se alcanza una hoja y la regla se activa. Esta estructura es, en esencia, una variante generalizada de un trie, un árbol de búsqueda que comparte los prefijos comunes.

Rete intercambia memoria por velocidad. En la mayoría de los casos la mejora frente a la implementación ingenua es de varios órdenes de magnitud, ya que, en teoría, su rendimiento no depende del número de reglas. Sin embargo, en sistemas expertos muy grandes su consumo de memoria puede convertirse en un problema, y se han diseñado después otros algoritmos, basados en él o independientes, que requieren menos.

El algoritmo fue el núcleo del lenguaje de sistemas de producción OPS5, con el que se construyeron sistemas tempranos como R1 para Digital Equipment Corporation. Hoy sirve de base a motores de reglas muy conocidos como CLIPS, Jess, Drools o Soar, y a plataformas comerciales de decisiones empresariales. Su nombre procede del latín «rete», que significa red, término que también se usa en italiano moderno con ese mismo sentido.

Cronología

  • 1974Forgy publica por primera vez la idea en un documento de trabajo.
  • 1979Desarrolla el algoritmo en su tesis doctoral en la Carnegie Mellon University.
  • 1982Aparece el artículo científico que lo describe en detalle.

Curiosidades y anécdotas

El nombre

«Rete» significa red en latín. Según se cuenta, Forgy lo eligió por su uso en anatomía para describir una red de vasos sanguíneos y fibras nerviosas.

Otros hitos de informática