Finden Sie eine optimale Bestellung

9

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 {1,0,1}n × k , zum Beispiel

[1010110001011011101110001]

Suchen Sie ohne jede einzelne Permutation eine Reihenfolge der Spalten , die die Anzahl der Zeilen maximiert, für die das erste Nicht-Null-Element .ci1

Für das obige Beispiel ist eine solche Reihenfolge (sie ist nicht eindeutig!) , dh(c3,c4,c1,c2,c5)

[1010100101100110111100101]

Hier ist für von Zeilen das erste Nicht-Null-Element .451

haijo
quelle
Welche algorithmischen Ansätze haben Sie versucht? Wo sind Sie auf dieses Problem gestoßen? Können Sie die ursprüngliche Quelle gutschreiben? Können Sie etwas über den Kontext oder die Motivation mitteilen? Vielleicht finden Sie diese Seite hilfreich bei der Verbesserung Ihrer Frage.
DW
1
Ich möchte einen Vorverarbeitungsschritt vorschlagen: Eine halbpositive Spalte (bzw. Zeile) sei eine Spalte (bzw. Zeile) mit nur 0 und 1. Der Vorschlag ist, alle halbpositiven Spalten sowie die Zeilen mit einer 1 in einer halbpositiven Spalte zu entfernen. In Ihrem Beispiel würden dadurch die Zeilen 1, 3 und 4 entfernt. Jetzt verbleiben Zeilen und Spalten, die alle -1s enthalten. Könnte nicht helfen, aber es könnte einfacher sein, darüber nachzudenken.
Pål GD
Können wir annehmen, dass die Anzahl der Zeilen viel kleiner ist als die Anzahl der Spalten? Dies könnte das Problem erleichtern.
Angela Richardson
1
@ Pål, eine ähnliche Vorverarbeitung ist mit Zeilen und Spalten möglich, die keine Einsen enthalten. Ich glaube jedoch nicht, dass es einfacher ist, darüber nachzudenken: nur kleiner.
Peter Taylor
1
FWIW das ist ein Cross-Post . haijo, wenn du auf einem Stapel keine Antwort erhältst und denkst, ein anderer könnte besser sein, kannst du sie markieren und eine Migration anfordern. Cross-Posting ist keine gute Etikette, da die Antwortenden die Antworten, die Sie möglicherweise auf der anderen Website erhalten haben, nicht kennen und möglicherweise ihre Zeit damit verschwenden, sie zu wiederholen.
Peter Taylor

Antworten:

4

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

Sei n=|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 Scheitelpunkt vi eine Spalte, in der:

  • unter dem ersten (n+1)m Reihen der j - ten Blöcke von n+1 enthält alle Zeilen ein +1 , wenn Kante ej fällt auf ist vi , und 0 sonst, und
  • Die unteren n Zeilen sind alle 0 mit Ausnahme des i ten, das -1 ist.

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 Schwellenwert k' 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 unteren n 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öchstens k 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öchstens k 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öchstens k 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 uv . 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 . Aberkn<n+1 : Widerspruch.

Da jeder der m 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 ksolche 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.

j_random_hacker
quelle
Wann immer es eine so nette Antwort gibt, frage ich mich, ob "Hot Network Questions" durch "Valuable Network Answers" ersetzt oder ergänzt werden sollten.
John L.
Könnten Sie etwas Licht ins Dunkel bringen, wie Sie die Antwort finden? Das sollte noch aufschlussreicher sein als die Antwort selbst.
John L.
1
@ Apass.Jack: Danke! :) Ich habe keine spezielle Strategie und kann lange Zeit in die falsche Richtung wandern. Zum Beispiel habe ich hier lange darüber nachgedacht, dass ich den Hamilton-Zyklus (der insofern ähnlich ist, als es um das Ordnen von Elementen geht) reduzieren könnte, bevor mir klar wurde, dass meine Konstruktion Konfigurationen zulässt, die Untertouren entsprechen, und daher nicht funktioniert. In der Regel versuche ich immer Reduzierungen von Vertex Cover oder Partition, dann vielleicht Clique. "Valuable Network Answers" klingt nach einer großartigen Idee :)
j_random_hacker
1
@ Apass.Jack: Eine nützliche allgemeine Idee ist es, darüber nachzudenken, wie Sie eine Zielprobleminstanz "skalieren" können, ohne ihre Antwort zu ändern - z. B. wenn das Zielproblem (was wir als schwierig erweisen wollen) Vertex Cover ist, was positiv ist Ganzzahl disjunkte Kopien des Graphen und auch das Multiplizieren des Schwellenwerts k mit r lässt die Antwort unverändert. Oft möchten Sie, dass bestimmte Verstöße (Ziellösungen, die nicht gültigen Quelllösungen entsprechen) bestimmte andere "überwältigen". In diesem Fall können Sie die Gadgets, die dem wichtigeren Verstoß entsprechen, "multiplizieren". rkr
j_random_hacker
1
Um meine Antwort zu reduzieren, möchten wir einen Fall eines Problems codieren, bei dem es zwei "Kräfte" gibt: Versuchen Sie, alle Kanten abzudecken, und versuchen Sie, so wenige Eckpunkte wie möglich zu verwenden. Die erste ist hier wichtiger, deshalb habe ich die Zeilen, die den Kanten entsprechen, "multipliziert": Jetzt kostet eine einzelne Kantenverletzung , was bedeutet, dass es schlimmer ist, eine einzelne Kante zu übersehen, als alle Eckpunkte einzuschließen. Und gerade wurde mir klar, dass ich die Antwort bearbeiten sollte, um deutlich zu machen, dass es sich um die Entscheidungsproblemversionen dieser beiden Probleme handelt, bei denen Schwellenparameter Teil der Probleminstanz sind ...n+1
j_random_hacker
2

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 Ausgabesequenz S. erstellen .

function simplification:
while(true)
    if any row i$ has no 1 or no -1 left, remove it
    if any column j has no -1 then,
       remove it and put j on the leftmost available position in S,
       remove all rows where column j has 1.
    if any column j has no 1 then, 
       remove it and put j on the rightmost available position in S.
    if no modification has been done on this loop, break

Dann müssen Sie eine vollständige Untersuchung der Kombinatorik durchführen, indem Sie iterativ die Funktionsauswahl verwenden:

function pick(k):
    put column k on the leftmost available position in S
    remove any row where column k is -1 or 1

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)

  • S[0]]=c3 , entferne r1, r3
  • S.[1]]=c4 , entferne r4
  • S.[2]]=c2 Damit können Sie eine einfache Matrix erkunden.
    [- -111- -1]]

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.

Optidad
quelle
1
@ Apass.Jack Ich habe es genauer bearbeitet. Ja, ich meinte die Spaltenposition in der Ausgabesequenz.
Optidad
Upvoted als Vereinfachungsschritt könnte für praktische Zwecke gut genug sein (wie Online-Programmierübungen?).
John L.
Vielen Dank, tatsächlich war ich daran interessiert, die amortisierten Zeitkosten abzuschätzen, aber ich weiß nicht wirklich, wie ich das machen soll. Ist das möglich ? Oder ist es zu viel problemabhängig?
Optidad
2
ijijjij
1
ijijijijikk