Komplexität der Homogenisierung eines Strings

10

Motivation : Bei der Entwicklung von Tools für die Datenversionierung haben wir uns schließlich mit Algorithmen zum "Unterscheiden" zweier Sätze von Ganzzahlen befasst, indem wir eine Folge von Transformationen entwickelt haben, die einen Satz von Ganzzahlen zum anderen führen. Wir konnten dieses Problem auf das folgende sehr natürliche Problem reduzieren, das Verbindungen zum Bearbeiten der Entfernung, zum Gruppieren durch Austauschen und zur minimalen gemeinsamen Zeichenfolgenpartition zu haben scheint .

Problem : Wir erhalten eine Zeichenfolge, dh eine Folge von Buchstaben, und unser Ziel ist es, sie zu minimalen Kosten zu homogenisieren . Das heißt, wir wollen eine neu angeordnete Sequenz, so dass alle Buchstaben, die gleich sind, nebeneinander liegen.

Die einzige Operation , die erlaubt ist, besteht darin, eine Teilfolge von Buchstaben aufzunehmen, die gleich sind, und diese Teilfolge irgendwohin zu verschieben, was mich 1 Einheit kostet.

Jede Hilfe, die die Komplexität dieses Problems charakterisiert, wäre sehr dankbar!

Beispiel :

  • aabcdab: Eingabe
  • bcd aa ab: Nach dem Verschieben des ersten aa in die Position direkt nach "d"
  • b bcdaaa: Nachdem Sie das nachfolgende b in die erste Position gebracht haben

Da die resultierende Zeichenfolge homogen ist, haben wir Kosten von 2.

Beachten Sie, dass wir in Bezug auf die Ausgabe in keiner Weise eingeschränkt sind: Solange diese homogen ist, müssen wir keine bestimmte Reihenfolge sicherstellen.

Aditya Parameswaran
quelle

Antworten:

6

Dieses Problem ist NP-vollständig, indem es vom Minimum Hitting Set reduziert wird .

USsS,sUHUsS,hHhs

Die Reduzierung ist wie folgt:

  • uUussSusu

  • s|s|1suusu

  • ususssSssu

  • |s|+|H|H

Da der minimale Schlagsatz NP-hart ist, ist auch eine optimale Homogenisierung einer Saite möglich. Da die Bewegungen einen Zeugen bilden, ist es NP-Complete.

isaacg
quelle
Dies ist eine elegante Reduktion - danke!
Aditya Parameswaran
2

Sehen Sie sich die Anzahl der Änderungen von einem Buchstaben zum anderen in Ihrer Zeichenfolge an, die Sie als Maß für die Inhomogenität der Zeichenfolge sehen können. Bei jeder (nützlichen) Bewegung einer Teilsequenz reduzieren Sie diese Zahl um eins, wenn der von Ihnen verschobenen Teilsequenz zwei unterschiedliche Buchstaben vorangestellt und gefolgt werden. Andernfalls reduzieren Sie die Inhomogenität um zwei.

Für eine Zeichenfolge mit k Änderungen benötigen Sie also höchstens k - l + 1 Züge, wobei l die Anzahl der verschiedenen Buchstaben in der Zeichenfolge ist, da am Ende l - 1 Änderungen verbleiben. Da eine Zeichenfolge mit der Länge n höchstens n-1 Buchstabenänderungen haben kann, kann sie höchstens n-l Züge benötigen . Die geringstmögliche Anzahl ist die Hälfte davon.

Die beste Strategie scheint daher zu sein, nach Teilsequenzen der Form abbba zu suchen und die bbb von dort weg zu bewegen. Wenn keine mehr vorhanden sind, bewegen Sie alles. Sie könnten immer noch versuchen, die Operationen durchzuführen, die neue Abbba-Situationen schaffen, aber ich denke, der Gewinn wird sehr gering sein. Da die schlechtestmögliche Strategie (ohne dumme Bewegungen, die die Inhomogenität erhöhen) höchstens doppelt so viele Bewegungen wie die optimale verwendet, scheint das Wenige, das Sie gewinnen könnten, in keinem vernünftigen Verhältnis zum Aufwand zu stehen, wie die Antwort von isaacg mit der Charakterisierung als NP-hart schlägt vor. Es sei denn, Sie zählen wirklich nur die Anzahl der Bewegungsvorgänge und kümmern sich nicht um die Zeit, um zu entscheiden, welche Bewegungen ausgeführt werden sollen.

Der schlimmste Fall ist daher eine Zeichenfolge, bei der sich jeder Buchstabe von seinem Vorgänger unterscheidet (und Sie keine Abbba-Boni erhalten). Hier benötigen Sie eine Reihe von Operationen, die in der Länge der Zeichenfolge linear sind und fast dieser Länge entsprechen.

In Ihrem Beispiel haben Sie 5 -> 4 -> 3 Änderungen und 3 entspricht der Anzahl der Buchstaben (4) minus 1.

Randnotiz: Bei einem Alphabet mit einer Größe von nur zwei verringert jede Bewegung, bei der kein Präfix oder Suffix der Zeichenfolge verschoben wird, die Inhomogenität um zwei, und daher ist jede Folge vernünftiger Bewegungen optimal.

Peter Leupold
quelle
Sie behaupten, dass ein Zug die Anzahl der Änderungen um höchstens 2 reduzieren kann, aber tatsächlich die Anzahl der Änderungen um bis zu 3 reduzieren kann. Beispiel: Konvertieren von "aabcabc" in "aaabbcc" durch Verschieben des ersten Teilstrings "bc" in Die Mitte des zweiten Teilstrings "bc" führt zu einer Verringerung der Anzahl der Änderungen in der Zeichenfolge von 5 auf 2.
Mikhail Rudoy
Hallo, @MikhailRudoy. Die Frage besagt, dass die Operation "eine Teilfolge von Buchstaben aufnimmt, die gleich sind", so dass bc meines Wissens nicht erlaubt ist.
Peter Leupold
Ich habe dieses Detail völlig vermisst. Sie sind in diesem Fall richtig.
Mikhail Rudoy
Peter hat recht: Diese Bewegungen sind nicht erlaubt.
Aditya Parameswaran
Betreff: Der Rest der Antwort - in der Tat sind diese Beobachtungen bezüglich der Untergrenzen, der Optimalität der Groß- und Kleinschreibung der Alphabetgröße 2 und der Heuristik für das, was zu jedem Zeitpunkt zu tun ist, wertvoll. Da jede Bewegung im schlimmsten Fall nur dieser Buchstabenfolge zugute kommt und im besten Fall höchstens zwei Buchstabenfolgen wie in Ihrer Abbba zusammenführt, erscheint eine 2-Näherung natürlich.
Aditya Parameswaran