cards-deck: 100-199_university::111-120_theoretic_cs::111_algorithms_datastructures

Dynamic Programming | Principle

anchored to [[111.00_anchor]] enhances on [[111.05_problem_beschreibungen]]

Overview

Unter dem Begriff der dynamischen Programmierung verstehen wir primär ein Prinzip, was uns dabei helfen kann, größere Probleme auf kleinere aufzuteilen und damit unter Umständen schneller zu sein. Als einfaches Beispiel dafür dient etwa Divide and Conquerm, denn hier werden größere Probleme in kleiner aufgeteilt und dann dadurch unter Umständen einfacher zu lösen ( weil wir uns nur noch kleine Probleme anschauen!)

Weitere Informationen über dieses Prinzip:

wird meist / primär angewandt, um Probleme zu optimieren bzw zu vereinfachen!
Probleme werden dabei so gelöst, dass man ein großes Problem in viele kleine subprobleme aufteilt, diese löst und anschließend die Lösung aus allen zusammenschließt
Each subproblem is solved just once and the answer is getting saved somewhere - table or similiar. _This avoids the work of recomputing_the answer every time we need to solve this subproblem.

Example for that might be the idea of divide and conquer because:

each subproblem of it is solved at most once!
subsproblems are much smaller than their large top-problems

[!Important] Difference dynamic programming and Divide Conquer the formal definition argues that Divide and conquer can be a a subtype of dynamic programming

Further we can say that instead of always splitting the problem into equal smaller problems, we sometimes just use partial splitting in dynamic programming.

[!Definition] Wie können wir ein größeres Problem schnell lösen? #card Durch das Aufteilen des Problems in viele kleine wird es uns ermöglicht, diese kleinen Teilprobleme u.U. schneller lösen und somit schneller zu einer Lösung zu kommen.

Wir können jedes dieser einzelnen Teilprobleme versuchen in kleinere Teilprobleme aufteilen zu können. Dabei kombinieren wir dann immer die ergebenen Lösungen und spoichern die beste Option dieser. Wir werden dann die gespeicherte (beste Lösung!) verwenden, um weitere Teilprobleme gleicher Art nicht nochmal berechnen zu müssen -> können also die Lösung übernehmen! ^1706623471495

Cutting Stick into pieces to maximize cost

Wir betrachten folgend ein Problem, welches sich damit beschäftigt eine Stange so zu zerschneiden, dass dabei der höchste Erlös generiert wird. Wir wollen also die beste Kombination von Aufteilungen unseres Problemes finden, um den höchsten Umsatz zu erhalten. Problembeschreibung: Betrachte folgend, dass wir eine Stange der Länge $n$ zerschneiden möchten. Weiter ist der Preis für ein Stück der Länge $i$ mit $p_{i}$ angegeben. Wie könnte ein Vorgehen von uns sein? #card

Wir könnten die Stange nicht zerschneiden, und somit einen Erlös von $p_{n}$ erhalten.
Alternativ könnten wir auch Stück von Länge $x = {1, 2, 3, \dots n - 1}$ zerschneiden und dann den Erlös entsprechend mit $p_{x} + r_{n - 1}$ , also der Umsatz wird um eins verringert, während unser Erlös eines Stücks zu nehmen wird. Folgend also: 1 Stück von Länge 1: Erlös $p_{1} + r_{n - 1}$ 1 Stück von Länge 2: Erlös hierbei dann: $p_{2} + r_{n - 2}$ Es gilt jetzt das Maximum all dieser Betrachtungen zu finden! ^1706623471504

Subprobleme erstellen | Berechnen des Optimums

Am obigen Beispiel der zu zerschneidenden Stange haben wir gesehen, dass wir im Endeffekt alle möglichen Teillösungen durchgehen und aus dieser dann eine beste finden müssen.

[!Definition] Wie können wir diesen Sachverhalt mathematisch beschreiben? #card Wir suchen das Maxima aus den Teilproblemen, ferner also: $Opt (n) = ma x_{k} {p_{k} ∣ Opt (n - k)}$ Wir berechnen also alle möglichen Optionen, wie $Opt (2), Opt (2), Opt (n - 1)$ Anschließend sollten wir nach dieser Fraktionierung in kleine Probleme jetzt auch einfach $Opt (n)$ berechnen können! Am Beispiel des optimalen zerschneidens einer Stange für maximalen Gewinn, sieht es dann etwa folgend aus:
Schnitt(n):
  if(n = 0) 
  	return 0 # we cant cut it with length of 0
  q = min_infinity
  for (i = 1 to n)
  	q = max{ q, p[i]+Schnitt(n-1)  }
  return q # which will be the maximum we found among all the options provided 
