Ich bin nicht gut in der programmatischen Implementierung eines heuristischen Suchalgorithmus / Dijkstra-Algorithmus / A * -Suchalgorithmus erwähnt. Während der Lösung eines Problems, das in einem meiner Beiträge erwähnt wurde ( Matrixmanipulation: Logik wird nicht korrekt gelesen für NXN-Matrixdaten höherer Ordnung ), Fand ich einen Fehler in meinem Ansatz, um das Problem zu lösen. Die Problembeschreibung ist wie folgt.
Problembeschreibung
Es gibt eine NxN-Matrix, die in N * N-Zellen unterteilt ist. Jede Zelle hat einen vordefinierten Wert. Was würde als Eingabe gegeben werden. Die Iteration muss K-mal vorkommen, was auch im Testeingang angegeben ist. Wir müssen sicherstellen, dass wir bei jeder Iteration den optimalen Wert / min für Zeilen / Spalten auswählen. Die endgültige Ausgabe ist die kumulative Summe des optimalen Werts, der am Ende jeder Iteration gespeichert wird.
Schritte 1. Fassen Sie die einzelnen Zeilen und Spalten zusammen und suchen Sie nach der minimalen Summe von Zeilen und Spalten (es könnte eine Zeile oder eine Spalte sein, brauchen Sie nur die minimale Zeile oder eine Spalte)
Schritt 2. Speichern Sie die oben gefundene Summe separat
Schritt 3. Inkremente Elemente der min. Summe Zeile oder Spalte. um 1
Wiederholen Sie die Schritte 1,2,3 von 1 bis K-Wert
addiere die Summe bei jeder Iteration (spezifiziert in Schritt 2)
output ist die Summe, die bei der K-ten Iteration erhalten wird.
Beispieldaten
%Vor%Ausgabedaten 22
Mein Code
%Vor%Problem mit meinem Code
Diese Lösung funktionierte für eine Matrix niedrigerer Ordnung und einfache Szenarien. Als ich jedoch Testfälle mit einer 100x100 großen Matrix ausprobierte, waren viele Testfälle fehlgeschlagen. Anfangs dachte ich, es wäre ein Speicherproblem / Stack-Überlauf, wenn die Array-Größe zunimmt, aber jetzt habe ich herausgefunden, dass es ein Fehler im Code ist, dass ich nicht den richtigen Weg antizipieren kann, der mich schließlich zur optimalen Lösung führen würde Ich würde gerne erreichen.
Der Fehler, den ich in meinem Code gefunden habe, ist in einem Szenario, wenn der optimale Wert aus beiden Zeilen und Spalten gleich ist. Ich bin frei, Zeile oder Spalte zu wählen, aber das Problem hier ist, sagen wir, wenn ich mit Reihe zuerst gehe, kann es die Werte der Reihe auf einen nicht optimalen Wert aktualisieren, ich glaube, dass ich vorher alle optimalen Wege kennen würde würde mir helfen, die richtige Antwort zu bekommen.
Jede Hilfe in dieser Hinsicht würde sehr geschätzt werden.
Diese Frage bezieht sich auf die Frage, die hier gestellt wird. Matrixmanipulation: Logik erhält keine richtige Antwort für NXN-Matrixdaten höherer Ordnung
Nur wenn eine Matrix höherer Ordnung verwendet wird, erhalte ich den folgenden Unterschied in der Ausgabe, wenn ich den obigen Ansatz anwende. Bearbeiten:
%Vor%Fall 3 (meine Ausgabe war 50778 und die erwartete war 50708) Fall 2 Beispieldaten unten (meine Ausgabe war 30066 und die erwartete war 30050)
%Vor% Dies ist der Algorithmus, den ich gefunden habe. Es ist O(n^2) , also ist es optimal. Warum? Sie müssen n^2 cells lesen, damit OPT mindestens O(n^2) ist.
Zählt die Summe aller Zeilen und aller Spalten. Speichern Sie sie in einem class wie folgt:
Der Algorithmus ist:
%Vor% Speichern Sie Sum s in heap - z. %Code%. Schreibe lieber deinen eigenen Haufen. Es kann auch eine Liste sein, die Sie sortieren, aber es wird weniger effizient sein. Hier müssen Sie untersuchen, welche Datenstruktur beim Umsortieren am effizientesten ist, wenn die Hälfte der Elemente inkrementiert und eine stark vergrößert wird.
Ich habe die Arbeitslösung mit java.util.PriorityQueue implementiert. Fühlen Sie sich frei, es zu verwenden, aber Sie müssen den Code ein wenig für die Effizienz ändern.
Dieser Code gibt ArrayList zurück, falls 30050 . Still 100 57 für 50778 Testfall.
Ich bin ein Neuling für Java. Also verwende ich diesen naiven Ansatz, um das Ergebnis für Ihr Problem zu finden. Ich berechne die Zeilensumme und die Spaltensumme und finde den Mindestwert und inkrementiere ihn entsprechend um +1. Wenn ich denselben Wert für Zeile und Spalte vorfinde, versuche ich, die Zeilen- und Spaltenwerte der vorherigen Iteration beizubehalten und die nächste von dort zu holen und zu inkrementieren.
Ich habe auch nicht nur für die NxN-Matrix, sondern auch für die MxN-Matrix gesorgt.
Unten ist mein Ansatz für dieses Problem:
%Vor%Sie können die Effizienz leicht verbessern, indem Sie einen besseren Ansatz verwenden.
Unten ist mein Code. Wenn es zu einem mehrdeutigen Fall kommt (wenn die Minimalwerte in Zeile und Spalte gefunden werden), versucht es beide Fälle und gibt das Minimum aus.
Bei jeder Iteration werden zwei Listen von n -Werten sortiert. Die Komplexität ist also O(C*k*n log n) , wobei C die Anzahl der verschiedenen Pfade ist. Ich glaube, das ist ziemlich nah an der optimalen (in Bezug auf die Komplexität für Brute-Force), da nach jeder Iteration, genau n+1 -Werte ändern und so müssen wir mindestens jeden von ihnen berühren (außer natürlich, einige mehr algorithmische Einsicht erlaubt es uns, nur einige von ihnen zu berühren). Abhängig von den Werten von k und n ist dies möglicherweise nicht ausreichend. Für Fall 2 läuft es in etwas mehr als 1 Sekunde.
Es kann auch den ausgewählten Pfad drucken, wenn Sie -v Argument:
java MinRowCol MinRowCol.test -v
Es gibt andere Optionen:
-quick - Dadurch wird die Anzahl der erkannten Fälle durch die Verwendung von Heuristiken reduziert. Die Heuristik kann mit anderen Optionen angegeben werden. -prefer_col - Dies wird Spalte über Zeile bevorzugen (standardmäßig lieber Zeile)
-use_sum_count - Dies wird die verwenden Multiplizität der Summe
Für kleine Testfälle wie folgt:
%Vor%Es wird ausgegeben:
%Vor%Das heißt, es hat drei mögliche Wege gefunden, zwei davon haben den Wert 3, einer hat den Wert 2. Also wählt er den einen mit dem Wert 2, und Sie können die getroffenen Entscheidungen sehen (die Summe und die Reihe / Spalte). Sie können sehen, dass die Auswahl der Spalte am Ende zu einem kleineren Wert führt.
Für Fall 3 (Fall 2 hat zu viele Optionen, um hier angezeigt zu werden) führen die vier Fälle zur gleichen Antwort:
%Vor%Für Fall 2 lautet das Ergebnis wie folgt:
Ohne Optionen (in allen Fällen suchen):
%Vor%Mit -quick -prefer_row:
%Vor%Mit -quick -prefer_col:
%Vor%Wir müssen also mehrere Pfade erkunden. Aber ich bin nicht sicher, warum für Fall 3 die richtige Antwort 50708 statt 50778 sein sollte.
Sie müssen nicht wirklich die ganze Matrix behalten, nur die Summen, nach Zeile und Spalte.
Gegeben sei eine NxN-Matrix, SumByRow sei ein Vektor der Länge N, der die Summe jeder Zeile der Matrix enthält, und SumByCol sei das Gleiche bezüglich der Spalten. In Ihrem Beispiel wären diese Vektoren:
%Vor%Jetzt können wir unabhängig vom tatsächlichen Index der Mindestzeile [Spalte] sicher sein, dass bei der nächsten Iteration der SumByRow [Col] Vektor ein um N inkrementiertes Element haben würde (weil wir eins zu addieren) Jedes Element dieser Zeile [Spalte]) und die SumByCol [Zeile] würde jedem seiner Elemente 1 hinzugefügt haben (denn unabhängig von der Summe addieren wir eins zu eins und nur eines der Elemente, aus denen es besteht).
So können wir die große hässliche Matrix loswerden und mit diesen beiden Vektoren arbeiten. Die obigen Überlegungen schlagen auch eine Möglichkeit vor, die Iteration zu implementieren, nämlich:
%Vor%Es gibt einen letzten Knick, was sollen wir tun, wenn der Mindestwert der Summe sowohl in der Zeile als auch in der Spalte gleich ist? Zufällig zu sein ist nicht wirklich hilfreich, noch ist es immer die eine oder die andere, da diese Methoden Sie in eine suboptimale Spur bringen könnten, eine Art Lookahead ist dann gefragt. Ich entschied mich für eine einfache Simulation dessen, was im nächsten Schritt passieren würde, wenn beide Optionen auf eine rekursive, aber begrenzte Art und Weise ungültig gemacht würden, um so weit wie möglich nach vorne zu schauen. Aber es könnte durchaus eine effizientere heuristische Herangehensweise oder sogar eine vollständige Strategie geben, aber mir fällt momentan nichts ein.
BEARBEITEN: Eigentlich bin ich dank Just Half nicht mehr sicher, ob ein lokal gieriger Ansatz gut ist, denn eine optimale Strategie könnte mit einigen nicht explizit optimalen Entscheidungen beginnen ...
Hier ist der Code, den ich zusammengeschustert habe, um zu demonstrieren, es ist ziemlich hässlich, aber ich hoffe, dass es verständlich ist. Bitte lassen Sie es mich wissen, wenn Sie Fehler entdecken oder eine Klärung benötigen Ссылка
%Vor%Tags und Links algorithm java greedy binary-search-tree heuristics