algorithm
Dynamisk programmering
Sök…
Introduktion
Dynamics-programmering är ett allmänt använt koncept och används ofta för optimering. Det hänvisar till att förenkla ett komplicerat problem genom att dela upp det i enklare delproblem på ett rekursivt sätt vanligtvis bottom-up-metoden. Det finns två viktiga attribut som ett problem måste ha för att dynamisk programmering ska vara tillämplig "Optimal understruktur" och "Överlappande delproblem". För att uppnå sin optimering använder Dynamics-programmering ett koncept som kallas Memorization
Anmärkningar
Dynamisk programmering är en förbättring av Brute Force, se detta exempel för att förstå hur man kan få en Dynamic Programming-lösning från Brute Force.
En dynamisk programmeringslösning har två huvudkrav:
Överlappande problem
Optimal understruktur
Överlappande delproblem innebär att resultaten från mindre versioner av problemet återanvänds flera gånger för att komma till lösningen på det ursprungliga problemet
Optimal substruktur innebär att det finns en metod för att beräkna ett problem från dess delproblem.
En dynamisk programmeringslösning har två huvudkomponenter, staten och övergången
Staten hänvisar till ett delproblem av det ursprungliga problemet.
Övergången är metoden för att lösa ett problem baserat på dess delproblem
Tiden som en dynamisk programmeringslösning tar kan beräknas som No. of States * Transition Time . Således om en lösning har N^2 tillstånd och övergången är O(N) , skulle lösningen ta ungefär O(N^3) tid.
Ryggsäckproblem
0-1 Ryggsäck
Ryggsäckproblemet är ett problem när man får en uppsättning artiklar, var och en med en vikt, ett värde och exakt 1 kopia , bestämmer vilka objekt som ska inkluderas i en samling så att den totala vikten är mindre än eller lika med en given gränsen och det totala värdet är så stort som möjligt.
C ++ Exempel:
Genomförande :
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
Utgång :
3
Det betyder att det maximala värdet kan uppnås är 3, vilket uppnås genom att välja (2,1) och (3,2).
Obundet ryggsäck
Problemet med obunden ryggsäck är ett problem som ger en uppsättning artiklar, var och en med en vikt, ett värde och oändliga kopior , bestämmer antalet för varje objekt som ska inkluderas i en samling så att den totala vikten är mindre än eller lika med en given gräns och det totala värdet är så stort som möjligt.
Python (2.7.11) Exempel:
Genomförande :
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
Komplexiteten i implementeringen är O(nC) , vilket n är antalet objekt.
Test :
w = [2, 3, 4, 5, 6]
v = [2, 4, 6, 8, 9]
print unbounded_knapsack(w, v, 13)
Utgång :
20
Det betyder att det maximala värdet kan uppnås är 20, vilket uppnås genom att välja (5, 8), (5, 8) och (3, 4).
Viktat jobbplaneringsalgoritm
Viktad jobbplaneringsalgoritm kan också betecknas som viktad aktivitetsval algoritm.
Problemet är, med tanke på vissa jobb med deras starttid och sluttid, och en vinst du gör när du är klar med jobbet, vad är den maximala vinsten du kan göra eftersom inga två jobb kan utföras parallellt?
Den här ser ut som Aktivitetsval med Greedy Algoritm, men det finns en extra twist. Det vill säga, istället för att maximera antalet färdigställda jobb fokuserar vi på att göra maximal vinst. Antalet utförda jobb spelar ingen roll här.
Låt oss titta på ett exempel:
+-------------------------+---------+---------+---------+---------+---------+---------+
| 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 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Jobbena har ett namn, deras start- och sluttid och vinst. Efter några iterationer kan vi ta reda på om vi utför Job-A och Job-E , kan vi få maximal vinst på 17. Nu hur kan vi ta reda på detta med hjälp av en algoritm?
Det första vi gör är att sortera jobben efter deras slutbehandlingstid i icke-minskande ordning. Varför gör vi det här? Det beror på att om vi väljer ett jobb som tar mindre tid att avsluta, lämnar vi mest tid för att välja andra jobb. Vi har:
+-------------------------+---------+---------+---------+---------+---------+---------+
| 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 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Vi kommer att ha en extra tillfällig matris Acc_Prof av storlek n (Här anger n det totala antalet jobb). Detta kommer att innehålla den maximala ackumulerade vinsten för att utföra jobb. Får du inte det? Vänta och se på. Vi initierar värdena i matrisen med vinsten för varje jobb. Det betyder att Acc_Prof [i] till en början kommer att ha vinsten med att utföra i-th jobb.
+-------------------------+---------+---------+---------+---------+---------+---------+
| Acc_Prof | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Låt oss nu beteckna position 2 med i , och position 1 kommer att betecknas med j . Vår strategi är att iterera j från 1 till i-1 och efter varje iteration kommer vi att öka i med 1 tills jag blir n + 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 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Vi kontrollerar om Job [i] och Job [j] överlappar, det vill säga om sluttiden för Job [j] är större än Job [i] : s starttid, kan dessa två jobb inte göras tillsammans. Men om de inte överlappar varandra kontrollerar vi om Acc_Prof [j] + Vinst [i]> Acc_Prof [i] . Om så är fallet kommer vi att uppdatera Acc_Prof [i] = Acc_Prof [j] + Profit [i] . Det är:
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
Här representerar Acc_Prof [j] + Profit [i] den ackumulerade vinsten för att göra dessa två jobb. Låt oss kolla det för vårt exempel:
Här överlappar Job [j] med Job [i] . Så dessa kan inte göras tillsammans. Eftersom vår j är lika med i-1 , ökar vi värdet på i till i + 1 som är 3 . Och vi gör 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 överlappar Job [j] och Job [i] inte. Den totala vinsten vi kan göra genom att välja dessa två jobb är: Acc_Prof [j] + Vinst [i] = 5 + 5 = 10 vilket är större än Acc_Prof [i] . Så vi uppdaterar Acc_Prof [i] = 10 . Vi ökar också j med 1. Vi får,
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 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Här överlappar Job [j] med Job [i] och j är också lika med i-1 . Så vi ökar i med 1 och gör j = 1 . Vi får,
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 överlappar Job [j] och Job [i] inte, vi får den ackumulerade vinsten 5 + 4 = 9 , vilket är större än Acc_Prof [i] . Vi uppdaterar Acc_Prof [i] = 9 och steget j med 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 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Återigen överlappar Job [j] och Job [i] inte. Den ackumulerade vinsten är: 6 + 4 = 10 , vilket är större än Acc_Prof [i] . Vi uppdaterar igen Acc_Prof [i] = 10 . Vi ökar j med 1. Vi får:
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 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Om vi fortsätter med denna process, efter att iterera hela tabellen med i , kommer vårt bord äntligen att se ut:
+-------------------------+---------+---------+---------+---------+---------+---------+
| 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 |
+-------------------------+---------+---------+---------+---------+---------+---------+
* Några steg har hoppats över för att göra dokumentet kortare.
Om vi uppdaterar oss genom matrisen Acc_Prof , kan vi ta reda på den maximala vinsten till 17 ! Pseudokoden:
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
Komplexiteten i att fylla i Acc_Prof- matrisen är O (n 2 ). Arrayomgången tar O (n) . Så den totala komplexiteten för denna algoritm är O (n 2 ).
Nu, om vi vill ta reda på vilka jobb som utfördes för att få maximal vinst, måste vi korsa matrisen i omvänd ordning och om Acc_Prof matchar maxProfit , kommer vi att trycka på namnet på jobbet i en stack och subtrahera vinsten av det jobbet från maxProfit . Vi kommer att göra detta tills vår maxProfit> 0 eller så når vi startpunkten för Acc_Prof- arrayen. Pseudokoden kommer att se ut:
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
Komplexiteten i denna procedur är: O (n) .
En sak att komma ihåg, om det finns flera jobbscheman som kan ge oss maximal vinst kan vi bara hitta ett jobbschema via den här proceduren.
Redigera avstånd
Problemmeddelandet är som om vi får två strängar str1 och str2, hur många minsta antal operationer som kan utföras på str1 att det konverteras till str2.
Implementering i 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()];
}
}
Produktion
3
Längsta vanliga efterföljande
Om vi får de två strängarna måste vi hitta den längsta vanliga undersekvensen som finns i båda.
Exempel
LCS för ingångssekvenser "ABCDGH" och "AEDFHR" är "ADH" i längd 3.
LCS för ingångssekvenser "AGGTAB" och "GXTXAYB" är "GTAB" i längd 4.
Implementering i 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()];
}
}
Produktion
4
Fibonacci-nummer
Nedifrån och upp-metoden för att skriva ut det nionde Fibonacci-numret med dynamisk programmering.
Rekursivt träd
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)
Överlappande delproblem
Här är fib (0), fib (1) och fib (3) de överlappande delproblemen. Fib (0) upprepas 3 gånger, fib (1) upprepas 5 gånger och fib (3) upprepas 2 gånger.
Genomförande
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];
}
Tidskomplexitet
På)
Längsta vanliga underlag
Med tanke på 2 strängar str1 och str2 måste vi hitta längden på den längsta vanliga substrängen mellan dem.
exempel
Ingång: X = "abcdxyz", y = "xyzabcd" Utgång: 4
Den längsta vanliga substring är "abcd" och har längd 4.
Ingång: X = "zxabcdezy", y = "yzabcdezx" Utgång: 6
Den längsta vanliga substrängen är "abcdez" och har längd 6.
Implementering i 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;
}
Tidskomplexitet
O (m * n)