Was ist die optimale „allgemeinste Einiger“ Algorithmus?

Question

Die Frage

Was ist der effizienteste MGU-Algorithmus? Was ist die Zeitkomplexität? Ist es einfach genug, um als Stapelüberlauf Antwort zu beschreiben?

Ich habe versucht, die Antwort auf Google zu finden, aber privat .pdfs halten zu finden, was ich kann nur den Zugriff über ein ACM-Abonnement.

Ich fand eine Diskussion in SICP:

War es hilfreich?

einreichen

Lösung

Die einfache algorith, die in der Praxis verwendet wird (beispielsweise in Prolog) exponentiell für pathologische Fälle.

Es gibt einen theoretisch effizienten Algorithmus von Martelli und Montanari (IIRC ist es linear), aber es ist viel langsamer für die einfachen Fälle, die in der Praxis auftreten, so wird es nicht verwendet viel.

Answer 1

Die einfache algorith, die in der Praxis verwendet wird (beispielsweise in Prolog) exponentiell für pathologische Fälle.

Es gibt einen theoretisch effizienten Algorithmus von Martelli und Montanari (IIRC ist es linear), aber es ist viel langsamer für die einfachen Fälle, die in der Praxis auftreten, so wird es nicht verwendet viel.

Answer 2

Baader und Snyder mehrere Einigungs Algorithmen veröffentlicht, sowohl syntaktische Vereinigung und equational Vereinigung.

Sie stellen fest, dass ihr dritte syntaktischer Unifikationsalgorithmus (in Abschnitt 2.3) in O läuft (n alpha (n)), wobei alpha (n) ist die inverse Ackermann-Funktion -. In praktischen Situationen ist es gleichbedeutend mit einem kleinen konstanten