Ich habe mich gefragt, ob mir jemand bei diesem Problem helfen könnte: Ich muss eine Liste mit Prolog mit Constraing Logic Programming bestellen, und ich muss es auf die effizienteste Weise tun, die ich kann.
Also ist das Hauptprädikat, das ich definiert habe, das nächste:
%Vor%Die Implementierung jedes der vorherigen Hilfsprädikate ist wie folgt:
%Vor%Ich habe das Programm, das ich gemacht habe, bewiesen und es funktioniert! Aber ich weiß nicht, ob es möglich ist, die Effizienz zu verbessern, und wenn ja, wie kann ich das tun? (Ich habe dieser alte Thread hier). Sollte ich irgendwelche Einschränkungen hinzufügen oder ändern?
Danke!
Ihre Definition von same_length/2 wird nicht sehr oft beendet. Betrachten Sie stattdessen
gleichermaßen, mit library(lambda) verwenden
anstelle von
%Vor%Es scheint, dass Sie die Sortierung neu formulieren wollen, indem Sie zuerst angeben, dass die Liste geordnet ist und erst dann nach einer Permutation sucht. Unten funktioniert in SICStus, SWI, YAP.
%Vor%Bitte beachten Sie, dass die Argumente in perm / 2 jetzt ausgetauscht werden! Mit SWI:
%Vor% Als Zugabe habe ich einen Sortier-Generator für das Netzwerk für die Länge 10 ausgeführt und den Code portiert (das wurde mit der Option "best" generiert) zu Prolog / clpfd.
Hier kommt list_sorted__SN10/2 ( SN10 steht für "sorting network size 10"):
Mal sehen, ob es funktioniert:
%Vor%Wie wäre es in die andere Richtung zu gehen?
%Vor%Hast du Geschwindigkeit?
%Vor%Bekomme Geschwindigkeit!
Sortierlisten Xs mit length(Xs,10) ist nett, aber was ist, wenn ich längere oder kürzere habe?
Noch einmal, Netze sortieren zur Rettung!
Hier ist ein Prolog / clpfd-Port des Codes, der in bitonischem Sortiernetzwerk für n keine Macht von 2 ; Der Prolog-Code verwendet attributierte Variablen für den wahlfreien Lese- / Schreibzugriff der zu sortierenden Objekte. Wir verwenden ein Attribut value , das das Element zu dieser Zeit an dieser bestimmten Position speichert.
Die rekursive Aufteilung, die für die bitonische Sortierung erforderlich ist, wird durch den folgenden Code erreicht:
%Vor%Die innere Schleife der Vergleiche sieht so aus:
%Vor% Fast fertig! Eine Sache fehlt ... fdBitonicCompareTwo_/4 liest den i-ten und den j-ten Punkt und setzt das Minimum und Maximum auf den i-ten und j-ten Platz Die Richtung ist ascending . Wenn die Richtung descending ist, werden das Minimum und Maximum an den j-ten und i-ten Platz gesetzt:
Zuerst 10 Mal für jede Listenlänge zwischen 1 und 200 Zufallszahlen zwischen 1 und 10000 eingeben und sortieren. Schreie laut, wenn das Ergebnis anders ist als msort/2 liefert.
Als nächstes nehmen Sie Listen von 1 bis N (mit N =< Ub ), betrachten alle Permutationen und sehen, dass jede von ihnen einen Fehler in der bitonischen Sortierung zeigt (ein Ergebnis, das sich von dem unterscheidet, was msort/2 uns gibt) ).
Der Test wird auf zwei verschiedene Arten durchgeführt: after und before . after baut das Constraint-Netzwerk auf und dann bindet die FD-Variablen an konkrete Werte.
before macht es umgekehrt, effektiv clpfd als Integer-Arithmetik zu verwenden - alle Constraints werden sofort aufgelöst.
Lassen Sie uns test_fdBitonicSort/2 :
Lassen Sie uns das Prädikat erneut verwenden, diesmal mit der Grundeingabe:
%Vor%Es funktioniert! Gibt es mehr zu tun? Ja , definitiv !
Zuerst sollte ein spezieller Code wie list_sorted__SN10/2 für andere kleine Größen generiert werden. Zweitens könnte man verschiedene äquivalente Netzwerksortiermethoden auswerten.
Hier sind zwei Implementierungen, die clpfd verwenden. Beide sind den in früheren Antworten vorgestellten Varianten der "Permutationssorte" ähnlich. Beide Ausdrücke drücken jedoch "Permutation" nicht durch Verwendung von permutation/2 aus, sondern durch eine Kombination von element/3 und all_distinct/1 .
element/3 gibt an, dass die Elemente der sortierten Liste alle Mitglieder der ursprünglichen Liste sind. all_distinct/1 stellt sicher, dass die Element-Indizes sich alle voneinander unterscheiden.
Beispielabfrage:
%Vor%Was ist, wenn das zweite Argument bekannt ist und das erste unbekannt ist?
%Vor%So weit, so gut. Was passiert, wenn die zu sortierende Liste Duplikate enthält?
%Vor%Nun, das sind viele überflüssige Antworten! Können wir es besser machen?
Ja! Die redundanten Antworten in der obigen Abfrage können eliminiert werden, indem eine Einschränkung hinzugefügt wird, die benachbarte Elemente in der sortierten Liste und ihre jeweiligen Positionen in der ursprünglichen Liste in Beziehung setzt.
Die Einschränkung Z1 #= Z2 #==> N1 #< N2 besagt: "Wenn zwei benachbarte Elemente in der sortierten Liste gleich sind, müssen ihre Positionen in der ursprünglichen Liste geordnet werden."
Aber ... funktioniert es?
%Vor%Tags und Links list prolog order constraint-programming