Erhalt der Mindestanzahl von Münzenden nach mehrmaligem Umdrehen der gesamten Reihe oder Spalte

Question

Wenn Münzen auf ein Gitter gelegt werden und nur eine ganze Reihe oder Spalte gewendet werden kann, wie können wir die Münzen umdrehen, um die Mindestanzahl zu erhalten Schwänze.

Ich habe versucht, die gierige Lösung zu verwenden, in der ich die Reihe oder Spalte klappen, wo die Anzahl der Schwänze größer als Köpfe ist und den Prozess wiederhole, bis es keine Änderung auf der Zahl gibt. Aber ich habe festgestellt, dass mir dieser Ansatz manchmal keine optimale Lösung bietet.

HHT 
THH 
THT 

Zum Beispiel, wenn die Münzen wie die oben platziert sind und ich die Münzen in unten Weise spiegeln, ist der erhaltene Wert 3, aber tatsächlich ist die Antwort 2.

1. Flip the row 3 
HHT 
THH 
HTH 
2. Then there exists no row or column where the number of tails are greater than that of heads. 
3. But if I flip the column 3, row 3, column 1, there exists a solution whose value is 2. 
THH 
HHT 
HHH 

Also, ich denke, Der obige Algorithmus funktioniert nicht. Welchen Ansatz und welchen Algorithmus soll ich verwenden?

Answer 1

Zunächst möchten wir bemerken, dass es keinen Sinn macht, die gleiche Zeile oder Spalte zweimal oder öfter zu spiegeln (eine bessere Lösung besteht darin, die Zeile/Spalte immer null oder einmal umzudrehen) und die Reihenfolge der Zeilen oder Spalten ist irrelevant, so dass wir eine Lösung als ein Bit-Array der Länge 2N beschreiben können. Ein Bit pro Zeile und ein Bit pro Spalte. Wenn wir diese Zeile/Spalte einmal umdrehen, schalten wir sie aus, wenn wir sie null Mal umdrehen.

Also müssen wir 2^(2N) mögliche Lösungen suchen, bevorzugen Lösungen mit mehr Nullen.

Zweitens lassen Sie uns feststellen, dass für eine Lösung gibt vier mögliche Zustände einer Münze sind:

1. Die Münze nicht umgedreht wurde (0 Flips)
2. Die Münze durch seine Reihe (1 Flip) gekippt wurde
3. Die Münze durch die Säule (1 Flip)
4. Die Münze wurde umgedreht, indem sowohl seine Zeile und Spalte (2 Flips)

N gekippt wurde Otice dieses Zustand 1 und 4 Ergebnis in dem ursprünglichen Wert der Münze

auch bemerken, dass der Zustand 2 und 3 Ergebnis im Gegenteil von dem ursprünglichen Wert der Münze

zunächst den ursprünglichen Zustand der Münzen ausdrücken als eine binäre Matrix (B). Das 2N-Bit-Feld als 2 Binärvektoren (R, C) und die Gesamtzahl der Schwänze in Abhängigkeit von diesem f (B, R, C) und die Gesamtzahl der Bits als Funktion g (V_1, V_2)

Also ist Ihr Ziel, f> = Minimum zu machen und dabei g zu minimieren.

Denken Sie, dass, wenn wir zuerst unsere R-Konfiguration reparieren (welche Reihen werden wir umdrehen), wie können wir das Problem nur für C lösen (welche Spalten werden wir umdrehen)? Anders ausgedrückt, betrachte das einfachere Problem, nur Spalten umkehren zu dürfen und keine Zeilen umkehren zu dürfen. Wie würdest du das lösen? (Tipp: DP) Kannst du diese Strategie jetzt auf das volle Problem zurückführen?

Answer 2

Nicht sicher über den vollständigen Algorithmus, aber eine Sache, die Sie auf jeden Fall ausprobieren sollten, ist die große Anzahl von Symmetrien in Ihrem Problem.

Viele verschiedene Münzkonfigurationen sind tatsächlich äquivalent, sodass Sie Ihre Konfiguration drehen und spiegeln können, ohne das Problem zu ändern. Am wichtigsten ist, dass Sie, wenn Sie den gesamten Satz umkehren können, indem Sie alle Zeilen umkehren, nach der minimalen Anzahl von Schwänzen Ausschau halten, wenn Sie nach der Mindestanzahl von Köpfen suchen.

In Ihrem Fall wäre es

HHT 
THH 
THT 

HTT 
TTH 
TTT 

Durch Umklappen der mittleren Spalte sein, und Sie sind fertig (Sie dann alles natürlich müssen drehen, wenn Sie es wirklich brauchen).

Answer 3

Eine naheliegende Lösung ist, alle Möglichkeiten zu versuchen, eine Zeile oder eine Spalte umzudrehen. Es gibt O(2^(2N)) solche Möglichkeiten. Allerdings können wir das Problem in O(N^2 * 2^N) mit einer Kombination von gierigen + Brute-Force lösen.

Generieren Sie alle Möglichkeiten, die Zeilen zu spiegeln (O(2^N)) und für jede von diesen, kippen Sie jede Spalte, die mehr Schwänze als Köpfe hat. Nimm die Lösung, die dir die Mindestschwänze gibt.

Dies sollte funktionieren. Ich werde später noch ein paar Details dazu hinzufügen.

Answer 4

Ein Ansatz wäre, http://en.wikipedia.org/wiki/Branch_and_bound abwechselnd neue vertikale Linien und neue horizontale Linien zu verwenden. Es gibt auch eine gewisse Symmetrie, die Sie entfernen können - wenn Sie alle horizontalen Linien und alle vertikalen Linien umdrehen, landen Sie wieder an der Stelle, an der Sie begonnen haben, also können Sie bei Verzweigungen und Grenzen auch willkürlich davon ausgehen, dass die linke vertikale Linie niemals umgedreht wird .

HHT 
THH 
THT 

In diesem Beispiel, wenn wir, dass die am weitesten links stehende Linie vertikal übernehmen nicht gekippt wird, dann, wenn wir auf der untersten horizontale Linie, die wir den Wert der am weitesten links stehenden niedrigste Münze wissen verzweigen, so haben wir zwei mögliche Teillösungen - eine, bei der diese einzelne bekannte Münze an Schwänzen befestigt ist, und eine, bei der sie an Köpfen befestigt ist. Wenn wir zuerst versuchen, die Teillösung zu erweitern, in der die einzelne bekannte Münze Köpfe ist, und finden, dass wir diese zu einer Lösung erweitern können, die keine Schwänze hervorbringt, dann können wir alle Teillösungen, die durch die Verlängerung der anderen erzeugt werden, einfach wegwerfen seine Nachkommen müssen mindestens einen Schwanz haben.

Ich würde als nächstes auf der linken, aber einer vertikalen Linie verzweigen, die uns eine andere bekannte Münze geben wird, und weiter verzweigen abwechselnd horizontal und vertikal.

Dies ist eine praktikable Möglichkeit, eine exakte Lösung zu finden, wenn es eine nahezu perfekte Lösung gibt oder wenn der Tisch sehr klein ist. Andernfalls müssen Sie es früh stoppen oder es haben glaubwürdige Lösungen überspringen, um das Problem in einer angemessenen Zeit fertig zu bekommen, und Sie werden wahrscheinlich nicht die beste Antwort erhalten.