Ist dieses kombinatorische Optimierungsproblem NP-schwer?

Question

Ich arbeite an einem kombinatorischen Optimierungsproblem, von dem ich vermute, dass es NP-schwer ist, und ein genetischer Algorithmus hat mit unserem Datensatz gut funktioniert. Wir sind eine Forschungsgruppe und planen, unsere Ergebnisse in unserem Fachgebiet (nicht in Mathematik oder Informatik) zu veröffentlichen, und ich würde gerne die Frage der NP-Härte untersuchen, bevor ich das Manuskript zur Begutachtung abschicke.

Es gibt zwei Hauptfragen:

1) Ich würde gerne wissen, ob dieses spezielle Optimierungsproblem bereits untersucht wurde. Ich habe die Literatur intensiv durchforstet, aber nichts genau Gleiches gefunden.

2) Wenn das Problem noch nicht untersucht worden ist, könnte ich mich an einem Reduzierbarkeitsbeweis versuchen und hätte gerne einige Hinweise auf gute NP-komplette Kandidaten für die Reduzierung.

Das Problem kann auf zwei Arten beschrieben werden: als Teilsequenzvariante und als bipartites Graphenproblem.

In der Teilsequenz-Variante möchte ich eine "entspannte" Teilsequenz finden, die Permutationen zulässt, und optimieren, um die Permutationsanzahl zu minimieren. Zum Beispiel: (. = ein beliebiges anderes Zeichen)

Abfrage: abc, Ziel: ..b.a.b.c., Ergebnis: abc (normale Teilsequenz)

Abfrage: abc, Ziel: ..b.a.c.a., Ergebnis: bac (Teilsequenz mit einer Permutation)

Bei der zweistufigen Formulierung handelt es sich um ein Matching-Problem oder ein lineares Zuordnungsproblem, bei dem der Graph in Abfragezeichenknoten und Zielzeichenknoten unterteilt ist. Die Kanten verbinden die Abfragezeichen mit den Zielzeichen, so dass es genau eine Kante von jedem Abfragezeichen zu einem Zielzeichen gibt. Die Zielfunktion besteht darin, die Anzahl der Kantenkreuzungen (in der Literatur auch "Kreuzungszahl" genannt) zu minimieren. Dies ähnelt den Algorithmen für das Layout von zweistufigen Graphen, die die Knoten neu anordnen, um Kantenkreuzungen zu minimieren, aber mein Problem erfordert, dass beide Knotenreihenfolgen fest bleiben.

Was sagen die Experten zu den Fragen 1 und 2?

Vielen Dank im Voraus!

Answer 1

Nur eine Idee: Ist das irgendwie gleichbedeutend mit dem Finden der minimalen Anzahl von Swaps, die zum Sortieren eines Arrays benötigt werden (MIN-SBR)? Wenn ja, ist dies NP-Hard .

(btw, arbeiten Sie gerade an etwas ähnlich wie hier ?)

Answer 2

Ich glaube nicht, dass dies NP-schwer ist. Siehe die Arbeit von Pevzner und Hannehali. Eine Arbeit, die mir in den Sinn kommt, trägt den Titel ``From Cabbage to Turnip''. Die Idee ist, die minimale Anzahl von Umkehrungen zu finden, um von einer Zeichenkette zu einer anderen zu gelangen. Sie haben dafür einen Polytime-Algorithmus entwickelt.

Answer 3

Das Problem mit dem "Wortproblem" sollte schwieriger sein, oder? - J-16 SDiZ 14

Ja, das mehrfache Vorkommen des Zeichens im Ziel scheint mein Problem schwieriger zu machen als MIN-SBR, so dass mein Problem unter diesem Gesichtspunkt mindestens so schwierig wie NP-komplett wäre. Andererseits ist mir noch nicht klar, wie ihr zentraler Begriff der Blockumkehrung meine Behauptung der NP-Vollständigkeit beeinflussen würde.

Es wäre schön zu wissen, ob meine Optimierung in polynomieller Zeit gelöst werden kann. Anders ausgedrückt: Es wäre sicher peinlich, wenn ein Gutachter mit fünf Zeilen Pseudocode zurückkäme, der das globale Maximum in O(n). findet.

Answer 4

Wäre dann Abfrage: abc Ziel: ..c.b.a.a Ergebnis: cba, drei Permutationen (wie Sie den Begriff verwenden)? Wenn ja, dann meinen Sie vielleicht Transpositionen und nicht Permutationen. Eine Transposition ist die Vertauschung zweier benachbarter Zeichen.

Gute Frage. Wir sind an einem Mapping von Query -> Target interessiert, das möglichst wenig Kreuzungen wie möglich. Dies ist genau die Motivation für die Erwähnung der bipartiten Kantenkreuzungen im ursprünglichen Beitrag. Alternativ kann man auch eine Rangstatistik, wie Spearmans Rho, über die Abbildung maximieren.

Und aus Neugierde: Wie viele eindeutige Zeichen enthält die Anfrage/das Ziel? - Justin Peel 18

Typische Abfrage: 100, typisches Ziel: 1000. Kombinatorisch gesehen ist das ein riesiger Lösungsraum.