Expandierender Nebel: Problem in zellulären Automaten oder Codierungstheorie

Erster Beitrag zu Math Stackexchange. Kürzlich wurde ich mit einer mathematisch intensiven Herausforderung in der Computerprogrammierung konfrontiert, bei der ich völlig ratlos bin, sie zu lösen. Um Ihnen einige Informationen zu meinem mathematischen Hintergrund zu geben, ich bin Physik-Hauptfach und Informatik-Nebenfach an der Universität und habe kürzlich einen Kurs in linearer Algebra abgeschlossen, zusätzlich zu Calc 1, 2, Multivariate Calc und Diff Eq. Ich habe einige kleine Erfahrungen mit diskreter Mathematik und Zahlentheorie aus einem Einführungskurs in die Informatik. Ich habe Kurse zu linearer Algebra, diskreter Mathematik und algebraischer Codierung durchgeführt, die in den nächsten 6 Monaten geplant sind, bin mir aber nicht sicher, ob ich das Material zur Beantwortung meines Problems behandeln werde. Ich würde warten, bis ich die Kurse besucht habe, um zu sehen, ob ich etwas Neues darauf anwenden kann, aber dieses Problem hat mich verrückt gemacht.

Ich suche nicht unbedingt nach einer Lösung, sondern nach einigen Bereichen, die ich untersuchen kann, die mir bei der Lösung helfen können. Wenn weitere Informationen oder Erklärungen benötigt werden, lassen Sie es mich bitte wissen. Das Problem ist wie folgt:

Aus den Scans des Nebels haben Sie herausgefunden, dass er sehr flach und in einzelne Flecken verteilt ist, sodass Sie ihn als 2D-Gitter modellieren können. Sie stellen fest, dass das aktuelle Vorhandensein von Gas in einer Zelle des Gitters genau durch die 4 benachbarten Zellen bestimmt wird, insbesondere (1) diese Zelle, (2) die Zelle darunter, (3) die Zelle rechts davon, und (4) die Zelle darunter und rechts davon. Wenn im aktuellen Zustand genau 1 dieser 4 Zellen im 2x2-Block Gas hat, dann wird sie auch im nächsten Zustand Gas haben. Andernfalls ist die Zelle im nächsten Zustand leer.

Nehmen wir zum Beispiel an, der vorherige Zustand des Gitters (p) war:

.O..
..O.
...O
O...

Um zu sehen, wie sich dieses Gitter im nächsten Zeitschritt zum aktuellen Gitter (c) ändert, betrachten Sie die 2x2-Zellenblöcke um jede Zelle herum. Von dem 2x2-Block von [p[0][0], p[0][1], p[1][0], p[1][1]] hat nur p[0][1] Gas drin it, was bedeutet, dass dieser 2x2-Block im nächsten Zeitschritt zur Zelle c[0][0] mit Gas werden würde:

.O -> O
..

Ebenso im nächsten 2x2-Block rechts, bestehend aus [p[0][1], p[0][2], p[1][1], p[1][2]], zwei der enthaltenden Zellen haben Gas, also wird c[0][1] im nächsten Zustand des Gitters KEIN Gas haben:

O. -> .
.O

Wenn man diesem Muster bis zu seinem Abschluss folgt, wird der aktuelle Zustand des Gitters c aus dem vorherigen Zustand p sein:

O.O
.O.
O.O

Beachten Sie, dass die resultierende Ausgabe 1 Zeile und Spalte weniger hat, da die unterste und ganz rechte Zelle keine Zelle darunter bzw. rechts davon hat.

Schreiben Sie eine Funktion answer(g), wobei gein Array von booleschen Werten ist, die angeben, ob in jeder Zelle Gas vorhanden ist (der aktuelle Scan des Nebels), und geben Sie ein int mit der Anzahl möglicher vorheriger Zustände zurück, die nach 1 Zeitschritt zu diesem Gitter geführt haben könnten . Wenn der Funktion beispielsweise der cobige aktuelle Zustand gegeben würde, würde sie ableiten, dass die möglichen vorherigen Zustände p(oben angegeben) sowie ihre horizontalen und vertikalen Reflexionen waren, und würde 4 zurückgeben. Die Breite des Gitters liegt zwischen 3 und 50 einschließlich, und die Höhe des Rasters liegt zwischen 3 und 9 einschließlich. Die Antwort wird immer weniger als eine Milliarde (10^9) sein.

