Board Assembly mit Einschränkungen
Ich mache dieses Problem, aber ich bin völlig neu in Prolog und ich habe keine Ahnung, wie es geht.
Neun Teile einer elektronischen Platine haben eine quadratische Form, die gleiche Größe und jede Kante jedes Teils ist mit einem Buchstaben und einem Plus- oder Minuszeichen gekennzeichnet. Die Teile müssen zu einer vollständigen Platine zusammengebaut werden, wie in der Abbildung unten gezeigt, so dass die gemeinsamen Kanten den gleichen Buchstaben und die entgegengesetzten Zeichen haben. Schreiben Sie einen Planer in Prolog, so dass das Programm "assemble" als die Abfrage ausführt und ausgibt, wie die Teile zusammengesetzt werden, d. H. Die Positionen und Positionen der Teile bestimmen wr.t. die aktuellen Positionen, so dass sie zusammen passen, um das komplette Brett zu machen.
Ich habe versucht, es zu lösen, und ich habe die folgenden Klauseln geschrieben:
%Vor%Ich weiß nicht einmal, ob sie richtig sind und ich bin nicht sicher, wie ich weiter vorgehen soll, um dieses Problem zu lösen.
3 Antworten
In Bezug auf die Leistung ist das Folgende kein Anwärter auf die sehr schnelle Lösung von @ false.
Ich möchte Ihnen jedoch eine andere Möglichkeit vorstellen, dies zu formulieren, so dass Sie den Constraint-Solver verwenden können, um die schnellere Zuweisungsstrategie zu approximieren, die @false manuell gefunden hat:
%Vor%Sie können jetzt die "First Fail" -Strategie von CLP (FD) verwenden und zuerst die am meisten eingeschränkten Elemente ausprobieren. Mit dieser Formulierung wird die Zeit benötigt, um alle 8 Lösungen zu finden:
%Vor%Außerdem möchte ich den folgenden Kandidaten für den Speed Contest anbieten, den ich mit einer ausführlichen Teilbewertung des ursprünglichen Programms erhalten habe:
%Vor%Die 8 Lösungen sind mit dieser Formulierung sehr schnell gefunden:
%Vor% Dies ist nur eine kleine Verbesserung für die schöne Lösung von @mat. Die Idee ist, den Etikettierungsprozess zu überdenken. Das ist maplist(board_piece,Board,Ps) was (halbprozedural) liest:
Für alle Elemente in
Ps, also für alle Teile in dieser Reihenfolge: Nimm ein Stück und lege es irgendwo auf das Brett gedreht oder nicht.
Dies bedeutet, dass jede Platzierung in voller Freiheit erfolgen kann. Um Ihnen eine schwache Reihenfolge zu zeigen, könnte man nehmen: A1,A3,C1,C3,B2 und dann den Rest. Auf diese Weise werden die tatsächlichen Einschränkungen nicht sehr ausgenutzt.
Es scheint jedoch keinen guten Grund zu geben, dass die zweite Kachel nicht in unmittelbarer Nähe zur ersten gelegt wird. Hier ist eine solche verbesserte Reihenfolge:
%Vor%Jetzt bekomme ich
%Vor% und ohne das Ziel maplist(maplist(tile), Board),
und alle Lösungen aufzählen
%Vor%zuvor (@ mats Originalversion) hat die erste Lösung genommen:
%Vor%und alle Lösungen:
%Vor%