Dados algunos fragmentos de cadena, me gustaría encontrar la cadena única más corta posible ("cadena de salida") que contenga todos los fragmentos. Los fragmentos pueden superponerse entre sí en la cadena de salida.
Ejemplo:
Para los fragmentos de cadena:
BCDA
AGF
ABC
La siguiente cadena de salida contiene todos los fragmentos y se realizó mediante un agregado ingenuo:
BCDAAGFABC
Sin embargo, esta cadena de salida es mejor (más corta), ya que emplea superposiciones:
ABCDAGF
^
ABC
^
BCDA
^
AGF
Estoy buscando algoritmos para este problema. No es absolutamente importante encontrar la cadena de salida estrictamente más corta, pero cuanto más corta, mejor. Estoy buscando un algoritmo mejor que el ingenuo obvio que intentaría agregar todas las permutaciones de los fragmentos de entrada y eliminar las superposiciones (que parece ser NP-Complete).
Empecé a trabajar en una solución y está resultando bastante interesante; Me gustaría ver qué podrían hacer otras personas. Agregaré mi trabajo en progreso a esta pregunta en un momento.
fuente
Respuestas:
Lo que está preguntando es sobre el problema de Superstring más corto, para el cual no existe un algoritmo que funcione para todos los casos. Pero es un problema común (en compresión y secuenciación de ADN) y se conocen varios algoritmos de aproximación.
Los algoritmos "codiciosos" son generalmente aceptados como los más efectivos (ya que tienen el peor de los casos menos malo).
Lea el documento Algoritmos de aproximación para el problema de supercuerda común más corto de Jonathan Turner para obtener más información.
fuente