Come determinare la sottosequenza crescente più lunga utilizzando la programmazione dynamic?

Ho un insieme di numeri interi. Voglio trovare la sottosequenza crescente più lunga di quel set utilizzando la programmazione dynamic.

OK, descriverò prima la soluzione più semplice che è O (N ^ 2), dove N è la dimensione della collezione. Esiste anche una soluzione O (N log N), che descriverò anche. Guardate qui alla sezione Algoritmi efficienti.

Assumerò che gli indici dell’array sono da 0 a N – 1. Quindi definiamo DP[i] come la lunghezza del LIS (la sottosequenza crescente più lunga) che termina con l’elemento con indice i . Per calcolare DP[i] guardiamo tutti gli indici j < i e controlliamo entrambi se DP[j] + 1 > DP[i] e array[j] < array[i] (vogliamo che sia in aumento). Se questo è vero, possiamo aggiornare l'attuale ottimale per DP[i] . Per trovare l'optimum globale per l'array, è ansible ottenere il valore massimo da 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]; } } 

Io uso l'array prev per poter successivamente trovare la sequenza effettiva non solo la sua lunghezza. Basta tornare indietro ricorsivamente da bestEnd in loop usando prev[bestEnd] . Il valore -1 è un segno di fermarsi.


OK, ora la soluzione O(N log N) più efficiente:

Sia S[pos] definito come il più piccolo numero intero che termina con una sequenza crescente di lunghezza pos . Ora esegui l'iterazione di ogni numero intero X dell'insieme di input e procedi come segue:

  1. Se X > ultimo elemento in S , quindi aggiungere X alla fine di S Questo significa essenzialmente che abbiamo trovato un nuovo LIS più grande.

  2. Altrimenti trova l'elemento più piccolo in S , che è >= di X , e cambialo in X Poiché S è ordinato in qualsiasi momento, l'elemento può essere trovato usando la ricerca binaria nel log(N) .

Total runtime - N interi e una ricerca binaria per ciascuno di essi - N * log (N) = O (N log N)

Ora facciamo un esempio reale:

Raccolta di numeri interi: 2 6 3 4 1 2 9 5 8

passi:

 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 

Quindi la lunghezza del LIS è 5 (la dimensione di S).

Per ribuild il LIS attuale utilizzeremo ancora una matrice madre. Lascia che il parent[i] sia il predecessore dell'elemento con indice i nel LIS termina con l'elemento con l'indice i .

Per semplificare le cose, possiamo tenere nell'array S , non gli interi effettivi, ma i loro indici (posizioni) nel set. Non manteniamo {1, 2, 4, 5, 8} , ma manteniamo {4, 5, 3, 7, 8} .

Quello è input [4] = 1 , input [5] = 2 , input [3] = 4 , input [7] = 5 , input [8] = 8 .

Se aggiorniamo correttamente l'array principale, il LIS attuale è:

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

Ora per l'importante - come aggiorniamo l'array principale? Ci sono due opzioni:

  1. Se X > ultimo elemento in S , quindi parent[indexX] = indexLastElement . Ciò significa che il genitore dell'elemento più recente è l'ultimo elemento. Abbiamo appena anteposto X alla fine di S

  2. Altrimenti trova l'indice dell'elemento più piccolo in S , che è >= di X , e cambialo in X Qui parent[indexX] = S[index - 1] .

La spiegazione di Petar Minchev mi ha aiutato a chiarire le cose, ma è stato difficile per me analizzare cosa fosse tutto, quindi ho realizzato un’implementazione Python con nomi di variabili eccessivamente descrittivi e molti commenti. Ho fatto una soluzione ricorsiva ingenua, la soluzione O (n ^ 2) e la soluzione O (n log n).

Spero che aiuti a chiarire gli algoritmi!

La soluzione ricorsiva

 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 soluzione di programmazione dynamic 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 soluzione di programmazione dynamic 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 

