Comment déterminer la plus longue sous-séquence croissante à l'aide de la programmation dynamique ?

Question

J'ai un ensemble d'entiers. Je veux trouver le la plus longue sous-séquence croissante de cet ensemble en utilisant la programmation dynamique.

Answer 1

OK, je vais d'abord décrire la solution la plus simple qui est O(N^2), où N est la taille de la collection. Il existe également une solution O(N log N), que je décrirai également. Regardez aquí pour cela à la section Algorithmes efficaces.

Je vais supposer que les indices du tableau sont de 0 à N - 1. Définissons donc DP[i] est la longueur de la sous-séquence croissante la plus longue (LIS) qui se termine à l'élément avec l'indice i . Pour calculer DP[i] nous examinons tous les indices j < i et vérifier à la fois si DP[j] + 1 > DP[i] y array[j] < array[i] (nous voulons qu'elle soit croissante). Si cela est vrai, nous pouvons mettre à jour l'optimum actuel de DP[i] . Pour trouver l'optimum global pour le tableau, vous pouvez prendre la valeur maximale 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];
   }
}

J'utilise le tableau prev pour pouvoir ensuite trouver la séquence réelle et pas seulement sa longueur. Il suffit de remonter récursivement de bestEnd dans une boucle en utilisant prev[bestEnd] . Le site -1 valeur est un signe pour s'arrêter.

---

OK, passons maintenant au plus efficace O(N log N) solution :

Soit S[pos] est défini comme le plus petit entier qui termine une séquence croissante de longueur pos . Maintenant, itérons à travers tous les entiers X de l'ensemble d'entrée et faire ce qui suit :

1. Si X > dernier élément dans S puis ajouter X à la fin de S . Cela signifie essentiellement que nous avons trouvé un nouveau plus grand LIS .

2. Sinon, trouvez le plus petit élément dans S qui est >= que X et le changer en X . Parce que S est trié à tout moment, l'élément peut être trouvé en utilisant la recherche binaire dans log(N) .

Temps d'exécution total - N entiers et une recherche binaire pour chacun d'eux - N * log(N) = O(N log N)

Maintenant, prenons un exemple concret :

Collection d'entiers : 2 6 3 4 1 2 9 5 8

Des pas :

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

La longueur du LIS est donc 5 (la taille de S).

Pour reconstruire le réel LIS nous utiliserons à nouveau un tableau parent. Soit parent[i] être le prédécesseur d'un élément avec l'indice i dans le LIS se terminant à l'élément avec l'indice i .

Pour simplifier les choses, nous pouvons garder dans le tableau S pas les entiers réels, mais leurs indices (positions) dans l'ensemble. Nous ne gardons pas {1, 2, 4, 5, 8} mais gardez {4, 5, 3, 7, 8} .

C'est-à-dire entrée [4] = 1 , input[5] = 2 , input[3] = 4 , input[7] = 5 , input[8] = 8 .

Si nous mettons à jour correctement le tableau parent, le LIS réel est :

input[S[lastElementOfS]], 
input[parent[S[lastElementOfS]]],
input[parent[parent[S[lastElementOfS]]]],
........................................

Passons maintenant à l'essentiel : comment mettre à jour le tableau parent ? Il y a deux possibilités :

1. Si X > dernier élément dans S entonces parent[indexX] = indexLastElement . Cela signifie que le parent de l'élément le plus récent est le dernier élément. Nous ajoutons simplement X à la fin de S .

2. Sinon, trouvez l'indice du plus petit élément dans S qui est >= que X et le changer en X . Ici parent[indexX] = S[index - 1] .

Answer 2

L'explication de Petar Minchev m'a aidé à clarifier les choses, mais il était difficile pour moi d'analyser ce que tout était, alors j'ai fait une implémentation Python avec des noms de variables trop descriptifs et beaucoup de commentaires. J'ai fait une solution récursive naïve, la solution O(n^2), et la solution O(n log n).

J'espère que cela aidera à clarifier les algorithmes !

La solution récursive

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 solution de programmation dynamique 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 solution de programmation dynamique 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

Answer 3

L'implémentation C++ suivante inclut également du code qui construit l'application réelle la plus longue sous-séquence croissante en utilisant un tableau appelé prev .

std::vector<int> longest_increasing_subsequence (const std::vector<int>& s)
{
    int best_end = 0;
    int sz = s.size();

    if (!sz)
        return std::vector<int>();

    std::vector<int> prev(sz,-1);
    std::vector<int> memo(sz, 0);

    int max_length = std::numeric_limits<int>::min();

    memo[0] = 1;

    for ( auto i = 1; i < sz; ++i)
    {
        for ( auto j = 0; j < i; ++j)
        {
            if ( s[j] < s[i] && memo[i] < memo[j] + 1 )
            {
                memo[i] =  memo[j] + 1;
                prev[i] =  j;
            }
        }

        if ( memo[i] > max_length ) 
        {
            best_end = i;
            max_length = memo[i];
        }
    }

    // Code that builds the longest increasing subsequence using "prev"
    std::vector<int> results;
    results.reserve(sz);

    std::stack<int> stk;
    int current = best_end;

    while (current != -1)
    {
        stk.push(s[current]);
        current = prev[current];
    }

    while (!stk.empty())
    {
        results.push_back(stk.top());
        stk.pop();
    }

    return results;
}

