Najkrótszy wspólny superstring: znajdź najkrótszy ciąg zawierający wszystkie podane fragmenty ciągu

12

Biorąc pod uwagę niektóre fragmenty ciągu, chciałbym znaleźć możliwie najkrótszy pojedynczy ciąg („ciąg wyjściowy”), który zawiera wszystkie fragmenty. Fragmenty mogą nakładać się na siebie w ciągu wyjściowym.

Przykład:

W przypadku fragmentów łańcucha:

BCDA
AGF
ABC

Poniższy ciąg wyjściowy zawiera wszystkie fragmenty i został utworzony przez naiwne dołączanie:

BCDAAGFABC

Jednak ten ciąg wyjściowy jest lepszy (krótszy), ponieważ wykorzystuje nakładki:

ABCDAGF
^
ABC
 ^
 BCDA
    ^ 
    AGF

Szukam algorytmów dla tego problemu. Znalezienie ściśle najkrótszego ciągu wyjściowego nie jest absolutnie ważne, ale im krótszy, tym lepiej. Szukam algorytmu lepszego niż oczywisty naiwny, który próbowałby dołączyć wszystkie permutacje fragmentów wejściowych i usunąć nakładanie się (które wydaje się być NP-Complete).

Rozpocząłem pracę nad rozwiązaniem, które okazuje się dość interesujące; Chciałbym zobaczyć, co wymyślą inni ludzie. Za chwilę dodam moją pracę w toku.

okluzja
źródło
3
Problem wydaje się być NP-zupełny. Jeśli tak, to nie będziesz w stanie znaleźć algorytmu wielomianowego do określania najkrótszego ciągu, ale mogą istnieć algorytmy wielomianowe, które dają przybliżone (nie najkrótsze) rozwiązania.
superM
3
Ten post na blogu dotyczący NP-Complete jest ładny: codinghorror.com/blog/2008/11/…
occulus
Blog jest naprawdę fajny, cały czas go czytam)))
superM
@ superM jest to wystarczająco podobne do sprzedawców podróżujących (każdy ciąg miasta i koszt między miastami = pewne nakładanie się liczb)
maniak zapadkowy
@ maniaku dziwaka, to _ możesz podać niewielki koszt między miastami, jeśli mają więcej wspólnych liter, a największy koszt, gdy nie mają w ogóle żadnej wspólnej litery
superM

Odpowiedzi:

14

To, o co pytasz, to najkrótszy wspólny problem superstrun, dla którego nie ma algorytmu, który działałby we wszystkich przypadkach. Ale jest to powszechny problem (podczas kompresji i sekwencjonowania DNA), a kilka algorytmów aproksymacyjnych jest dobrze znanych.

Algorytmy „chciwe” są ogólnie akceptowane jako najskuteczniejsze (ponieważ mają najgorszy najgorszy przypadek).

Przeczytaj artykuł Algorytmy aproksymacji najkrótszego typowego problemu superstrunu autorstwa Jonathana Turnera, aby uzyskać więcej informacji.

pdr
źródło
Hmm, zauważ, że pierwszy link w moim komentarzu tuż powyżej dotyczy supersekwencji, a nie superstrun! Wydaje się, że nadsekwencja nie wymaga, aby wszystkie znaki w sekwencji były ciągłe.
occulus
Twój link jest martwy.
Majid