Hallo Leute,
guckt euch bitte erstmal 10 Sekunden lang diese Seite an http://logic.stanford.edu/intrologic/ex ... 02_02.html.
Ich habe ein kleines Programm geschrieben http://www.python-forum.de/pastebin.php?mode=view&s=301, das durch Bruteforce alle denkbaren "Welten"/"Freundschaftskombinationen" für den angegebenen Satz von Vorschriften findet. In diesem Fall sind alle Lösungen bereits unten angegeben aber es gibt auch komplizierte Vorschriftensätze für die man entsprechende
Welten so bruten kann.
Eine spezielle Frage hätte ich: Gibt es eine andere Möglichkeit die like_combs zusammenzustellen?
Ansonsten sind jegliche Anmerkungen willkommen.
SororityWorld
-
BlackJack
@derrick: Statt brute force durch *alle* Kombinationen zu gehen, könnte man das ganze als Suchbaum auffassen und Zweige bei denen eine Bedingung verletzt ist, gar nicht erst weiterverfolgen. Stichwort „branch and bound”.
Man könnte das Problem auch als Graph sehen mit den Personen als Knoten und erst einmal eine Kante von jedem Knoten zu jedem anderen erstellen, inklusive einer Kante von jedem Knoten zu sich selbst. Jetzt kann jede dieser Kanten vorhanden oder nicht vorhanden sein (oder „an” oder „aus”), und man könnte alle Kombinationen die Kanten an- oder auszuschalten durchprobieren und jeweils die Bedingungen testen. Das ist im Grunde das was Dein Programm macht.
Da es aber feste Regeln für einige Kanten gibt, die für *jede* gültige Lösung gelten, kann man diese vor dem Durchprobieren aussortieren. Zum Beispiel kann man alle Kanten streichen, die von einem Knoten zu sich selbst führen, weil sich ja niemand selbst mag. Genau so kann man mit den „1:1 nicht mögen”-Beziehungen verfahren (Dana↔Abby). Und die „1:1 mögen”-Beziehung(en) kann man als Kante festschreiben die *immer* da sein muss. Dann braucht man nur noch die verbleibenden Kantenkombinationen durchtesten. Wobei man auch dort wieder „branch and bound” anwenden könnte.
Man könnte das Problem auch als Graph sehen mit den Personen als Knoten und erst einmal eine Kante von jedem Knoten zu jedem anderen erstellen, inklusive einer Kante von jedem Knoten zu sich selbst. Jetzt kann jede dieser Kanten vorhanden oder nicht vorhanden sein (oder „an” oder „aus”), und man könnte alle Kombinationen die Kanten an- oder auszuschalten durchprobieren und jeweils die Bedingungen testen. Das ist im Grunde das was Dein Programm macht.
Da es aber feste Regeln für einige Kanten gibt, die für *jede* gültige Lösung gelten, kann man diese vor dem Durchprobieren aussortieren. Zum Beispiel kann man alle Kanten streichen, die von einem Knoten zu sich selbst führen, weil sich ja niemand selbst mag. Genau so kann man mit den „1:1 nicht mögen”-Beziehungen verfahren (Dana↔Abby). Und die „1:1 mögen”-Beziehung(en) kann man als Kante festschreiben die *immer* da sein muss. Dann braucht man nur noch die verbleibenden Kantenkombinationen durchtesten. Wobei man auch dort wieder „branch and bound” anwenden könnte.
@BlackJack danke für deinen Hinweis auf Branch and Bound ich habe das jetzt mal versucht umzusetzen http://www.python-forum.de/pastebin.php?mode=view&s=302, die Laufzeit hat sich bei mir etwa gedrittelt. Nochmals die Nachfrage ob das mit den like_combs also den Möglichen Freundschaftsbeziehungen einer einzelnen Person anders zu lösen ist.