Ich habe ein Beispiel für naive Art gefunden, das in Prolog geschrieben ist, und ich versuche es zu verstehen:
%Vor%Naive_sort Call funktioniert korrekt, aber ich kann einfach nicht herausfinden warum. Das Hauptproblem ist die Permutation. Wenn es implizit aufgerufen wird, gibt es immer nur einen Wert zurück. Wie ist es dann möglich, dass im naive_sort Funktionsaufruf alle Permutationen überprüft werden? Wie könnte ich auch die Perm-Funktion ändern, um alle Permutationen zu schreiben?
Dies ist wirklich eine naive Art - es durchquert den Baum aller möglichen Permutationen, bis es glücklicherweise einen sortierten findet. Das ist eine Komplexität von O (n!) Ich nehme an: & gt;
Über die Permutationsfunktion - sie funktioniert "rückwärts" - beachten Sie, dass die Definition den Kopf aus dem Ergebnis entfernt. Wenn Sie Ihren Standpunkt umkehren, werden Sie bemerken, dass Sie Werte löschen, anstatt sie zu löschen, indem Sie rückwärts arbeiten. Da der Algorithmus rückwärts arbeitet, kann die H ead also alles sein, was es erlaubt, ein Ergebnis zu erzeugen, also einen unbenutzten Wert aus List.
Grundsätzlich wird der Permutationsalgorithmus in die folgende prozedurale Implementierung übersetzt:
Auf diese Weise erzeugen Sie Permutationen. Alle von ihnen.
Kurz gesagt - perm erzeugt den gesamten Raum möglicher Lösungen, indem er aus einer leeren Lösung heraus startet und prüft, wie die gegebene Lösung aus einem gültigen Löschen möglich ist.
%Vor%Das Hauptproblem ist die Permutation Funktion. Wenn es implizit aufgerufen wird es ruft immer nur einen Wert ab.
Prolog ist eine Sprache, die immer versucht, die Wahrheit einer Aussage zu beweisen, indem sie sie anhand der gegebenen Axiome (Fakten oder Regeln) ableitet.
perm ist keine Funktion im Sinne einer prozeduralen Programmierung. perm ist ein Prädikat, über das wir zwei Dinge erzählen:
List ist eine Permutation von [H|Perm] , wenn es eine Liste Rest gibt, so dass Rest erhalten wird, indem H von List gelöscht wird und Rest eine Permutation von Perm ist. Wenn gefragt wird, ob eine Liste eine Permutation eines anderen ist, wird prolog versuchen, diese Ableitungsschritte (rekursiv) anzuwenden, um es zu beweisen. Wenn diese Rekursion eine Sackgasse erreicht, d. H. Eine Anweisung, die nicht bewiesen werden kann, da keine Regeln auf sie angewendet werden können, rückt sie zurück.
Tags und Links prolog