Kaip nustatyti ilgiausią papildomą seką naudojant dinaminį programavimą?

Turiu sveikų skaičių rinkinį. Noriu rasti ilgiausią šio rinkinio pakopą pagal dinaminį programavimą.

169
13 апр. Tony rinkinys balandžio 13 d 2010-04-13 20:26 '10, 20:26, 2010-04-13 20:26
@ 13 atsakymų

Gerai, pirmiausia aprašysiu paprastiausią sprendimą, kuris yra O (N ^ 2), kur N yra kolekcijos dydis. Taip pat yra O (N log N) tirpalas, kurį taip pat aprašysiu. Čia žiūrėkite skyriuje Efektyvūs algoritmai.

Darau prielaidą, kad masyvo indeksai yra nuo 0 iki N - 1. Todėl apibrėžime DP[i] kaip LIS ilgį (ilgiausią didėjančią seką), kuri baigiasi elementu su indeksu i . Norėdami apskaičiuoti DP[i] , atsižvelgiame į visus indeksus j < i ir patikrinkite, ar DP[j] + 1 > DP[i] ir array[j] < array[i] (mes norime, kad jis padidėtų). Jei taip, mes galime atnaujinti dabartinį optimalų DP[i] . Norint rasti masyvo pasaulinį optimalumą, galite naudoti maksimalią DP[0...N - 1] reikšmę.

 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]; } } 

Aš naudoju prev masyvą, kad vėliau rastume faktinę seką, o ne tik jo ilgį. Grįžkite į rekursyviai iš bestEnd prev[bestEnd] kilpoje naudojant prev[bestEnd] . -1 vertė yra stabdymo ženklas.


Gerai, dabar naudokite efektyvesnį sprendimą O(N log N) :

Tegul S[pos] apibrėžiamas kaip mažiausias sveikasis skaičius, kuris nutraukia didėjančią ilgio pos . Dabar mes kartojame kiekvieną įvesties rinkinio X skaičių ir atlikite šiuos veiksmus:

  • Jei X > yra paskutinis elementas „ S , pridėkite „ X į „ S Tai iš esmės reiškia, kad radome naują didžiausią LIS .

  • Priešingu atveju suraskite mažiausią elementą S , kuris yra >= nei X , ir pakeiskite jį į X Kadangi S surūšiuotas bet kuriuo metu, elementą galima rasti naudojant dvejetainę paiešką log(N) .

Bendras vykdymo laikas yra N sveikieji skaičiai ir kiekvienos iš jų binarinė paieška - N * log (N) = O (N log N)

Dabar paimkime pavyzdį:

Sveikų skaičių rinkinys: 2 6 3 4 1 2 9 5 8

Žingsniai:

 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 

Taigi LIS ilgis yra 5 (S dydis).

Norėdami atkurti faktinį LIS , mes vėl panaudosime pagrindinę masyvą. Leiskite parent[i] būti elemento su indeksu i LIS pirmtaku, baigiant elementu su indeksu i .

Kad būtų paprasčiau, mes galime laikyti masyvą S , o ne faktinius sveikuosius skaičius, bet jų indeksus (pozicijas) rinkinyje. Mes neišsaugome {1, 2, 4, 5, 8} , bet laikome {4, 5, 3, 7, 8} .

Tai yra įvestis [4] = 1 , įvestis [5] = 2 , įvestis [3] = 4 , įvestis [7] = 5 , įvestis [8] = 8 .

Jei teisingai pakeisime pagrindinę masyvą, faktinė LIS yra:

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

Dabar svarbu - kaip atnaujinti pagrindinę masyvą? Yra dvi parinktys:

  • Jei X > yra paskutinis elementas S , tada parent[indexX] = indexLastElement . Tai reiškia, kad paskutinio elemento tėvas yra paskutinis elementas. Mes paprasčiausiai pridedame X prie S

  • Priešingu atveju suraskite mažiausio elemento indeksą S , kuris yra >= nei X , ir pakeiskite jį į X Čia parent[indexX] = S[index - 1] .

324
13 апр. Petar Minchev atsakymas, pateiktas balandžio 13 d 2010-04-13 20:39 '10, 08:39 PM 2010-04-13 20:39

