Ich kämpfe mich durch Künstliche Intelligenz: Ein moderner Ansatz , um meine natürliche Dummheit zu lindern. Beim Versuch, einige der Übungen zu lösen, bin ich auf das Problem "Who Owns the Zebra" gestoßen, Übung 5.13 in Kapitel 5 . Dies wurde ein Thema hier auf SO , aber die Antworten befassten sich hauptsächlich mit der Frage " Wie würdest du das lösen, wenn du eine freie Auswahl an Problemlösungssoftware hättest? "
Ich akzeptiere, dass Prolog eine sehr geeignete Programmiersprache für diese Art von Problem ist, und es gibt einige gute Pakete, z. in Python, wie die Top-Antwort und auch Standalone zeigt. Leider hilft mir das alles nicht, wie es in dem Buch beschrieben ist.
Das Buch scheint darauf hinzuweisen, eine Reihe von dualen oder vielleicht globalen Einschränkungen zu erstellen und dann einige der genannten Algorithmen zu implementieren, um eine Lösung zu finden. Ich habe eine Menge Schwierigkeiten mit einer Reihe von Einschränkungen, die für die Modellierung des Problems geeignet sind. Ich studiere das alleine, also habe ich keinen Zugang zu einem Professor oder TA, um mich über den Buckel zu bringen - hier bitte ich um deine Hilfe.
Ich sehe wenig Ähnlichkeit mit den Beispielen in diesem Kapitel.
Ich war bestrebt, doppelte Einschränkungen zu erstellen und begann damit, 25 Variablen zu erstellen (das logische Äquivalent davon): nationality1 , nationality2 , nationality3 , ... nationality5 , pet1 , pet2 , pet3 , ... pet5 , drink1 ... drink5 usw., wo die Nummer die Position des Hauses anzeigt.
Dies ist zum Aufbau der unären Beschränkungen, z.B.
%Vor%Der Norweger lebt im ersten Haus:
Aber die meisten Einschränkungen sind eine Kombination von zwei solchen Variablen durch eine gemeinsame Hausnummer, z.B.
%Vor%Der Schwede hat einen Hund:
wobei n offensichtlich zwischen 1 und 5 liegen kann. Oder anders gesagt:
... was sich entschieden anders anhört als die "Liste der Tupel", die das Buch befürwortet:
%Vor%Ich suche nicht nach einer Lösung an sich; Ich bin auf der Suche nach einem Ansatz, um dieses Problem so zu modellieren, dass es mit dem Ansatz des Buches kompatibel ist. Jede Hilfe wird geschätzt.
Danke an alle für einige hilfreiche Informationen!
Der Hinweis, den ich wirklich brauchte, kam im Stau. Anstatt Nationalitäten, Haustiere usw. an Häuser zu vergeben (Variablen mit dem Namen country1 , country2 , pet1 , pet2 ), musste ich Häuser den Elementen der Domäne zuweisen! Beispiel:
Dies hat mir erlaubt, einfache Formulierungen für meine Einschränkungen zu finden, so:
%Vor%Ich bin noch nicht fertig (puttering in diesem nur Teilzeit), aber ich werde eine vollständige Lösung posten, sobald ich es ausarbeiten.
Update: Ungefähr zwei Wochen später habe ich eine funktionierende Lösung in Clojure gefunden:
%Vor%Das sind 292 Zeilen, aber da ist eine Menge Debug / Diagnose-Codierung drin. Alles in allem bin ich sehr glücklich darüber, eine relativ kurze Lösung in Clojure gefunden zu haben. Funktionale Programmierung für eine kleine Herausforderung gemacht, aber ich habe es geschafft, einen ziemlich konsistenten funktionalen Stil beizubehalten.
Kritik willkommen obwohl!
Für alle, die sich interessieren, hier ist die Lösung:
%Vor%Es gibt mehrere Bibliotheken zum Lösen von CSP:
Und es gibt viele mehr. Diese können zur effizienten Constraint-Lösung verwendet werden.
Wenn Sie andererseits Ihren allgemeinen Constraint-Solver implementieren möchten, sollten Sie einen CSP-Solver implementieren: Erstellen Sie einen Constraint-Graph, wobei die Knoten die Constraint-Variablen sind und die Verbindungen beschränken. Speichern Sie für jede Variable die mögliche Domäne, und erstellen Sie einen Benachrichtigungsmechanismus. Die Constraints werden benachrichtigt, wenn sich die zugehörigen Variablen ändern, und starten dann einen Propagierungsprozess: Indem Sie die aktuellen Werte der zugehörigen Variablen betrachten, reduzieren Sie die Domänen der möglichen Variablen.
Propagierungsbeispiel:
Es ist möglich, dass die Verbreitung nicht ausreicht. In diesem Fall wird eine Backtracking- / Backjumping-Suche verwendet: Wir versuchen, den Wert einer einzelnen Variablen auszuwählen, die Änderungen zu propagieren usw.
Dieser Algorithmus wird als ziemlich schnell betrachtet, obwohl er leicht zu verstehen ist. Ich habe eine Implementierung, die unseren speziellen Fall von Problemen sehr effizient löst.
Warnung: Ich bin mir nicht sicher, wonach Sie suchen, denn ich habe Künstliche Intelligenz: Ein moderner Ansatz , aber ich denke, was folgt ist trotzdem interessant.
Edi Weitz hat eine interessante Seite zu diesem Rätsel, mit erklärt Quelle in Common Lisp und andere Quellen in C ++ und Common Lisp ohne detaillierte Kommentare. Ich fand die C ++ - Quelle von Klaus Betzler besonders interessant (umformatiert):
%Vor%Alle Hinweise im Rätsel hinzufügen Einschränkungen. Ohne Einschränkungen ist jede Kombination möglich.
Was Sie also tun möchten, ist die Eliminierung . Dies ist der umgekehrte Ansatz von dem, was Sie in Ihren Beispielen verwendet haben. Hier ist wie:
Sie benötigen eine Matrix mit einer Zeile für jede Nationalität und eine Spalte für jedes Attribut boolean ("lebt in einem roten Haus", "lebt in einem blauen Haus "," hat einen Hund ", ...)
Jede Zelle in dieser Matrix sollte zunächst auf TRUE gesetzt werden.
Dann iterieren Sie durch die Liste von Einschränkungen und versuchen Sie, sie anzuwenden deine Matrix. Zum Beispiel der Hinweis "Der Engländer lebt in den roten Zahlen Haus. "setzt jede der Zellen in der "rotes Haus" Spalte zu FALSE außer für den einen auf Englisch Nationalitätenlinie.
Überspringe Hinweise, die sich auf Attribute beziehen das ist noch nicht abgeleitet. Zum Beispiel: "Der Winston Raucher besitzt Schnecken." - Nun, wenn es noch nicht bestimmt ist, wer Winston raucht oder wem Schnecken gehören, dann überspringen Sie diese Einschränkung für jetzt.
Dies ist übrigens auch, wie Sie Sudoku-Rätsel lösen und ähnliches.
Tags und Links artificial-intelligence constraints modeling