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

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.

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.