Ich habe eine Zeit lang über das folgende Problem nachgedacht und keine polynomielle Lösung dafür gefunden. Nur rohe Quelle. Ich habe versucht, ein NP-Complete-Problem ohne Erfolg zu reduzieren.
Hier ist das Problem :
Sie haben eine sortierte Menge positiver ganzzahliger Paare.
Die folgende Operation kann zu einem Paar angewendet werden: Swap(pair)
. Es tauscht die Elemente des Paares aus, sodass zu
Wenn ein Paar im Set getauscht wird, wird das Set automatisch erneut sortiert (das getauschte Paar ist nicht richtig platziert und wird an seinen Platz im Set verschoben).
Das Problem besteht darin, zu sehen, ob es eine Sequenz gibt, die, beginnend mit einem Paar, den gesamten Satz mit der folgenden Bedingung austauscht:
Nachdem ein Paar getauscht wurde, muss das nächste auszutauschende Paar entweder das Nachfolger- oder das Vorgängerpaar im Satz sein.
Es wäre großartig, eine polynomielle Zeitlösung für dieses Problem zu finden oder ein NP-vollständiges Problem darin zu reduzieren.
Hinweis:
Es ist bereits ein Entscheidungsproblem. Ich möchte nicht wissen, um welche Sequenz es sich handelt: Nur wenn eine Sequenz existiert.
Beispiel, wie das Set nach dem Tausch eines Paares sortiert wird
( 1 , 2 ) ( 3 , 4 ) ( 7 , 8 )
Wenn ich das erste Paar vertausche, wird es zu: , und nach dem Sortieren des Satzes (Platzieren des sortierten Paares an seiner neuen Position) haben wir:
( 3 , 4 ) (5,6) ( 7 , 8 )
Dann muss ich entweder das (Vorgänger) Paar oder ( 7 , 8 ) (Nachfolger) tauschen und den Vorgang wiederholen, bis alle Paare getauscht sind (falls möglich).
Wichtig:
Ein bereits getauschtes Paar kann nicht getauscht werden.
Wenn es eine Folge von 'Swap'-Operationen gibt, müssen alle Paare einmal und nur einmal umbenannt werden.
Beispiel, bei dem nicht alle Paare getauscht werden können
( 1 , 4 ) ( 3 , 2 ) ( 5 , 5 )
quelle
Antworten:
... Ich habe einige Muster durchsucht, um eine Reduktion aus einem NPC-Problem zu erstellen, habe aber keine Möglichkeit gefunden, einen "Fluss" mit einer "Gabel" darzustellen ...
Also (nach einiger Arbeit) ist dies ein Polynomalgorithmus ...
ALGORITHMUS
Die Startliste kann als Array von aufeinanderfolgenden " Löchern " angesehen werden. Setzen Sie für jedes Anfangspaar ( a j , b j ) das " Element " b j an Lochnummer a j . Jedes Paar kann als gerichtete Kante von Position a j bis Position b j betrachtet werden . Ein Zug besteht , ein Element in der Kommissionierung b j an Position a j und es zu seiner Zielposition zu bewegen b jN∗2 (aj,bj) bj aj aj bj bj aj bj (das Zielloch wird zum unmovable PEG ). Wir löschen die Kante und wählen den nächsten Zug, der von einem der beiden am nächsten erreichbaren Elemente ab Position b j beginnt (nur Löcher zwischen b j und b k sind zulässig). Wir müssen eine Folge von N aufeinanderfolgenden Zügen finden.bk bj bj bk N
Für jedes betrachte b j (an der Array-Position a j ) als das Startelement s t a r t .(aj,bj) bj aj start
Für jedes betrachten einen k als letztes Element e n d (die Kante von Position a k zur Position b k wird die letzte Kante sein).(ak,bk),ak≠aj ak end ak bk
Wenn Sie einen Schritt machen fixieren Sie einen Stift an Position und das Array ist in zwei Partitionen aufgeteilt L (links) und R (rechts) und den einzigen Weg aus zu gehen , L bis R (oder von R bis L ) einem unter Verwendung von Kante, die über den Stift springt. einstellenbj L R L R R L
Fälle:
A) wenn wenn eine der beiden Partitionen nicht mehr erreichbar ist, stoppen Sie|flow|>1
Nehmen wir nun an, dass , dh e n d ∈ Rend>bj end∈R
B) Wenn dann gibt es eine zusätzliche Kante von links nach rechts, Sie müssen nach links gehen (wählen Sie das nächste Element von L ), sonst werden Sie nie e n d erreichenflow=1 L end
C) Wenn ist, gibt es eine zusätzliche Kante von rechts nach links, und welcher Knoten auch immer Sie auswählen, Sie werden niemals e n d erreichen , stoppen Sieflow=−1 end
D) Wenn , müssen Sie nach rechts gehen (wählen Sie das nächste Element von R ), andernfalls werden Sie e n d nicht erreichenflow=0 R end
Wenden Sie bei jeder Bewegung die gleiche Resonanz an.
KOMPLEXITÄT
Die Ströme über jedes Loch können in O (N) vorberechnet und bei jedem Scan erneut verwendet werden.
Die Schleifen sind:
CODE
Dies ist eine funktionierende Java-Implementierung des Algorithmus:
quelle
Dies ist keine Lösung, sondern eine Neuformulierung, die die explizite Erwähnung der Austausch- und Sortiervorgänge vermeidet. Sortieren Sie zunächst die gesamte kombinierte Liste der Dateinamen und ihrer ausgetauschten Versionen, und identifizieren Sie jeden Dateinamen mit seinem Index in dieser Liste. Dann sind zwei Dateien Nachbarn, wenn alle alten Dateinamen zwischen ihnen bereits zerstört wurden und noch keiner der neuen Dateinamen zwischen ihnen erstellt wurde. Das umformulierte Problem ist das folgende:
quelle