Aus dieser Betrachtung heraus können wir dann erkennen, wie Laufzeit sein wird: $T (0) = 1$ und für n dann: $T (n) = 1 + j = 1 \sum n - 1 T (j)$ # also wir kombinieren die Laufzeit eines jeden Teilproblemes und fügen diese dann zusammen ! Umgeformt folgend dann: $T (n) = 1 + j = 1 \sum n - 1 T (j) = 1 + (2^{n} - 1) = 2^{n}$ also nicht soo gut

Wir möchten einen weiteren Versuch zur Berechnung des selben Problemes betrachten: ^1706623471508

[!Important] Berechnen des optimalen Schnitts mittels Bottom-Up Wir werden ähnlich vorgehen, jedoch diesmal bottom up also von klein nach groß !
Schnitt(n): 
  r[0] = 0 
  for j = 1 to n 
  	q = - infinity 
  	for i 1 to j # also wir bewegen uns immer von 1 bis zur derzeitigen Boundary durch j
  		q = max{ q, p[i] + r[j-i]  } # wir betrachten also das maxima von q und der neuen Berechnung aus dem Erlös bei [i], sowie DIfferenz aus einer vorherigen Lösung, welche wir aus [j-i] herausfinden
  	r[j] = q # wir setzen für den gegebene Index jetzt also das Maxima!
  return r[n], da sich hier am Ende das Maxima befinden muss!
Wir können aus dieser Betrachtung schon sehen, ,dass wir in der inneren Iteration nur eine kleine Boundary betrachten und nicht alles von 1 to n

Es ergibt sich folgende Laufzeit für diese Operation: $T (n) = j = 1 \sum n j = \frac{n ( n + 1 )}{2} = O (n^{2})$ Was schonmal besser als zuvor ist! Einfach, weil wir uns weniger Elemente pro Iteration anschauen, um ein Maxima zu finden.

Konstruktion der optimalen Lösung

Wir möchten jetzt nochmals betrachten, wie aus den vielen kleinen Teillösungen, die Lösung für das gesamte / große Problem geschaffen werden kann.

[!Definition] Rekonstruktion einer optimalen Lösung | Betrachtung des Schnitt-Problems #card Unter Betrachtung, dass wir hier viele kleine Lösungen zum zerschneiden einer Stange gefunden haben, möchten wir die optimale Lösung nochmal rekonstruieren / ihre Findung betrachten Durch das Speichern den optimalen Schnitt für das Teilproblem einer Stange der länge $j$ , können wir schon eine erste Annäherung finden. Das passiert indem wir jetzt $q = ma x {q, p [i] + r [j - i]}$ folgend ersetzen:
if ( q < p[i] + r[j-i]) 
	q = p[i] + r[j-i]
	s[j] = i 
Wobei hier $s [j] = i$ den ersten Schnitt im Teilproblem der Länge $j$ mit einer Länge von $i$ ist!. Also für Länge $j$ ist ein Schnitt an Stelle $i$ am besten! Wir erhalten anschließend eine Ausgabe von:
while ( n > 0) 
  print s[n]
  n = n- s[n]  			
Also wir geben jeweils die Stelle des Schnittes aus und verringern dann die Größe der Stange, bis wir bei 0 angekommen sind! ^1706623471513

Beispiel | Matrixmultiplikation optimieren

Wir möchten folgend eine Optimierung der Matrixmultiplikation von $A \cdot B, A \in M_{n, m}, B \in M_{m, n}$ anschauen.

Auch hier bieten sich wieder verschiedene Ansätz an, das ganze zu berechnen.