Parlando della soluzione DP, ho trovato sorprendente il fatto che nessuno abbia menzionato il fatto che il LIS può essere ridotto a LCS . Tutto quello che devi fare è ordinare la copia della sequenza originale, rimuovere tutti i duplicati e fare LCS. In pseudocodice è:

 def LIS(S): T = sort(S) T = removeDuplicates(T) return LCS(S, T) 

E la piena implementazione scritta in Go. Non è necessario mantenere l’intera matrice n ^ 2 DP se non è necessario ribuild la soluzione.

 func lcs(arr1 []int) int { arr2 := make([]int, len(arr1)) for i, v := range arr1 { arr2[i] = v } sort.Ints(arr1) arr3 := []int{} prev := arr1[0] - 1 for _, v := range arr1 { if v != prev { prev = v arr3 = append(arr3, v) } } n1, n2 := len(arr1), len(arr3) M := make([][]int, n2 + 1) e := make([]int, (n1 + 1) * (n2 + 1)) for i := range M { M[i] = e[i * (n1 + 1):(i + 1) * (n1 + 1)] } for i := 1; i <= n2; i++ { for j := 1; j <= n1; j++ { if arr2[j - 1] == arr3[i - 1] { M[i][j] = M[i - 1][j - 1] + 1 } else if M[i - 1][j] > M[i][j - 1] { M[i][j] = M[i - 1][j] } else { M[i][j] = M[i][j - 1] } } } return M[n2][n1] } 

La seguente implementazione C ++ include anche del codice che costruisce la sottosequenza crescente più lunga effettiva usando un array chiamato prev .

 std::vector longest_increasing_subsequence (const std::vector& s) { int best_end = 0; int sz = s.size(); if (!sz) return std::vector(); std::vector prev(sz,-1); std::vector memo(sz, 0); int max_length = std::numeric_limits::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 results; results.reserve(sz); std::stack 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; } 

L’implementazione senza stack semplicemente inverte il vettore

 #include  #include  #include  std::vector LIS( const std::vector &v ) { auto sz = v.size(); if(!sz) return v; std::vector memo(sz, 0); std::vector prev(sz, -1); memo[0] = 1; int best_end = 0; int max_length = std::numeric_limits::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 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; } 

Ecco tre passaggi per valutare il problema dal punto di vista della programmazione dynamic:

  1. Definizione di ricorrenza: maxLength (i) == 1 + maxLength (j) dove 0 array [j]
  2. Limite del parametro di ricorrenza: potrebbero esserci da 0 a 1 – sequenze secondarie passate come parametro
  3. Ordine di valutazione: dal momento che sta aumentando la sotto-sequenza, deve essere valutato da 0 a n

Se prendiamo come esempio la sequenza {0, 8, 2, 3, 7, 9}, all’indice:

  • [0] avremo una sottosequenza {0} come caso base
  • [1] abbiamo 1 nuova sottosequenza {0, 8}
  • [2] cercando di valutare due nuove sequenze {0, 8, 2} e {0, 2} aggiungendo l’elemento nell’indice 2 alle sequenze secondarie esistenti – solo una è valida, quindi aggiungendo solo la terza ansible sequenza {0, 2} alla lista dei parametri …

Ecco il codice C ++ 11 funzionante:

 #include  #include  int getLongestIncSub(const std::vector &sequence, size_t index, std::vector> &sub) { if(index == 0) { sub.push_back(std::vector{sequence[0]}); return 1; } size_t longestSubSeq = getLongestIncSub(sequence, index - 1, sub); std::vector> tmpSubSeq; for(std::vector &subSeq : sub) { if(subSeq[subSeq.size() - 1] < sequence[index]) { std::vector 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>>(sub)); return longestSubSeq; } int getLongestIncSub(const std::vector &sequence) { std::vector> sub; return getLongestIncSub(sequence, sequence.size() - 1, sub); } int main() { std::vector seq{0, 8, 2, 3, 7, 9}; std::cout << getLongestIncSub(seq); return 0; } 

