Rete-Algorithmus

Rete-Algorithmus
Prinzipbild des Rete-Algorithmus

Der Rete-Algorithmus (rete, lat. für Netz oder Netzwerk) ist ein Algorithmus und Expertensystem zur Mustererkennung und zur Abbildung von Systemprozessen über Regeln. Er wurde vom US-amerikanischen Informatiker Charles Forgy im Rahmen seiner Doktorarbeit an der Carnegie Mellon University entwickelt bzw. die ihn 1979 zum Titel führen sollte.[1] Der Algorithmus ist frei, da das amerikanische Verteidigungsministerium bei seiner Erstellung hinreichend mit beteiligt war.

Inhaltsverzeichnis

Ziele des Algorithmus

Der Rete-Algorithmus wurde unter dem Gesichtspunkt entwickelt, eine sehr effiziente Regelverarbeitung zu gewährleisten.[2][3] Zudem können auch große Regelsätze noch performant behandelt werden. Bei seiner Entwicklung war er den bestehenden Systemen um den Faktor 3000 überlegen.

Einsatz und Variationen

RETE bildet heutzutage die Grundlage für viele Regelsysteme wie z. B. diverse Prolog-Interpreter oder sogenannte Business Rules Engines, etwa Drools[4], und hat sich für diese als De-facto-Standard etabliert.

Bislang gibt es zwei direkte Nachkömmlinge Rete II und Rete III. Beide sind ca. 50mal schneller als der ursprüngliche Ansatz. Rete III umfasst ein paar Erweiterungen, die seine Effizienz nochmals leicht erhöhen. Die Entwicklung war eng an die Plattform DEC XCON angelehnt und fand ihre Implementierung zunächst in OPS-Systemen, speziell in OPS2 bzw. später in OPS5. Einsparungen in Millionenhöhe wurden benannt. Das implementierte Regelwerk hatte im Endausbau ca. 10.000 Elemente.

Nachteile

Die hohe Geschwindigkeit des Algorithmus geht zu Lasten des genutzten Speichers.

Einzelnachweise

  1. Charles Forgy: Rete: A Fast Algorithm for the Many Pattern/Many Object Pattern Match Problem. In: Artificial Intelligence, vol. 19, pp. 17–37, 1982.
  2. www2.inf.fh-rhein-sieg.de/~pbecke2m/xps/regel2.pdf
  3. Lars Wunderlich: Java Rules Engines. Entwicklung von regelbasierten Systemen. Frankfurt/M.: entwickler.press 2006. ISBN 3-935042-75-2
  4. http://www.jboss.org/drools/

Wikimedia Foundation.

Игры ⚽ Нужно решить контрольную?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Algorithmus — Al Chwarizmi, der Namensgeber des Algorithmus, auf einer sowjetischen Briefmarke anlässlich seines 1200 jährigen Geburtsjubiläums. Ein Algorithmus ist eine aus endlich vielen Schritten bestehende eindeutige Handlungsvorschrift zur Lösung eines… …   Deutsch Wikipedia

  • Charles Forgy — Charles L. Forgy (* 12. Dezember 1949 in Texas) ist ein US amerikanischer Fachinformatiker. Forgy wurde bekannt aufgrund des von ihm entwickelten Rete Algorithmus. Dieser fand in OPS5 und anderen Produktionssystemen Anwendung, um Expertensysteme… …   Deutsch Wikipedia

  • Forgy — Charles L. Forgy (* 12. Dezember 1949 in Texas) ist ein US amerikanischer Fachinformatiker. Forgy wurde bekannt aufgrund des von ihm entwickelten Rete Algorithmus. Dieser fand in OPS5 und anderen Produktionssystemen Anwendung, um Expertensysteme… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”