algorithm
Dynamisch programmeren
Zoeken…
Invoering
Dynamiekprogrammering is een veelgebruikt concept en wordt vaak gebruikt voor optimalisatie. Het verwijst naar het vereenvoudigen van een gecompliceerd probleem door het op te splitsen in eenvoudigere subproblemen op een recursieve manier, meestal bottom-up benadering. Er zijn twee belangrijke attributen die een probleem moet hebben om dynamisch programmeren toepasbaar te maken "Optimale substructuur" en "Overlappende subproblemen". Om zijn optimalisatie te bereiken, gebruikt Dynamics programmeren een concept genaamd Memorisatie
Opmerkingen
Dynamisch programmeren is een verbetering van Brute Force, zie dit voorbeeld om te begrijpen hoe iemand een dynamische programmeeroplossing bij Brute Force kan krijgen.
Een dynamische programmeeroplossing heeft 2 hoofdvereisten:
Overlappende problemen
Optimale onderbouw
Overlappende subproblemen betekent dat resultaten van kleinere versies van het probleem meerdere keren worden hergebruikt om tot de oplossing voor het oorspronkelijke probleem te komen
Optimale substructuur betekent dat er een methode is om een probleem uit de subproblemen te berekenen.
Een dynamische programmeeroplossing heeft 2 hoofdcomponenten, de staat en de overgang
De staat verwijst naar een deelprobleem van het oorspronkelijke probleem.
De Transitie is de methode om een probleem op te lossen op basis van de subproblemen
De tijd die een dynamische programmeeroplossing nodig heeft, kan worden berekend als het No. of States * Transition Time . Dus als een oplossing N^2 toestanden heeft en de overgang O(N) , dan zou de oplossing ongeveer O(N^3) tijd vergen.
Knapzak Probleem
0-1 Knapzak
Het Knapzakprobleem is een probleem wanneer een set items wordt gegeven, elk met een gewicht, een waarde en precies 1 exemplaar , bepalen welk item (s) in een verzameling moeten worden opgenomen, zodat het totale gewicht kleiner is dan of gelijk aan een gegeven limiet en de totale waarde is zo groot mogelijk.
C ++ Voorbeeld:
Implementatie :
int knapsack(vector<int> &value, vector<int> &weight, int N, int C){
int dp[C+1];
for (int i = 1; i <= C; ++i){
dp[i] = -100000000;
}
dp[0] = 0;
for (int i = 0; i < N; ++i){
for (int j = C; j >= weight[i]; --j){
dp[j] = max(dp[j],dp[j-weight[i]]+value[i]);
}
}
return dp[C];
}
Test :
3 5
5 2
2 1
3 2
Uitgang :
3
Dat betekent dat de maximale waarde die kan worden behaald 3 is, wat wordt bereikt door te kiezen voor (2,1) en (3,2).
Onbeperkte Knapzak
Het Unbounded Knapsack-probleem is een probleem waarbij een aantal items, elk met een gewicht, een waarde en oneindige kopieën , het aantal items bepaalt dat in een verzameling moet worden opgenomen, zodat het totale gewicht kleiner is dan of gelijk is aan een bepaalde limiet en de totale waarde is zo groot mogelijk.
Python (2.7.11) Voorbeeld:
Implementatie :
def unbounded_knapsack(w, v, c): # weight, value and capactiy
m = [0]
for r in range(1, c+1):
val = m[r-1]
for i, wi in enumerate(w):
if wi > r:
continue
val = max(val, v[i] + m[r-wi])
m.append(val)
return m[c] # return the maximum value can be achieved
De complexiteit van die implementatie is O(nC) , waarbij n het aantal items is.
Test :
w = [2, 3, 4, 5, 6]
v = [2, 4, 6, 8, 9]
print unbounded_knapsack(w, v, 13)
Uitgang :
20
Dat betekent dat de maximale waarde die kan worden bereikt 20 is, wat wordt bereikt door te kiezen voor (5, 8), (5, 8) en (3, 4).
Gewogen taakplanningalgoritme
Gewogen taakplanningalgoritme kan ook worden aangeduid als gewogen activiteitselectie-algoritme.
Het probleem is, gezien bepaalde taken met hun starttijd en eindtijd, en een winst die u maakt wanneer u de taak voltooit, wat is de maximale winst die u kunt maken, gezien het feit dat er geen twee taken tegelijkertijd kunnen worden uitgevoerd?
Deze lijkt op Activiteitselectie met behulp van Greedy Algorithm, maar er is een extra wending. Dat wil zeggen, in plaats van het aantal voltooide taken te maximaliseren, richten we ons op maximale winst. Het aantal uitgevoerde taken maakt hier niet uit.
Laten we een voorbeeld bekijken:
+-------------------------+---------+---------+---------+---------+---------+---------+
| Name | A | B | C | D | E | F |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)| (2,5) | (6,7) | (7,9) | (1,3) | (5,8) | (4,6) |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Profit | 6 | 4 | 2 | 5 | 11 | 5 |
+-------------------------+---------+---------+---------+---------+---------+---------+
De banen worden aangeduid met een naam, hun start- en eindtijd en winst. Na een paar iteraties kunnen we erachter komen of we Job-A en Job-E uitvoeren , we kunnen de maximale winst van 17 krijgen. Hoe kunnen we dit nu vinden met behulp van een algoritme?
Het eerste wat we doen is de taken sorteren op hun eindtijd in niet-afnemende volgorde. Waarom doen we dit? Dit komt omdat als we een taak selecteren die minder tijd kost om te voltooien, we de meeste tijd overlaten om andere taken te kiezen. Wij hebben:
+-------------------------+---------+---------+---------+---------+---------+---------+
| Name | D | A | F | B | E | C |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)| (1,3) | (2,5) | (4,6) | (6,7) | (5,8) | (7,9) |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Profit | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
We hebben een extra tijdelijke array Acc_Prof van maat n (hier geeft n het totale aantal taken aan). Dit bevat de maximale geaccumuleerde winst van het uitvoeren van de taken. Snap je het niet? Wacht en kijk. We initialiseren de waarden van de array met de winst van elke taak. Dat betekent dat Acc_Prof [i] in eerste instantie de winst zal behalen van het uitvoeren van i-de taak.
+-------------------------+---------+---------+---------+---------+---------+---------+
| Acc_Prof | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Laten we nu positie 2 aangeven met i , en positie 1 wordt aangegeven met j . Onze strategie zal zijn om j van 1 naar i-1 te herhalen en na elke iteratie zullen we i met 1 verhogen, totdat i n + 1 wordt .
j i
+-------------------------+---------+---------+---------+---------+---------+---------+
| Name | D | A | F | B | E | C |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)| (1,3) | (2,5) | (4,6) | (6,7) | (5,8) | (7,9) |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Profit | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Acc_Prof | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
We controleren of Job [i] en Job [j] elkaar overlappen, dat wil zeggen dat als de eindtijd van Job [j] groter is dan de starttijd van Job [i] , deze twee jobs niet samen kunnen worden uitgevoerd. Als ze elkaar echter niet overlappen, controleren we of Acc_Prof [j] + Profit [i]> Acc_Prof [i] . Als dit het geval is, zullen we Acc_Prof [i] = Acc_Prof [j] + Profit [i] updaten. Dat is:
if Job[j].finish_time <= Job[i].start_time
if Acc_Prof[j] + Profit[i] > Acc_Prof[i]
Acc_Prof[i] = Acc_Prof[j] + Profit[i]
endif
endif
Hier vertegenwoordigt Acc_Prof [j] + Profit [i] de geaccumuleerde winst van het uitvoeren van deze twee taken toegther. Laten we het voor ons voorbeeld bekijken:
Hier overlapt Job [j] met Job [i] . Dus deze kunnen niet samen worden gedaan. Omdat onze j gelijk is aan i-1 , verhogen we de waarde van i tot i + 1 dat 3 is . En we maken j = 1 .
j i
+-------------------------+---------+---------+---------+---------+---------+---------+
| Name | D | A | F | B | E | C |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)| (1,3) | (2,5) | (4,6) | (6,7) | (5,8) | (7,9) |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Profit | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Acc_Prof | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Nu overlappen Job [j] en Job [i] elkaar niet. De totale hoeveelheid winst die we kunnen maken door deze twee banen te kiezen, is: Acc_Prof [j] + Profit [i] = 5 + 5 = 10, wat groter is dan Acc_Prof [i] . Dus werken we Acc_Prof [i] = 10 bij . We verhogen ook j met 1. We krijgen,
j i
+-------------------------+---------+---------+---------+---------+---------+---------+
| Name | D | A | F | B | E | C |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)| (1,3) | (2,5) | (4,6) | (6,7) | (5,8) | (7,9) |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Profit | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Acc_Prof | 5 | 6 | 10 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Hier overlapt Job [j] met Job [i] en is j ook gelijk aan i-1 . Dus we verhogen i met 1 en maken j = 1 . We krijgen,
j i
+-------------------------+---------+---------+---------+---------+---------+---------+
| Name | D | A | F | B | E | C |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)| (1,3) | (2,5) | (4,6) | (6,7) | (5,8) | (7,9) |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Profit | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Acc_Prof | 5 | 6 | 10 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Nu overlappen Job [j] en Job [i] elkaar niet, we krijgen de gecumuleerde winst 5 + 4 = 9 , die groter is dan Acc_Prof [i] . We werken Acc_Prof [i] = 9 bij en verhogen j met 1.
j i
+-------------------------+---------+---------+---------+---------+---------+---------+
| Name | D | A | F | B | E | C |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)| (1,3) | (2,5) | (4,6) | (6,7) | (5,8) | (7,9) |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Profit | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Acc_Prof | 5 | 6 | 10 | 9 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Opnieuw overlappen Job [j] en Job [i] elkaar niet. De gecumuleerde winst is: 6 + 4 = 10 , wat groter is dan Acc_Prof [i] . We werken Acc_Prof [i] = 10 opnieuw bij . We verhogen j met 1. We krijgen:
j i
+-------------------------+---------+---------+---------+---------+---------+---------+
| Name | D | A | F | B | E | C |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)| (1,3) | (2,5) | (4,6) | (6,7) | (5,8) | (7,9) |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Profit | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Acc_Prof | 5 | 6 | 10 | 10 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Als we doorgaan met dit proces, nadat we de hele tabel met i hebben herhaald, ziet onze tabel er uiteindelijk uit als:
+-------------------------+---------+---------+---------+---------+---------+---------+
| Name | D | A | F | B | E | C |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)| (1,3) | (2,5) | (4,6) | (6,7) | (5,8) | (7,9) |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Profit | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Acc_Prof | 5 | 6 | 10 | 14 | 17 | 8 |
+-------------------------+---------+---------+---------+---------+---------+---------+
* Een paar stappen zijn overgeslagen om het document korter te maken.
Als we de reeks Acc_Prof doorlopen , kunnen we de maximale winst 17 vinden ! De pseudo-code:
Procedure WeightedJobScheduling(Job)
sort Job according to finish time in non-decreasing order
for i -> 2 to n
for j -> 1 to i-1
if Job[j].finish_time <= Job[i].start_time
if Acc_Prof[j] + Profit[i] > Acc_Prof[i]
Acc_Prof[i] = Acc_Prof[j] + Profit[i]
endif
endif
endfor
endfor
maxProfit = 0
for i -> 1 to n
if maxProfit < Acc_Prof[i]
maxProfit = Acc_Prof[i]
return maxProfit
De complexiteit van het vullen van de Acc_Prof- array is O (n 2 ). De array-doorloop neemt O (n) . Dus de totale complexiteit van dit algoritme is O (n 2 ).
Als we nu willen weten welke taken zijn uitgevoerd om de maximale winst te krijgen, moeten we de array in omgekeerde volgorde doorlopen en als de Acc_Prof overeenkomt met de maxProfit , zullen we de naam van de taak in een stapel plaatsen en de winst van die baan van maxProfit . We zullen dit doen tot onze maxProfit> 0 of we bereiken het beginpunt van de Acc_Prof- array. De pseudo-code ziet eruit als:
Procedure FindingPerformedJobs(Job, Acc_Prof, maxProfit):
S = stack()
for i -> n down to 0 and maxProfit > 0
if maxProfit is equal to Acc_Prof[i]
S.push(Job[i].name
maxProfit = maxProfit - Job[i].profit
endif
endfor
De complexiteit van deze procedure is: O (n) .
Een ding om te onthouden, als er meerdere taakplanningen zijn die ons maximale winst kunnen opleveren, kunnen we slechts één taakplanning vinden via deze procedure.
Bewerk afstand
De probleemstelling is als wanneer we twee tekenreeksen str1 en str2 krijgen, hoeveel minimaal aantal bewerkingen kunnen worden uitgevoerd op de str1 dat deze wordt geconverteerd naar str2.
Implementatie in Java
public class EditDistance {
public static void main(String[] args) {
// TODO Auto-generated method stub
String str1 = "march";
String str2 = "cart";
EditDistance ed = new EditDistance();
System.out.println(ed.getMinConversions(str1, str2));
}
public int getMinConversions(String str1, String str2){
int dp[][] = new int[str1.length()+1][str2.length()+1];
for(int i=0;i<=str1.length();i++){
for(int j=0;j<=str2.length();j++){
if(i==0)
dp[i][j] = j;
else if(j==0)
dp[i][j] = i;
else if(str1.charAt(i-1) == str2.charAt(j-1))
dp[i][j] = dp[i-1][j-1];
else{
dp[i][j] = 1 + Math.min(dp[i-1][j], Math.min(dp[i][j-1], dp[i-1][j-1]));
}
}
}
return dp[str1.length()][str2.length()];
}
}
uitgang
3
Langste gemeenschappelijke gevolg
Als we de twee strings krijgen, moeten we de langste gemeenschappelijke subsequentie vinden die in beide aanwezig is.
Voorbeeld
LCS voor invoerreeksen "ABCDGH" en "AEDFHR" is "ADH" met lengte 3.
LCS voor invoerreeksen "AGGTAB" en "GXTXAYB" is "GTAB" met lengte 4.
Implementatie in Java
public class LCS {
public static void main(String[] args) {
// TODO Auto-generated method stub
String str1 = "AGGTAB";
String str2 = "GXTXAYB";
LCS obj = new LCS();
System.out.println(obj.lcs(str1, str2, str1.length(), str2.length()));
System.out.println(obj.lcs2(str1, str2));
}
//Recursive function
public int lcs(String str1, String str2, int m, int n){
if(m==0 || n==0)
return 0;
if(str1.charAt(m-1) == str2.charAt(n-1))
return 1 + lcs(str1, str2, m-1, n-1);
else
return Math.max(lcs(str1, str2, m-1, n), lcs(str1, str2, m, n-1));
}
//Iterative function
public int lcs2(String str1, String str2){
int lcs[][] = new int[str1.length()+1][str2.length()+1];
for(int i=0;i<=str1.length();i++){
for(int j=0;j<=str2.length();j++){
if(i==0 || j== 0){
lcs[i][j] = 0;
}
else if(str1.charAt(i-1) == str2.charAt(j-1)){
lcs[i][j] = 1 + lcs[i-1][j-1];
}else{
lcs[i][j] = Math.max(lcs[i-1][j], lcs[i][j-1]);
}
}
}
return lcs[str1.length()][str2.length()];
}
}
uitgang
4
Fibonacci-nummer
Bottom-up benadering voor het afdrukken van het negende Fibonacci-nummer met Dynamic Programming.
Recursieve boom
fib(5)
/ \
fib(4) fib(3)
/ \ / \
fib(3) fib(2) fib(2) fib(1)
/ \ / \ / \
fib(2) fib(1) fib(1) fib(0) fib(1) fib(0)
/ \
fib(1) fib(0)
Overlappende subproblemen
Hier zijn fib (0), fib (1) en fib (3) de overlappende subproblemen. Fib (0) wordt 3 keer herhaald, fib (1) wordt 5 keer herhaald en fib (3) wordt herhaald 2 keer.
Implementatie
public int fib(int n){
int f[] = new int[n+1];
f[0]=0;f[1]=1;
for(int i=2;i<=n;i++){
f[i]=f[i-1]+f[i-2];
}
return f[n];
}
Tijd Complexiteit
Aan)
Langste gemeenschappelijke substring
Gegeven 2 string str1 en str2 moeten we de lengte vinden van de langste gemeenschappelijke substring ertussen.
Voorbeelden
Ingang: X = "abcdxyz", y = "xyzabcd" Uitgang: 4
De langste gemeenschappelijke substring is "abcd" en is van lengte 4.
Ingang: X = "zxabcdezy", y = "yzabcdezx" Uitgang: 6
De langste gemeenschappelijke substring is "abcdez" en heeft een lengte van 6.
Implementatie in Java
public int getLongestCommonSubstring(String str1,String str2){
int arr[][] = new int[str2.length()+1][str1.length()+1];
int max = Integer.MIN_VALUE;
for(int i=1;i<=str2.length();i++){
for(int j=1;j<=str1.length();j++){
if(str1.charAt(j-1) == str2.charAt(i-1)){
arr[i][j] = arr[i-1][j-1]+1;
if(arr[i][j]>max)
max = arr[i][j];
}
else
arr[i][j] = 0;
}
}
return max;
}
Tijd Complexiteit
O (m * n)