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

Greedy Algorithms

anchored to [[111.00_anchor]] contrary to [[111.38_DynamicProgamming]]

High level explanation

[!Definition] Erklärung für Greedy Algorithmen wie ist ihr vorgehen, beispiel? #card Greedy algorithms typically apply to optimization problems in which we make a set of choices in order to arrive at an optimal solution. Also werden sie, wie [[111.38_DynamicProgamming]] für Optimierungen angewandt. Weiterhin agieren sie nach dem Prinzip des lokalen Optima, was heißt –> We make one choice at a time and work from there - backtracking as example –> A greedy algorithms always makes the choice that looks best at the moment, also wir können somit nicht immer von einer globalen besten Lösung ausgehen, weil wir hier nur die lokale beste betrachten

That is, it makes a locally optimal choice in the hope that this choice will lead to a globally optimal solution. In most cases the greedy strategy does not lead to a global solution, but to a local optimum only. But there also exist examples where the greedy solution is always globally optimal. ^1706623464193

Wir können diese unterschiedlichen Herangehensweisen mit einem einfachen Beispiel zeigen: Betrachten wir $n$ Jobs $= {a_{1}, \dots a_{n}}$ , welche eine Starzeit von $s_{j}$ haben. Weiterhin enden sie nach $e_{i}$ . Wir nennen zwei Jobs kompatibel, wenn sich ihre Intervalle nicht überlappen. wie lösen wir das jetzt greedy und dynamisch? #card Als Greedy-Algorithmus betrachten wir konstant ein lokales Optima und haben somit nicht zwingend eine Sicht auf die globalen Zustände. Daraus folgt, dass wir eine beste Lösung finden, unter Umständen aber auch eine bessere existiert. –> Denn wir prüfen nicht alle Kombinationen der Jobs Für dynamic programming: Werden wir viele kleine Teilprobleme lösen ( somit am Ende alle Kombinationen probiert haben) und anschließend die beste globale lösen ^1706623464197

Als kurzer Exkurs: Wir könnten das ganze durch dynamische Programmierung folgend angehen: Seien jetzt $S_{ij}$ die Jobs, die starten, nachdem ein Job $a_{j}$ endet und welche auch enden, bevor $a_{j}$ beginnt –> also quasi Jobs, die innerhalb dieses Zeitfensters liegen Wir suchen dann die maximale Anzahl von kompatiblen Jobs auf $S_{ij}$ . Sei dafür $A_{ij}$ eine Menge mit solchen Inhalten und weiterhin $a_{k} \in A_{ij}$
Wenn jetzt $a_{j}$ eine optimale Teillößung ist, ergeben sich daraus dann zwei neue Teilprobleme: $S_{ik}, S_{kj}$ wobei hier also eine Aufspaltung auftritt: $A_{ik} = A_{ij} \cap S_{ik}, A_{kj} = A_{ij} \cap S_{kj}$ und weiterhin auch $A_{ij} = A_{ik} \cup {a_{k}} \cup A_{kj}$ –> also die Menge bildet sich aus der Aufteilung wieder! Wir können dann die optimale Menge $A_{ij}$ bestimmen, indem wir sie aus $a_{k}$ und den ergebenden Optima für die Subprobleme bilden! Sei dann jetzt $min [i, j]$ die optimale Anzahl von Jobs für $S_{ij}$ . Es folgt jetzt:

$min [i, j] = 0 ⟹ S_{ij} = \emptyset$
$min [i, j] = ma x_{ak \in S_{ij}} {min [, ik] + min [k, j] + 1}$

Und als Lösung mit Greedy-Algorithmus: Wähle den Job als ersten, der als erstes enden wird. Also etwa $a_{1}$ , dann lassen wir alle Jobs weg, die damit im Konflikt stehen würden und arbeiten uns so Schritt für Schritt zu einer Lösung, indem wir immer mehr herauslassen / nicht mehr betrachten werden

Prinzip für Greedy-Algorithmen

Wir möchten ferner die notwendigen Prinzipien zur Bestimmung und Nutzung von Greedy-Algorithmen betrachten: welche wären das? wie lösen wir die Probleme dann? #card