Inputs:
(boolean) g = [
                [true, false, true],
                [false, true, false],
                [true, false, true]
              ]
Output:
(int) 4

Inputs:
(boolean) g = [
                [true, false, true, false, false, true, true, true],
                [true, false, true, false, false, false, true, false],
                [true, true, true, false, false, false, true, false],
                [true, false, true, false, false, false, true, false],
                [true, false, true, false, false, true, true, true]
              ]
Output:
(int) 254

Inputs:
(boolean) g = [
                [true, true, false, true, false, true, false, true, true, false],
                [true, true, false, false, false, false, true, true, true, false],
                [true, true, false, false, false, false, false, false, false, true],
                [false, true, false, false, false, false, true, true, false, false]
              ]
Output:
(int) 11567

Ich habe mich mit der Codierungstheorie befasst, glaube aber nicht, dass dies in eine dieser Kategorien fällt. Ich habe Optionen in der Bildverarbeitung mit Bitmaskierung und zellularen Automaten untersucht. Am nächsten bin ich einer Lösung gekommen, als ich die zellularen 2D-Automaten in der Margolus-Nachbarschaft erforscht habe. Da dies per Definition nicht reversibel ist, habe ich keine Lösung oder gar allgemeine Methode gefunden, um eine Lösung zu finden. Ich bin nur neugierig, wo ich suchen soll. Ich weiß, dass dies eine Antwort aus einem Bereich der Mathematik sein muss, aber es ähnelt nichts, was ich derzeit weiß.

Wie soll der Wert answer(g) berechnet werden? Sie haben uns gesagt, was die Eingabe ist, aber nicht, was uns die Ausgabe sagen soll. Die Regeln für die Evolution sind ein bisschen wie Conways Game of Life, aber auf den ersten Blick sieht es so aus, als würde man sich diesem am ehesten durch bitweise Operationen auf binären Strings nähern.
Ich denke, das ist wirklich der Kern meines Problems. Ich habe die Aufgabe, die Funktion zu entwerfen. Fast alle Herausforderungen, die mir gestellt wurden, betrafen die Kombinatorik mit einigen Designproblemen und einer schwierigen Rekursionsbeziehung. Die Ausgabe ist die Anzahl möglicher vorheriger Zustände, die nach der gegebenen Nachbarschaftsregel zu dem gegebenen aktuellen Zustand führen. Ich habe eine Bearbeitung hinzugefügt. Es sieht so aus, als ob im ursprünglichen Beitrag ein Teil der Frage fehlte, der die Bedeutung der Ausgabe beschreibt und wie eine Lösung aussehen sollte. Hoffentlich hilft das.
Ich bin um ein paar Jahre zu spät zur Party :) Dieses Problem kann auf verschiedene Arten gelöst werden, was ich auch getan habe. Grundsätzlich empfehle ich, eine Brute-Force-Lösung zu schreiben. Dann optimieren. Und dann schauen Sie sich genau an, warum die Brute-Force-Methode unter größeren Gittern nicht abgeschlossen wird.

Antworten (1)