[!Important] Greedy-Ansatz zur Berechnung Wir können sehr naiv und greedy eine erste Lösung dafür finden, brauchen aber drei nested For-loops, also werden wir sehr sehr langsam sein! Betrachten wir dafür folgenden PseudoCode zur Berechnung dieser MatrixMultiplikation
C = empty Matrix of size (A.col, B.row)
for ( Arow = 1 to A.row)
  for ( Bcol = 1 to B.col )
  	c(Arow,Bcol) = 0
  	for k = 1 to A.col
  		# iterating over available entries 
  		c(Arow,Bcol) = c(Arow,Bcol) + a(Arow,k)*b(k,Bcol)
  	end for 
  end for 
end for 
Die starker Vernestung der Schleifen gibt uns folgende eine Laufzeit von: $O (A . ro w \cdot B . co l \cdot A . co l)$

Betrachten wir diese Komplexität für die einfache Multiplikation, dann wird es sehr wichtig, für folgende Aufgabe eine bessere Berechnung finden zu können: Berechnen wir jetzt $A_{1} \cdot A_{2} \cdot A_{3} \cdot \dots \cdot A_{n}$ –> Dafür möchten wir eine optimale Klammerung finden, also das Problem so aufteilen ,dass wir es hoffentlich schneller berechnen können!

Idee zur Lösung: Wir können die Berechnung in kleine Matrixmultiplikationen aufteilen und so folgend immer in zweier-paaren berechnen: $(A_{i} \dots A_{k}) \cdot (A_{k + 1} \dots A_{j})$ , Also folgend $\forall i \leq k \leq j$ berechnen wir jetzt $A_{j} \dots A_{k}$ und den fortfolgenden $A_{k + 1} \dots A_{j}$ . Diese beiden Terme können wir dann multiplizieren und dann über $k$ minimieren!

–> Es muss hier bei beiden Teilproblemen die Klammerung optimal sein!

[!Tip] Zusammengefasster Plan zur besseren Berechnung Wir möchten also folgend vorgehen: Berechne minimale Kosten für $A_{i} \dots A_{j}$ $\forall1 \leq i \leq j \leq n$ Anschließend wird $min [i, j]$ das Minimum aller Multiplikationen für die einzelnen Matrizen $A_{i}, A_{2} \dots A_{j}$ sein Wir wollen anschließend noch $min [1, n]$ bestimmen!

[!Warning] Matrix $A_{i}$ hat jetzt die Dimension $p_{i - 1} \cdot p_{i}$

Betrachten wir jetzt die rekursive Berechnung: Hier wird $min [i, j] = mi n_{k} {min [i, k] + min [k + 1, j] + p_{i - 1} \cdot p_{k} \cdot p_{j}}$ sein, also das minimum, was wir schon kennen oder das neu berechnete minimum Weiterhin gilt: $min [i, j] = 0, i = j$

Wir möchten weiterhin noch $s [i, j] = k$ speichern, wobei $k$ das Minimum bestimmt

Aus dieser Betrachtung können wir jetzt eine 3-Fache-For-Schleife konstruieren

n = |Matrizen | -1 

for ( i = 1 to n) 
	min[i,i] = 0

for ( Index = 2 to n)
	for i = 1 to n-Index + 1
		J = i + Index -1
		min[i,j] = infinity
		for  k = i to j+1 
			q = min[i,k] + min[k+1,j] + p_i-1 * p_k *p_j
			if q < min[i,j] 
				min[i,j] = q 
				s[i,j] = k
		emd for
	end for 
end for

und damit haben wir jetzt eine entsprechende Berechnung gefunden. Ihre Laufzeit beläuft sich auf $O (n^{3})$ , also ist richtig scheiße xd

Example | Edit Distances

[!Definition] Edit Distance what do we mean with those? #card We would like to define distances between strings x and y The given distance will define the steps to convert String X into String y by either :

deleting a letter

inserting a letter

replacing a letter by another The Edit Distance between two strings will be the minimal number of elementary operations that are required to transform x to y.

Use cases of edit distances are things like:

spell checks, and suggestions,

similiarity between genes,

in machine learning - similiar principle to compute distances between various structured objects >> graphs or such ^1706623471518

Computing the Edit Distances

Consider we are given two string $x, y$ $x [1, \dots, m]$ and $y [1, \dots, n]$ With $E (i, j)$ we denote the problem of computing the edit distance between both prefixes of $x [1, \dots, i], y [1, \dots j]$ >> fractions of the actual word, we are computing it step by step. -> We will divide into three different separations that we can look after $E (i - 1, j - 1), E (i - 1, j), E (i, j - 1)$ >> they all have one letter less, at different positions. Why this is possible, maybe be obvious with observing their three possible alignments:

