c++.de :: Logik-Rätsel maschinell lösen

Antoras Mitglied 20:37:16 14.05.2012 Titel:

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:

Code:
1 2 3 4 5 6 7 8	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:

Code:
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?

Mechanics Mitglied 20:44:24 14.05.2012 Titel:

Prolog. Da ist sowas schon optimiert.

SeppJ Moderator 20:50:27 14.05.2012 Titel:

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.

Antoras Mitglied 21:10:26 14.05.2012 Titel:

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

Code:
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.

Mechanics Mitglied 21:19:49 14.05.2012 Titel:

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?

Antoras Mitglied 21:22:05 14.05.2012 Titel:

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).

SeppJ Moderator 21:28:42 14.05.2012 Titel:

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.

Antoras Mitglied 21:42:03 14.05.2012 Titel:

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.

cooky451 Mitglied 21:53:33 14.05.2012 Titel:

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:

Code:
1 2 3 4 5 6 7 8 9	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.

nachtfeuer Moderator 22:07:47 14.05.2012 Titel:

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. ....... e/~algorithmus/algo14.php