dies ist eindeutig eine Frage eines zellularen Automaten (CA). Es handelt sich um die Berechnung der Anzahl von Urbildern einer bestimmten CA-Regel der Größe 2x2 innerhalb eines endlichen rechteckigen Arrays. Überlegen Sie, wie Sie versuchen würden, solche Vorbilder zu konstruieren. Die Eingabe (aktuelle Konfiguration) ist ein Array der Größe NxM mit den Werten 0 und 1 (true und false, wenn Sie es vorziehen). Also haben die Urbilder (dh Konfigurationen einen Zeitschritt in der Vergangenheit) die Größe (N+1)x(M+1) auch mit den Werten 0 und 1. Was ist nun die lokale Evolutionsregel von einer Konfiguration zur nächsten? Es hat damit zu tun, dass die Werte von vier benachbarten Zellen den neuen Wert einer Zelle bestimmen. Versuchen Sie, ein kleines Beispiel von Hand zu machen, z. B. angesichts der 3x3-Eingabe g aus Ihrem Beitrag. Können Sie Schritt für Schritt alle vier Urbildkonfigurationen finden? Überlegen Sie, was es bedeutet, einige der Zellen im Preimage anzugeben (z

Im Allgemeinen ist das Auffinden von Urbildern von CAs (oder sogar das Bestimmen ihrer Anzahl) ein schwieriges Problem, aber im Fall von endlichen Konfigurationen und dieser spezifischen Evolutionsregel kann ein Computer damit umgehen. Es gibt einen Brute-Force-Algorithmus, der für die angegebenen Eingabegrößen gut funktionieren sollte, aber es gibt auch einen clevereren/aufwändigeren Algorithmus, um viel Zeit zu sparen, insbesondere wenn Ihre Eingabe ein ziemlich langes, aber schmales Rechteck ist.

Ich hoffe, diese Kommentare geben Ihnen einige Ideen, wie Sie das Problem angehen können. Wenn Sie weitere Details benötigen, lassen Sie es mich wissen.

Ok, also habe ich die obere Reihe der angegebenen 3x3-Matrix erweitert und bin zu einigen Schlussfolgerungen gekommen. Zeile (1 0 1) ergibt 8 Urbilder. (Ich habe versucht, sie hier aufzulisten, kann sie aber nicht richtig formatieren.) Beim Erweitern der nächsten Reihe ist mir aufgefallen, dass die korrekten Urbilder für die zweite Reihe ihre obere Reihe mit der unteren Reihe der Urbilder der ersten Reihe gemeinsam hatten. Sie "überlappen" Es scheint ziemlich entmutigend, einen Algorithmus zu schreiben, um die Urbilder einer Zeile zu finden und dann die Matrix hinunterzugehen, wobei nur Urbilder beibehalten werden, die sich "überlappen".
Aber im Kern ist es die richtige Idee.
Was die Dinge behandelbarer macht, ist, dass Sie etwas einrichten könnten, das als Transfermatrix bezeichnet wird. Die Idee ist, dass bei einer gegebenen Spalte (nimm die kürzere der beiden Seiten des Rechtecks) bestimmte Urbilder möglich sind. Diese haben die Form eines Rechtecks ​​der Breite 2 (dh zwei Spalten) und Sie könnten mögliche Urbilder für eine bestimmte Bildspalte in einem Array speichern. Für die nächste Spalte würden Sie nun deren Preimages nehmen und einfach vergleichen, welche zulässig sind, mit denen, die die vorherige Spalte erzeugt hat.
Da die Höhe Ihres Eingaberechtecks ​​nicht mehr als 9 Zellen beträgt, hat dieses Preimages-Array nicht mehr als 512 Einträge und der Algorithmus zum Durchlaufen von bis zu 50 Spalten sollte schnell genug sein, um die gewünschte Antwort zu liefern. (Es gibt noch mehr Tricks, um die Berechnung zu beschleunigen, aber beginnen Sie mit etwas Einfachem, Brute-Force-ish.) Und alle Schritte (dh Füllen der Matrix, Vergleichen von Überlappungen von Spalten usw.) können automatisch unter Verwendung von Unterroutinen durchgeführt werden.
Nun, sie ist nicht hübsch, aber ich habe ein funktionierendes Programm, um zumindest die mir gegebenen Testfälle zu lösen. Hoffentlich läuft es in angemessener Zeit, um komplexere Fälle zu lösen. Danke für die Inspiration und Ideen!
@MHS Hallo, die Transfermatrix-Methode ist eine gute Idee! Ich verwende die Methode, indem ich jede mögliche Preimage-Spalte als Knoten nehme, um den Graphen zu konstruieren. Das Ergebnis ist, dass, wenn das Gitter alles „falsch“ oder alles „wahr“ enthält, das Matrixergebnis gleich den Vorzustandszählungen ist. Aber wenn das Raster sowohl „false“ als auch „true“ enthält, ist das Matrixergebnis größer als der tatsächliche Pre-Zustand zählt, denn es gibt viele „Pfade“ mit denselben „Wanderungen“, die aber nicht von der ersten Urbild-Spalte oder dem Ende bis zum beginnen last preimage col oder "innere" Pfade. Hätten Sie einige Vorschläge zu dieser Bedingung? Danke schön!
Expandierender Nebel: Problem in zellulären Automaten oder Codierungstheorie
AntwortenHierDatenschutz-Bestimmungen1y, 0v