Implémentation sans pile, il suffit d'inverser le vecteur

#include <iostream>
#include <vector>
#include <limits>
std::vector<int> LIS( const std::vector<int> &v ) {
  auto sz = v.size();
  if(!sz)
    return v;
  std::vector<int> memo(sz, 0);
  std::vector<int> prev(sz, -1);
  memo[0] = 1;
  int best_end = 0;
  int max_length = std::numeric_limits<int>::min();
  for (auto i = 1; i < sz; ++i) {
    for ( auto j = 0; j < i ; ++j) {
      if (s[j] < s[i] && memo[i] < memo[j] + 1) {
        memo[i] = memo[j] + 1;
        prev[i] = j;
      }
    }
    if(memo[i] > max_length) {
      best_end = i;
      max_length = memo[i];
    }
  }

  // create results
  std::vector<int> results;
  results.reserve(v.size());
  auto current = best_end;
  while (current != -1) {
    results.push_back(s[current]);
    current = prev[current];
  }
  std::reverse(results.begin(), results.end());
  return results;
}

Answer 4

Voici les trois étapes de l'évaluation du problème du point de vue de la programmation dynamique :

1. Définition de la récurrence : maxLength(i) == 1 + maxLength(j) où 0 < j < i et array[i] > array[j]
2. Limite du paramètre de récurrence : il peut y avoir de 0 à i - 1 sous-séquences passées en paramètre.
3. Ordre d'évaluation : comme il s'agit d'une sous-séquence croissante, elle doit être évaluée de 0 à n.

Si nous prenons comme exemple la séquence {0, 8, 2, 3, 7, 9}, à l'indice :

• [0] nous obtiendrons la sous-séquence {0} comme cas de base.
• [1] nous avons 1 nouvelle sous-séquence {0, 8}
• [2] Essayer d'évaluer deux nouvelles séquences {0, 8, 2} et {0, 2} en ajoutant l'élément à l'indice 2 aux sous-séquences existantes - une seule est valide, donc ajouter la troisième séquence possible {0, 2} seulement à la liste des paramètres. ...

Voici le code C++11 fonctionnel :

#include <iostream>
#include <vector>

int getLongestIncSub(const std::vector<int> &sequence, size_t index, std::vector<std::vector<int>> &sub) {
    if(index == 0) {
        sub.push_back(std::vector<int>{sequence[0]});
        return 1;
    }

    size_t longestSubSeq = getLongestIncSub(sequence, index - 1, sub);
    std::vector<std::vector<int>> tmpSubSeq;
    for(std::vector<int> &subSeq : sub) {
        if(subSeq[subSeq.size() - 1] < sequence[index]) {
            std::vector<int> newSeq(subSeq);
            newSeq.push_back(sequence[index]);
            longestSubSeq = std::max(longestSubSeq, newSeq.size());
            tmpSubSeq.push_back(newSeq);
        }
    }
    std::copy(tmpSubSeq.begin(), tmpSubSeq.end(),
              std::back_insert_iterator<std::vector<std::vector<int>>>(sub));

    return longestSubSeq;
}

int getLongestIncSub(const std::vector<int> &sequence) {
    std::vector<std::vector<int>> sub;
    return getLongestIncSub(sequence, sequence.size() - 1, sub);
}

int main()
{
    std::vector<int> seq{0, 8, 2, 3, 7, 9};
    std::cout << getLongestIncSub(seq);
    return 0;
}

Answer 5

Ceci peut être résolu en O(n^2) en utilisant la programmation dynamique. Le code Python pour la même chose serait le suivant::-

def LIS(numlist):
    LS = [1]
    for i in range(1, len(numlist)):
        LS.append(1)
        for j in range(0, i):
            if numlist[i] > numlist[j] and LS[i]<=LS[j]:
                LS[i] = 1 + LS[j]
    print LS
    return max(LS)

numlist = map(int, raw_input().split(' '))
print LIS(numlist)

Pour l'entrée : 5 19 5 81 50 28 29 1 83 23

La sortie serait : [1, 2, 1, 3, 3, 3, 4, 1, 5, 3] 5

L'index de la liste de sortie est l'index de la liste d'entrée. La valeur d'un index de liste donné dans la liste de sortie indique la longueur de la plus longue sous-séquence croissante pour cet index de liste.