Greedy Algorithmen

Question 1

Wie funktionieren Greedy Algorithmen?

Answer 1

• Fallen unter die selbe Kategorie wie Probleme der dynamischen Programmierung
• In jedem Schritt wird die lokale beste Entscheidung getroffen um ein globales Problem zu lösen
• Dabei wird nicht auf die Konsequenzen “in der Zukunft” rücksicht genommen

Question 2

Wie sind die 4 Schritte in einem Greedy Algorithmus?

Answer 2

• Greedy Algorithmen bestehen aus 4 Schritten
  1. Initialisierung: Setzen Sie den Anfangszustand des Problems.
  2. Auswählen: Wählen Sie die beste verfügbare Option aus.
  3. Anwenden: Führen Sie die ausgewählte Option aus und aktualisieren Sie den Zustand des Problems.
  4. Überprüfen: Überprüfen Sie, ob das Ziel erreicht wurde. Wenn ja, beenden Sie den Algorithmus. Andernfalls gehen Sie zu Schritt 2 zurück.

Question 3

Wann sollte man Greedy-Algorithmen als Lösung eines Problems nutzen?

Answer 3

• Greedy-Algorithmen sind besonders nützlich, wenn das Problem in Teilprobleme unterteilt werden kann
• Diese müssen unabhängig voneinander lösbar sein
• Dann kann ein Greedy-Algorithmus schnell eine Lösung finden
• Eine Garantie für die optimale Lösung bei Greedy-Algorithmus ist nicht gegeben

Question 4

Was ist ein minimaler Spannbaum (MST)?

Answer 4

• Ein Teilgraph eines ungerichteten, gewichteten Graphen
• Dieser verbindet alle Knoten auf die effizienteste Weise

Question 5

Wie funktioniert Prim’s Algorithmus?

Answer 5

1. Wähle einen beliebigen Knoten aus dem Graphen und füge ihn zum minimalen Spannbaum hinzu.
2. Finde die Kante mit dem geringsten Gewicht, die einen Knoten im minimalen Spannbaum mit einem Knoten außerhalb des Spannbaums verbindet.
3. Füge den Knoten, der an der anderen Seite der Kante liegt, zum minimalen Spannbaum hinzu und füge die Kante selbst hinzu.
4. Wiederhole Schritt 2 und 3, bis alle Knoten des Graphen im minimalen Spannbaum enthalten sind.
   * Laufzeit: Abhängig der Datenstruktur, aber meist O(E log V), wobei E die Anzahl der Kanten und V die Anzahl der Knoten im Graphen ist.

Question 6

Wie funktioniert Kruskal’s Algorithmus?

Answer 6

1. Speichere alle Kanten ab und sortiere sie aufsteigend
2. Markiere alle Kanten nacheinander, wenn sie keinen Kreis bilden
   * Laufzeit:Abhängig der Datenstruktur, aber meist O(E log E), wobei E die Anzahl der Kanten im Graphen ist.

Question 7

Wie funktioniert Dijkstra’s Algorithmus?

Answer 7

1. Setze den Abstandswert des Startknotens auf 0 und alle anderen Abstandswerte auf unendlich.
2. Füge den Startknoten in eine Prioritätswarteschlange ein.
3. Solange die Prioritätswarteschlange nicht leer ist, nimm den Knoten mit dem kleinsten Abstandswert aus der Warteschlange.
4. Für jeden benachbarten Knoten des aktuellen Knotens aktualisiere den Abstandswert, wenn der Pfad über den aktuellen Knoten zum benachbarten Knoten kürzer ist als der bisher bekannte Pfad.
5. Füge den benachbarten Knoten mit dem aktualisierten Abstandswert in die Prioritätswarteschlange ein.
6. Wiederhole Schritt 3 bis 5, bis alle Knoten besucht wurden.
   * Laufzeit: Abhängig der Datenstruktur, aber meist O((E+V)logV), wobei E die Anzahl der Kanten und V die Anzahl der Knoten im Graphen ist