Dados alguns fragmentos de string, eu gostaria de encontrar a menor string possível possível ("string de saída") que contenha todos os fragmentos. Fragmentos podem se sobrepor na cadeia de saída.
Exemplo:
Para os fragmentos de cadeia:
BCDA
AGF
ABC
A seguinte sequência de saída contém todos os fragmentos e foi criada por um ingênuo anexo:
BCDAAGFABC
No entanto, essa sequência de saída é melhor (mais curta), pois emprega sobreposições:
ABCDAGF
^
ABC
^
BCDA
^
AGF
Estou procurando algoritmos para esse problema. Não é absolutamente importante encontrar a string de saída estritamente mais curta, mas quanto menor, melhor. Estou procurando um algoritmo melhor que o óbvio ingênuo que tentaria anexar todas as permutações dos fragmentos de entrada e remover sobreposições (que pareceriam ser NP-Complete).
Comecei a trabalhar em uma solução e está se mostrando bastante interessante; Eu gostaria de ver o que outras pessoas poderiam inventar. Vou adicionar meu trabalho em andamento a essa pergunta daqui a pouco.
fonte
Respostas:
O que você está perguntando é o problema de Menor supercorda comum, para o qual não há algoritmo que funcione para todos os casos. Mas é um problema comum (na compressão e no seqüenciamento de DNA) e vários algoritmos de aproximação são bem conhecidos.
Geralmente, os algoritmos "gananciosos" são aceitos como os mais eficazes (como no pior dos casos).
Leia o artigo Algoritmos de aproximação para o menor problema de supercorda comum de Jonathan Turner para obter mais informações.
fonte