Münzwurf-Spiel: Optimierungsproblem
Es gibt ein rechteckiges Münzraster, wobei Köpfe durch den Wert 1 und Schwänze durch den Wert 0 dargestellt werden. Sie repräsentieren dies mit einer 2D-Integer-Array-Tabelle (zwischen 1 bis 10 Zeilen / Spalten einschließlich) / p>
Bei jeder Bewegung wählt man eine einzelne Zelle (R, C) im Gitter (R-te Reihe, C-te Spalte) und dreht die Münzen in allen Zellen (r, c), wobei r zwischen 0 und liegt R, einschließlich, und c ist zwischen 0 und C einschließlich. Das Umdrehen einer Münze bedeutet das Umkehren des Wertes einer Zelle von Null auf Eins oder Eins auf Null.
Geben Sie die Mindestanzahl an Moves ein, die erforderlich sind, um alle Zellen im Raster in Tails zu ändern. Dies wird immer möglich sein.
Beispiele:
%Vor%Das habe ich ausprobiert: Da die Reihenfolge des Umdrehens keine Rolle spielt und eine Bewegung auf einer Münze zweimal so ist, als würde man überhaupt keine Bewegung machen, können wir einfach alle eindeutigen Kombinationen von umwerfenden Münzen finden und die Größe von guten Kombinationen minimieren (gut gemeint diejenigen, die gib alle Schwänze).
Dies kann gemacht werden, indem ein Satz gemacht wird, der aus allen Münzen besteht, die jeweils durch einen Index dargestellt sind (d. h. wenn es insgesamt 20 Münzen gäbe, würde dieser Satz 20 Elemente enthalten und ihnen einen Index von 1 bis 20 geben). Dann machen Sie alle möglichen Teilmengen und sehen Sie, welche von ihnen die Antwort geben (d. H. Wenn eine Bewegung auf den Münzen in der Teilmenge uns alle Schwänze gibt). Schließlich minimieren Sie die Größe der guten Kombinationen.
Ich weiß nicht, ob ich mich zu deutlich ausdrücken konnte ... Ich poste einen Code, wenn du willst. Wie auch immer, diese Methode ist zu zeitaufwendig und verschwenderisch und nicht möglich für Münzen Nr. 20 (in meinem Code). Wie geht das?
5 Antworten
Ich denke, ein Greedy-Algorithmus genügt, mit einem Schritt pro Münze.
Jede Bewegung dreht eine rechteckige Teilmenge der Tafel um. Einige Münzen sind in mehr Teilmengen enthalten als andere: Die Münze bei (0,0) oben links ist in jeder Teilmenge, und die Münze rechts unten ist nur eine Teilmenge, nämlich diejenige, die jede Münze enthält.
>Also, die Wahl des ersten Zuges ist offensichtlich: Drehe jede Münze, wenn die untere rechte Ecke gewendet werden muss. Beseitigen Sie diese mögliche Bewegung.
Nun können die unmittelbaren Nachbarn der unteren rechten Münze, links und oben, nur durch einen einzigen verbleibenden Zug umgekippt werden. Also, wenn diese Bewegung ausgeführt werden muss, tun Sie es. Die Reihenfolge der Bewertung der Nachbarn spielt keine Rolle, da sie nicht wirklich Alternativen zueinander sind. Ein Rastermuster sollte jedoch ausreichen.
Wiederholen bis zum Ende.
Hier ist ein C ++ Programm:
%Vor%Nicht C ++. Stimmen Sie mit @Potatoswatter überein, dass die optimale Lösung gierig ist, aber ich habe mich gefragt, ob ein lineares diophantisches System auch funktioniert. Diese Mathematica-Funktion macht es:
%Vor%Wenn Sie mit Ihren Beispielen aufgerufen werden (-1 statt 0)
%Vor%Das Ergebnis ist
%Vor%Oder :)
Löst ein zufälliges 20x20-Problem in 90 Sekunden auf dem Laptop meines armen Mannes.
Im Grunde nehmen Sie die N + M-1-Münzen in den rechten und unteren Rand und lösen sie, dann rufen Sie den Algorithmus nur rekursiv auf alles andere auf. Das ist im Grunde, was Potatoswatter sagt. Unten ist ein sehr einfacher rekursiver Algorithmus dafür.
%Vor% Hinweis: Es ist wahrscheinlich sinnvoll, Grid.ShallowCopy zu implementieren, indem Sie einfach Solver Argumente für die Breite und die Höhe des Rasters haben. Ich habe es nur Grid.ShallowCopy genannt, um anzuzeigen, dass Sie keine Kopie des Gitters übergeben sollten, obwohl C ++ dies bei Arrays sowieso nicht tun wird.
Ein einfaches Kriterium für das zu spiegelnde Rechteck (x, y) scheint zu sein: genau dann, wenn die Anzahl der Einsen im 2x2 Quadrat mit dem oberen linken Quadrat (x, y) ungerade ist.
(Code in Python)
%Vor%Das zurückgegebene 2D-Array hat eine 1 in Position (x, y), wenn das Rechteck (x, y) umgedreht werden soll, also ist die Anzahl der Einsen die Antwort auf Ihre ursprüngliche Frage.
BEARBEITEN: Um zu sehen, warum es funktioniert: Wenn wir uns bewegen (x, y), (x, y-1), (x-1, y), (x-1, y-1), wird nur das Quadrat (x, y) invertiert. Dies führt zu dem obigen Code. Die Lösung muss optimal sein, da es 2 ^ (h w) mögliche Konfigurationen der Platine und 2 ^ (h w) Möglichkeiten gibt, die Platine zu transformieren (vorausgesetzt, jede Bewegung kann 0 oder 1 erfolgen) mal). Mit anderen Worten, es gibt nur eine Lösung, daher erzeugt das obige das Optimale.
Sie könnten rekursive Versuche verwenden.
Sie würden mindestens die Anzahl der Züge benötigen und eine Kopie des Vektors übergeben. Sie sollten auch eine maximale Bewegungsabschaltung festlegen, um eine Grenze für die Breite der Verzweigungen festzulegen, die an jedem Knoten des Suchbaums ausgegeben werden. Beachten Sie, dass dies ein "Brute-Force" -Ansatz ist. "
Ihre allgemeine Algorithmusstruktur wäre:
%Vor%... sorry im Voraus für Tippfehler / geringfügige Syntaxfehler. Wollte eine schnelle Lösung für Sie entwickeln, schreiben Sie nicht den vollständigen Code ...
Oder einfacher noch, Sie könnten einfach eine rohe Kraft von linearen Versuchen verwenden. Verwenden Sie eine äußere for-Schleife wäre die Anzahl der Versuche, innere for-Schleife wäre im Versuch Flips. In jeder Schleife würden Sie umdrehen und überprüfen, ob Sie erfolgreich waren, indem Sie Ihren Erfolg recyceln und Code von oben kopieren. Der Erfolg würde die innere Schleife kurzschließen. Speichern Sie das Ergebnis am Ende der inneren Schleife im Array. Wenn nach max_moves fehlgeschlagen ist, speichern Sie -1. Suche nach dem maximalen Wert.
Eine elegantere Lösung wäre es, eine Multithreading-Bibliothek zu verwenden, um eine Reihe von Thread-Flips zu starten und ein Thread-Signal an andere zu senden, wenn eine Übereinstimmung gefunden wird und die Übereinstimmung niedriger ist als die Anzahl der bisher ausgeführten Schritte ein anderer Thread, dieser Thread wird mit einem Fehler beendet.
Ich schlage MPI vor, aber CUDA könnte dir Bonuspunkte bringen, da es gerade heiß ist.
Hoffe das hilft, viel Glück!
Tags und Links algorithm optimization c++ dynamic