Rete-algoritme

Overzicht van het Rete-algoritme.

Het rete-algoritme is een algoritme voor patroonmatching, gebruikt bij regelgebaseerde productiesystemen (expertsystemen). Het werd in 1979 ontwikkeld door Dr. Charles L. Forgy van de Carnegie-Mellon Universiteit. Het rete-algoritme wordt toegepast in veelgebruikte expertsystemen zoals OPS5, CLIPS, JESS en LISA.

Een eenvoudige implementatie van een expertsysteem zou elke productieregel kunnen vergelijken met alle feiten in de feitenverzameling van het expertsysteem, en deze proberen uit te voeren wanneer aan de condities van de productieregel voldaan zijn. Zelfs voor kleine feitenverzamelingen en kennisbanken is deze benadering veel te traag.

Het rete-algoritme (van het Latijnse rete, dat net, netwerk betekent) ligt aan de basis van een meer efficiënte implementatie: het algoritme bouwt een graaf op waarbij elke knoop (behalve de wortel) overeenkomt met een bepaald patroon in de condities van de productieregel. Het pad van de wortel tot een terminale knoop definieert een dergelijke (conjunctie van) condities. Elke knoop houdt in het geheugen de lijst van feiten bij die aan het patroon horend bij de knoop voldoen.