Der synthetische Ansatz zur Umwandlung von Entscheidungstabellen

Frühere Ansätze zur Problematik der automatischen Umwandlung von Entscheidungstabellen in Computerprogramme basierten auf Zerlegung. In jedem Schritt wird eine Bedingung zur Überprüfung ausgewählt, und es werden zwei kleinere Probleme (Entscheidungstabellen mit einer Bedingung weniger) erstellt. Ein optimales Programm (in Bezug auf die durchschnittliche Ausführungszeit oder den Speicherplatz, zum Beispiel) wird nur durch implizite Enumeration aller möglichen Entscheidungsmöglichkeiten unter Verwendung einer Technik wie Branch-and-Bound gefunden. Der in diesem Papier beschriebene neue Ansatz verwendet dynamische Programmierung, um einen optimalen Entscheidungsbaum zu synthetisieren, aus dem ein Programm erstellt werden kann. Mit diesem Ansatz wird die Effizienz der Erstellung eines optimalen Programms erheblich gesteigert, was die Generierung optimaler Programme für Entscheidungstabellen mit bis zu zehn bis zwölf Bedingungen ermöglicht.