Problema de supersecuencia común más corto
En informática , la supersecuencia común más corta de dos secuencias X e Y es la secuencia más corta que tiene X e Y como subsecuencias . Este es un problema estrechamente relacionado con el problema de subsecuencia común más largo . Dadas dos secuencias X = <x 1 , ..., x m > e Y = <y 1 , ..., y n >, una secuencia U = <u 1 , ..., u k > es una supersecuencia común de X e Ysi los artículos pueden ser retirados de U para producir X y Y .
Una supersecuencia común más corta (SCS) es una supersecuencia común de longitud mínima. En el problema de supersecuencia común más corto, se dan dos secuencias X e Y , y la tarea es encontrar una supersecuencia común más corta posible de estas secuencias. En general, un SCS no es único.
Para dos secuencias de entrada, un SCS puede formarse fácilmente a partir de una subsecuencia común más larga (LCS). Por ejemplo, la subsecuencia común más larga de X y Y es Z . Al insertar los símbolos que no son LCS en Z mientras se conserva su orden original, obtenemos una supersecuencia común U más corta . En particular, la ecuación es válida para dos secuencias de entrada.
![[1..m] = abcbdab](https://wikimedia.org/api/rest_v1/media/math/render/svg/a81f42392c43a0b0298789a903338bf76dc97223)
![[1..n] = bdcaba](https://wikimedia.org/api/rest_v1/media/math/render/svg/9c34a14553055e81f2d6a800b4b8a81818503a8b)
![{\ Displaystyle [1..L] = bcba}](https://wikimedia.org/api/rest_v1/media/math/render/svg/650337a86ee10a285698a036e6bc6c051142551a)
![{\ displaystyle [1..S] = abdcabdab}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6d2cc9828f4d32339be1fc26d946996bd3da65e3)
No existe una relación similar entre las supersecuencias comunes más cortas y las subsecuencias comunes más largas de tres o más secuencias de entrada. (En particular, LCS y SCS no son problemas duales ). Sin embargo, ambos problemas pueden resolverse a tiempo usando programación dinámica, donde es el número de secuencias y su longitud máxima. Para el caso general de un número arbitrario de secuencias de entrada, el problema es NP-difícil . [1]
El problema estrechamente relacionado de encontrar una cadena de longitud mínima que sea una supercuerda de un conjunto finito de cadenas S = { s 1 , s 2 , ..., s n } también es NP-difícil. [2] Se han propuesto varias aproximaciones de factores constantes a lo largo de los años, y el algoritmo actual más conocido tiene un factor de aproximación de 2.4783. [3] Sin embargo, quizás la solución más simple sea reformular el problema como una instancia de cobertura de conjunto ponderada de tal manera que el peso de la solución óptima para la instancia de cobertura de conjunto sea menos del doble de la longitud de la supercuerda S más corta . Entonces uno puede usar elO (log ( n )) - aproximación para la cobertura del conjunto ponderado para obtener una O (log ( n )) - aproximación para la supercuerda más corta (tenga en cuenta que esta no es una aproximación de factor constante).
Para cualquier cadena x en este alfabeto, defina P ( x ) como el conjunto de todas las cadenas que son subcadenas de x . La instancia I de cobertura del conjunto se formula de la siguiente manera: