Ich bin auf dieses Problem gestoßen und habe Mühe, einen Weg zu finden, um es anzugehen. Irgendwelche Gedanken wären sehr dankbar!
Angenommen, wir erhalten eine Matrix , zum Beispiel
Suchen Sie ohne jede einzelne Permutation eine Reihenfolge der Spalten , die die Anzahl der Zeilen maximiert, für die das erste Nicht-Null-Element .
Für das obige Beispiel ist eine solche Reihenfolge (sie ist nicht eindeutig!) , dh
Hier ist für von Zeilen das erste Nicht-Null-Element .
Antworten:
Dieses Problem, das ich CO für die Spaltenbestellung nennen werde, ist NP-schwer . Hier ist eine Reduktion vom NP-harten Problem Vertex Cover (VC) darauf:
Entscheidungsproblemformen von VC und CO
Die VC-Eingangsinstanz sei(V,E,k) . Es stellt die Frage: "Ist es angesichts des Graphen ( V., E.) möglich, eine Menge von höchstens k Eckpunkten aus V. so zu wählen, dass jede Kante in E. auf mindestens einen ausgewählten Eckpunkt fällt?" Wir werden eine Instanz (A,k′) von CO konstruieren , die die Frage darstellt: "Gegeben ist die Matrix A mit Elementen in {−1,0,1} Ist es möglich, die Spalten von A so zu permutieren, dass eine 1 in mindestens k′ Zeilen vor einer -1 erscheint ? "Diese beiden Probleme werden in Form eines Entscheidungsproblems angegeben , wobei die Antwort auf jedes entweder JA oder NEIN lautet: formal Es ist nicht allzu schwer zu erkennen, dass die in der Frage des OP angegebene natürlichere Form des Optimierungsproblems in Bezug auf die Komplexität ungefähr gleichwertig ist: binäre Suche auf der Schwelle Parameter können verwendet werden, um das Optimierungsproblem unter Verwendung eines Entscheidungsproblemlösers zu lösen, während ein einzelner Aufruf eines Optimierungsproblemlösers, gefolgt von einem einzelnen Vergleich, ausreicht, um das Entscheidungsproblem zu lösen.
Erstellen einer CO-Instanz aus einer VC-Instanz
Sein=|V| und m=|E| . Wir werden eine Matrix A mit ( n + 1 ) m + n Zeilen und n + 1 Spalten erstellen . Die oberen ( n + 1 ) m Reihen bestehen aus m Blöcken mit jeweils n + 1 Reihen, wobei jeder Block eine Kante darstellt, die abgedeckt werden muss . Der Boden n Zeilen enthalten Scheitelpunkt- "Flags", die dazu führen, dass eine Spalte (die einem Scheitelpunkt entspricht) feste Kosten verursacht, wenn sie auf der linken Seite der CO-Lösung enthalten ist (entsprechend einem Scheitelpunkt, der in der Scheitelpunktabdeckung des enthalten ist VC-Lösung).
Erstellen Sie für jeden Scheitelpunktvich eine Spalte, in der:
Erstellen Sie eine weitere "Zaun" -Spalte, die aus( n + 1 ) m Kopien von -1 besteht, gefolgt von n Kopien von +1.
Stellen Sie schließlich den Schwellenwertk' für die konstruierte CO-Instanz ein: ( n + 1 ) m + n - k . Mit anderen Worten, wir erlauben höchstens k Zeilen, in denen ein -1 vor einem +1 erscheint. Nennen wir diese Anzahl verletzender Zeilen die "Kosten" einer CO-Lösung.
Beweis
Die Entsprechung zwischen einer Lösung für die CO-Instanz und einer Menge von Scheitelpunkten in der ursprünglichen VC-Instanz lautet: Jede Spalte links vom Zaun entspricht einem Scheitelpunkt, der sich in der Menge befindet, und jede Spalte rechts vom Zaun entspricht ein Scheitelpunkt, der nicht ist.
Intuitiv erzwingen die -1s oben in der "Zaun" -Spalte die Auswahl einer Teilmenge von Spalten, die links davon platziert werden sollen und zusammen +1s in all diesen Positionen enthalten - entsprechend einer Teilmenge von Eckpunkten, die auf jede einfallen Kante. Jede dieser Spalten, die links vom "Zaun" angezeigt wird, hat eine -1 in einer bestimmten Zeile irgendwo in den unterenn Zeilen, was Kosten von 1 verursacht. Die +1 am unteren Rand des "Zauns" stellen sicher, dass für alle rechts angeordneten Säulen keine derartigen Kosten anfallen.
Es ist klar, dass eine VC-Lösung, die höchstensk Eckpunkte verwendet, eine Lösung für die konstruierte CO-Instanz mit höchstens k Kosten ergibt : Ordnen Sie einfach die Spalten, die den Eckpunkten in der Scheitelpunktabdeckung entsprechen, willkürlich an, gefolgt von der Zaunsäule, gefolgt von allen verbleibenden Spalten in beliebiger Reihenfolge .
Es bleibt zu zeigen, dass eine Lösung für die CO-Instanz mit Kosten von höchstensk einer Scheitelpunktabdeckung mit höchstens k Scheitelpunkten entspricht.
Nehmen wir im Gegenteil an, es gibt eine Lösung für die CO-Instanz mit höchstensk Kosten , die eine Zeile in den oberen ( n + 1 ) m Zeilen mit einem -1 vor einem +1 belässt . Diese Zeile gehört zu einem Block von ( n + 1 ) Zeilen, die einer bestimmten Kante u v . Jede Zeile in diesem Block in der ursprünglichen Instanz EIN ist konstruktionsbedingt identisch. Das Permutieren von Spalten kann diese Zeilen ändern, hat jedoch keinen Einfluss auf die Tatsache, dass sie identisch sind. Somit hat jede dieser n + 1 identischen Zeilen ein -1 vor einem +1 in der Lösung, was Kosten von mindestens impliziertn + 1 . Aberk≤n<n+1 : Widerspruch.
Da jeder derm Zeilenblöcke in den oberen (n+1)m Zeilen eine +1 vor einer -1 hat, wird jede der entsprechenden Kanten von einem Scheitelpunkt abgedeckt, der einer Spalte links vom Zaun entspricht bildet diese Teilmenge von Eckpunkten eine Eckpunktabdeckung. Da keine der oberen (n+1)m Reihen eine -1 vor einer +1 hat, ist der einzige Ort, an dem Kosten in der Lösung anfallen können, in den unteren n Reihen von Spalten links vom Zaun. Jede solche Spalte hat genau 1 gekostet. Wenn also die Kosten höchstens k , müssen höchstens k solche Spalten und damit höchstens k Eckpunkte in der Abdeckung.
Schließlich ist klar, dass die CO-Instanz in Polynomzeit aus der VC-Instanz konstruiert werden kann, was bedeutet, dass, wenn ein Polynomzeitalgorithmus zum Lösen von CO vorhanden wäre, jede VC-Instanz auch in Polynomzeit gelöst werden könnte, indem zuerst eine CO-Instanz wie beschrieben konstruiert wird oben und dann lösen. Da VC NP-hart ist, ist es auch CO.
quelle
Ich weiß nicht, ob es tatsächlich eine Polynomlösung gibt. Basierend auf dem Kommentar von Pål GD können Sie jedoch eine Vereinfachungsfunktion erstellen. Die anfängliche Matrix wird vereinfacht, wenn Sie die AusgabesequenzS. erstellen .
Dann müssen Sie eine vollständige Untersuchung der Kombinatorik durchführen, indem Sie iterativ die Funktionsauswahl verwenden:
Nach jeder Auswahl können Sie eine Vereinfachung vornehmen, um möglicherweise die Anzahl der Erkundungsmöglichkeiten zu verringern. Ich schlage vor, gierig zu erkunden, beginnend mit der Spalte mit dem Wert weniger -1, damit Sie eine Untergrenze erreichen und ein Stoppkriterium festlegen können.
Auf dem gegebenen Beispiel gibt die erste Vereinfachung (wie Pål GD im Kommentar erklärte)
Ich denke, eine Matrix, die diese Methode ziemlich ineffizient macht, hätte genau eine 1 und eine -1 pro Zeile / Spalte, so etwas wie⎡⎣⎢⎢⎢⎢⎢⎢⎢⎢- 1100001- 1000000- 1100001- 1000000- 1100001- 1⎤⎦⎥⎥⎥⎥⎥⎥⎥⎥
Trotzdem vereinfacht die Vereinfachung noch etwa die Hälfte der Explorationsschritte. Und diese Art von Matrix kann in mehrere unabhängige Submatrix aufgeteilt werden.
quelle