[!Definition] Prinzipien der Greedy-Algorithmen Wir versuchen eine Teilstruktur zu schaffen ( also vielleicht wie beim backtraking!) Wir lösen jetzt rekursiv das Problem ( dafür versuchen wir das immer nur auf ein Teilproblem zu betrachten) Sobald wir das berechnet haben, wird sich ein Optimum gefunden haben Sobald das passiert ist ( rekursiv) können wir die Lösung zusammenfassen, was wieder iterativ passiert ^1706623464200

Knapsack Problem |

[!Definition] Beschreibung des Rucksackproblems was für einen Grundzustand haben wir, was möchten wir jetzt erreichen? #card Wir haben hier $n$ Gegenstände ${g_{1}, \dots, g_{n}}$ mit einem Wert $v_{i}$ und weiterhin auch einem Gewicht $w_{i}$ füý $1 \leq i \leq n$ Wir wissen hier, dass unsere Person nur $\leq W$ Kilo tragen kann Wir möchten ein Maxima des Wertes erhalten.

We have n objects, each of which has a certain value value i and volume i. The backpack can only fit a total volume of vol_total. We want to put as much value as possible in the backpack. We want to maximize the amount of things that we can take with us, while also maximizing the value.

Another Description for it: Given values val_1, … val_n volumes vol_1, … vol_n and vol_total. We want to find a subset of all items, such that the volume is smaller than vol_total but the value is as large as possible >> $s = 1 \sum k (v a l_{i})$ One can prove that this problem is NP hard! : [[111.99_algo_ProblemComplexity#Complexity class NP ::|NP problems]] ^1706623464203 ^1706623464207

Wir könnten das Problem in dynamischer Programmierung anschauen: Wir nehmen die wertvollste Menge und werden dann für den Rest die wertvollste Ladung sammeln. Danach werden wir entsprechend maximieren ![[111.38_DynamicProgamming#Knapsack-Problem, but dynamic programmed]]

Wir können es aber auch noch Greddy anschauen:

[!Definition] Ansatz zur Lösung durch Greedy-Verfahren wie möchten wir jetzt Greedy vorgehen? #card

Take the most valuable object that has volume smaller than vol_total and put it in the bag.

Among the remaining objects, we select the remaining one that suits our system the best. the most valuable one that still fits in the bag under the volume constraint.

we continue until no other object fits in the bag anymore Das heißt also auf high-level Ebene
Ordne Gegenstände nach Wert pro Kilo ( g1, ..., gn):
  i = 1 
  while ( W noch nicht erreicht ( also noch Platz))
  	stecke jetzt g_i oder einen Teil davon in den Rucksack ( also nimm das nächst-beste / wertvollste)
  	erhöhe _i_
Welche Laufzeit werden wir dafür erhalten $O (n)$ ^1706623464211

Problem durch die Greedy-Algorithmus

Problem with that approach it could occur, that an object is the most valuable and heaviest. Now we assume that two lighter elements exist that are more valuable in combination. ![[Pasted image 20230109143254.png]] Our system would result with 60€, although we can achieve 90€ with an alternative matching. –> Alternative example of Knapsack problem <–

New approach

For each item we calculate the value-per-volume ration val_i / vol_i
At each step, we select the item with the largest value-per-volume ratio. yet again it cannot guarantee the correct placement as seen below ![[Pasted image 20230109143440.png]]

Technically we can achieve 220€, yet our system will find 160€ with the given system, because the ratio can be misleading.

However the second approach for solving Knapsack proofs useful for the fractional knapsack problem. We fill up a backpack with a resource that we can partition into smaller fractions - powder of gold for example. We now take the ressource with the best ratio and fill up our backpack until either the reesource is depleted and we take the next one or our backpack is filled.
That way we can always find the correct partition / load for our backpack

Example for finding a MST

–> [[111.26_Graphen_MST]] Both Kruskals and Prims algorithm are greedy algorithms.

That is because they are constantly adding a new node to the MST by choosing the globally shortest solution without breaking the solution - creating a circle for example. So that means its collecting the best solution at any given time without being clever so its trying and thus greedy.

Whats to be observed with those examples

We can conclude that:

A greedy algorithm is often very simple
Sometimes, there exist several plausible greedy strategies that lead to different solutions
A greedy algorithm typically leads to a valid solution in the sense that the solution always satisfies the volume constraint $\sum\limits_{s=1}^{k} vol_{i} \seq vol_{total}$
In each iteration we strictly improve upon the previous solution that is because we are trying to add an item, while also maintaining constraints.

Yet again : We cannot give any general guarantee on the quality of a solution. In special cases, however, we might be able to give guarantees, sometimes.

One particular property of greedy algorithms

the algorithm is not allowed to “trace back” and rever a decision that has been made earlier - choose an alternative object after evaluating with another object In knapsack : it cannot take and object ouf of the bag again.
If the algorithm made a bad decision in the beginning, it can never rever that decision

Of course one could apply further heuristics to allow the algorithm to revert decisions :: ^1706623464215

In each step we are allowed to take one object ouf of the bag and put two new objects inside. Always make the joint selection that leads to the largest improvement.

Strategies for building “good” greedy algorithms

First Step for devising greedy algorithms is always:

Cast the optimizatio problem as one in which we make one choice at each time and are left with a similar, but smaller problem to solve.

Basically dividing the problem further so that we can continue with a smaller portion of it afterwards.

Secondly If you want to achieve that the greedy choice always leads to a globally optimal solution you can try the following:

Prove that there is always an optimal solution to the original problem that makes the greedy choice. This means that the greedy choice is always safe - what we did with MST, guaranteeing that our solution stays correct
Demonstrate optimal substructure“ by showing that, having made the greedy choice, what remains is a subproblem with the property that if we combine an optimal solution to the subproblem with the greedy choice we have made, we arrive at an optimal solution to the original problem.

Alternative Strategy

first try to come up with a more complicated algorithm that correctly solve the problem - for example, by dynamic programming
Then, by analyzing this algorithm, one can sometimes show that in certain places, we can always make a greedy choice and still maintain correctness.
Then one can try to simplify the algorithm considerably using greedy choices in the first place.

An example where this works is interval scheduling problem.

Beispiel | Enumeration

Betrachten wir folgendes Problem: -> systematisches Aufzählen aller Lösungen durch Durchmustern des Lösungsraumes.

Beispiele dafür: Zähle alle Möglichkeiten auf, die eine $9$ durch eine Summe von drei verschiedenen Zahlen darstellen kann.

Wir können es auch durch einen -> Aufzählungsbaum <- darstellen / lösen Setzen wir dafür $x_{i} = 1$ genau dann wenn $i$ genutzt wird.

Visuell betrachtet: ![[Pasted image 20240130002950.png]]

[!Important] Lösung durch einen Aufzählungsbaum Kanten haben hier immer Restriktionen. Weiterhin hat ein jeder Knoten noch weitere Unterbäume, mit allen Kandidaten, die diese Restriktionen auf Pfad Wurzel zu Knoten bestimmen.

Wenn wir jetzt Backtracken, dann bricht man mit Durchforstung eines Unterbaums ab - weil man da sehen kann, dass da noch keine Lösung vorhanden ist / war. Dann gehen wir hoch und suchen da weiter

Alternativ möchten wir noch das Knotenfärben eines Graphen betrachten: Sei hier folgende Grundidee / Struktur:

[!Definition] Knoten eines Graphen färben Färbe Graph $G = (V, E)$ mit $k$ Farben, sodass dann $F (v) \neq = F (w)$ für einen Pfad $(v, w) \in E$ ist –> also jede Verbindung soll nie die gleiche Farbe haben!

[!Example] Betrachtung für einen gegebenen Graphen $G$ Betrachten wir folgenden Graphen, dann möçhten wir durch einen k-baume alle Kombinationen der möglichen Einfärbungen betrachten und einfügen. ![[Pasted image 20240130140938.png]] Hier möchten wir etwa $k = 3$ annehmen und damit versuchen eine entsprechende Färbung erhalten zu können, die unsere Anforderungen löst: Darstellen können wir diese Entscheidung jetzt durch einen Baum: ![[Pasted image 20240130141033.png]] Wir sehen hier, dass es sich um einen k-nären Baum handelt, welcher eine Höhe von $n + 1$ hat ( wobei n die Menge der Knoten entspricht). –> Wir fangen ohne Einfärbung an und dann ist jeder der k-Bäume eine Entscheidungsmöglichkeit unter Anwendung der $k$ Farben! Er hat dabei eine Baumgröße von $O (k^{n})$

Branch and Bound | B&B

see more here

[!Important] Intuition was ist unser Ansatz für B&B? #card Gilt auch als weitere Idee, um Optimisierungsprobleme lösen zu können, indem wir sie in kleinere Subprobleme aufteilen. Weiterhin wird eine Bounding-Funktion eingebracht, welche dazu da ist, Teilprobleme mit unlösbaren Zuständen ausschließen zu können ( und sie nicht zu berechnen!) Wichtig ist die effiziente Berechnung dieses Bounds, weil er uns hilft, schnell andere Lösungen ausschließen zu können.

Wir versuchen hier immer alle Entscheidungen durchzugehen ( etwa in einem Baum), und sobald eine Kondition für maximale/minimale Kosten nicht mehr erfüllt wird - weil wir etwa eine vorherige Lösung gefunden haben, die besser scheint/ist - dann verwerfen wir sie direkt und würden anschließend die nächste Lösung anschauen

^1706623464219

Beispiel | TSP - Travelling Salesman Problem

[!Definition] Definition von TSP was ist gegeben, was wollen wir berechnen? #card Unter Betrachtung des TSP Problemes möchten wir für $n$ Städte, nummeriert ${0, 1, \dots, n - 1}$ , mit bestimmten Kosten $c_{i, j} \in N_{0}$ ( also Verbindung von i nach j) die günstigste Route finden, sodass wir jede Stadt nur einmal besuchen –> wir wollen also in der Betrachtung eine Rundreise durchführen, dabei aber den günstigsten Weg dieser finden / bestimmen lassen. ^1706623464223

[!Question] Wie können wir jetzt für das TSP eine mögliche untere Schranke definieren und finden, die uns dabei helfen kann, eine Lösung für das Städte-Problem zu finden? was benötigen wir dafür? #card Wir können sagen, dass wir eine Untere schranke damit definieren können, dass jede Stadt betreten und verlassen werden muss. Das heißt folgend: $C_{o pt} \geq \frac{1}{2} i = 0 \sum n - 1 min_{j} c_{ji} + min_{k} c_{ik}$ denn aus der Betrachtung folgt: $C_{o pt} \geq i \sum min_{j} c_{ij}, C_{o pt} \geq i \sum min_{k} \cdot c_{ik}$ Also wir wissen, dass die Kosten pro Stadt mindestens der günstigste Weg nach und aus der Stadt ist ( also wie wir am günstigsten rein kommen und wie wir am günstigsten heraus kommen –> das ist ja gefordert, wenn wir jede Stadt min und max 1x besuchen) ^1706623464227

Ansätze zur Lösung: Wenn wir jetzt TSP nativ lösen möchte gehen wir wie vor? #card Prinzipiell möçhten wir einfach alle möglichen Permutationen der Städte in ihrer Abfolge durchprobieren und da das Minimum finden. Also ferner $n! \leq n^{n} = 2^{n l o g n}$ –> was sehr schlecht ist! (( BTW TSP is NP-hard)) ^1706623464230

Wir möchten es noch dynamisch lösen wie wäre da unser Ansatz zur Lösung von TSP? #card Wir möchten in einer Stadt $0$ starten, die beliebig gewählt werden kann ( wir müssen sie ja eh durchlaufen). Anschließend möchten wir jetzt für alle anderen Städte immer das Optimum von der Start-Stadt, durch die eine Stadt $s$ Stadt in eine andere $i \in S$ finden –> also das Optimum einer Verbindung von Stadt $0 \to S \to i$ . Wir können dann daraus folgern, dass $OPT ([i], i) = c_{o, i}, 1 \leq i < n - 1$ ist, also wir ein Optimum von unserer Start-Stadt $0$ nach $i$ finden / gefunden haben. Weiterhin gilt dann für die Berechnung $OPT (S, i)$ , dass $mi n_{k \in S - {i}} (OPT (S - {i}, k) + c_{ki})$ ist, wenn $∣ S ∣> 1$ Wir können jetzt weiter die Kante zum Start zurück folgend bestimmen und finden: $OPT = mi n_{i} OPT (1, \dots, n - 1, i) + c_{i, 0}$ Wir möchten jetzt alle diese Kombinationen ( bester Pfad rein / bester Pfad raus) Speichern, und weil wir dieses Problem für jeden Knoten aufgeteilt betrachten, können wir dann eine Laufzeit von $O (n \cdot 2^{n})$ erhalten. Das kommt daher, dass wir $2^{n}$ solcher Probleme lösen müssen und das jeweils $O ((n))$ benötigen ( also die Suche nach der Besten Route von, durch, nach!) ^1706623464234

scattered-lenity