¿Cómo determinar la subsecuencia creciente más larga usando programación dinámica?
Tengo un conjunto de números enteros. Quiero encontrar la subsecuencia creciente más larga de ese conjunto usando programación dinámica.
Bien, primero describiré la solución más simple que es O(N^2), donde N es el tamaño de la colección. También existe una solución O(N log N), que también describiré. Búscalo aquí en la sección Algoritmos eficientes.
Asumiré que los índices de la matriz son de 0 a N - 1. Entonces, definamos DP[i]que es la longitud de la LIS (subsecuencia creciente más larga) que termina en el elemento con índice i. Para calcular, DP[i]miramos todos los índices j < iy comprobamos si DP[j] + 1 > DP[i]y array[j] < array[i](queremos que aumente). Si esto es cierto, podemos actualizar el óptimo actual para DP[i]. Para encontrar el óptimo global para la matriz, puede tomar el valor máximo de DP[0...N - 1].
int maxLength = 1, bestEnd = 0;
DP[0] = 1;
prev[0] = -1;
for (int i = 1; i < N; i++)
{
DP[i] = 1;
prev[i] = -1;
for (int j = i - 1; j >= 0; j--)
if (DP[j] + 1 > DP[i] && array[j] < array[i])
{
DP[i] = DP[j] + 1;
prev[i] = j;
}
if (DP[i] > maxLength)
{
bestEnd = i;
maxLength = DP[i];
}
}
Utilizo la matriz prevpara poder encontrar más tarde la secuencia real, no solo su longitud. Simplemente regrese recursivamente desde bestEndun bucle usando prev[bestEnd]. El -1valor es una señal para detenerse.
O(N log N)Bien, ahora a la solución más eficiente :
Definamos S[pos]como el número entero más pequeño que termina una secuencia creciente de longitud pos. Ahora repita cada número entero Xdel conjunto de entrada y haga lo siguiente:
Si
X> es el último elemento deS, añádaloXal final deS. Básicamente, esto significa que hemos encontrado un nuevo modelo más grandeLIS.De lo contrario, busque el elemento más pequeño en
S, que es>=queX, y cámbielo aX. ComoSse ordena en cualquier momento, el elemento se puede encontrar mediante la búsqueda binaria enlog(N).
Tiempo de ejecución total: Nnúmeros enteros y una búsqueda binaria para cada uno de ellos: N * log(N) = O(N log N)
Ahora hagamos un ejemplo real:
Colección de números enteros:
2 6 3 4 1 2 9 5 8
Pasos:
0. S = {} - Initialize S to the empty set
1. S = {2} - New largest LIS
2. S = {2, 6} - New largest LIS
3. S = {2, 3} - Changed 6 to 3
4. S = {2, 3, 4} - New largest LIS
5. S = {1, 3, 4} - Changed 2 to 1
6. S = {1, 2, 4} - Changed 3 to 2
7. S = {1, 2, 4, 9} - New largest LIS
8. S = {1, 2, 4, 5} - Changed 9 to 5
9. S = {1, 2, 4, 5, 8} - New largest LIS
Entonces la longitud del LIS es 5(el tamaño de S).
Para reconstruir lo real LISusaremos nuevamente una matriz principal. Sea parent[i]el predecesor de un elemento con índice ial LISfinal del elemento con índice i.
Para simplificar las cosas, podemos mantener en la matriz S, no los números enteros reales, sino sus índices (posiciones) en el conjunto. No mantenemos {1, 2, 4, 5, 8}, pero mantenemos {4, 5, 3, 7, 8}.
Es decir, entrada[4] = 1 , entrada[5] = 2 , entrada[3] = 4 , entrada[7] = 5 , entrada[8] = 8 .
Si actualizamos correctamente la matriz principal, el LIS real es:
input[S[lastElementOfS]],
input[parent[S[lastElementOfS]]],
input[parent[parent[S[lastElementOfS]]]],
........................................
Ahora a lo importante: ¿cómo actualizamos la matriz principal? Hay dos opciones:
Si
X> último elemento enS, entoncesparent[indexX] = indexLastElement. Esto significa que el padre del elemento más nuevo es el último elemento. Simplemente anteponemosXhasta el final deS.De lo contrario, busque el índice del elemento más pequeño en
S, que es>=queX, y cámbielo aX. Aquíparent[indexX] = S[index - 1].
La explicación de Petar Minchev me ayudó a aclarar las cosas, pero me resultó difícil analizar qué era todo, así que hice una implementación de Python con nombres de variables demasiado descriptivos y muchos comentarios. Hice una solución recursiva ingenua, la solución O(n^2) y la solución O(n log n).
¡Espero que ayude a aclarar los algoritmos!
La solución recursiva
def recursive_solution(remaining_sequence, bigger_than=None):
"""Finds the longest increasing subsequence of remaining_sequence that is
bigger than bigger_than and returns it. This solution is O(2^n)."""
# Base case: nothing is remaining.
if len(remaining_sequence) == 0:
return remaining_sequence
# Recursive case 1: exclude the current element and process the remaining.
best_sequence = recursive_solution(remaining_sequence[1:], bigger_than)
# Recursive case 2: include the current element if it's big enough.
first = remaining_sequence[0]
if (first > bigger_than) or (bigger_than is None):
sequence_with = [first] + recursive_solution(remaining_sequence[1:], first)
# Choose whichever of case 1 and case 2 were longer.
if len(sequence_with) >= len(best_sequence):
best_sequence = sequence_with
return best_sequence
La solución de programación dinámica O(n^2)
def dynamic_programming_solution(sequence):
"""Finds the longest increasing subsequence in sequence using dynamic
programming. This solution is O(n^2)."""
longest_subsequence_ending_with = []
backreference_for_subsequence_ending_with = []
current_best_end = 0
for curr_elem in range(len(sequence)):
# It's always possible to have a subsequence of length 1.
longest_subsequence_ending_with.append(1)
# If a subsequence is length 1, it doesn't have a backreference.
backreference_for_subsequence_ending_with.append(None)
for prev_elem in range(curr_elem):
subsequence_length_through_prev = (longest_subsequence_ending_with[prev_elem] + 1)
# If the prev_elem is smaller than the current elem (so it's increasing)
# And if the longest subsequence from prev_elem would yield a better
# subsequence for curr_elem.
if ((sequence[prev_elem] < sequence[curr_elem]) and
(subsequence_length_through_prev >
longest_subsequence_ending_with[curr_elem])):
# Set the candidate best subsequence at curr_elem to go through prev.
longest_subsequence_ending_with[curr_elem] = (subsequence_length_through_prev)
backreference_for_subsequence_ending_with[curr_elem] = prev_elem
# If the new end is the best, update the best.
if (longest_subsequence_ending_with[curr_elem] >
longest_subsequence_ending_with[current_best_end]):
current_best_end = curr_elem
# Output the overall best by following the backreferences.
best_subsequence = []
current_backreference = current_best_end
while current_backreference is not None:
best_subsequence.append(sequence[current_backreference])
current_backreference = (backreference_for_subsequence_ending_with[current_backreference])
best_subsequence.reverse()
return best_subsequence
La solución de programación dinámica O(n log n)
def find_smallest_elem_as_big_as(sequence, subsequence, elem):
"""Returns the index of the smallest element in subsequence as big as
sequence[elem]. sequence[elem] must not be larger than every element in
subsequence. The elements in subsequence are indices in sequence. Uses
binary search."""
low = 0
high = len(subsequence) - 1
while high > low:
mid = (high + low) / 2
# If the current element is not as big as elem, throw out the low half of
# sequence.
if sequence[subsequence[mid]] < sequence[elem]:
low = mid + 1
# If the current element is as big as elem, throw out everything bigger, but
# keep the current element.
else:
high = mid
return high
def optimized_dynamic_programming_solution(sequence):
"""Finds the longest increasing subsequence in sequence using dynamic
programming and binary search (per
http://en.wikipedia.org/wiki/Longest_increasing_subsequence). This solution
is O(n log n)."""
# Both of these lists hold the indices of elements in sequence and not the
# elements themselves.
# This list will always be sorted.
smallest_end_to_subsequence_of_length = []
# This array goes along with sequence (not
# smallest_end_to_subsequence_of_length). Following the corresponding element
# in this array repeatedly will generate the desired subsequence.
parent = [None for _ in sequence]
for elem in range(len(sequence)):
# We're iterating through sequence in order, so if elem is bigger than the
# end of longest current subsequence, we have a new longest increasing
# subsequence.
if (len(smallest_end_to_subsequence_of_length) == 0 or
sequence[elem] > sequence[smallest_end_to_subsequence_of_length[-1]]):
# If we are adding the first element, it has no parent. Otherwise, we
# need to update the parent to be the previous biggest element.
if len(smallest_end_to_subsequence_of_length) > 0:
parent[elem] = smallest_end_to_subsequence_of_length[-1]
smallest_end_to_subsequence_of_length.append(elem)
else:
# If we can't make a longer subsequence, we might be able to make a
# subsequence of equal size to one of our earlier subsequences with a
# smaller ending number (which makes it easier to find a later number that
# is increasing).
# Thus, we look for the smallest element in
# smallest_end_to_subsequence_of_length that is at least as big as elem
# and replace it with elem.
# This preserves correctness because if there is a subsequence of length n
# that ends with a number smaller than elem, we could add elem on to the
# end of that subsequence to get a subsequence of length n+1.
location_to_replace = find_smallest_elem_as_big_as(sequence, smallest_end_to_subsequence_of_length, elem)
smallest_end_to_subsequence_of_length[location_to_replace] = elem
# If we're replacing the first element, we don't need to update its parent
# because a subsequence of length 1 has no parent. Otherwise, its parent
# is the subsequence one shorter, which we just added onto.
if location_to_replace != 0:
parent[elem] = (smallest_end_to_subsequence_of_length[location_to_replace - 1])
# Generate the longest increasing subsequence by backtracking through parent.
curr_parent = smallest_end_to_subsequence_of_length[-1]
longest_increasing_subsequence = []
while curr_parent is not None:
longest_increasing_subsequence.append(sequence[curr_parent])
curr_parent = parent[curr_parent]
longest_increasing_subsequence.reverse()
return longest_increasing_subsequence