$x [1, \dots, i - 1]$ is aligned to $y [1, \dots, j]$ That is the last letter $x [i]$ is matched to “-” > no letter In that case $E (i, j) = E (i - 1, j) + 1$
Case 2: $x [1, \dots, i]$ is aligned to $y [1, \dots, j - 1]$ Then $E (i, j (= E (i, j - 1) +!$
$x [1, \dots, i - 1]$ is aligned to $y [1, \dots, j - 1]$ THen $E (i, j) = E (i - 1, j - 1) + 1_{x [i] \neq = y [y]}$

As visual representation: ![[Pasted image 20230113110223.png]]

given diagram denotes all given cases. With these three cases we have the possibility to find the smallest distance by simply checking for these conditions at each given round.

$E (i, j) = min {E (i - 1, j) + 1, E (i, j - 1) + 1, E (i - 1, j - 1) + 1 +_{x [i] \neq = y [k]}}$

The resulting pseudo-code would be:


for i = 0, 1, 2, . . . , m:  
	E(i, 0) = i  
for j = 1, 2, . . . , n:  
	E(0, j) = j  
for i = 1, 2, . . . , m:  
	for j = 1, 2, . . . , n:  
		E(i, j) = min{E(i − 1, j) + 1, E(i, j − 1) + 1, E(i − 1, j − 1) + diff(i, j)}  
return E(m, n)

Running Time

overall the running time is $O (m * n)$

we simply fill all the entries of the m x n table of problems E(i,j)
Each entry can be computed using preious entries in constant time.

Knapsack-Problem, but dynamic programmed

Review the Knapsack-problem from here [[111.39_greedyAlgorithm#Knapsack Problem]]

Idea for dynamic programming:

Define the problem K(V,j) the maximum value we can pack in a knapsack of volume V if can we just use items 1,…,j
Further we are looking for $K (v o l_{t o t a l}, n)$
we require two dynamics

For finding the best solution we observe two distinct cases:

Case1 we dont use a given item j. Then we can compute : $K (V, j) = K (V, j - 1)$ >> we dont do anything
Case2 we use item j. -> Then we first pack j in the knapsack, and have to figure out which of the remaining items 1,…j-1 >> all but the one we took, will fit in the remaining volume.

$K (V, j) = K (V - v o l_{j}, j - 1) + v a l_{j}$ >> we once assume the weight of our backpack without the new item and with the new item. and continue calculating from there. We thus can result with the given equation of: $K (V, j) = ma x {(K (V_{v} o l_{j}, j - 1) + v a l_{j})_{c a se 2}, (K (V, j - 1))_{c a se 1}}$

Dynamic in the total weight :: ^1706623471522 We also want to be dynamic in the total weight: -> starting with total volume of 1, we increase the volume by 1 until we reach our set maximum.

So now that means we have to fill a _table of n x [ $v o l_{t o t a l}$ ] subproblems.

# Assumption: all vali and voli and voltotal are integers!  
for all (j = 1, ..., n), Initialize K (0, j) = 0, end for  
for all (v = 1, ..., voltotal ), Initialize K (v , 0) = 0, end for  
for j = 1, ..., n  
	for v = 1, ..., voltotal  
		if volj > v  
			K (v , j) = K (v , j − 1)  
		else  
			K (v , j) = max{K (v , j − 1), K (v − volj , j − 1) + valj }  

Return K (vtotal , n)

Whenever we set up dynamic programming we need to ensure that we have already solved the previous subproblems $K (v, j - 1)$ and $K (v - v o l_{j}, j - 1)$ when we need them. So the order of the loops can be critical.

In our knapsack case the whole system would not work if we have the loop of the volume and then the loop with the items

[!Definition] Running Time for Knapsack-Problem $O (n * v_{t o t a l})$ Attention: Denote that we do not make any assumptions on $v_{[} t o t a l]$ It might just be a fixed constant, than the complexity would boil down to $O (n)$ Or it could be exponentially large with n, so the running time woulld be exponential in n as well.

we could also achieve a running time of $O (n * V)$ where V is the sum of the values of all objects.

scattered-lenity