Pjotro Minčevo paaiškinimas padėjo man jį išsiaiškinti, bet man buvo sunku išsiaiškinti, kas viskas buvo, taigi aš padariau „Python“ įgyvendinimą pernelyg apibūdinančiais kintamųjų pavadinimais ir daug komentarų. Aš padariau naivų rekursinį tirpalą, O (n ^ 2) tirpalą ir O (n log n) tirpalą.

Tikiuosi, kad tai padės išsiaiškinti algoritmus!

Rekursinis sprendimas

 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 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 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 

O (n log n) dinaminis programavimo sprendimas

09 нояб. atsakymą pateikė Sam King . 2013-11-09 04:48 '13, 4:48, 2013-11-09 04:48

Kalbant apie DP sprendimą, nustebau, kad niekas nepaminėjo, kad LIS gali būti sumažintas iki LCS . Viskas, ką jums reikia padaryti, yra rūšiuoti originalios sekos kopiją, pašalinti visus dublikatus ir padaryti juos LCS. Pseudokode tai yra:

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

Ir visiškas įgyvendinimas yra parašytas „Go“. Jei nereikia atkurti sprendimo, nereikia palaikyti visos „n ^ 2 DP“ matricos.

 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] } 
15
25 апр. Salvadoro Dali atsakymas balandžio 25 d 2016-04-25 12:33 '16 at 12:33 pm 2016-04-25 12:33

Toliau pateiktas C ++ diegimas taip pat apima tam tikrą kodą, kuris sukuria faktinę ilgiausią pakopinę seką naudojant masyvą, pavadintą 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; } 

Įgyvendinimas be kamino tiesiog traukia vektorių

 #include <iostream> #include <vector> #include <limits> std::vector<int> LIS( const std::vector<int>  ) { 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; } 
8
28 окт. bjackfly atsakymas 28 sp 2013-10-28 19:10 '13, 19:10, 2013-10-28 19:10

Toliau pateikiami trys žingsniai problemos įvertinimui pagal dinaminį programavimą:

  • Pakartokite apibrėžimą: maxLength (i) == 1 + maks. Ilgis (j), kur 0 <j <i ir masyvas [i]> masyvas [j]
  • Pakartotinių parametrų ribos: gali būti nuo 0 iki i - 1 sekos, perduodamos kaip parametras
  • Vertinimo tvarka: kadangi ji padidina seką, ji turi būti įvertinta nuo 0 iki n

Jei pavyzdžiu laikomės sekos {0, 8, 2, 3, 7, 9} pagal indeksą:

  • [0] kaip pagrindinį atvejį gauname {0} seką
  • [1] mes turime 1 naują seką {0, 8}
  • [2], bandydami įvertinti dvi naujas sekas {0, 8, 2} ir {0, 2}, pridedant elementą prie indekso 2 prie esamų posistemių - tik vienas yra leidžiamas, todėl pridedant trečiąją galimą seką {0, 2} tik į parametrų sąrašą ...

Čia yra C ++ 11 darbo kodas:

 #include <iostream> #include <vector> int getLongestIncSub(const std::vector<int>  size_t index, std::vector<std::vector<int>>  { 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>  : 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>  { 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; } 
3
13 нояб. Atsakymą pateikė Iuri Covalisin lapkričio 13 d 2013-11-13 03:54 '13, 3:54, 2013-11-13 03:54

Čia pateikiamas „Scala“ algoritmo O (n ^ 2) įgyvendinimas:

 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))) } } 
1
14 дек. atsakymas pateikiamas lcn 14 dec. 2014-12-14 08:21 '14, 8:21 val. 2014-12-14 08:21

Čia yra dar vienas O (n ^ 2) JAVA įgyvendinimas. Nėra rekursijos / atminties, kad būtų sukurta tikra seka. Tiesiog eilutės masyvas, kuriame kiekviename etape saugoma faktinė LIS, ir masyvas kiekvienam elementui saugoti LIS ilgį. Graži. Pažvelkite:

 import java.io.BufferedReader; import java.io.InputStreamReader;  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<n;i++) { a[i]=Integer.parseInt(s1[i]); } int[]dp=new int[n];//Storing length of max subseq. int max=dp[0]=1;//Defaults String seq=ls[0]=s1[0];//Defaults for(int i=1;i<n;i++) { dp[i]=1; String x=""; for(int j=i-1;j>=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]<a[i] { 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); } } 

Veiklos kodas: http://ideone.com/sBiOQx

1
16 апр. Atsakymą pateikė bholagabbar balandžio 16 d 2015-04-16 18:56 '15, 18:56, 2015-04-16 18:56

