Logik-Rätsel maschinell lösen
-
Hallo,
ich möchte meinem PC beibringen verschiedene Logikrätsel zu lösen. Ich wollte mit dem "Wiegeproblem" beginnen.
Darum geht es um mehrere Kugeln, die bis auf eine alle das gleiche Gewicht haben und man nur mit Hilfe einer Waage herausfinden soll welche dies ist. Ich möchte mehrere Wiegevorgänge vorgeben mit deren Hilfe die entsprechende Kugel gefunden werden kann. Ich habe mir mal folgendes Beispiel ausgedacht:
Es gibt 7 Kugeln von 1-7. Die 4 hat ein anderes Gewicht (schwerer oder leichter) Es wurde drei Mal gewogen mit folgendem Ergebnis: 3,4,2 > 1,7,6 3,5 < 4,2 2 = 7 Mehrere Kugeln, die auf einer Seite an einem Wiegevorgang beteiligt sind, sind mit einem Komma getrennt.
Man kann einfach folgern, dass 2 und 7 beim ersten Wiegevorgang herausgenommen werden können. Die 3 ist einmal leichter, einmal schwerer, also muss sie Normalgewicht haben. Übrig bleiben:
4 > 1 4 > 6 5 < 4
Da die 4 zu mehr als einer Kugel schwerer sein soll muss sie die schwerere Kugel sein.
Jetzt meine Frage? Wie löst man so etwas effizient per PC? Eine Brute-Force-Methode würde mir einfallen, aber bei mehreren hundert oder sogar tausend Kugeln, bzw. mehreren tausend Vergleichsvorgängen würde das vermutlich schnell nicht mehr ausreichen.
Kann mir jemand Algorithmen nennen, mit denen man solche Probleme effizient lösen kann?
-
Prolog. Da ist sowas schon optimiert.
-
Was genau möchtest du lösen? Allgemeine Logikprobleme? Da müsstest du zuerst einmal eine allgemeine Sprache entwickeln, um die Logikprobleme darin zu formulieren. Eventuell reicht schon die formale Logik als Sprache dafür, musst du mal erforschen. Diese Sprache musst du dann einem Computer beibringen und eine allgemeine Lösungsmethode dafür entwickeln. Ich glaube, das dürfte eines der ambitioniertesten Projekte sein, die jemals in diesem Forum vorgeschlagen wurden und damit schließe ich die zahlreichen "ich programmiere den WoW-Killer" mit ein (auf dem Gebiet ist es in letzter Zeit merkwürdig still geworden. Wo sind die MMORPG-Kids alle hin?).
Oder möchtest du speziell dein Kugelproblem lösen? Du hast es auf dem Papier doch längst gelöst, jetzt musst du nur noch deinen Algorithmus in der Programmiersprache deiner Wahl* in den Computer eintippen. Dazu wird es vermutlich helfen, wenn du deine Lösung mal so allgemein wie möglich formulierst, also für N Kugeln, von denen die M'te ein anderes Gewicht hat (M <= N), anstatt mit konkreten Zahlen.
*: Ja, Prolog wäre dafür eine interessante Wahl. Dann sieht man mal, dass es auch noch was anderes gibt, außer den imperativen Programmiersprachen.
-
Prolog kenne ich schon ein wenig. Ich würde es aber gerne selbst lösen und nicht Prolog das Lösen überlassen.
SeppJ schrieb:
Oder möchtest du speziell dein Kugelproblem lösen? Du hast es auf dem Papier doch längst gelöst, jetzt musst du nur noch deinen Algorithmus in der Programmiersprache deiner Wahl* in den Computer eintippen. Dazu wird es vermutlich helfen, wenn du deine Lösung mal so allgemein wie möglich formulierst, also für N Kugeln, von denen die M'te ein anderes Gewicht hat (M <= N), anstatt mit konkreten Zahlen.
Genau da hänge ich momentan. Mir will nicht einfallen wie ich meinem Programm beibringe alle Schlussfolgerungen selbst zu ziehen.
Konkret hänge ich gerade bei
4 > 1 4 > 6 5 < 4
Wie organisiert man das intern am besten, dass man effizient an diese Form kommt? Bisher habe ich für je eine Seite an ein Set gedacht, aus dem die Kugeln entfernt werden können, bei denen man sicher ist, dass sie sich nicht von den anderen unterscheiden. Bei so einem kleinen Problem ist das mit Sicherheit gut machbar, nur bei größeren Datensätzen stellt sich mir die Frage ob es nicht total ineffizient wird wenn man für jede ausgeschlossene Kugel über alle Sets iterieren muss um zu prüfen ob sie dort vorhanden ist um diese dann entfernen zu können.
-
Schau dir an, wie Prolog sowas implementiert, z.B. auf der englischen Wikipedia Seite. Das ist aber eine Lösung für allgemeine Probleme, wie man sie in Prolog eben formulieren kann. Oder geht es dir um die Optimierung dieses ganz konkreten Problems?
-
Hier geht es mir jetzt um die Optimierung. Also um eine Lösung, die möglichst gut passt (und nicht in erster Linie auf andere Probleme übertragbar ist).
-
Du könntest zuerst einmal feststellen, ob deine Fehlkugel leichter oder schwerer als die anderen ist. Dann kannst du danach nämlich die Lösung in O(log(N)) finden. Genauer gesagt ist das der Logarithmus zur Basis 3, da du dann bei jedem Schritt zwei Drittel der noch vorhandenen Kugeln ausschließen kannst (nach dem dir vermutlich bekannten Dreiteilungsmethode). Die Lösung dieses Problems mittels der Drittelungsmethode ist meines Wissens nach optimal. Auf jeden Fall ist eine logarithmische Laufzeitkomplexität sehr sehr gut.
Um herauszufinden, ob die Fehlkugel schwerer oder leichter ist, vergleichst du zuerst die eine Hälfte der Kugeln mit der anderen. Dann nimmst du die schwerere Hälfte und vergleichst wieder zwei Hälften von dieser Hälfte. Wenn diese beiden Viertel gleich schwer sind, dann muss die Fehlkugel in der leichteren Hälfte gewesen sein und muss daher leichter als die anderen sein und du kannst mit der leichteren Hälfte mit dem Drittelungsverfahren fortfahren. Stellst du jedoch fest, dass eines der viertel schwerer ist, dann muss die Fehlkugel in diesem schweren Viertel sein und sie muss schwerer als die anderen sein und du kannst hier fortfahren. Insgesamt verlierst du dadurch nicht sehr viele Schritte, da du nach diesem Test, der dich zwei Wiegevorgänge kostet, schon nur noch die Halfte bzw. ein Viertel der Kugeln hast.
Falls beim Halbieren Einzelkugeln übrig bleiben, so muss man sich diese noch gesondert ansehen.
Du könntest noch ausrechnen (oder auch durch explizites Ausprobieren, da das Problem doch sehr überschaubar ist), ab welcher Kugelmenge N es sich lohnt, am Anfang diesen Test zu machen. Ich schätze mal ab eine niedrigen zweistelligen Anzahl sollte sich das lohnen.
-
Der von dir genannte Algo kann doch aber nur eingesetzt werden, wenn bekannt ist ob eine Kugel schwerer oder leichter ist. Ich sehe aber nicht wie ich das bei meinem Problem herausbekomme. Ich möchte ja Wiegevorgänge vorgeben, die ich zwar analysieren kann, aber mit denen ich doch niemals genau herausbekomme was für ein Gewicht eine Kugel hat.
-
Könnte man die Menge nicht einfach in drei gleich große Teile a, b und c einteilen, und dann testen welche Menge zwei mal != einer anderen ist? (Und das dann rekursiv so lange wiederholen, bis eine Menge nur noch aus einem Element besteht. Also logisch rekursiv, eventuell trotzdem iterativ implementieren.)
Oder habe ich da einen Denkfehler? ("Überhängende" Kugeln testet man einfach einzeln, das sollte die Performance ja quasi nicht beeinflussen.)z.B. für 9 Kugeln:
a = {1, 2, 3}, b = {4, 5, 6}, c = {7, 8, 9} a != b a == c 4 != 5 4 != 6 -> 4
@SeppJ
Wie könnte man ein solches Problem in eine Formale Sprache (in ein Kalkül?) überführen, also wie könnte das aussehen? Jetzt haste mich ein bisschen neugierig gemacht, aber so konkrete Dinge findet man nicht im Netz.
-
Ich würde auch in Richtung Prolog tendieren, oder eben in Richtung Fuzzy Logic und natürlich mit den zugrunde liegenden Wertetabellen und Zahlentheoriegedönsen, bzw. Boolean Logik-Gedönsen. Da kann man manchmal ganz kirre werden, aber muß nicht erwarten, dass einem der Rechner das abnimmt, bevor mans hineingekodet hat. Also erst selber Wertetabellen erstellen, sacken lassen, coden.
Oder...vielleicht? http://www-i1.informatik.rwth-aachen.de/~algorithmus/algo14.php
-
Mechanics schrieb:
Prolog. Da ist sowas schon optimiert.
Du erwartest zu viel von Prolog.
-
Antoras schrieb:
Der von dir genannte Algo kann doch aber nur eingesetzt werden, wenn bekannt ist ob eine Kugel schwerer oder leichter ist. Ich sehe aber nicht wie ich das bei meinem Problem herausbekomme. Ich möchte ja Wiegevorgänge vorgeben, die ich zwar analysieren kann, aber mit denen ich doch niemals genau herausbekomme was für ein Gewicht eine Kugel hat.
Das ist doch genau deine Problembeschreibung, die du im ersten Beitrag gegeben hast.
Darum geht es um mehrere Kugeln, die bis auf eine alle das gleiche Gewicht haben und man nur mit Hilfe einer Waage herausfinden soll welche dies ist.
Genau dieses Problem habe ich angegangen. Bei meiner Lösung muss man niemals das genaue Gewicht der Fehlkugel kennen, es läuft alles über Vergleiche. Man bekommt das Gewicht auch gar nicht heraus, man bekommt nur heraus, welche Kugel nicht passt und (für große Kugelmengen), ob sie schwerer oder leichter als die anderen ist.
-
SeppJ, du solltest cooky antworten.
-
314159265358979 schrieb:
SeppJ, du solltest cooky antworten.
cooky451 schrieb:
@SeppJ
Wie könnte man ein solches Problem in eine Formale Sprache (in ein Kalkül?) überführen, also wie könnte das aussehen? Jetzt haste mich ein bisschen neugierig gemacht, aber so konkrete Dinge findet man nicht im Netz.Keine Ahnung, bin kein Informatiker. Ich dachte mir nur, dass das damit sicherlich möglich ist, da ich weiß, dass es existiert und zu so etwas gut ist.
Ich war jedenfalls schwer begeistert, als neulich jemand nach KI für allgemeine Spiele gefragt hat und ich mir erst einmal durchgelesen habe, wie man überhaupt Spielregeln so allgemein formulieren kann, dass man damit sowohl Schach als auch Poker beschreiben kann.
Hier ist der Thread:
http://www.c-plusplus.net/forum/303054
-
SeppJ schrieb:
Keine Ahnung, bin kein Informatiker. Ich dachte mir nur, dass das damit sicherlich möglich ist, da ich weiß, dass es existiert und zu so etwas gut ist.
Hm.. schade, vielleicht findet sich ja noch jemand. Von Wikipedia kann ich ableiten, wie man ein Alphabet und eine Grammatik aufstellt, über Axiome Sätze wie "es gibt ein x, sodass gilt blubb" aufstellen kann, daraus über Ableitungsregeln wieder neue Sätze bilden kann, aber wie man ein Problem formal formuliert, das würde mich ja wirklich interessieren. Wobei Spielregeln bei denen man gewinnen und verlieren kann ist doch quasi das Gleiche, das gucke ich mir mal an.
-
cooky451 schrieb:
SeppJ schrieb:
Keine Ahnung, bin kein Informatiker. Ich dachte mir nur, dass das damit sicherlich möglich ist, da ich weiß, dass es existiert und zu so etwas gut ist.
Hm.. schade, vielleicht findet sich ja noch jemand. Von Wikipedia kann ich ableiten, wie man ein Alphabet und eine Grammatik aufstellt, über Axiome Sätze wie "es gibt ein x, sodass gilt blubb" aufstellen kann, daraus über Ableitungsregeln wieder neue Sätze bilden kann, aber wie man ein Problem formal formuliert, das würde mich ja wirklich interessieren. Wobei Spielregeln bei denen man gewinnen und verlieren kann ist doch quasi das Gleiche, das gucke ich mir mal an.
Ähm. Du möchtest "Gödel Escher Bach" lesen.
-
SeppJ schrieb:
Um herauszufinden, ob die Fehlkugel schwerer oder leichter ist, vergleichst du zuerst die eine Hälfte der Kugeln mit der anderen. Dann nimmst du die schwerere Hälfte und vergleichst wieder zwei Hälften von dieser Hälfte.
Der erste Satz ist so weit ok. Am Beispiel 3,4,2 > 1,7,6 würde man rechts mit links vergleichen. Ich sehe jetzt nicht wie ich die schwere Hälfte unterteilen kann und wieder herausbekomme wie das Verhältnis zueinander ist. Woher kommt die Information wie 3,4,2 zueinander stehen? Die muss ich doch erst anhand der anderen Beispiele ermitteln. Oder habe ich deine Idee jetzt falsch verstanden?
-
Das Problem musst du selbst formulieren (in Prolog üblicherweise als Menge von Hornklauseln repräsentiert). Die Logik-Kalküle können dir dann Auskunft über Erfüllbarkeit etc. geben. Dazu gibt's auch einiges an Literatur ("Logik für Informatiker" von Schöning (bzw. Martin Kreuzer unter dem gleichen Titel)
Der Tipp von volkard ist überdies sehr nützlich (wenngleich ich das Buch in Teilen unnötig aufgebläht gefunden habe).
-
cooky451 schrieb:
z.B. für 9 Kugeln:
a = {1, 2, 3}, b = {4, 5, 6}, c = {7, 8, 9} a != b a == c 4 != 5 4 != 6 -> 4
Das ganze Ding nennt sich constraint programming. a,b,c sind deine Domains, gefolgt von den Nebenbedingungen. Geschicktes Suchen in Algorithmenform fuehrt dann zur Loesung.
Wobei Spielregeln bei denen man gewinnen und verlieren kann ist doch quasi das Gleiche, das gucke ich mir mal an.
Habe in meinem Seminar/Praktikum/whatever: General Game Playing http://www.eclipseclp.org/ benutzt, geht ganz gut. Nach diesen Stichworten im Netzt einfach suchen.
-
JFB schrieb:
Der Tipp von volkard ist überdies sehr nützlich (wenngleich ich das Buch in Teilen unnötig aufgebläht gefunden habe).
Ich habe geschwelgt. Und gelernt. Viel. Grandios…
Und erst die Hälfte kapiert. me silly.Ist aber definitiv kein Nachschlagewerk, was im Schrank stehen muss. Hälfte reicht ja. Vielleicht sollten wir einen GEB-Pool bilden. Man liest es meist nicht zweimal, fürchte ich. Und falls doch, kann man es ja nochmal ordern.
JFB hat anscheinend eins frei. Da ist es nur noch eine Sache des Portos.Ich mag mich noch noch trennen, weil es so geil war, und ich es eigentlich am nächsten Wochenende wieder anfangen will, und dann am nächsten, am nächsten, ein endloses Band.
edit: Vielleicht auch einen größeren Pool. TAOCP muß man auch lesen aber nicht stehen haben.