Bei einigen Fragmenten würde ich gerne die kürzestmögliche einzelne Zeichenfolge ("Ausgabezeichenfolge") finden, die alle Fragmente enthält. Fragmente können sich in der Ausgabezeichenfolge überlappen.
Beispiel:
Für die Saitenfragmente:
BCDA
AGF
ABC
Die folgende Ausgabezeichenfolge enthält alle Fragmente und wurde durch naives Anhängen erstellt:
BCDAAGFABC
Diese Ausgabezeichenfolge ist jedoch besser (kürzer), da sie Überlappungen verwendet:
ABCDAGF
^
ABC
^
BCDA
^
AGF
Ich suche nach Algorithmen für dieses Problem. Es ist nicht unbedingt wichtig, den kürzesten Ausgabestring zu finden, aber je kürzer, desto besser. Ich suche einen Algorithmus, der besser ist als der offensichtlich naive, der versucht, alle Permutationen der Eingabefragmente anzufügen und Überlappungen zu entfernen (die NP-vollständig zu sein scheinen).
Ich habe angefangen, an einer Lösung zu arbeiten, die sich als sehr interessant herausstellt. Ich würde gerne sehen, was sich andere Leute einfallen lassen. Ich werde diese Frage in Kürze um meine in Bearbeitung befindlichen Arbeiten ergänzen.
quelle
Antworten:
Was Sie fragen, ist das Shortest Common Superstring-Problem, für das es keinen Algorithmus gibt, der für alle Fälle funktioniert. Es ist jedoch ein häufiges Problem (bei der Komprimierung und DNA-Sequenzierung) und es sind mehrere Approximationsalgorithmen bekannt.
"Gierige" Algorithmen gelten allgemein als die effektivsten (da sie den schlechtesten und schlechtesten Fall haben).
Lesen Sie den Artikel Approximationsalgorithmen für das kürzeste häufig auftretende Superstring-Problem von Jonathan Turner, um weitere Informationen zu erhalten.
quelle