O (n ^ 2) java diegimas:

 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]<arr[i]  ((maxCount[j]+1)>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]+" "); } } 
0
17 февр. Atsakyti Mostafizar 17 Vas. 2017-02-17 23:27 '17 23:27 pm 2017-02-17 23:27

patikrinkite java kodą ilgiausiam didėjančiam seka su masyvo elementais

http://ideone.com/Nd2eba

  import java.util.Scanner;  class LongestIncreasingSubsequence {  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;  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); } }  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; }  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);  System.out.print("\nLongest Increasing Subsequence : "); for (int i = 0; i < result.length; i++) System.out.print(result[i] +" "); System.out.println(); } } 
0
27 окт. atsakymą pateikė jayant singh 27 oct. 2015-10-27 14:09 '15 - 14:09 2015-10-27 14:09

čia įgyvendinamas java O (nlogn) įgyvendinimas

 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<size){ A[k++] = in.nextInt(); if(k<size-1) in.nextLine(); } table[0] = A[0]; int len = 1; for (int i = 1; i < A.length; i++) { if(table[0] > A[i]){ table[0] = A[i]; }else if(table[len-1]<A[i]){ table[len++]=A[i]; }else{ table[binarySearch(table, A[i],len)+1] = A[i]; } } System.out.println(len); } } 
0
14 мая '15 в 21:20 2015-05-14 21:20 atsakymą pateikė fatih tekin gegužės 15 d. 15:20 2015-05-14 21:20

Tai „Java“ diegimas O (n ^ 2). Aš paprasčiausiai nenaudojau „Binary Search“, kad surastumėte mažiausią elementą „S“, kuris yra> = nei X. Aš tiesiog naudoju „for loop“. Naudojant dvejetainę paiešką bus sudėtinga 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<seq.length; i++){ int x = seq[i]; if (memo[pos] < x){ pos++; memo[pos] = x; } else { for(int j=0; j<=pos; j++){ if (memo[j] >= 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)); } 
0
09 марта '15 в 1:55 2015-03-09 01:55 atsakymą pateikė „ Shashank Agarwal“ kovo 09–15 d. 1:55 2015-03-09 01:55

Tai gali būti išspręsta O (n ^ 2) naudojant dinaminį programavimą. Tokio paties „Python“ kodas atrodys taip: -

 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) 

Už indėlį: 5 19 5 81 50 28 29 1 83 23

: [1, 2, 1, 3, 3, 3, 4, 1, 5, 3] 5

Išvesties sąrašo sąrašas list_index - sąrašo įvesties sąrašas_index. Nurodytame list_index reikšmė išvesties sąraše nurodo ilgiausią šio sąrašo_indekso sekos ilgį.

0
13 апр. Atsakyti Barun Sharma balandžio 13 2014-04-13 22:57 '14 ne 10:57 AM 2014-04-13 22:57

Tai gali būti išspręsta O (n ^ 2) naudojant dinaminį programavimą.

Proceso įvesties elementus tvarkykite ir tvarkykite kiekvieno elemento eilių sąrašą. Kiekvienas elemento I rinkinys (A, B) žymi: A = ilgiausio didėjančio sekos ilgio, kuris baigiasi su i, ir B = ankstesnio sąrašo [i] indeksas ilgiausioje didėjančioje sekoje, baigiantis sąraše [i].

Pradėkite nuo 1 punkto, elemento 1 eilutės sąrašas bus [(1,0)] elementui, aš nuskaitysiu sąrašą 0..i ir surasiu elementų [k] sąrašą [k] <sąrašas [i], A reikšmė elementui i, Ai bus Ak + 1, o Bi bus k. Jei yra keletas tokių elementų, pridėkite juos prie elemento i elemento sąrašo.

Galų gale suraskite visus elementus, kurių maksimali vertė yra A (elemento ilgio LIS ilgis), ir grąžinimo kelią, naudodami eilutes, kad gautumėte sąrašą.

Šį kodą bendrinau šiuo adresu: http://www.edufyme.com/code/?id=66f041e16a60928b05a7e228a89c3799

0
16 нояб. atsakymą pateikė Somil Bhandari . 2015-11-16 20:41 '15 at 8:41 pm 2015-11-16 20:41

Žr. Kitus klausimus apie žymeklių arba Užduokite klausimą