La subsecuencia común más larga para múltiples secuencias

He hecho un montón de investigación para encontrar el más largo para M = 2 secuencias, pero estoy tratando de averiguar cómo hacerlo para M> = 2 secuencias. Me están dando secuencias N y M: M, con N elementos únicos. N es el conjunto de {1 - N}. He pensado en el enfoque de programación dinámica, pero todavía estoy confundido sobre cómo incorporarlo realmente.La subsecuencia común más larga para múltiples secuencias

de entrada Ejemplo
5 3
5 3 4 1 2
2 5 4 3 1
5 2 3 1 4

La secuencia max aquí puede ser visto para ser

Exp Salida ected
Longitud = 3

Fuente

2011-04-22 mkobit

¿Puedes publicar los enfoques que has probado hasta ahora? Desde allí podemos indicarle la dirección correcta. –

M es el número de secuencias en las cuales la subsecuencia debe estar presente? – BiGYaN

@Jerry la primera línea especifica N y M. Esto es normal para las especificaciones del problema del concurso/tarea C :) –

Una idea simple.

Para cada número i entre 1 y N, calcular la subsecuencia más largo que el último número es i. (Vamos a llamarlo a[i])

Para hacer eso, repetiremos los números i en la primera secuencia de principio a fin. Si a[i] > 1, entonces existe el número j tal que en cada secuencia viene antes del i.
Ahora podemos simplemente verificar todos los valores posibles de j y (si la condición anterior es válida) hacer a[i] = max(a[i], a[j] + 1).

Como el último bit, porque j viene antes de i en la primera secuencia, significa que a[j] ya está calculado.

for each i in first_sequence 
    // for the OP's example, 'i' would take values [5, 3, 4, 1, 2], in this order 
    a[i] = 1; 
    for each j in 1..N 
     if j is before i in each sequence 
      a[i] = max(a[i], a[j] + 1) 
     end 
    end 
end

Es O(N^2*M), si se calcula la matriz de posiciones de antemano.

Fuente

2011-04-22 04:38:16

Creo que esto es bastante correcto, pero el pseudocidio que has escrito es confuso. Parece que 'i' itera la lista de secuencias, pero ¿no debería iterar de' 1' a 'N'? Supongo que consideras 'secuencias [0]' como la primera secuencia, y por lo tanto contienen todos los elementos '1 .. N', pero creo que escribirlo como lo hiciste para' j' es más claro. – IVlad

@IVlad Sí, debe iterar iterar todos los números de 1 a N, pero también en el orden correcto. Pero tienes razón, el pseudocódigo era confuso. Lo he aclarado un poco. No estoy seguro de si el requisito de 'orden' puede presentarse mejor. –

Muchas gracias, me tomó un poco de tiempo entender lo que estaba pasando aquí, pero ahora tiene sentido. – mkobit

Puede consultar el documento "Design of a new Deterministic Algorithm for finding Common DNA Subsequence". Puede usar este algoritmo para construir el DAG (página 8, figura 5). Desde el DAG, lea las subsecuencias separadas más grandes comunes. Luego intente con un enfoque de programación dinámica usando el valor de M para decidir cuántos DAG necesita construir por secuencia. Básicamente use estas subsecuencias como clave y almacene los números de secuencia correspondientes donde se encuentra y luego intente encontrar la subsecuencia más grande (que puede ser más de 1).

Fuente

2011-04-22 04:25:54 BiGYaN

Puesto que usted tiene elementos únicos, la respuesta de @Nikita Rybak es la de ir con, pero ya que ha mencionado la programación dinámica, aquí te mostramos cómo utilizar DP cuando se tiene más de dos secuencias:

dp[i, j, k] = length of longest common subsequence considering the prefixes 
       a[1..i], b[1..j], c[1..k]. 


dp[i, j, k] = 1 + dp[i - 1, j - 1, k - 1] if a[i] = b[j] = c[k] 
      = max(dp[i - 1, j, k], dp[i, j - 1, k], dp[i, j, k - 1]) otherwise

Para recuperar la subsecuencia real, use una función recursiva que comience en dp[a.Length, b.Length, c.Length] y básicamente invierta las fórmulas anteriores: si los tres elementos son iguales, retroceda a dp[a.Length - 1, b.Length - 1, c.Length - 1] e imprima el carácter. Si no, retroceda de acuerdo con el máximo de los valores anteriores.

Fuente

2011-04-22 11:21:06 IVlad

La subsecuencia común más larga para múltiples secuencias

Respuesta

Cuestiones relacionadas