Algoritme Repte

Archiu:Rete.svg

Algoritme Repte

El algoritme Repte és un algoritme de reconeiximent de patrons eficient per a implementar un sistema de producció de regles. Va ser creat pel Dr. Charles L. Forgy en la Carnegie Mellon University. La seua primera referència escrita data de 1974, i va aparéixer de forma més detallada en la seua tesis doctoral (en 1979) i en un artícul científic de 1982. Repte és hui en dia la base de molts sistemes experts molt famosos, incloent CLIPS, Jess, Drools, i Soar.

Ventages

Una implementació simple d'un sistema expert basat en regles comprovaria cada regla en els fets de la base de coneiximent activant la regla si correspon, i passant a evaluar la següent. Este algoritme, inclús per a un número baix de regles i fets, té un temps d'eixecució molt alt (fent-ho inadequat per a sistemes de producció reals).

L'algoritme Repte (la pronunciació del qual sol ser 'REET', 'REE-tee' o, en Europa, 're-tay' que ve de la seua pronunciació en llatí, ya que 'repte' significa ret en llatí) és la base de diverses implementacions més eficients de sistemes experts. Un sistema expert basat en Repte construïx una ret de nodos, a on cada u d'ells (llevat el nodo raïl) representa un patró que apareix en la part esquerra (el condicional) d'una regla. Per lo tant, el camí des del nodo raïl a una full definix la part condicional sancera d'una regla. Cada nodo té una memòria de fets que satisfan el seu patró. Esta estructura és, bàsicament, un Trie.

A mida que s'afigen o modifiquen fets, es propaguen els canvis per la ret, fent que els nodos que s'activen en el patró s'activen. Quan un fet o un conjunt d'ells fa que tots els patrons d'una regla se satisfacen, s'aplega a un nodo full i la regla és activada.

Bàsicament, l'algoritme Repte sacrifica memòria per a incrementar velocitat de processament. En la majoria dels casos l'increment de velocitat comparat en l'implementació simple és de varis órdens de magnitut (perque teòricament el rendiment de Repta és independent del número de regles del sistema). En sistemes experts molt grans, no obstant, Repte sol presentar problemes per la seua gran cantitat de consum memòria. Existixen atres algoritmes tant basats en ell com a independents, que necessiten menys memòria.

Referències

• 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, "Repte: A Fast Algorithm for the Many Pattern/Many Object Pattern Match Problem", Artificial Intelligence, 19, pp 17-37, 1982