Lust auf ein kleines Denkspiel?
-
Hallo!
Ich habe mir eine kleine Denkaufgabe überlegt, welche man auch gut programmieren kann. Ich nenne sie "Kampf gegen Entropie".Man stelle sich einen Kreis aus einer geraden Anzahl von Punkten vor. Jeder dieser Punkte kann entweder blau oder grün sein (:(, :p). Die Reihenfolge der Punkte wird gewürfelt, wobei zu beachten ist, dass die Anzahl der grünen Punkte gleich der der blauen ist. Nun soll den Punkten der Auftrag gegeben werden, sich möglichst geordnet im Kreis aufzustellen, sodass keine zwei gleichfarbigen Punkte nebeneinander stehen. Das Problem dabei ist, dass die Punkte eine sehr schlechte Sehkraft besitzen, mit der sie gerade mal ihre Nachbarn erkennen können.
Jeder Punkt kommt der Reihe nach dran und kann sich dann entscheiden, ob er die Position mit einem seiner Nachbarn tauschen will. Hat ein Punkt mit dem Nachbarn getauscht, der als nächstes an der Reihe gewesen wäre, darf er noch einmal tauschen.Es gibt ein Paar Ansätze, die bei kleiner Punktezahl nur bei bestimmter Anordnung funktionieren und bei anderer Reihenfolge in einer Endlosschleife enden. Gesucht ist aber ein Algorithmus, der bei jeder Anordnung funktioniert.
Ich bin nach einiger Zeit des Rumprobierens zu einer Lösung gekommen, mit der sich 100 Punkte in 9 - 15 Durchläufen richtig anordnen. Ich bin mal gespannt ob jemand bessere Werte bekommt.
Viel Spass!
-
Gibt es ein Gedaechtnis? Weiss ein Punkt, ob und mit wem er im letzten Durchgang getauscht hat? Falls Nein: Weiss ein Punkt, ob er gerade eben an einem Tausch beteiligt war (also ob er ein Punkt ist, der zum zweiten Mal hintereinander dran kommt, da er in Durchlaufreihenfolge getauscht hat)?
Koennen die Punkte untereinander kommunizieren? Ich nehmen Mal an, Kommunikation ueber die lokale Farbverteilung ist ausgeschlossen. Aber was ist mit Kommunikation, ob Punkte die Position getauscht haben?
-
klingt spannend.
-
Also ich habe es so einfach wie möglich gehalten. Ein bool Array welches druchlaufen wird und für jedes i als Infos i - 1 und i + 1 zur Verfügung stehen und wenn das i + 1 oder i - 1 über das Array hinausgehen werden sie durch 0 bzw max i ersetzt, damit es eine Kreisform hat. Ich habe kein Gedächtnis oder ähnlichs verwendet. Ist auf jeden Fall eine interessante Idee. Solange es nicht gegen die Regel verstößt, dass ein Punkt beim Fällen der Entscheidung nur die Farbe seiner beiden Nachbarn sieht, ist alles erlaubt. Er kann auch nur mit den Nachbarn tauschen, die er sieht. Ich bin mal gespannt auf die Lösungswege, auf die du mit deinen kreativen Ideen kommst
-
Bakkaa schrieb:
Ich bin nach einiger Zeit des Rumprobierens zu einer Lösung gekommen, mit der sich 100 Punkte in 9 - 15 Durchläufen richtig anordnen. Ich bin mal gespannt ob jemand bessere Werte bekommt.
Wirklich fuer jede Anordnung? Ich meine, es ist einfach einen Algorithmus anzugeben, der eine durchschnittliche Anordnung in wenigen Schritten mischt* (in dem Sinne, dass er perfekte 1-0 Ordnung herstellt). Aber mischt er auch eine Anordnung, wo am Anfang alle Punkte einer Farbe auf einer Seite sind?
Da 50/3=16 und du sagst, dass du mit 15 Durchlaeufen auskommst, habe ich schon eine Ahnung, wie du vorgehst. Aber das wuerde im Fall kompletter Ordnung bedeuten, dass irgendeine Art von Kommunikation notwendig ist, damit ein Punkt feststellen kann, ob er richtig ist. Ohne Kommunikation waere die "Schallgeschwindigkeit" naemlich eine Position pro Durchlauf, mit der sich die Information fortpflanzen kann. Einzelne Punkte koennen zwar auch mit "unendlicher" Geschwindigkeit vorwaerts tauschen, aber ohne irgendeinen Gedaechtnis- oder Kommunikationseffekt wuerden sie einfach so lange weiter laufen, bis die lokalen Gegebenheiten sich aendern, anstatt am richtigen Platz anhalten zu koennen.
Koennen Punkte ihrer momentanen Position eine Zahl zuordnen? Sprich: Wissen sie, wo sie sind?
*: Der Algo waere, dass er mit seinem Nachfolger tauscht, dann und nur dann, wenn sein Vorgaenger die gleiche Farbe wie er selbst hat und sein Nachfolger eine andere Farbe als er selbst hat. Das mischt die zufaellige Durchschnittskonfiguration in wenigen Schritten (ca. 4-7 bei Groesse 100), hat aber Schwierigkeiten mit dem worst-case.
-
Bakkaa schrieb:
Das Problem dabei ist, dass die Punkte eine sehr schlechte Sehkraft besitzen, mit der sie gerade mal ihre Nachbarn erkennen können.
Und sich selbst?
-
Meine Tipp:
"Wenn die beiden Nachbarn ungleicher Farbe sind, dann tausche mit dem linken Nachbarn."
Soweit ich gerade sehe, müßte das garantieren, daß ein Durchlauf reicht.
-
volkard schrieb:
Meine Tipp:
"Wenn die beiden Nachbarn ungleicher Farbe sind, dann tausche mit dem linken Nachbarn."
Soweit ich gerade sehe, müßte das garantieren, daß ein Durchlauf reicht.Nein, das ist äquivalent zu meinem Vorschlag und braucht für ein vollständig geordnetes System ebenfalls (Systemgröße/4) Durchläufe. Oder ich verstehe dich gerade falsch.
-
SeppJ schrieb:
volkard schrieb:
Meine Tipp:
"Wenn die beiden Nachbarn ungleicher Farbe sind, dann tausche mit dem linken Nachbarn."
Soweit ich gerade sehe, müßte das garantieren, daß ein Durchlauf reicht.Nein, das ist äquivalent zu meinem Vorschlag und braucht für ein vollständig geordnetes System ebenfalls (Systemgröße/4) Durchläufe. Oder ich verstehe dich gerade falsch.
Hab die Aufgabe falsch gelesen.
"Hat ein Punkt mit dem Nachbarn getauscht, der als nächstes an der Reihe gewesen wäre, darf er noch einmal tauschen."
las ich als
"Hat ein Punkt mit einem Nachbarn getauscht, darf er noch einmal tauschen."
-
SeppJ schrieb:
Wirklich fuer jede Anordnung?
Nein. Ich habe das mit dem Durchschnittswert nicht so genau genommen. Einfach ein paar mal eine zufällige Anordnung durchlaufen lassen und das höchste war 15. Desto größer die Gruppen gleichfarbiger Punkte sind, desto mehr Schritte braucht mein Algorithmus. Aber ich habe ja auch geschrieben, dass die Anordnung gewürfelt wird und daher die Wahrscheinlichkeit gegen Null geht, dass größere Gruppen entstehen.
SeppJ schrieb:
Aber mischt er auch eine Anordnung, wo am Anfang alle Punkte einer Farbe auf einer Seite sind?
Bei einer solchen Anordnung ist es, glaube ich, gar nicht möglich weniger als 50 Schritte zu brauchen. Es wäre trotzdem mal interessant deine Ansätze umgesetzt zu sehen.
volkard schrieb:
Und sich selbst?
Sie wissen auch ihre Farbe.
volkard schrieb:
Meine Tipp:
"Wenn die beiden Nachbarn ungleicher Farbe sind, dann tausche mit dem linken Nachbarn."
Soweit ich gerade sehe, müßte das garantieren, daß ein Durchlauf reicht.Genau das war auch mein erster Ansatz. Der führte jedoch bei den meisten Anordnungen zu einer Endlosschleife, die nie die richtige Ordnung erreicht.
SeppJ schrieb:
Koennen Punkte ihrer momentanen Position eine Zahl zuordnen? Sprich: Wissen sie, wo sie sind?
Nein das wäre doch zu einfach. Dann müsste ja jeder Punkt einer Farbe nur auf einer Position mit gerader Zahl stehenbleiben und umgekehrt. Gehen würde, dass ein Punkt sich merkt wieviele Schritte er schon gegangen ist.
Ich will die Regeln gar nicht viel genauer festlegen, da es sonst interessante Lösungswege verbieten würde, wie die von SeppJ mit intelligenten Punkten.
-
Bakkaa schrieb:
SeppJ schrieb:
Wirklich fuer jede Anordnung?
Nein. Ich habe das mit dem Durchschnittswert nicht so genau genommen. Einfach ein paar mal eine zufällige Anordnung durchlaufen lassen und das höchste war 15. Desto größer die Gruppen gleichfarbiger Punkte sind, desto mehr Schritte braucht mein Algorithmus. Aber ich habe ja auch geschrieben, dass die Anordnung gewürfelt wird und daher die Wahrscheinlichkeit gegen Null geht, dass größere Gruppen entstehen.
Dann vermute ich mal, dass deine Lösung ungefähr dem von mir und volkard entspricht. Bei meinen Tests kam ich jedoch mit ungefähr der Hälfte aus.
SeppJ schrieb:
Aber mischt er auch eine Anordnung, wo am Anfang alle Punkte einer Farbe auf einer Seite sind?
Bei einer solchen Anordnung ist es, glaube ich, gar nicht möglich weniger als 50 Schritte zu brauchen. Es wäre trotzdem mal interessant deine Ansätze umgesetzt zu sehen.
Meiner und volkards Ansatz brauchen 25 Schritte.
SeppJ schrieb:
Koennen Punkte ihrer momentanen Position eine Zahl zuordnen? Sprich: Wissen sie, wo sie sind?
Nein das wäre doch zu einfach. Dann müsste ja jeder Punkt einer Farbe nur auf einer Position mit gerader Zahl stehenbleiben und umgekehrt. Gehen würde, dass ein Punkt sich merkt wieviele Schritte er schon gegangen ist.
Schade, du hast genau erfasst, worauf ich hinaus wollte
. Mit dem Merken hätte ich auch eine wilde Idee, aber es wird ca. 24 Stunden zum Testen brauchen und es ist nicht 100% klar, ob das wirklich gut ist. Ich versteife mich gerade vermutlich zu sehr auf den vollständig geordneten Fall.
-
'Ne Art Game of Life?
Hat sich für Bazillen auf Agar- Agar bereits als beschränkt hilfreich erwiesen, wie sich Bakterienkulturen verhalten, aber das war Ende der 70er.
Hier der Link: http://en.wikipedia.org/wiki/Conway's_Game_of_Life
-
SeppJ schrieb:
Dann vermute ich mal, dass deine Lösung ungefähr dem von mir und volkard entspricht. Bei meinen Tests kam ich jedoch mit ungefähr der Hälfte aus.
Zitat:Das ist seltsam. Denn eure Lösung war auch meine erste Idee aber sie hat nicht funktioniert und sich meist in einer Endlosschleife aufgehangen.
Kannst du mir nochmal genau schildern wie du und volkard es gemacht haben?Edit:
Ich hab den Fehler entdeckt jetzt komme ich aufs selbe Ergebnis.
