In der Informatik ist die kürzeste gemeinsame Supersequenz von zwei Sequenzen X und Y die kürzeste Sequenz, die X und Y als Untersequenzen. Dies ist ein Problem, das eng mit dem am längsten auftretenden Teilfolgenproblem zusammenhängt. Gegeben zwei Sequenzen X = <x 1 ..., x m > und Y = <y 1 ..., y n >, eine Sequenz U = <u 1 ..., u k > ist eine übliche Supersequenz von X und Y wenn Elemente aus U entfernt werden können, um X oder Y herzustellen. .
Eine kürzeste Common-Supersequenz (SCS) ist eine häufige Supersequenz von minimaler Länge. Bei dem kürzesten gemeinsamen Supersequenzproblem werden die zwei Sequenzen X und Y angegeben, und es ist die Aufgabe, eine möglichst kurze gemeinsame Supersequenz dieser Sequenzen zu finden. Im Allgemeinen ist ein SCS nicht eindeutig.
Für zwei Eingangssequenzen kann ein SCS leicht aus einer längsten gemeinsamen Untersequenz (LCS) gebildet werden. Zum Beispiel, wenn X Y . Durch Einfügen der Nicht-lcs-Symbole unter Beibehaltung der Symbolreihenfolge erhalten wir die SCS: U für zwei Eingangssequenzen. Für drei oder mehr Eingabesequenzen gilt dies jedoch nicht. Man beachte auch, dass die Probleme der LCS und der SCS keine dualen Probleme sind.
![[1..m] = abcbdab](https://wikimedia.org/api/rest_v1/media/math/render/svg/a81f42392c43a0b0298789a903338bf76dc97223)
![[1..n] = bdaba </annotation></semantics></math></span><img src=](https://wikimedia.org/api/rest_v1/media/math/render/svg/9c34a14553055e81f2d6a800b4b8a81818503a8b)
![[1..r] = bcba](https://wikimedia.org/api/rest_v1/media/math/render/svg/3b3420b174001e3458f72cfd5121bfc789e03e67)
![[1..t] = abdcabdabo . </p><p> Es ist ziemlich klar, dass <span class=](https://wikimedia.org/api/rest_v1/media/math/render/svg/56442a3d6041f3395a6d3c705c0e4d391d5c9b63)
Kürzeste gewöhnliche Superstring [ edit ]
Das eng damit verbundene Problem, eine Saite zu finden, die eine Superstring einer endlichen Menge von Saiten ist S = { ] s 1 s 2 ..., s n } ist NP-Complete. [1] Auch gut ( Konstante Faktoren) Näherungen wurden für den Durchschnittsfall gefunden, nicht jedoch für den Worst-Case. [2][3] Es kann jedoch als ein Fall einer gewichteten Satzabdeckung so formuliert werden, dass das Gewicht der optimalen Lösung für die Satzabdeckungsinstanz entspricht ist weniger als doppelt so lang wie die kürzeste Superstring S . Man kann dann die O (log ( n )) - Näherung für die gewichtete Abdeckung verwenden, um ein O (log ( n )) - Näherung für die kürzeste Superstring zu erhalten (beachten Sie das Dies ist nicht eine Annäherung mit konstantem Faktor).
Für jede Zeichenfolge x in diesem Alphabet definieren Sie P ( x ) als die Menge aller Zeichenfolgen, die Teilzeichenfolgen von x sind. . Die Instanz I der Deckung wird wie folgt formuliert:
- Es sei M leer.
- Für jedes Saitenpaar s i und s j ]wenn die letzten k Symbole von s i dieselben sind wie die ersten k k s j fügen Sie dann eine Zeichenfolge zu M hinzu, die aus der Verkettung mit maximaler Überlappung von i mit s besteht ] j .
- Definiert das Universum "/> des Deckblattes Beispiel S
- Definieren Sie die Menge der Teilmengen des Universums als { P ( x ) | x [1945 S ∪ M }
- Definieren Sie die Kosten für jede Teilmenge. P (x) wird x |, die Länge von x .
Die Instanz I kann dann unter Verwendung eines Algorithmus für die gewichtete Satzabdeckung gelöst werden, und der Algorithmus kann eine beliebige Verkettung des Saiten x für die der gewichtete Satzabdeckungsalgorithmus P ( x ) ausgibt.
Beispiel [ edit ]. 19659106] Betrachten Sie die Menge S = {abc, cde, fab}, die zum Universum der gewichteten Deckungsinstanz wird. In diesem Fall M = {abcde, fabc}. Dann ist die Menge der Teilmengen des Universums -
die Kosten 3, 3, 3, 5 bzw. 4 haben.
Verweise [ edit ]
Externe Links [ edit ]
No comments:
Post a Comment