Effiziente kombinatorische Algorithmen - Cheatsheet

Breitensuche (BFS) und Tiefensuche (DFS)

Definition:

Breitensuche (BFS) und Tiefensuche (DFS) sind Graphdurchsuchungsalgorithmen, um bestimmte Knoten oder Pfade zu finden.

Details:

• BFS: Nutzt eine Warteschlange (Queue), um Knoten schichtweise zu durchsuchen.
• DFS: Nutzt einen Stapel (Stack), entweder explizit oder durch Rekursion, um in die Tiefe zu gehen.
• Komplexität beider Algorithmen: O(V + E), wobei V die Anzahl der Knoten und E die Anzahl der Kanten ist.
• BFS: Gut geeignet, um kürzeste Wege in ungewichteten Graphen zu finden.
• DFS: Kann für Topologische Sortierung und zum Finden von Zusammenhangskomponenten verwendet werden.

Kürzeste Wege: Dijkstra, Bellman-Ford, und A*

Definition:

Algorithmen zur Berechnung der kürzesten Wege in Graphen - Fokus auf Dijkstra, Bellman-Ford und A*

Details:

• Dijkstra: Effizient für Graphen mit nicht-negativen Kantengewichten. Zeitkomplexität: \( O((V + E) \log V) \) mit Fibonacci-Heaps.
• Bellman-Ford: Funktioniert mit negativen Gewichten, erkennt negative Zyklen. Zeitkomplexität: \( O(VE) \).
• A*: Heuristischer Algorithmus; effizienter durch Verwendung einer Abschätzungsfunktion (Heuristik), die die Schätzung der Kosten vom aktuellen Knoten zum Zielknoten beinhaltet.

Minimaler Spannbaum: Kruskal und Prim

Definition:

Kruskal und Prim sind Algorithmen zur Berechnung des minimalen Spannbaums (MST) eines zusammenhängenden, ungerichteten Graphen mit gewichteten Kanten.

Details:

• Kruskal's Algorithmus: Sortiere alle Kanten nach Gewicht und füge sie schrittweise hinzu, vermeide Zyklen.
• Prim's Algorithmus: Starte bei einem Knoten und füge iterativ die billigsten Kanten hinzu, die einen neuen Knoten verbinden.
• Komplexität: Kruskal O(|E| log |E|), Prim O(|E| + |V| log |V|)
• \textbf{Kruskal Formalisierung}:
• Sortiere Kanten nach Gewicht
• Verwende Union-Find zur Zyklenvermeidung
• \textbf{Prim Formalisierung}:
• Verwende Prioritätswarteschlange für Kanten
• Füge den minimalen Randknoten zum MST hinzu

Dynamische Programmierung: Grundprinzipien und Memoization

Definition:

Effiziente Problemlösung durch Zerlegung in überlappende Teilprobleme und Speicherung ihrer Ergebnisse zur Vermeidung mehrfacher Berechnungen.

Details:

• Zerlege komplexes Problem in einfachere Teilprobleme.
• Speichere Ergebnisse der Teilprobleme (Memoization).
• Vermeide rekursive Berechnungen für bereits bekannte Lösungen.
• Tabellenbasierte Bottom-up-Ansatz oft effizienter als Top-down.
• Anwendungsbeispiele: Fibonacci-Folge, Kürzeste-Wege-Problem, Rucksackproblem.
• Rekursive Formeln:
  • Fibonacci: \( F(n) = F(n-1) + F(n-2) \)
  • Kürzeste-Wege (Bellman-Ford): \( d[v] = \text{min}(d[v], d[u] + w(u,v)) \)

Ford-Fulkerson-Algorithmus und Edmonds-Karp-Implementierung

Definition:

Ford-Fulkerson-Algorithmus zur Berechnung des maximalen Flusses in Flussnetzwerken, Edmonds-Karp als spezialisierte Implementierung mit Breitensuche (BFS)

Details:

• Nutze Residualgraphen und augmentierende Pfade
• Ford-Fulkerson: Generisches Gerüst, Verbesserung des Flusses iterativ
• Edmonds-Karp: BFS zur Pfadfindung, garantiert polynomielle Laufzeit
• Laufzeit: Ford-Fulkerson im schlechtesten Fall exponentiell, Edmonds-Karp \[O(V E^2)\]
• Kapazitäten: \[f(u, v) \leq c(u, v)\]
• Nettoflusskonservierung: \[\sum_{(u,v) \in E} f(u,v) = 0\]
• Schrittweise: Fluss erhöhen entlang des gefundenen augumentierenden Pfades, Rückflüsse erlauben

Max-Flow Min-Cut Theorem

Definition:

Max-Flow Min-Cut Theorem: Das maximale Flusswert in einem Flussnetzwerk ist gleich der minimalen Schnittkapazität.

Details:

• Flussnetzwerk: Gerichteter Graph mit Quelle (s) und Senke (t).
• Kapazität (c): Maximale Flussmenge durch eine Kante.
• Fluss (f): Tatsächlicher Fluss durch eine Kante, mit Einschränkungen: \(0 \leq f \leq c\).
• Maximaler Fluss: \(\sum_{(s,v) \in E} f(s,v) - \sum_{(v,t) \in E} f(v,t)\).
• Schnitt: Aufteilung der Knotenmenge in zwei disjunkte Mengen, wobei die Quelle und die Senke getrennt sind.
• Schnittkapazität: Summe der Kapazitäten der Kanten, die von der Menge der Quelle zur Menge der Senke führen.
• Theorem: \( \text{Max-Flow} = \text{Min-Cut} \).

Greedy-Algorithmen und deren Anwendung im TSP

Definition:

Greedy-Algorithmen wählen iterativ die lokal beste Option mit der Hoffnung, eine globale Lösung zu finden. Im TSP werden Städte sukzessiv nach minimaler Distanz besucht.

Details:

• Greedy-Algorithmen: Jede Entscheidung basiert auf dem lokalen Optimum in jedem Schritt.
• TSP (Traveling Salesman Problem): Finde den kürzesten Rundweg durch alle Städte.
• Verfahren: Beginne bei einer Startstadt, wähle immer die nächstgelegene unbesuchte Stadt.
• Vorteile: Einfach zu implementieren und schnell.
• Nachteile: Keine Garantie für globale Optimalität, oft nur eine Näherungslösung.
• Anwendung: Nearest-Neighbor-Heuristik ist ein Beispiel.

NP-Vollständigkeit und Reduktionen

Definition:

NP-Vollständigkeit beschreibt Probleme, für die es keine bekannten polynomialen Algorithmen gibt, die aber verifiziert werden können, wenn eine Lösung bekannt ist. Reduktionen transformieren ein Problem effizient in ein anderes, oft zum Nachweis der NP-Vollständigkeit.

Details:

• Ein Problem in NP: wenn Lösung in polynomieller Zeit geprüft werden kann
• NP-vollständig: Problem ist in NP und jedes Problem in NP kann in polynomieller Zeit darauf reduziert werden
• Karp-Reduktion: Transformation von Problem A zu Problem B in polynomieller Zeit
• Cook-Levin-Theorem: SAT ist NP-vollständig