Ecco un’implementazione di Scala dell’algoritmo O (n ^ 2):

 object Solve { def longestIncrSubseq[T](xs: List[T])(implicit ord: Ordering[T]) = { xs.foldLeft(List[(Int, List[T])]()) { (sofar, x) => if (sofar.isEmpty) List((1, List(x))) else { val resIfEndsAtCurr = (sofar, xs).zipped map { (tp, y) => val len = tp._1 val seq = tp._2 if (ord.lteq(y, x)) { (len + 1, x :: seq) // reversely recorded to avoid O(n) } else { (1, List(x)) } } sofar :+ resIfEndsAtCurr.maxBy(_._1) } }.maxBy(_._1)._2.reverse } def main(args: Array[String]) = { println(longestIncrSubseq(List( 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15))) } } 

Ecco un’altra implementazione di O (n ^ 2) JAVA. Nessuna ricorsione / memoizzazione per generare la sottosequenza effettiva. Solo un array di stringhe che memorizza il LIS effettivo in ogni fase e un array per memorizzare la lunghezza del LIS per ciascun elemento. Abbastanza dannatamente facile. Dare un’occhiata:

 import java.io.BufferedReader; import java.io.InputStreamReader; /** * Created by Shreyans on 4/16/2015 */ class LNG_INC_SUB//Longest Increasing Subsequence { public static void main(String[] args) throws Exception { BufferedReader br=new BufferedReader(new InputStreamReader(System.in)); System.out.println("Enter Numbers Separated by Spaces to find their LIS\n"); String[] s1=br.readLine().split(" "); int n=s1.length; int[] a=new int[n];//Array actual of Numbers String []ls=new String[n];// Array of Strings to maintain LIS for every element for(int i=0;i=0;j--) { //First check if number at index j is less than num at i. // Second the length of that DP should be greater than dp[i] // -1 since dp of previous could also be one. So we compare the dp[i] as empty initially if(a[j]dp[i]-1) { dp[i]=dp[j]+1;//Assigning temp length of LIS. There may come along a bigger LIS of a future a[j] x=ls[j];//Assigning temp LIS of a[j]. Will append a[i] later on } } x+=(" "+a[i]); ls[i]=x; if(dp[i]>max) { max=dp[i]; seq=ls[i]; } } System.out.println("Length of LIS is: " + max + "\nThe Sequence is: " + seq); } } 

Codice in azione: http://ideone.com/sBiOQx

Questo può essere risolto in O (n ^ 2) usando la programmazione dynamic. Il codice Python per lo stesso sarebbe come: –

 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) 

Per input: 5 19 5 81 50 28 29 1 83 23

l'output sarebbe: [1, 2, 1, 3, 3, 3, 4, 1, 5, 3] 5

Il list_index dell'elenco di output è il list_index dell'elenco di input. Il valore in un determinato list_index nella lista di output indica la lunghezza di sottosequenza crescente più lunga per quel list_index.

ecco l’implementazione di java O (nlogn)

 import java.util.Scanner; public class LongestIncreasingSeq { private static int binarySearch(int table[],int a,int len){ int end = len-1; int beg = 0; int mid = 0; int result = -1; while(beg <= end){ mid = (end + beg) / 2; if(table[mid] < a){ beg=mid+1; result = mid; }else if(table[mid] == a){ return len-1; }else{ end = mid-1; } } return result; } public static void main(String[] args) { // int[] t = {1, 2, 5,9,16}; // System.out.println(binarySearch(t , 9, 5)); Scanner in = new Scanner(System.in); int size = in.nextInt();//4; int A[] = new int[size]; int table[] = new int[A.length]; int k = 0; while(k A[i]){ table[0] = A[i]; }else if(table[len-1] 

Questa è un’implementazione Java in O (n ^ 2). Semplicemente non ho usato la ricerca binaria per trovare l’elemento più piccolo in S, che è> = di X. Ho appena usato un ciclo for. Usare la ricerca binaria renderebbe la complessità a O (n logn)

 public static void olis(int[] seq){ int[] memo = new int[seq.length]; memo[0] = seq[0]; int pos = 0; for (int i=1; i= x){ memo[j] = x; break; } } } //just to print every step System.out.println(Arrays.toString(memo)); } //the final array with the LIS System.out.println(Arrays.toString(memo)); System.out.println("The length of lis is " + (pos + 1)); } 

verifica il codice in java per la sottosequenza crescente più lunga con gli elementi dell’array

http://ideone.com/Nd2eba

 /** ** Java Program to implement Longest Increasing Subsequence Algorithm **/ import java.util.Scanner; /** Class LongestIncreasingSubsequence **/ class LongestIncreasingSubsequence { /** function lis **/ public int[] lis(int[] X) { int n = X.length - 1; int[] M = new int[n + 1]; int[] P = new int[n + 1]; int L = 0; for (int i = 1; i < n + 1; i++) { int j = 0; /** Linear search applied here. Binary Search can be applied too. binary search for the largest positive j <= L such that X[M[j]] < X[i] (or set j = 0 if no such value exists) **/ for (int pos = L ; pos >= 1; pos--) { if (X[M[pos]] < X[i]) { j = pos; break; } } P[i] = M[j]; if (j == L || X[i] < X[M[j + 1]]) { M[j + 1] = i; L = Math.max(L,j + 1); } } /** backtrack **/ int[] result = new int[L]; int pos = M[L]; for (int i = L - 1; i >= 0; i--) { result[i] = X[pos]; pos = P[pos]; } return result; } /** Main Function **/ public static void main(String[] args) { Scanner scan = new Scanner(System.in); System.out.println("Longest Increasing Subsequence Algorithm Test\n"); System.out.println("Enter number of elements"); int n = scan.nextInt(); int[] arr = new int[n + 1]; System.out.println("\nEnter "+ n +" elements"); for (int i = 1; i <= n; i++) arr[i] = scan.nextInt(); LongestIncreasingSubsequence obj = new LongestIncreasingSubsequence(); int[] result = obj.lis(arr); /** print result **/ System.out.print("\nLongest Increasing Subsequence : "); for (int i = 0; i < result.length; i++) System.out.print(result[i] +" "); System.out.println(); } } 

Questo può essere risolto in O (n ^ 2) usando la programmazione dynamic.

Elaborare gli elementi di input in ordine e mantenere un elenco di tuple per ciascun elemento. Ogni tupla (A, B), per l’elemento che indicherò, A = lunghezza della sotto-sequenza crescente più lunga che termina con i e B = indice del predecessore della lista [i] nella sotto-sequenza crescente più lunga che termina alla lista [i ].

Partire dall’elemento 1, l’elenco di tuple per l’elemento 1 sarà [(1,0)] per l’elemento i, scansionare l’elenco 0..i e trovare l’elenco di elementi [k] tale che lista [k]

Alla fine, trova tutti gli elementi con valore massimo di A (lunghezza di LIS che termina con l’elemento) e torna indietro usando le tuple per ottenere l’elenco.

Ho condiviso il codice per lo stesso su http://www.edufyme.com/code/?id=66f041e16a60928b05a7e228a89c3799

Implementazione java O (n ^ 2):

 void LIS(int arr[]){ int maxCount[]=new int[arr.length]; int link[]=new int[arr.length]; int maxI=0; link[0]=0; maxCount[0]=0; for (int i = 1; i < arr.length; i++) { for (int j = 0; j < i; j++) { if(arr[j]maxCount[i])){ maxCount[i]=maxCount[j]+1; link[i]=j; if(maxCount[i]>maxCount[maxI]){ maxI=i; } } } } for (int i = 0; i < link.length; i++) { System.out.println(arr[i]+" "+link[i]); } print(arr,maxI,link); } void print(int arr[],int index,int link[]){ if(link[index]==index){ System.out.println(arr[index]+" "); return; }else{ print(arr, link[index], link); System.out.println(arr[index]+" "); } } 
 def longestincrsub(arr1): n=len(arr1) l=[1]*n for i in range(0,n): for j in range(0,i) : if arr1[j] 

anche se c'è un modo in cui è ansible risolverlo in tempo O (nlogn) (questo risolve in O (n ^ 2) tempo), ma comunque in questo modo fornisce un approccio alla programmazione dynamic che è anche buono.