Ich habe eine n x m
Matrix, die aus nicht negativen ganzen Zahlen besteht. Beispielsweise:
2 3 4 7 1
1 5 2 6 2
4 3 4 2 1
2 1 2 4 1
3 1 3 4 1
2 1 4 3 2
6 9 1 6 4
"Eine Bombe fallen lassen" verringert die Anzahl der Zielzellen und aller acht Nachbarn um eins auf ein Minimum von Null.
x x x
x X x
x x x
Was ist ein Algorithmus, der die Mindestanzahl von Bomben bestimmt, die erforderlich sind, um alle Zellen auf Null zu reduzieren?
B Option (Da ich kein aufmerksamer Leser bin)
Eigentlich ist die erste Version des Problems nicht die, auf die ich eine Antwort suche. Ich habe die ganze Aufgabe nicht sorgfältig gelesen, es gibt zusätzliche Einschränkungen, sagen wir:
Was ist mit einem einfachen Problem, wenn die Reihenfolge in der Reihe nicht erhöht werden darf:
8 7 6 6 5
ist mögliche Eingabesequenz
7 8 5 5 2
ist nicht möglich, da 7 -> 8 in einer Sequenz wachsen.
Vielleicht hilft es, eine Antwort für einen "einfacheren" Fall zu finden, um eine Lösung für einen schwierigeren Fall zu finden.
PS: Ich glaube, wenn wir in mehreren Situationen minimale Bomben benötigen, um die obere Linie zu löschen, wählen wir eine, die die meisten Bomben auf der "linken Seite" der Reihe verwendet. Noch ein Beweis, der richtig sein könnte?
quelle
what's the minimum amount of bombs required to clean the board?
Bedeutet dies, dass es nicht unbedingt erforderlich ist, ein tatsächliches Bombenmuster zu finden, sondern nur die minimale Anzahl von Bomben?Antworten:
Es gibt eine Möglichkeit, dies auf ein einfaches Unterproblem zu reduzieren.
Die Erklärung besteht aus zwei Teilen: dem Algorithmus und dem Grund, warum der Algorithmus eine optimale Lösung bietet. Das erste macht ohne das zweite keinen Sinn, also beginne ich mit dem Warum.
Wenn Sie daran denken, das Rechteck zu bombardieren (nehmen Sie ein großes Rechteck an - noch keine Randfälle), können Sie sehen, dass die einzige Möglichkeit, das hohle Rechteck der Quadrate am Umfang auf 0 zu reduzieren, darin besteht, entweder den Umfang oder das hohle Rechteck von zu bombardieren Quadrate direkt innerhalb des Umfangs. Ich werde die Umfangsebene 1 und das Rechteck darin Ebene 2 nennen.
Eine wichtige Erkenntnis ist, dass es keine Punktbombenschicht 1 gibt, da der "Explosionsradius", den Sie dadurch erhalten, immer im Explosionsradius eines anderen Quadrats aus Schicht 2 enthalten ist. Sie sollten sich leicht davon überzeugen können.
Wir können das Problem also darauf reduzieren, einen optimalen Weg zu finden, um den Umfang zu bombardieren, und dies dann wiederholen, bis alle Quadrate 0 sind.
Aber das wird natürlich nicht immer eine optimale Lösung finden, wenn es möglich ist, den Umfang nicht optimal zu bombardieren, aber durch die Verwendung von X zusätzlichen Bomben wird das Problem der Reduzierung der inneren Schicht durch> X Bomben einfacher. Wenn wir also die Permiter-Schicht eins nennen und zusätzliche X-Bomben irgendwo in Schicht 2 (direkt innerhalb von Schicht 1) platzieren, können wir den Aufwand für das spätere Bombardieren von Schicht 2 um mehr als X reduzieren? Mit anderen Worten, wir müssen beweisen, dass wir bei der Reduzierung des Außenumfangs gierig sein können.
Aber wir wissen, dass wir gierig sein können. Weil keine Bombe in Schicht 2 jemals effizienter sein kann, um Schicht 2 auf 0 zu reduzieren, als eine strategisch platzierte Bombe in Schicht 3. Und aus dem gleichen Grund wie zuvor - es gibt immer eine Bombe, die wir in Schicht 3 platzieren können und die jedes Quadrat betrifft von Schicht 2, die eine in Schicht 2 platzierte Bombe kann. Es kann uns also niemals schaden, gierig zu sein (in diesem Sinne gierig).
Wir müssen also nur den optimalen Weg finden, um den Permiter durch Bombardierung der nächsten inneren Schicht auf 0 zu reduzieren.
Wir werden nie verletzt, wenn wir zuerst die Ecke auf 0 bombardieren, weil nur die Ecke der inneren Schicht sie erreichen kann, so dass wir wirklich keine Wahl haben (und jede Bombe am Umfang, die die Ecke erreichen kann, hat einen Explosionsradius in der Strahlradius von der Ecke der inneren Schicht).
Sobald wir dies getan haben, können die Quadrate am Umfang neben der 0-Ecke nur durch 2 Quadrate von der inneren Schicht erreicht werden:
Zu diesem Zeitpunkt ist der Umfang effektiv eine geschlossene eindimensionale Schleife, da jede Bombe 3 benachbarte Quadrate reduziert. Abgesehen von einigen Verrücktheiten in der Nähe der Ecken kann X A, B, C und D "treffen".
Jetzt können wir keine Explosionsradius-Tricks verwenden - die Situation jedes Quadrats ist symmetrisch, mit Ausnahme der seltsamen Ecken, und selbst dort ist kein Explosionsradius eine Teilmenge eines anderen. Beachten Sie, dass die Lösung trivial ist, wenn dies eine Linie (wie Colonel Panic erläutert) anstelle einer geschlossenen Schleife wäre. Die Endpunkte müssen auf 0 reduziert werden, und es schadet Ihnen nie, die Punkte neben den Endpunkten zu bombardieren, da der Explosionsradius wiederum eine Obermenge ist. Sobald Sie Ihren Endpunkt auf 0 gesetzt haben, haben Sie immer noch einen neuen Endpunkt. Wiederholen Sie diesen Vorgang (bis alle Zeilen 0 sind).
Wenn wir also ein einzelnes Quadrat in der Ebene optimal auf 0 reduzieren können, haben wir einen Algorithmus (weil wir die Schleife geschnitten haben und jetzt eine gerade Linie mit Endpunkten haben). Ich glaube, dass Bombenangriffe neben dem Quadrat mit dem niedrigsten Wert (mit 2 Optionen), so dass der höchste Wert innerhalb von 2 Quadraten dieses niedrigsten Werts das minimal mögliche ist (Sie müssen möglicherweise Ihre Bombenangriffe aufteilen, um dies zu erreichen), aber ich bin optimal habe (noch?) keinen Beweis.
quelle
But, we do know we can be greedy...
- Ich kaufe das nicht. Betrachten Sie1 1 2 1 1 2
den Umfang. Die Mindestanzahl an Bomben beträgt 4, es gibt jedoch drei verschiedene Lösungen. Jede Lösung hat unterschiedliche Auswirkungen auf die nächste Schicht. Solange es mehrere Minimallösungen für einen Perimeter gibt, können Sie den Perimeter nicht vollständig isolieren, ohne die inneren Schichten zu berücksichtigen. Ich glaube wirklich nicht, dass dieses Problem ohne Rückverfolgung gelöst werden kann.0011100
0100010
0000000
0000000
1110111
. Der optimale Weg, um die erste Schicht zu bombardieren, besteht darin, in der Mitte der zweiten Reihe zu bombardieren und insgesamt drei Bomben zu nehmen, um die äußere Schicht zu töten. Aber dann braucht man zwei Bomben, um sich um die nächste Schicht zu kümmern. Optimal sind insgesamt nur vier Bomben erforderlich: zwei für die ersten beiden Reihen und zwei für die letzte Reihe.Pólya sagt: "Wenn Sie ein Problem nicht lösen können, gibt es ein einfacheres Problem, das Sie lösen können: Finden Sie es."
Das offensichtlich einfachere Problem ist das eindimensionale Problem (wenn das Gitter eine einzelne Zeile ist). Beginnen wir mit dem einfachsten Algorithmus - dem gierigen Bombardieren des größten Ziels. Wann geht das schief?
Angesichts dessen
1 1 1
ist der gierige Algorithmus gleichgültig, welche Zelle er zuerst bombardiert. Natürlich ist die mittlere Zelle besser - sie setzt alle drei Zellen gleichzeitig auf Null. Dies legt einen neuen Algorithmus A nahe, "Bombe, um die verbleibende Summe zu minimieren". Wann geht dieser Algorithmus schief?Angesichts dessen
1 1 2 1 1
ist Algorithmus A gleichgültig zwischen dem Bombardieren der 2., 3. oder 4. Zelle. Aber die 2. Zelle zu bombardieren, um zu verlassen,0 0 1 1 1
ist besser als die 3. Zelle zu bombardieren, um zu verlassen1 0 1 0 1
. Wie kann man das beheben? Das Problem beim Bombardieren der 3. Zelle besteht darin, dass wir links und rechts arbeiten müssen, was separat erfolgen muss.Wie wäre es mit "Bombe, um die verbleibende Summe zu minimieren, aber das Minimum links (von wo wir bombardiert haben) plus das Minimum rechts zu maximieren". Nennen Sie diesen Algorithmus B. Wann geht dieser Algorithmus schief?
Bearbeiten: Nach dem Lesen der Kommentare stimme ich zu, dass ein viel interessanteres Problem darin besteht, das eindimensionale Problem so zu ändern, dass sich die Enden verbinden. Würde gerne Fortschritte sehen.
quelle
Ich musste nur bei einer Teillösung aufhören, da ich keine Zeit mehr hatte, aber hoffentlich bietet sogar diese Teillösung einige Einblicke in einen möglichen Ansatz zur Lösung dieses Problems.
Wenn ich mit einem schwierigen Problem konfrontiert werde, stelle ich mir gerne einfachere Probleme vor, um eine Intuition über den Problemraum zu entwickeln. Hier war der erste Schritt, den ich unternahm, dieses 2-D-Problem in ein 1-D-Problem zu reduzieren. Betrachten Sie eine Linie:
Irgendwie wissen Sie, dass Sie
4
viermal an oder um die Stelle bombardieren müssen, um sie auf 0 zu bringen. Da links von der Stelle eine niedrigere Zahl ist, hat es keinen Vorteil, die0
oder die4
Überbombe zu bombardieren2
. Tatsächlich glaube ich (aber es fehlt ein strenger Beweis), dass das Bombardieren,2
bis der4
Punkt auf 0 fällt, mindestens so gut ist wie jede andere Strategie, um das4
auf 0 zu bringen. Man kann in einer Strategie von links nach rechts vorgehen so was:Ein paar Beispiele für Bombenanschläge:
Die Idee, mit einer Zahl zu beginnen, die auf die eine oder andere Weise sinken muss, ist ansprechend, weil es plötzlich möglich wird, eine Lösung zu finden, die behauptet, mindestens so gut zu sein wie alle anderen Lösungen.
Der nächste Schritt in der Komplexität, bei dem diese Suche nach mindestens ebenso guten Ergebnissen noch möglich ist, befindet sich am Rande des Bretts. Mir ist klar, dass es niemals einen strengen Vorteil gibt, die Außenkante zu bombardieren. Du bist besser dran, die Stelle zu bombardieren und drei weitere Plätze kostenlos zu bekommen. In Anbetracht dessen können wir sagen, dass das Bombardieren des Rings innerhalb der Kante mindestens so gut ist wie das Bombardieren der Kante. Darüber hinaus können wir dies mit der Intuition kombinieren, dass das Bombardieren des rechten innerhalb der Kante tatsächlich der einzige Weg ist, Kantenabstände auf 0 zu reduzieren. Darüber hinaus ist es trivial einfach, die optimale Strategie herauszufinden (insofern, als sie sich befindet) mindestens so gut wie jede andere Strategie), um Ecknummern auf 0 zu bringen. Wir setzen dies alles zusammen und können einer Lösung im 2D-Raum viel näher kommen.
Angesichts der Beobachtung von Eckstücken können wir mit Sicherheit sagen, dass wir die optimale Strategie kennen, um von jedem Startbrett zu einem Brett mit Nullen an allen Ecken zu gelangen. Dies ist ein Beispiel für eine solche Karte (ich habe die Zahlen von den beiden linearen Karten oben ausgeliehen). Ich habe einige Leerzeichen anders beschriftet und erkläre, warum.
Man wird in der oberen Zeile bemerkt wirklich ähnelt das lineare Beispiel haben wir bereits gesehen haben. Wir erinnern an unsere frühere Beobachtung, dass der optimale Weg, um die oberste Reihe auf 0 zu bringen, darin besteht, die zweite Reihe (die
x
Reihe) zu bombardieren . Es gibt keine Möglichkeit, die oberste Reihe durch Bombardierung einer dery
Reihen zu räumen, und es gibt keinen zusätzlichen Vorteil, die oberste Reihe zu bombardieren, anstatt den entsprechenden Platz in derx
Reihe zu bombardieren .Wir könnten die lineare Strategie von oben anwenden (die entsprechenden Felder in der
x
Reihe bombardieren ) und uns nur mit der obersten Reihe und sonst nichts befassen. Es würde ungefähr so aussehen:Der Fehler in diesem Ansatz wird in den letzten beiden Bombenanschlägen sehr deutlich. Es ist klar, dass die einzigen Bombenstellen, die die
4
Zahl in der ersten Spalte in der zweiten Reihe reduzieren, die erstex
und diey
. Die letzten beiden Bombenanschläge sind deutlich schlechter als nur die erstex
, die genau das Gleiche getan hätte (in Bezug auf den ersten Punkt in der obersten Reihe, den wir auf keine andere Weise beseitigen können). Da wir gezeigt haben, dass unsere derzeitige Strategie nicht optimal ist, ist eine Änderung der Strategie eindeutig erforderlich.An diesem Punkt kann ich einen Schritt zurück in die Komplexität gehen und mich nur auf eine Ecke konzentrieren. Betrachten wir diesen:
Es ist der einzige Weg , löschen , die Räume mit bekommen
4
bis auf Null sind eine Kombination aus bombardierenx
,y
undz
. Bei einigen Akrobatik in meinem Kopf, ich bin ziemlich sicher , dass die optimale Lösung zu bombardieren istx
dreimal und danna
dannb
. Jetzt geht es darum herauszufinden, wie ich zu dieser Lösung gekommen bin und ob sich daraus eine Intuition ergibt, mit der wir dieses lokale Problem sogar lösen können. Ich bemerke, dass es keine Bombenangriffey
undz
Räume gibt. Der Versuch, eine Ecke zu finden, in der es Sinn macht, diese Räume zu bombardieren, ergibt eine Ecke, die so aussieht:In diesem Fall ist mir klar, dass die optimale Lösung darin besteht,
y
fünfmal undz
fünfmal zu bombardieren . Gehen wir noch einen Schritt weiter.Hier fühlt es sich ähnlich intuitiv , dass die optimale Lösung zu bombardieren ist
a
undb
6 - mal und dannx
4 mal.Jetzt wird es zu einem Spiel, wie man diese Intuitionen in Prinzipien verwandelt, auf denen wir aufbauen können.
Hoffentlich geht es weiter!
quelle
Bei aktualisierten Fragen liefert ein einfacher Greedy-Algorithmus ein optimales Ergebnis.
Wirf A [0,0] -Bomben in Zelle A [1,1], dann A [1,0] -Bomben in Zelle A [2,1] und setze diesen Vorgang nach unten fort. Um die linke untere Ecke zu reinigen, werfen Sie maximal (A [N-1,0], A [N-2,0], A [N-3,0]) Bomben auf die Zelle A [N-2,1]. Dadurch werden die ersten 3 Spalten vollständig bereinigt.
Reinigen Sie mit dem gleichen Ansatz die Spalten 3,4,5, dann die Spalten 6,7,8 usw.
Leider hilft dies nicht, eine Lösung für das ursprüngliche Problem zu finden.
Ein "größeres" Problem (ohne "nicht zunehmende" Einschränkung) kann sich als NP-hart erweisen. Hier ist eine Skizze eines Beweises.
Angenommen, wir haben ein planares Diagramm mit einem Grad von bis zu 3. Lassen Sie uns die minimale Scheitelpunktabdeckung für dieses Diagramm ermitteln. Laut Wikipedia-Artikel ist dieses Problem für planare Graphen mit einem Grad bis zu 3 NP-schwer. Dies könnte durch Reduktion von Planar 3SAT bewiesen werden. Und Härte von Planar 3SAT - durch Reduzierung von 3SAT. Beide Beweise werden in jüngsten Vorlesungen in "Algorithmic Lower Bounds" von prof. Erik Demaine (Vorlesungen 7 und 9).
Wenn wir einige Kanten des Originaldiagramms (linkes Diagramm im Diagramm) mit jeweils einer geraden Anzahl zusätzlicher Knoten teilen, sollte das resultierende Diagramm (rechtes Diagramm im Diagramm) genau die gleiche minimale Scheitelpunktabdeckung für die ursprünglichen Scheitelpunkte aufweisen. Eine solche Transformation ermöglicht das Ausrichten von Diagrammscheitelpunkten an beliebigen Positionen im Raster.
Wenn wir Diagrammscheitelpunkte nur auf geraden Zeilen und Spalten platzieren (so dass keine zwei Kanten, die auf einen Scheitelpunkt fallen, einen spitzen Winkel bilden), fügen Sie "Einsen" überall dort ein, wo es eine Kante gibt, und fügen Sie "Nullen" in andere Gitterpositionen ein. Wir könnten jede Lösung für das ursprüngliche Problem verwenden, um eine minimale Scheitelpunktabdeckung zu finden.
quelle
Sie können dieses Problem als ganzzahliges Programmierproblem darstellen. (Dies ist nur eine der möglichen Lösungen, um dieses Problem anzugehen.)
Punkte haben:
man kann 16 Gleichungen schreiben, wobei zum Beispiel für Punkt f gilt
minimiert über die Summe aller Indizes und der ganzzahligen Lösung.
Die Lösung ist natürlich die Summe dieser Indizes.
Dies kann weiter vereinfacht werden, indem alle xi an den Grenzen 0 gesetzt werden, sodass Sie in diesem Beispiel die 4 + 1-Gleichung haben.
Das Problem ist, dass es keinen trivialen Algorithmus zur Lösung solcher Probleme gibt. Ich bin kein Experte in diesem Bereich, aber die Lösung dieses Problems als lineare Programmierung ist NP-schwierig.
quelle
Dies ist eine teilweise Antwort. Ich versuche, eine Unter- und Obergrenze zu finden, die die mögliche Anzahl von Bomben sein könnte.
Bei 3x3 und kleineren Platinen ist die Lösung trivial immer die Zelle mit der größten Nummer.
Bei Brettern größer als 4x4 ist die erste offensichtliche Untergrenze die Summe der Ecken:
Wie auch immer Sie die Bombe arrangieren, es ist unmöglich, dieses 4x4-Brett mit weniger als 2 + 1 + 6 + 4 = 13 Bomben zu räumen.
In anderen Antworten wurde erwähnt, dass es niemals schlimmer ist, die Bombe an der zweiten Ecke zu platzieren, um die Ecke zu beseitigen, als die Bombe an der Ecke selbst zu platzieren.
Wir können die Ecken auf Null setzen, indem wir Bomben auf die zweite Ecke legen, um ein neues Brett zu erhalten:
So weit, ist es gut. Wir brauchen 13 Bomben, um die Ecken zu räumen.
Beachten Sie nun die unten markierten Nummern 6, 4, 3 und 2:
Es gibt keine Möglichkeit, zwei dieser Zellen mit einer einzigen Bombe zu bombardieren. Daher hat sich die Mindestbombe um 6 + 4 + 3 + 2 erhöht. Wenn wir also die Anzahl der Bomben erhöhen, mit denen wir die Ecken geräumt haben, erhalten wir das Minimum Die Anzahl der für diese Karte erforderlichen Bomben beträgt 28 Bomben. Es ist unmöglich, diese Karte mit weniger als 28 Bomben zu löschen. Dies ist die Untergrenze für diese Karte.
Sie können den Greedy-Algorithmus verwenden, um eine Obergrenze festzulegen. Andere Antworten haben gezeigt, dass ein gieriger Algorithmus eine Lösung erzeugt, die 28 Bomben verwendet. Da wir bereits früher bewiesen haben, dass keine optimale Lösung weniger als 28 Bomben haben kann, sind 28 Bomben in der Tat eine optimale Lösung.
Wenn gierig und die oben erwähnte Methode zum Finden der minimalen Grenze nicht konvergiert, müssen Sie wahrscheinlich alle Kombinationen überprüfen.
Der Algorithmus zum Finden der Untergrenze ist der folgende:
minimums
Liste hinzu.minimums
Liste, um die Untergrenze zu erhalten.quelle
Dies wäre ein gieriger Ansatz:
Berechnen Sie eine "Score" -Matrix der Ordnung n X m, wobei Score [i] [j] der Gesamtabzug der Punkte in der Matrix ist, wenn Position (i, j) bombardiert wird. (Die maximale Punktzahl eines Punktes beträgt 9 und die minimale Punktzahl 0)
Bewegen Sie sich zeilenweise und suchen Sie die erste Position mit der höchsten Punktzahl (z. B. (i, j)).
Bombe (i, j). Erhöhen Sie die Anzahl der Bomben.
Wenn alle Elemente der ursprünglichen Matrix nicht Null sind, gehen Sie zu 1.
Ich habe meine Zweifel, dass dies die optimale Lösung ist.
Bearbeiten:
Der oben veröffentlichte Greedy-Ansatz bietet uns wahrscheinlich nicht die optimale Lösung, obwohl er funktioniert. Also dachte ich mir, ich sollte ein paar Elemente von DP hinzufügen.
Ich denke, wir können uns darauf einigen, dass zu jedem Zeitpunkt eine der Positionen mit der höchsten "Punktzahl" (Punktzahl [i] [j] = Gesamtabzug der Punkte, wenn (i, j) bombardiert wird) als Ziel ausgewählt werden muss. Ausgehend von dieser Annahme ist hier der neue Ansatz:
NumOfBombs (M): (gibt die erforderliche Mindestanzahl an Bomben zurück)
Gegeben ist eine Matrix M der Ordnung n X m. Wenn alle Elemente von M Null sind, geben Sie 0 zurück.
Berechnen Sie die "Score" -Matrix M.
Die k verschiedenen Positionen P1, P2, ... Pk (1 <= k <= n * m) seien die Positionen in M mit den höchsten Punktzahlen.
return (1 + min (NumOfBombs (M1), NumOfBombs (M2), ..., NumOfBombs (Mk)))
wobei M1, M2, ..., Mk die resultierenden Matrizen sind, wenn wir die Positionen P1, P2, ... bzw. Pk bombardieren.
Wenn wir möchten, dass die Reihenfolge der Positionen zusätzlich nuklear wird, müssen wir auch die Ergebnisse von "min" verfolgen.
quelle
Ihr neues Problem mit den nicht abnehmenden Werten in den Zeilen ist recht einfach zu lösen.
Beachten Sie, dass die linke Spalte die höchsten Zahlen enthält. Daher muss jede optimale Lösung diese Spalte zuerst auf Null reduzieren. Auf diese Weise können wir einen 1-D- Bombenangriff auf diese Säule durchführen und jedes Element darin auf Null reduzieren. Wir lassen die Bomben auf die zweite Säule fallen, damit sie maximalen Schaden anrichten. Ich denke, es gibt hier viele Beiträge, die sich mit dem 1D-Fall befassen, daher fühle ich mich sicher, diesen Fall zu überspringen. (Wenn du willst, dass ich es beschreibe, kann ich es.) Aufgrund der abnehmenden Eigenschaft werden alle drei Spalten ganz links auf Null reduziert. Wir werden hier jedoch nachweislich eine Mindestanzahl von Bomben verwenden, da die linke Spalte auf Null gesetzt werden muss.
Sobald die linke Spalte auf Null gesetzt ist, schneiden wir einfach die drei Spalten ganz links ab, die jetzt auf Null gesetzt sind, und wiederholen sie mit der jetzt reduzierten Matrix. Dies muss uns eine optimale Lösung geben, da wir in jeder Phase eine nachweislich minimale Anzahl von Bomben einsetzen.
quelle
Mathematica Integer Linear Programming mit Branch-and-Bound
Wie bereits erwähnt, kann dieses Problem mit einer ganzzahligen linearen Programmierung (die NP-hart ist ) gelöst werden . In Mathematica ist ILP bereits integriert.
"To solve an integer linear programming problem Mathematica first solves the equational constraints, reducing the problem to one containing inequality constraints only. Then it uses lattice reduction techniques to put the inequality system in a simpler form. Finally, it solves the simplified optimization problem using a branch-and-bound method."
[Siehe Tutorial zur eingeschränkten Optimierung in Mathematica.]Ich habe den folgenden Code geschrieben, der ILP-Bibliotheken von Mathematica verwendet. Es ist überraschend schnell.
Für das im Problem bereitgestellte Beispiel:
Ausgänge
Für alle, die dies mit einem gierigen Algorithmus lesen
Probieren Sie Ihren Code für das folgende 10x10-Problem aus:
Hier ist es durch Kommas getrennt:
Für dieses Problem enthält meine Lösung 208 Bomben. Hier ist eine mögliche Lösung (ich konnte dies in ca. 12 Sekunden lösen).
Um die Ergebnisse zu testen, die Mathematica liefert, prüfen Sie, ob Ihr gieriger Algorithmus es besser kann.
quelle
Es besteht keine Notwendigkeit, das Problem in lineare Unterprobleme umzuwandeln.
Verwenden Sie stattdessen eine einfache gierige Heuristik, die die Ecken bombardiert , beginnend mit der größten.
Im angegebenen Beispiel gibt es vier Ecken, {2, 1, 6, 4}. Für jede Ecke gibt es keinen besseren Zug, als die Zellendiagonale zur Ecke zu bombardieren. Wir wissen also, dass unsere ersten 2 + 1 + 6 + 4 = 13 Bombenangriffe in diesen diagonalen Zellen stattfinden müssen. Nach dem Bombenangriff bleibt uns eine neue Matrix:
Nach den ersten 13 Bombenanschlägen verwenden wir die Heuristik, um 3 0 2 über drei Bombenanschläge zu eliminieren. Jetzt haben wir 2 neue Ecken, {2, 1} in der 4. Reihe. Wir bombardieren diese, weitere 3 Bombenanschläge. Wir haben die Matrix jetzt auf 4 x 4 reduziert. Es gibt eine Ecke oben links. Wir bombardieren das. Jetzt haben wir noch 2 Ecken, {5, 3}. Da 5 die größte Ecke ist, bombardieren wir diese zuerst, 5 Bomben, und schließlich die 3 in der anderen Ecke. Die Summe beträgt 13 + 3 + 3 + 1 + 5 + 3 = 28.
quelle
Dies führt eine breite Suche nach dem kürzesten Weg (einer Reihe von Bombenanschlägen) durch dieses "Labyrinth" von Positionen durch. Nein, ich kann leider nicht beweisen, dass es keinen schnelleren Algorithmus gibt.
quelle
Es scheint, dass ein linearer Programmieransatz hier sehr hilfreich sein kann.
Sei P m xn die Matrix mit den Werten der Positionen:
Definieren wir nun eine Bombenmatrix B (x, y) mxn mit 1 ≤ x ≤ m , 1 ≤ y ≤ n wie folgt
Sodass
Beispielsweise:
Wir suchen also nach einer Matrix B m xn = [ b ij ], die
Kann als Summe von Bombenmatrizen definiert werden:
( q ij wäre dann die Menge der Bomben, die wir in Position p ij fallen lassen würden )
p ij - b ij ≤ 0 (um prägnanter zu sein, sagen wir es als P - B ≤ 0 )
Außerdem sollte B die Summe minimieren .
Wir können auch B als die hässliche Matrix vor uns schreiben :
und da P - B ≤ 0 (was P ≤ B bedeutet ) haben wir das folgende ziemlich lineare Ungleichungssystem unten:
Als q mn x 1 definiert als
p mn x 1 definiert als
Wir können sagen, wir haben ein System Das folgende System wird als Produkt von Matrizen dargestellt: http://latex.codecogs.com/gif.download?S%5Cmathbf%7Bq%7D&space;%5Cge&space;%5Cmathbf%7Bp%7D ist S mn x In der Matrix muss umgekehrt werden, um das System zu lösen. Ich habe es nicht selbst erweitert, aber ich glaube, es sollte einfach sein, es im Code zu tun.
Jetzt haben wir ein minimales Problem, das als angegeben werden kann
Ich glaube, es ist etwas Leichtes, fast Triviales, mit so etwas wie dem Simplex-Algorithmus gelöst zu werden (es gibt dieses ziemlich coole Dokument darüber ). Ich kenne jedoch fast keine lineare Programmierung (ich werde einen Kurs darüber auf Coursera belegen, aber es ist erst in der Zukunft ...), ich hatte einige Kopfschmerzen beim Versuch, es zu verstehen, und ich habe einen riesigen freiberuflichen Job zu erledigen, also habe ich gib einfach hier auf. Es kann sein , dass ich etwas falsch an einem gewissen Punkt hat, oder dass es nicht weiter gehen können, aber ich glaube , dieser Weg schließlich führen kann die Lösung. Wie auch immer, ich bin gespannt auf Ihr Feedback.
(Besonderer Dank für diese erstaunliche Website zum Erstellen von Bildern aus LaTeX-Ausdrücken )
quelle
"Despite the many crucial applications of this problem, and intense interest by researchers, no efficient algorithm is known for it.
siehe Seite 254. Die ganzzahlige lineare Programmierung ist ein sehr schwieriges Rechenproblem. Unsere einzige Hoffnung, effizient zu sein, besteht darin, die intrinsischen Eigenschaften Ihrer Matrix S auszunutzen. Es ist schließlich nicht so willkürlich.Diese gierige Lösung
scheint richtig zu sein:Wie in den Kommentaren erwähnt, schlägt dies in 2D fehl. Aber vielleicht können Sie es verbessern.
Für 1D:
Wenn es mindestens 2 Zahlen gibt, müssen Sie nicht ganz links schießen, da das Schießen auf die zweite nicht schlechter ist . Schießen Sie also auf die Sekunde, während die erste nicht 0 ist, weil Sie es tun müssen. Gehen Sie zur nächsten Zelle. Vergiss die letzte Zelle nicht.
C ++ - Code:
Also für 2D:
Nochmals: Sie müssen nicht in der ersten Reihe schießen (wenn es die zweite gibt). Also schieß zum zweiten. Lösen Sie die 1D-Aufgabe für die erste Zeile. (weil Sie es null machen müssen). Gehen. Letzte Reihe nicht vergessen.
quelle
"0110","1110","1110"
. Sie brauchen nur 1 Schuss, aber ich glaube, Ihr Algorithmus würde 2 verwenden.Um die Anzahl der Bomben zu minimieren, müssen wir die Wirkung jeder Bombe maximieren. Um dies zu erreichen, müssen wir bei jedem Schritt das beste Ziel auswählen. Für jeden Punkt, der es summiert, und seine acht Nachbarn - könnte als Effizienzmaß für die Bombardierung dieses Punktes verwendet werden. Dies liefert eine nahezu optimale Reihenfolge der Bomben.
UPD : Wir sollten auch die Anzahl der Nullen berücksichtigen, da die Kombination dieser Nullen ineffizient ist. Tatsächlich besteht das Problem darin, die Anzahl der geschlagenen Nullen zu minimieren. Aber wir können nicht wissen, wie ein Schritt uns diesem Ziel näher bringt. Ich stimme der Idee zu, dass das Problem NP-vollständig ist. Ich schlage einen gierigen Ansatz vor, der eine Antwort gibt, die der Realität nahe kommt.
quelle
1010101
,0010100
(obere Reihe, untere Reihe) Ihr Ansatz 3. benötigen Sie kann in 2 durchgeführt werdenIch glaube, um die Anzahl der Bomben zu minimieren, müssen Sie einfach die Schadensmenge maximieren. Dazu müssen Sie den Bereich mit der stärksten Kraft überprüfen. Analysieren Sie also zuerst das Feld mit einem 3x3-Kernel und überprüfen Sie, wo sich die Summe befindet ist stärker .. und Bombe dort .. und tun, bis das Feld flach ist .. für dieses Feld ist die Antwort 28
quelle
Hier ist eine Lösung, die die guten Eigenschaften der Ecken verallgemeinert.
Nehmen wir an, wir könnten einen perfekten Ablagepunkt für ein bestimmtes Feld finden, dh einen besten Weg, um den Wert darin zu verringern. Um dann die Mindestanzahl der abzuwerfenden Bomben zu ermitteln, könnte ein erster Entwurf eines Algorithmus erstellt werden (der Code wird aus einer Ruby-Implementierung kopiert):
Die Herausforderung ist
choose_a_perfect_drop_point
. Definieren wir zunächst, was ein perfekter Ablagepunkt ist.(x, y)
verringert den Wert in(x, y)
. Es kann auch Werte in anderen Zellen verringern.(x, y)
ist besser als ein Abwurfpunkt b für,(x, y)
wenn er die Werte in einer geeigneten Obermenge der Zellen verringert , für die b abnimmt.(x, y)
sind äquivalent, wenn sie denselben Satz von Zellen verringern.(x, y)
ist perfekt, wenn er allen maximalen Drop-Punkten für entspricht(x, y)
.Wenn es einen perfekten Abwurfpunkt für gibt
(x, y)
, können Sie den Wert nicht(x, y)
effektiver verringern, als eine Bombe auf einen der perfekten Abwurfpunkte für zu werfen(x, y)
.Ein perfekter Drop-Point für ein bestimmtes Feld ist ein perfekter Drop-Point für eine seiner Zellen.
Hier einige Beispiele:
Der perfekte Ablagepunkt für die Zelle
(0, 0)
(nullbasierter Index) ist(1, 1)
. Alle anderen Punkte abgezogen(1, 1)
, das heißt(0, 0)
,(0, 1)
und(1, 0)
, weniger Zellen verringern.Ein perfekter Einstichpunkt für die Zelle
(2, 2)
(Null-Basis - Index) ist(2, 2)
, und auch alle umgebenden Zellen(1, 1)
,(1, 2)
,(1, 3)
,(2, 1)
,(2, 3)
,(3, 1)
,(3, 2)
, und(3, 3)
.Ein perfekter Abwurfpunkt für die Zelle
(2, 2)
ist(3, 1)
: Er verringert den Wert in(2, 2)
und den Wert in(4, 0)
. Alle anderen Abwurfpunkte für(2, 2)
sind nicht maximal, da sie eine Zelle weniger verringern. Der perfekte Drop-Point für(2, 2)
ist auch der perfekte Drop-Point für(4, 0)
und der einzige perfekte Drop-Point für das Feld. Dies führt zur perfekten Lösung für dieses Feld (ein Bombenabwurf).Es gibt keinen perfekten Abwurfpunkt für
(2, 2)
: Beide(1, 1)
und(1, 3)
Abnehmen(2, 2)
und eine andere Zelle (sie sind maximale Abwurfpunkte für(2, 2)
), aber sie sind nicht gleichwertig. Ist(1, 1)
jedoch ein perfekter Ablagepunkt für(0, 0)
und(1, 3)
ist ein perfekter Ablagepunkt für(0, 4)
.Mit dieser Definition perfekter Abwurfpunkte und einer bestimmten Reihenfolge von Überprüfungen erhalte ich das folgende Ergebnis für das Beispiel in der Frage:
Der Algorithmus funktioniert jedoch nur, wenn nach jedem Schritt mindestens ein perfekter Abwurfpunkt vorhanden ist. Es ist möglich, Beispiele zu konstruieren, bei denen es keine perfekten Abwurfpunkte gibt:
In diesen Fällen können wir den Algorithmus so ändern, dass wir anstelle eines perfekten Abwurfpunkts eine Koordinate mit einer minimalen Auswahl an maximalen Abwurfpunkten auswählen und dann das Minimum für jede Auswahl berechnen. Im obigen Fall haben alle Zellen mit Werten zwei maximale Abwurfpunkte. Hat zum Beispiel
(0, 1)
die maximalen Abwurfpunkte(1, 1)
und(1, 2)
. Die Auswahl einer der beiden Optionen und die anschließende Berechnung des Minimums führt zu folgendem Ergebnis:quelle
Hier ist eine andere Idee:
Beginnen wir damit, jedem Feld auf dem Brett ein Gewicht zuzuweisen, wie viele Zahlen durch das Abwerfen einer Bombe reduziert würden. Wenn der Raum also eine Zahl ungleich Null hat, erhält er einen Punkt, und wenn ein angrenzender Raum eine Zahl ungleich Null hat, erhält er einen zusätzlichen Punkt. Wenn es also ein 1000-mal-1000-Raster gibt, wird jedem der 1 Million Felder ein Gewicht zugewiesen.
Sortieren Sie dann die Liste der Felder nach Gewicht und bombardieren Sie das Feld mit dem höchsten Gewicht. Dies ist sozusagen das Beste für unser Geld.
Aktualisieren Sie danach das Gewicht jedes Feldes, dessen Gewicht von der Bombe beeinflusst wird. Dies ist der Raum, den Sie bombardiert haben, und jeder Raum unmittelbar daneben und jeder Raum unmittelbar daneben. Mit anderen Worten, jeder Raum, dessen Wert durch die Bombardierung auf Null hätte reduziert werden können, oder der Wert eines benachbarten Raums, der auf Null reduziert werden könnte.
Sortieren Sie dann die Listenbereiche nach Gewicht neu. Da nur eine kleine Teilmenge der Felder durch die Bombardierung ihr Gewicht geändert hat, müssen Sie nicht die gesamte Liste neu erstellen, sondern nur diese in der Liste verschieben.
Bombardieren Sie den neuen Raum mit dem höchsten Gewicht und wiederholen Sie den Vorgang.
Dies garantiert, dass jeder Bombenangriff so viele Felder wie möglich reduziert (im Grunde trifft er so wenige Felder, die bereits Null sind, wie möglich), so dass es optimal wäre, außer dass es sich um Gewichte handeln kann. Daher müssen Sie möglicherweise eine Rückverfolgung durchführen, wenn es eine Krawatte für das Spitzengewicht gibt. Es kommt jedoch nur auf ein Unentschieden für das Spitzengewicht an, nicht auf andere Unentschieden. Hoffentlich ist es nicht zu viel Rückverfolgung.
Bearbeiten: Das folgende Gegenbeispiel von Mysticial zeigt, dass dies tatsächlich nicht garantiert optimal ist, unabhängig von Gewichtsbindungen. In einigen Fällen, wenn Sie das Gewicht in einem bestimmten Schritt so weit wie möglich reduzieren, sind die verbleibenden Bomben tatsächlich zu weit verteilt, um nach dem zweiten Schritt eine so hohe kumulative Reduzierung zu erzielen, wie Sie es mit einer etwas weniger gierigen Wahl im ersten Schritt hätten tun können. Ich war etwas irregeführt von der Vorstellung, dass die Ergebnisse unempfindlich gegenüber der Reihenfolge der Bombenanschläge sind. Sie sindunempfindlich gegenüber der Reihenfolge, da Sie jede Reihe von Bombenangriffen von Anfang an in einer anderen Reihenfolge wiederholen und am Ende das gleiche Ergebnis erhalten können. Daraus folgt jedoch nicht, dass Sie jeden Bombenanschlag einzeln betrachten können. Zumindest muss jeder Bombenanschlag so betrachtet werden, dass berücksichtigt wird, wie gut er das Brett für nachfolgende Bombenangriffe vorbereitet.
quelle
1010101
,0010100
Könnte ein Gegenbeispiel sein , die diesen Ansatz erweist sich als nicht optimal. Dieser Ansatz erfordert 3. Es kann in 2.Nehmen wir an, wir nummerieren die Boardpositionen 1, 2, ..., nx m. Jede Folge von Bombenabwürfen kann durch eine Folge von Zahlen in diesem Satz dargestellt werden, wobei sich Zahlen wiederholen können. Der Effekt auf dem Brett ist jedoch der gleiche, unabhängig davon, in welcher Reihenfolge Sie die Bomben abwerfen. Daher kann wirklich jede Auswahl an Bombenabwürfen als Liste von nxm-Zahlen dargestellt werden, wobei die erste Zahl die Anzahl der auf Position 1 abgeworfenen Bomben darstellt Die zweite Zahl gibt die Anzahl der Bomben an, die auf Position 2 usw. abgeworfen wurden. Nennen wir diese Liste der nxm-Zahlen den "Schlüssel".
Sie können versuchen, zuerst alle Board-Zustände zu berechnen, die sich aus einem Bombenabwurf ergeben, und dann alle Board-Zustände zu berechnen, die sich aus 2 Bombenabwürfen usw. ergeben, bis Sie alle Nullen erhalten. Bei jedem Schritt würden Sie die Zustände mit dem oben definierten Schlüssel zwischenspeichern, damit Sie diese Ergebnisse bei der Berechnung des nächsten Schritts verwenden können (ein "dynamischer Programmier" -Ansatz).
Abhängig von der Größe von n, m und den Zahlen im Raster kann der Speicherbedarf dieses Ansatzes jedoch zu hoch sein. Sie können alle Ergebnisse für N Bombenabwürfe wegwerfen, sobald Sie alle Ergebnisse für N + 1 berechnet haben. Dort gibt es also einige Einsparungen. Und natürlich können Sie nichts zwischenspeichern, wenn es viel länger dauert - der dynamische Programmieransatz tauscht Speicher gegen Geschwindigkeit.
quelle
Wenn Sie die absolut optimale Lösung zum Reinigen des Boards wünschen, müssen Sie klassisches Backtracking verwenden. Wenn die Matrix jedoch sehr groß ist, dauert es ewig, bis die beste Lösung gefunden ist. Wenn Sie eine "mögliche" optimale Lösung wünschen, können Sie den Greedy-Algorithmus verwenden Wenn Sie Hilfe beim Schreiben des Algorithmus benötigen, kann ich Ihnen helfen
Kommen Sie und denken Sie daran, das ist der beste Weg. Erstellen Sie dort eine weitere Matrix, in der Sie die Punkte speichern, die Sie entfernen, indem Sie dort eine Bombe ablegen. Wählen Sie dann die Zelle mit den maximalen Punkten aus und lassen Sie die Bombe dort fallen. Aktualisieren Sie die Punktematrix und fahren Sie fort. Beispiel:
Zellenwert +1 für jede benachbarte Zelle mit einem Wert höher als 0
quelle
Rohe Gewalt !
Ich weiß, dass es nicht effizient ist, aber selbst wenn Sie einen schnelleren Algorithmus finden, können Sie immer anhand dieses Ergebnisses testen, wie genau es ist.
Verwenden Sie eine Rekursion wie folgt:
Sie können dies durch Zwischenspeichern effizienter gestalten. Wenn unterschiedliche Methoden zu demselben Ergebnis führen, sollten Sie nicht dieselben Schritte wiederholen.
Um dies zu erläutern:
Wenn die Bombardierung der Zelle 1,3,5 zum gleichen Ergebnis führt wie die Bombardierung der Zelle 5,3,1, sollten Sie in beiden Fällen nicht alle nächsten Schritte erneut ausführen. Nur 1 ist ausreichend. Sie sollten alle irgendwo speichern Tabelle gibt an und verwendet die Ergebnisse.
Ein Hash von Tabellenstatistiken kann verwendet werden, um einen schnellen Vergleich durchzuführen.
quelle
Bearbeiten: Ich habe nicht bemerkt, dass Kostek fast den gleichen Ansatz vorgeschlagen hat, daher behaupte ich jetzt stärker: Wenn zu löschende Ecken so gewählt werden, dass sie sich immer auf der äußersten Ebene befinden, ist dies optimal.
Im Beispiel von OP: Wenn Sie 2 (als 1 + 1 oder 2) auf etwas anderes als auf 5 fallen lassen, wird kein Quadrat getroffen, das auf 5 fallen würde. Also müssen wir einfach 2 auf 5 fallen lassen (und 6 auf links unten 1 ...)
Danach gibt es nur noch eine Möglichkeit, die Ecke (oben links) zu löschen, die ursprünglich 1 (jetzt 0) war, und zwar durch Ablegen von 0 auf B3 (Excel-ähnliche Notation). Und so weiter.
Beginnen Sie erst nach dem Löschen ganzer A- und E-Spalten sowie 1 und 7 Zeilen mit dem Löschen einer Ebene tiefer.
Betrachten Sie das Löschen nur der absichtlich gelöschten. Das Löschen von Ecken mit 0 Werten kostet nichts und vereinfacht das Nachdenken darüber.
Da alle auf diese Weise abgeworfenen Bomben abgeworfen werden müssen und dies zu geräumten Feldern führt, ist dies eine optimale Lösung.
Nach einem guten Schlaf wurde mir klar, dass dies nicht stimmt. Erwägen
Mein Ansatz würde Bomben auf B3 und C2 abwerfen, wenn das Abwerfen auf B2 ausreichen würde
quelle
Hier ist meine Lösung. Ich werde es noch nicht in Code schreiben, da ich keine Zeit habe, aber ich glaube, dass dies jedes Mal eine optimale Anzahl von Zügen erzeugen sollte - obwohl ich nicht sicher bin, wie effizient es sein würde, es zu finden die Punkte zu bombardieren.
Erstens, wie @Luka Rahne in einem der Kommentare feststellte, ist die Reihenfolge, in der Sie bombardieren, nicht wichtig - nur die Kombination.
Zweitens ist, wie viele andere angegeben haben, das Bombardieren der Diagonale von den Ecken aus optimal, da es mehr Punkte als die Ecken berührt.
Dies bildet die Grundlage für meine Version des Algorithmus: Wir können das "1-off von den Ecken" zuerst oder zuletzt bombardieren, es spielt keine Rolle (theoretisch). Wir bombardieren diese zuerst, weil es spätere Entscheidungen erleichtert (in der Praxis). Wir bombardieren den Punkt, der die meisten Punkte betrifft, und bombardieren gleichzeitig diese Ecken.
Definieren wir Widerstandspunkte als die Punkte auf dem Brett mit den nicht bombardierbarsten Punkten + der größten Anzahl von Nullen um sie herum
Nicht bombardierbare Punkte können als Punkte definiert werden, die in unserem aktuellen Geltungsbereich nicht existieren des Boards, das wir betrachten, sind.
Ich werde auch 4 Grenzen definieren, die unseren Bereich behandeln: Oben = 0, Links = 0, Unten = k, rechts = j. (Werte zum Starten)
Schließlich definiere ich optimale Bomben als Bomben, die auf Punkte abgeworfen werden, die an Widerstandspunkte angrenzen und (1) den höchstwertigen Widerstandspunkt und (2) die größtmögliche Anzahl von Punkten berühren.
In Bezug auf den Ansatz ist es offensichtlich, dass wir von außen nach innen arbeiten. Wir werden in der Lage sein, gleichzeitig mit 4 'Bombern' zu arbeiten.
Die ersten Widerstandspunkte sind offensichtlich unsere Ecken. Die "out of bound" -Punkte sind nicht bombardierbar (es gibt 5 Punkte außerhalb des Bereichs für jede Ecke). Also bombardieren wir die Punkte diagonal zuerst an den Ecken.
Algorithmus:
Wiederholen, bis TOP = BOTTOM und LEFT = RIGHT
Ich werde später versuchen, den eigentlichen Code zu schreiben
quelle
Sie könnten die Zustandsraumplanung verwenden. Verwenden Sie beispielsweise A * (oder eine seiner Varianten) in Verbindung mit einer Heuristik
f = g + h
wie dieser:quelle
Ich habe auch 28 Züge. Ich habe zwei Tests für den besten nächsten Zug verwendet: erstens den Zug, der die minimale Summe für das Brett ergibt. Zweitens für gleiche Summen die Bewegung, die die maximale Dichte erzeugt, definiert als:
Das ist Haskell. "Karte lösen" zeigt die Lösung des Motors. Sie können das Spiel spielen, indem Sie "main" eingeben und dann einen Zielpunkt eingeben, "best" für eine Empfehlung oder "quit", um das Spiel zu beenden.
AUSGABE:
* Haupt> Karte lösen
[(4,4), (3,6), (3,3), (2,2), (2,2), (4,6), (4,6), (2,6), (3,2), (4,2), (2,6), (3,3), (4,3), (2,6), (4,2), (4 , 6), (4,6), (3,6), (2,6), (2,6), (2,4), (2,4), (2,6), (3,6 ), (4,2), (4,2), (4,2), (4,2)]
quelle
Hier scheint es eine nicht zweigeteilte passende Unterstruktur zu geben. Betrachten Sie die folgende Instanz:
Die optimale Lösung für diesen Fall hat die Größe 5, da dies die Größe einer minimalen Abdeckung der Eckpunkte eines 9-Zyklus durch seine Kanten ist.
Insbesondere dieser Fall zeigt, dass die von einigen Leuten veröffentlichte lineare Programmierentspannung nicht genau ist, nicht funktioniert und all diese anderen schlechten Dinge. Ich bin mir ziemlich sicher, dass ich "die Eckpunkte meines planaren kubischen Graphen um so wenige Kanten wie möglich abdecken" auf Ihr Problem reduzieren kann, was mich bezweifeln lässt, ob eine der gierigen / Bergsteigerlösungen funktionieren wird.
Ich sehe keinen Weg, dies im schlimmsten Fall in Polynomzeit zu lösen. Möglicherweise gibt es eine sehr clevere binäre Such- und DP-Lösung, die ich nicht sehe.
EDIT : Ich sehe, dass der Wettbewerb ( http://deadline24.pl ) sprachunabhängig ist; Sie senden Ihnen eine Reihe von Eingabedateien und Sie senden ihnen Ausgaben. Sie brauchen also nichts, was in der Polynomzeit des schlimmsten Falls läuft. Insbesondere können Sie sich die Eingabe ansehen !
Es gibt eine Reihe kleiner Fälle in der Eingabe. Dann gibt es einen 10x1000-Fall, einen 100x100-Fall und einen 1000x1000-Fall. Die drei großen Fälle sind alle sehr brav. Horizontal benachbarte Einträge haben normalerweise den gleichen Wert. Auf einer relativ bulligen Maschine kann ich alle Fälle durch Brute-Forcing mit CPLEX in nur wenigen Minuten lösen. Ich hatte Glück auf der 1000x1000; Die LP-Relaxation hat zufällig eine ganzheitliche optimale Lösung. Meine Lösungen stimmen mit den
.ans
im Testdatenpaket enthaltenen Dateien überein .Ich wette, Sie können die Struktur der Eingabe viel direkter verwenden als ich, wenn Sie sie sich ansehen. Es scheint, als könnten Sie die erste Reihe oder zwei oder drei wiederholt abschneiden, bis Sie nichts mehr übrig haben. (Sieht so aus, als würden im 1000x1000 alle Zeilen nicht zunehmen? Ich denke, dort kommt Ihr "Teil B" her?)
quelle
Ich kann mir keine Möglichkeit vorstellen, die tatsächliche Anzahl zu berechnen, ohne nur die Bombenkampagne mit meiner besten Heuristik zu berechnen, und hoffe, dass ich ein vernünftiges Ergebnis erhalte.
Meine Methode besteht also darin, für jede Zelle eine Bombing-Effizienz-Metrik zu berechnen, die Zelle mit dem höchsten Wert zu bombardieren und den Prozess zu wiederholen, bis ich alles abgeflacht habe. Einige haben befürwortet, einfachen potenziellen Schaden (dh Punktzahl von 0 bis 9) als Metrik zu verwenden, aber dies wird nicht erreicht, indem hochwertige Zellen geschlagen werden und keine Schadensüberlappung verwendet wird. Ich würde berechnen
cell value - sum of all neighbouring cells
, jedes positive auf 0 zurücksetzen und den absoluten Wert von allem negativen verwenden. Intuitiv sollte diese Metrik eine Auswahl treffen, die dazu beiträgt, die Schadensüberlappung bei Zellen mit hoher Anzahl zu maximieren, anstatt diese direkt zu zerstören.Der folgende Code erreicht die vollständige Zerstörung des Testfelds in 28 Bomben (beachten Sie, dass die Verwendung von potenziellem Schaden als Metrik 31 ergibt!).
Das resultierende Bombenmuster wird wie folgt ausgegeben (Feldwerte links, Metrik rechts)
quelle
Dies kann mit einem Baum der Tiefe O (3 ^ (n)) gelöst werden. Wobei n die Summe aller Quadrate ist.
Betrachten Sie zunächst, dass es trivial ist, das Problem mit einem Baum von O (9 ^ n) zu lösen, und betrachten Sie einfach alle möglichen Bombardierungsorte. Ein Beispiel finden Sie in der Implementierung von Alfe .
Als nächstes stellen wir fest, dass wir daran arbeiten können, von unten nach oben zu bombardieren und trotzdem ein minimales Bombenmuster zu erhalten.
Dieser Algorithmus ist richtig, weil
In der Praxis ist dieser Algorithmus regelmäßig besser als sein theoretisches Maximum, da er regelmäßig Nachbarn bombardiert und die Größe der Suche verringert. Wenn wir annehmen, dass jede Bombardierung den Wert von 4 zusätzlichen Zielen verringert, wird unser Algorithmus in O (3 ^ (n / 4)) oder ungefähr O (1,3 ^ n) ausgeführt.
Da dieser Algorithmus immer noch exponentiell ist, ist es ratsam, die Suchtiefe zu begrenzen. Wir können die Anzahl der zulässigen Verzweigungen auf eine bestimmte Anzahl X beschränken, und sobald wir so tief sind, zwingen wir den Algorithmus, den besten Pfad zu wählen, den er bisher identifiziert hat (den, der die minimale Gesamtsumme der Platine in einem seiner Terminalblätter aufweist ). Dann wird garantiert, dass unser Algorithmus in O (3 ^ X) -Zeit ausgeführt wird, aber es wird nicht garantiert, dass er die richtige Antwort erhält. Wir können jedoch immer X erhöhen und empirisch testen, ob sich der Kompromiss zwischen erhöhter Berechnung und besseren Antworten lohnt.
quelle
Bewertungsfunktion, Gesamtsumme:
Zielfunktion:
Zerstörungsfunktion:
Zielfunktion:
lineare Maximierungsfunktion:
Dies ist nicht optimal, kann aber durch die Suche nach einer besseren Bewertungsfunktion optimiert werden.
.. aber als ich über dieses Problem nachdachte, dachte ich, dass eines der Hauptprobleme darin besteht, irgendwann verlassene Zahlen in der Mitte von Nullen zu bekommen, also würde ich einen anderen Ansatz wählen .. das ist, dominierende Minimalwerte in Null zu dominieren, und dann versuchen Escape-Nullen wie möglich, was zu einer allgemeinen Minimierung der minimalen vorhandenen Werte führt
quelle
Dieses Problem besteht lediglich darin, eine Bearbeitungsentfernung zu berechnen. Berechnen Sie einfach eine Variante des Levenshtein-Abstands zwischen der angegebenen Matrix und der Nullmatrix, wobei Änderungen durch Bombenangriffe ersetzt werden. Verwenden Sie dazu die dynamische Programmierung, um die Abstände zwischen Zwischenarrays zu speichern. Ich schlage vor, einen Hash der Matrizen als Schlüssel zu verwenden. In Pseudo-Python:
quelle
Dies war eine Antwort auf die erste gestellte Frage. Ich hatte nicht bemerkt, dass er die Parameter geändert hatte.
Erstellen Sie eine Liste aller Ziele. Weisen Sie dem Ziel einen Wert zu, der auf der Anzahl der positiven Werte basiert, die von einem Abfall betroffen sind (selbst und alle Nachbarn). Der höchste Wert wäre eine Neun.
Sortieren Sie die Ziele nach der Anzahl der betroffenen Ziele (absteigend), wobei eine sekundäre absteigende Sortierung nach der Summe jedes betroffenen Ziels erfolgt.
Wirf eine Bombe auf das Ziel mit dem höchsten Rang, berechne die Ziele neu und wiederhole sie, bis alle Zielwerte Null sind.
Einverstanden ist dies nicht immer das Optimalste. Beispielsweise,
Dieser Ansatz würde 5 Bomben erfordern, um zu klären. Optimalerweise könnten Sie es in 4 schaffen. Trotzdem ziemlich nah dran und es gibt kein Backtracking. In den meisten Situationen ist es optimal oder sehr nahe.
Unter Verwendung der ursprünglichen Problemnummern löst dieser Ansatz 28 Bomben.
Hinzufügen von Code zur Demonstration dieses Ansatzes (mithilfe eines Formulars mit einer Schaltfläche):
Eine Klasse, die Sie brauchen werden:
quelle
09090
Dieser Ansatz erfordert 18 Bomben. Es kann in 9.1010101
,0010100
?