Effiziente kombinatorische Algorithmen - Exam

Aufgabe 1)

Breitensuche (BFS) und Tiefensuche (DFS)Breitensuche (BFS) und Tiefensuche (DFS) sind Graphdurchsuchungsalgorithmen, um bestimmte Knoten oder Pfade zu finden. 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. Beide Algorithmen haben eine Komplexität von O(V + E), wobei V die Anzahl der Knoten und E die Anzahl der Kanten ist. BFS ist gut geeignet, um kürzeste Wege in ungewichteten Graphen zu finden. DFS kann für Topologische Sortierung und zum Finden von Zusammenhangskomponenten verwendet werden.

a)

Gegeben ist der folgende ungerichtete Graph als Adjazenzliste:

{ 'A': ['B', 'C'], 'B': ['A', 'D', 'E'], 'C': ['A', 'F'], 'D': ['B'], 'E': ['B', 'F'], 'F': ['C', 'E'] }

Erstelle die Reihenfolge der Knoten, die unter folgenden Bedingungen durchlaufen werden:

• Mit BFS beginnend von Knoten 'A'.
• Mit DFS beginnend von Knoten 'A'.

Beschreibe die Unterschiede im Durchlauf der Knoten beider Algorithmen und erkläre, warum diese Unterschiede entstehen.

Lösung:

Lösung des Unteraufgabe:

• BFS beginnend von Knoten 'A':

Wir verwenden eine Warteschlange (Queue), um die Knoten schichtweise zu durchsuchen.

{ 'A': ['B', 'C'], 'B': ['A', 'D', 'E'], 'C': ['A', 'F'], 'D': ['B'], 'E': ['B', 'F'], 'F': ['C', 'E'] }

Algorithmus-Schritte:

1. Initialisierung: Starte bei Knoten 'A' und füge ihn in die Warteschlange ein. Besuchte Knoten: {'A'}
2. Iteration 1: Entferne 'A' aus der Warteschlange und füge seine Nachbarn 'B' und 'C' hinzu. Warteschlange: ['B', 'C']
3. Iteration 2: Entferne 'B' aus der Warteschlange und füge seine unbesuchten Nachbarn 'D' und 'E' hinzu. Warteschlange: ['C', 'D', 'E']
4. Iteration 3: Entferne 'C' aus der Warteschlange und füge seinen unbesuchten Nachbarn 'F' hinzu. Warteschlange: ['D', 'E', 'F']
5. Iteration 4: Entferne 'D' aus der Warteschlange. 'D' hat keine unbesuchten Nachbarn. Warteschlange: ['E', 'F']
6. Iteration 5: Entferne 'E' aus der Warteschlange. 'E' hat keine unbesuchten Nachbarn. Warteschlange: ['F']
7. Iteration 6: Entferne 'F' aus der Warteschlange. 'F' hat keine unbesuchten Nachbarn. Warteschlange: []

Reihenfolge der Knoten mit BFS: A, B, C, D, E, F

• DFS beginnend von Knoten 'A':

Wir verwenden einen Stapel (Stack) oder Rekursion, um in die Tiefe zu gehen.

{ 'A': ['B', 'C'], 'B': ['A', 'D', 'E'], 'C': ['A', 'F'], 'D': ['B'], 'E': ['B', 'F'], 'F': ['C', 'E'] }

Algorithmus-Schritte:

1. Initialisierung: Starte bei Knoten 'A'. Besuchte Knoten: {'A'}
2. Iteration 1: Gehe zu 'B'. Besuchte Knoten: {'A', 'B'}
3. Iteration 2: Gehe zu 'D'. Besuchte Knoten: {'A', 'B', 'D'}
4. Iteration 3: 'D' hat keine unbesuchten Nachbarn. Gehe zurück zu 'B' und dann zu 'E'. Besuchte Knoten: {'A', 'B', 'D', 'E'}
5. Iteration 4: Gehe zu 'F'. Besuchte Knoten: {'A', 'B', 'D', 'E', 'F'}
6. Iteration 5: 'F' hat keine unbesuchten Nachbarn. Gehe zurück zu 'E', 'B', und schließlich zu 'C'. Besuchte Knoten: {'A', 'B', 'D', 'E', 'F', 'C'}

Reihenfolge der Knoten mit DFS: A, B, D, E, F, C

• Unterschiede im Durchlauf der Knoten und Gründe:

Die Unterschiede entstehen durch den verschiedenen Umgang mit Knoten-Erkundungen beider Algorithmen:

• BFS: Durchläuft Knoten schichtweise von der Startposition aus und fügt alle Nachbarn der aktuellen Ebene der Warteschlange hinzu. Dies führt zu einer breiteren, ebenenbasierten Abdeckung des Graphen.
• DFS: Geht so tief wie möglich von der Startposition aus, bevor es zurückverfolgt und andere Pfade untersucht. Dies führt zu einer tieferen, pfadbasierten Abdeckung des Graphen.

b)

Betrachte eine ungerichtete Graph G mit V Knoten und E Kanten.

Beweise, dass beide BFS und DFS in einem verbundenen Graphen G mit V Knoten und E Kanten eine Zeitkomplexität von O(V + E) haben.

Verwende dabei die Definitionen der Datenstrukturen und analysiere die Durchführung der Algorithmen. Achte darauf, sowohl die Initialisierung als auch die Iterationsprozesse detailliert zu erläutern.

Lösung:

Beweis der Zeitkomplexität von BFS und DFS:

Zunächst betrachten wir die verwendeten Datenstrukturen und dann analysieren wir die Durchführung beider Algorithmen im Detail.

• BFS (Breitensuche)

In BFS verwenden wir eine Warteschlange (Queue), um Knoten schichtweise zu durchsuchen.

Initialisierung:

• Wir fügen den Startknoten in die Warteschlange ein (O(1)).
• Wir markieren den Startknoten als besucht, was O(1) Speicher und Zeit benötigt.

Iteration:

• Für jeden Knoten, der aus der Warteschlange entfernt wird, durchlaufen wir alle seine Nachbarn.
• Wenn ein Nachbar noch nicht besucht wurde, fügen wir ihn in die Warteschlange ein und markieren ihn als besucht.
• Jeder Knoten wird nur einmal markiert und besucht.
• Jede Kante wird nur einmal überprüft, ob sie zu einem neuen Knoten führt.

Die Gesamtzeitkomplexität der Iterationsprozesse ergibt sich also aus:

• Jeder Knoten wird genau einmal in die Warteschlange eingefügt und entfernt: dies kostet maximal O(V).
• Jede Kante wird genau zweimal überprüft (einmal für jeden Endknoten der Kante): dies kostet O(E).

Die Gesamtzeitkomplexität für BFS ist daher O(V + E).

• DFS (Tiefensuche)

In DFS verwenden wir einen Stapel (Stack) oder Rekursion, um die Knoten in die Tiefe zu durchsuchen.

Initialisierung:

• Wir starten bei einem Knoten und markieren ihn als besucht (O(1)).

Iteration:

• Für den aktuellen Knoten durchlaufen wir alle seine Nachbarn.
• Wenn ein Nachbar noch nicht besucht wurde, rufen wir die DFS-Funktion rekursiv auf ihn auf oder fügen ihn dem Stapel hinzu.
• Jeder Knoten wird nur einmal markiert und besucht.
• Jede Kante wird nur einmal überprüft, um einen unbesuchten Nachbarn zu finden.

Die Gesamtzeitkomplexität der Iterationsprozesse ergibt sich also aus:

• Jeder Knoten wird genau einmal besucht, was O(V) Operationen erfordert.
• Jede Kante wird genau einmal überprüft, was O(E) Operationen erfordert.

Die Gesamtzeitkomplexität für DFS ist daher O(V + E).

• Zusammenfassung

Beide Algorithmen verwenden effiziente Datenstrukturen, die eine lineare Iteration über die Knoten und die Kanten ermöglichen. Da jeder Knoten und jede Kante nur einmal verarbeitet werden, ergibt sich für beide Algorithmen eine Zeitkomplexität von O(V + E), wobei V die Anzahl der Knoten und E die Anzahl der Kanten im verbundenen Graphen G sind.

Aufgabe 2)

In einem ungerichteten, gewichteten Graphen repräsentieren die Knoten Städte und die Kanten die Straßenverbindungen zwischen ihnen, mit den zugehörigen Distanzen als Gewichtungen. Du bist ein Städteplaner und möchtest die effizientesten Wege zwischen verschiedenen Städten berechnen. Benutze hierfür die Algorithmen Dijkstra, Bellman-Ford und A*, um die kürzesten Wege zu bestimmen und analysiere ihre Effizienz und Eignung in verschiedenen Szenarien.

a)

Angenommen, alle Straßengewichte sind nicht-negativ. Verwende den Dijkstra-Algorithmus, um den kürzesten Weg vom Startknoten A zum Endknoten H zu finden. Gib die vollständige Schritt-für-Schritt-Berechnung inklusive der Aktualisierung der Distanzwerte und Vorgängerknoten an.

Lösung:

Dijkstra-Algorithmus: Schritt-für-Schritt-Anleitung

Angenommen, alle Straßengewichte sind nicht-negativ und Du möchtest den kürzesten Weg vom Startknoten A zum Endknoten H berechnen. Verwende den Dijkstra-Algorithmus und folge der nachstehenden Schritt-für-Schritt-Anleitung zur Berechnung, inklusive der Aktualisierung der Distanzwerte und Vorgängerknoten.

• Schritt 1: Initialisierung
• Setze die Distanz aller Knoten auf ∞, außer für den Startknoten A, der auf 0 gesetzt wird.
• Initialisiere eine leere Menge von besuchten Knoten.
• Speichere die Vorgängerknoten, um den endgültigen Pfad rekonstruieren zu können.
• Schritt 2: Ausführung
• Wähle den Knoten mit der kleinsten aktuellen Distanz, der noch nicht besucht wurde. Dies ist der aktuelle Knoten.
• Aktualisiere die Distanzen zu den Nachbarn dieses Knotens.
• Aktualisiere gegebenenfalls die Vorgängerknoten.
• Markiere den aktuellen Knoten als besucht.
• Wiederhole den Vorgang, bis das Endziel (Knoten H) erreicht ist oder alle erreichbaren Knoten besucht wurden.
• Schritt 3: Ergebnis
• Der kürzeste Pfad und die Distanzen können nun durch die Vorgängerknoten verfolgt werden.

Beispielgraph

Angenommen, der Graph sieht wie folgt aus:

 A - B: 4 A - C: 2 B - C: 5 B - D: 10 C - E: 3 D - F: 11 E - D: 4 E - F: 2 F - H: 1 

Berechnungsschritte

Hier ist eine mögliche Schritt-für-Schritt-Aktualisierung der Distanzwerte und Vorgängerknoten:

1. Start bei A:
   • Distanz: A=0, B=∞, C=∞, D=∞, E=∞, F=∞, H=∞
   • Vorgänger: B=, C=, D=, E=, F=, H=
2. Von A zu seinen Nachbarn:
   • Distanz: A=0, B=4, C=2, D=∞, E=∞, F=∞, H=∞
   • Vorgänger: B=A, C=A, D=, E=, F=, H=
3. Von C zu seinen Nachbarn:
   • Distanz: A=0, B=4, C=2, D=∞, E=5, F=∞, H=∞
   • Vorgänger: B=A, C=A, E=C, D=, F=, H=
4. Von B zu seinen Nachbarn:
   • Distanz: A=0, B=4, C=2, D=14, E=5, F=∞, H=∞
   • Vorgänger: B=A, C=A, E=C, D=B, F=, H=
5. Von E zu seinen Nachbarn:
   • Distanz: A=0, B=4, C=2, D=9, E=5, F=7, H=∞
   • Vorgänger: B=A, C=A, E=C, D=E, F=E, H=
6. Von D zu seinen Nachbarn:
   • Distanz: A=0, B=4, C=2, D=9, E=5, F=7, H=∞
   • Vorgänger: B=A, C=A, E=C, D=E, F=E, H=
7. Von F zu seinen Nachbarn:
   • Distanz: A=0, B=4, C=2, D=9, E=5, F=7, H=8
   • Vorgänger: B=A, C=A, E=C, D=E, F=E, H=F

Der kürzeste Weg von A nach H verläuft über A-C-E-F-H mit einer Gesamtdistanz von 8.

b)

Der Straßennetzwerk enthält auch einige Straßengewichte, die negativ sein können. Benutze den Bellman-Ford Algorithmus, um den kürzesten Weg vom Startknoten A zum Endknoten H zu berechnen. Zeige, wie negative Gewichtungen gehandhabt werden und prüfe, ob es einen negativen Zyklus im Graphen gibt. Wenn ja, gib das Vorhandensein eines negativen Zyklus an und erkläre, warum dies problematisch ist.

Lösung:

Bellman-Ford Algorithmus: Schritt-für-Schritt-Anleitung

Angenommen, das Straßennetzwerk enthält auch einige negative Straßengewichte und Du möchtest den kürzesten Weg vom Startknoten A zum Endknoten H berechnen. Verwende den Bellman-Ford Algorithmus und folge der nachstehenden Schritt-für-Schritt-Anleitung zur Berechnung, inklusive der Handhabung negativer Gewichtungen und der Überprüfung auf das Vorhandensein eines negativen Zyklus.

• Schritt 1: Initialisierung
• Setze die Distanz aller Knoten auf ∞, außer für den Startknoten A, der auf 0 gesetzt wird.
• Speichere die Vorgängerknoten, um den endgültigen Pfad rekonstruieren zu können.
• Schritt 2: Entspanne alle Kanten (|V|-1) mal
• Für jeden Knoten, gehe alle Kanten durch.
• Wenn die Distanz zum Endknoten durch eine Kante verringert werden kann:
• Aktualisiere die Distanz des Endknotens.
• Speichere den Vorgängerknoten.
• Schritt 3: Überprüfung auf negative Zyklen
• Durchlaufe alle Kanten erneut:
• Wenn man eine Distanz noch weiter verringern kann, existiert ein negativer Zyklus.

Beispielgraph

Angenommen, der Graph sieht wie folgt aus:

 A - B: 4 A - C: 2 B - C: 5 B - D: 10 C - E: 3 D - F: 11 E - D: -4 E - F: 2 F - H: 1 

Berechnungsschritte

Hier ist eine mögliche Schritt-für-Schritt-Aktualisierung der Distanzwerte und Vorgängerknoten:

1. Start bei A:
   • Distanz: A=0, B=∞, C=∞, D=∞, E=∞, F=∞, H=∞
   • Vorgänger: B=, C=, D=, E=, F=, H=
2. Entspanne alle Kanten (1. Durchlauf):
   • Distanz: A=0, B=4, C=2, D=∞, E=5, F=∞, H=∞
   • Vorgänger: B=A, C=A, E=C, D=, F=, H=
3. Entspanne alle Kanten (2. Durchlauf):
   • Distanz: A=0, B=4, C=2, D=11, E=5, F=7, H=∞
   • Vorgänger: B=A, C=A, E=C, D=E, F=E, H=
4. Entspanne alle Kanten (3. Durchlauf):
   • Distanz: A=0, B=4, C=2, D=7, E=5, F=7, H=∞
   • Vorgänger: B=A, C=A, E=C, D=E, F=E, H=
5. Entspanne alle Kanten (4. Durchlauf):
   • Distanz: A=0, B=4, C=2, D=7, E=5, F=7, H=∞
   • Vorgänger: B=A, C=A, E=C, D=E, F=E, H=
6. Entspanne alle Kanten (5. Durchlauf):
   • Distanz: A=0, B=4, C=2, D=7, E=5, F=7, H=∞
   • Vorgänger: B=A, C=A, E=C, D=E, F=E, H=
7. Entspanne alle Kanten (6. Durchlauf):
   • Distanz: A=0, B=4, C=2, D=7, E=5, F=7, H=8
   • Vorgänger: B=A, C=A, E=C, D=E, F=E, H=F
8. Entspanne alle Kanten (7. Durchlauf):
   • Distanz: A=0, B=4, C=2, D=7, E=5, F=7, H=8
   • Vorgänger: B=A, C=A, E=C, D=E, F=E, H=F
9. Überprüfung auf negative Zyklen:
   • Es gibt keine weiteren Relaxationen, daher gibt es keinen negativen Zyklus.

Der kürzeste Weg von A nach H verläuft über A - C - E - F - H mit einer Gesamtdistanz von 8.

Wenn jedoch eine Relaxation möglich gewesen wäre, hätte das das Vorhandensein eines negativen Zyklus angezeigt, was problematisch ist, weil dadurch keine stabile Lösung für kürzeste Wege existiert.

c)

In deinem Graphen weißt Du, dass der Knoten H das Ziel ist. Implementiere den A*-Algorithmus, um den kürzesten Weg vom Startknoten A zum Knoten H unter Verwendung einer geeigneten Heuristik zu berechnen. Beschreibe die gewählte Heuristik, warum sie angemessen ist und zeige die vollständige Schritt-für-Schritt-Berechnung der Wegesuche mit der Heuristik auf.

Lösung:

A*-Algorithmus: Schritt-für-Schritt-Anleitung

Angenommen, Du möchtest den kürzesten Weg vom Startknoten A zum Zielknoten H unter Verwendung des A*-Algorithmus berechnen. Die Wahl einer geeigneten Heuristik ist entscheidend für die Effizienz des Algorithmus.

Wahl der Heuristik

Für die Heuristik wählen wir die gerade Distanz (Luftlinie) zwischen den Knoten als Schätzung der verbleibenden Distanz zum Zielknoten H. Diese Heuristik ist angemessen, weil sie:

• Admissible (zulässig) ist: Sie überschätzt den tatsächlichen Abstand nicht, da die Luftlinie in einem kartesischen Koordinatensystem immer die kürzeste Distanz ist.
• Consistent (konsistent) ist: Sie erfüllt die Dreiecksungleichung, was sicherstellt, dass der Algorithmus keine Knoten mehrmals besuchen muss.

Schritte des A*-Algorithmus

• Schritt 1: Initialisierung
• Setze die Startkosten (g-Wert) für A auf 0 und die heuristische Schätzung (h-Wert) auf die Luftlinie von A nach H.
• Initialisiere eine Prioritätswarteschlange mit dem Startknoten A.
• Speichere die Vorgängerknoten für die Pfadrekonstruktion.
• Schritt 2: Ausführung
• Entferne den Knoten mit den geringsten geschätzten Gesamtkosten (f-Wert = g + h) aus der Warteschlange und setze ihn als aktuellen Knoten.
• Wenn der aktuelle Knoten das Ziel H ist, beende die Suche.
• Für jeden Nachbarn des aktuellen Knotens:
• Berechne die Startkosten (g-Wert) des Nachbarn.
• Berechne die geschätzten Gesamtkosten (f-Wert) des Nachbarn.
• Wenn dieser Weg besser ist als der bisher bekannte, aktualisiere die Kosten und den Vorgängerknoten.
• Füge den Nachbarn in die Warteschlange ein.

Beispielgraph

Angenommen, der Graph sieht wie folgt aus:

 A - B: 4 A - C: 2 B - C: 5 B - D: 10 C - E: 3 D - F: 11 E - D: 4 E - F: 2 F - H: 1 

Die Luftlinien-Distanzen (heuristische Schätzungen) sind:

 A: 7 B: 6 C: 4 E: 3 D: 2 F: 1 H: 0 

Berechnungsschritte

Verwende diese Zahlen zur Berechnung:

1. Initialisierung:
   • Knoten: A
   • g(A) = 0, h(A) = 7, f(A) = 7
   • Warteschlange: [(A, 7)]
2. Entferne A:
   • Aktueller Knoten: A
   • Warteschlange: []
   • Erkunde Nachbarn: B, C
   • g(B) = 0 + 4 = 4, h(B) = 6, f(B) = 10
   • g(C) = 0 + 2 = 2, h(C) = 4, f(C) = 6
   • Warteschlange: [(C, 6), (B, 10)]
   • Vorgänger: B=A, C=A
3. Entferne C:
   • Aktueller Knoten: C
   • Warteschlange: [(B, 10)]
   • Erkunde Nachbarn: E
   • g(E) = 2 + 3 = 5, h(E) = 3, f(E) = 8
   • Warteschlange: [(E, 8), (B, 10)]
   • Vorgänger: E=C
4. Entferne E:
   • Aktueller Knoten: E
   • Warteschlange: [(B, 10)]
   • Erkunde Nachbarn: D, F
   • g(D) = 5 + 4 = 9, h(D) = 2, f(D) = 11
   • g(F) = 5 + 2 = 7, h(F) = 1, f(F) = 8
   • Warteschlange: [(F, 8), (B, 10), (D, 11)]
   • Vorgänger: D=E, F=E
5. Entferne F:
   • Aktueller Knoten: F
   • Warteschlange: [(B, 10), (D, 11)]
   • Erkunde Nachbarn: H
   • g(H) = 7 + 1 = 8, h(H) = 0, f(H) = 8
   • Warteschlange: [(B, 10), (D, 11), (H, 8)]
   • Vorgänger: H=F
6. Entferne H:
   • Aktueller Knoten: H
   • Warteschlange: [(B, 10), (D, 11)]
   • Zielknoten H erreicht.

Der kürzeste Weg von A nach H verläuft über A-C-E-F-H mit einer Gesamtdistanz von 8.

d)

Vergleiche die Zeitkomplexitäten von Dijkstra, Bellman-Ford und A* an Hand des gegebenen Graphen. Diskutiere, in welchem Szenario jeder Algorithmus effizienter ist und begründe Deine Antwort. Zeige detaillierte Berechnungen oder Argumente, um Deine Schlussfolgerungen zu untermauern.

Lösung:

Vergleich der Zeitkomplexitäten: Dijkstra, Bellman-Ford und A*

In diesem Abschnitt werden wir die Algorithmen Dijkstra, Bellman-Ford und A* hinsichtlich ihrer Zeitkomplexität analysieren und ihre Effizienz in verschiedenen Szenarien diskutieren.

Zeitkomplexität

• Dijkstra
  • Algorithmus: Berechnet kürzeste Wege von einem Startknoten zu allen anderen Knoten in einem Graphen mit nicht-negativen Gewichtungen.
  • Zeitkomplexität: O((V + E) \times \text{log} V) unter Verwendung eines Min-Heap (Fibonacci-Heap).
  • Wobei V die Anzahl der Knoten und E die Anzahl der Kanten ist.
• Bellman-Ford
  • Algorithmus: Berechnet kürzeste Wege von einem Startknoten zu allen anderen Knoten in einem Graphen, der auch negative Gewichtungen enthalten kann.
  • Zeitkomplexität: O(V \times E).
  • Wobei V die Anzahl der Knoten und E die Anzahl der Kanten ist.
• A*
  • Algorithmus: Berechnet den kürzesten Weg von einem Startknoten zu einem Zielknoten unter Verwendung einer Heuristik, die die Suche leitet.
  • Zeitkomplexität: O(E) im schlimmsten Fall (abhängig von der gewählten Heuristik kann es im besten Fall schneller sein).
  • Wobei V die Anzahl der Knoten und E die Anzahl der Kanten ist.

Effizienz in verschiedenen Szenarien

Jeder Algorithmus hat seine spezifischen Stärken und Schwächen, je nach Eigenschaften des Graphen und der Anforderungen der Aufgabenstellung.

• Dijkstra
  • Szenario: Graph hat keine negativen Gewichtungen.
  • Begründung: Durch die Verwendung eines Min-Heaps ist Dijkstra sehr effizient im Umgang mit Graphen ohne negative Kantengewichte, liefert aber auch suboptimale Lösungen, wenn negative Kanten vorhanden sind.
  • Bestens geeignet für: Städteplanung in Szenarien mit positiven Distanzen.
• Bellman-Ford
  • Szenario: Graph kann negative Gewichtungen enthalten.
  • Begründung: Bellman-Ford ist langsamer als Dijkstra bei Graphen ohne negative Gewichtungen, kann jedoch zuverlässig mit negativen Gewichtungen umgehen. Darüber hinaus kann es negative Zyklen erkennen, was Dijkstra nicht kann.
  • Bestens geeignet für: Szenarien, in denen es wichtig ist, negative Zyklen zu erkennen und Entfernungen mit negativen Gewichtungen sicher zu verarbeiten.
• A*
  • Szenario: Es gibt ein klar definiertes Ziel und eine gute Heuristik zur Schätzung der Entfernung zum Zielknoten.
  • Begründung: A* kann sehr effizient sein, wenn eine gute Heuristik verwendet wird, da es die Suche auf relevante Teile des Graphen beschränkt. Ohne eine geeignete Heuristik entspricht die Leistung im schlimmsten Fall der BFS (Breadth-First Search).
  • Bestens geeignet für: Navigation und Routenplanung, bei denen das Ziel bekannt ist und eine gute heuristische Abschätzung der Entfernung genutzt werden kann.

Zusammenfassung

Dijkstra ist geeignet für Graphen ohne negative Kantengewichte und bietet eine effiziente Lösung mit einer Zeitkomplexität von O((V + E) \times \text{log} V). Bellman-Ford ist robuster bei Graphen mit negativen Gewichtungen und kann negative Zyklen erkennen, hat jedoch eine langsamere Zeitkomplexität von O(V \times E). A* kann den schnellsten Weg zu einem Zielknoten finden, wenn eine geeignete Heuristik verwendet wird, und hat im schlimmsten Fall eine Zeitkomplexität von O(E), abhängig von der Qualität der Heuristik.

Aufgabe 3)

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

• 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|)
• Kruskal Formalisierung:
  • Sortiere Kanten nach Gewicht
  • Verwende Union-Find zur Zyklenvermeidung
• Prim Formalisierung:
  • Verwende Prioritätswarteschlange für Kanten
  • Füge den minimalen Randknoten zum MST hinzu

a)

Gegeben sei ein Graph G=(V,E) mit den Knoten V={1, 2, 3, 4, 5} und den Kanten E={(1, 2, 4), (1, 3, 2), (2, 3, 3), (2, 4, 1), (3, 4, 5), (3, 5, 8), (4, 5, 7)}. Finde den minimalen Spannbaum (MST) mithilfe von Kruskal's Algorithmus und gib die Reihenfolge der hinzugefügten Kanten an, sowie die finale Struktur des MST.

Lösung:

Lösung des Unterexercises mithilfe von Kruskal's Algorithmus:

Wir beginnen damit, alle Kanten des Graphen nach ihrem Gewicht zu sortieren:

• (2, 4, 1)
• (1, 3, 2)
• (2, 3, 3)
• (1, 2, 4)
• (3, 4, 5)
• (4, 5, 7)
• (3, 5, 8)

Schrittweise werden nun die Kanten hinzugefügt, wobei darauf geachtet wird, keine Zyklen zu erzeugen. Dazu verwenden wir die Union-Find-Datenstruktur:

1. Füge Kante (2, 4, 1) hinzu: MST = {(2, 4, 1)}
2. Füge Kante (1, 3, 2) hinzu: MST = {(2, 4, 1), (1, 3, 2)}
3. Füge Kante (2, 3, 3) hinzu: MST = {(2, 4, 1), (1, 3, 2), (2, 3, 3)}
4. Füge Kante (1, 2, 4) hinzu: Diese Kante wird nicht hinzugefügt, da sie einen Zyklus bilden würde.
5. Füge Kante (3, 4, 5) hinzu: Diese Kante wird nicht hinzugefügt, da sie einen Zyklus bilden würde.
6. Füge Kante (4, 5, 7) hinzu: MST = {(2, 4, 1), (1, 3, 2), (2, 3, 3), (4, 5, 7)}

Die finale Struktur des minimalen Spannbaums (MST) ist:

• (2, 4, 1)
• (1, 3, 2)
• (2, 3, 3)
• (4, 5, 7)

b)

Verwende den gleichen Graphen G=(V,E) wie in der vorherigen Aufgabe. Finde den minimalen Spannbaum (MST) mithilfe von Prim's Algorithmus, beginnend bei Knoten 1. Gib die Reihenfolge der hinzugefügten Kanten an, sowie die finale Struktur des MST.

Lösung:

Lösung des Unterexercises mithilfe von Prim's Algorithmus:

Wir beginnen bei Knoten 1. Prim's Algorithmus verwendet eine Prioritätswarteschlange, um die Kanten nach ihrem Gewicht zu sortieren, und fügt iterativ die billigsten Kanten hinzu, die einen neuen Knoten verbinden.

• Initialisiere den MST mit dem Startknoten 1.
• Füge alle Kanten, die von Knoten 1 ausgehen, in die Prioritätswarteschlange ein.

Details:

1. Starte bei Knoten 1:

• Kanten zu Knoten 1 werden der Prioritätswarteschlange hinzugefügt: (1, 2, 4) und (1, 3, 2)

• Knoten 3 wird besucht, füge seine neuen Kanten zur Prioritätswarteschlange hinzu: (3, 2, 3), (3, 4, 5), (3, 5, 8)

• Knoten 2 wird besucht, füge seine neuen Kanten zur Prioritätswarteschlange hinzu: (2, 4, 1)

• Knoten 4 wird besucht, füge seine neuen Kanten zur Prioritätswarteschlange hinzu: (4, 5, 7)

• Jetzt sind alle Knoten im MST enthalten.

Die finale Struktur des minimalen Spannbaums (MST) ist:

• (1, 3, 2)
• (3, 2, 3)
• (2, 4, 1)
• (4, 5, 7)

c)

Vergleiche die Komplexität von Kruskal's Algorithmus und Prim's Algorithmus für dichte und spärliche Graphen. Erkläre anhand von Beispielen, welcher Algorithmus in welcher Situation effizienter ist.

Lösung:

Vergleich der Komplexität von Kruskal's Algorithmus und Prim's Algorithmus:

Um die Effizienz beider Algorithmen besser zu verstehen, vergleichen wir ihre Komplexitäten:

• Kruskal's Algorithmus: Die Komplexität beträgt O(|E| log |E| ), wobei |E| die Anzahl der Kanten im Graphen ist. Diese Komplexität ergibt sich aus dem Sortieren der Kanten sowie der Union-Find-Datenstruktur für die Zyklenvermeidung.
• Prim's Algorithmus: Die Komplexität beträgt O(|E| + |V| log |V| ), wobei |V| die Anzahl der Knoten im Graphen ist. Diese Komplexität resultiert aus der Verwendung einer Prioritätswarteschlange zum Hinzufügen der billigsten Kanten.

Nun betrachten wir die Effizienz beider Algorithmen für unterschiedliche Arten von Graphen:

Dichte Graphen:

• In dichten Graphen ist die Anzahl der Kanten |E| annähernd gleich |V|^2.
• Kruskal's Algorithmus: In dichten Graphen ist die Komplexität O(|E| log |E| ) ungefähr O(|V|^2 log |V| ).
• Prim's Algorithmus: In dichten Graphen ist die Komplexität O(|E| + |V| log |V| ) ungefähr O(|V|^2).
• Schlussfolgerung: Für dichte Graphen könnte Prim's Algorithmus effizienter sein, da seine Laufzeit durch die Anzahl der Kanten |E| dominiert wird, und hierbei gilt |E| ≈ |V|^2.

Spärliche Graphen:

• In spärlichen Graphen ist die Anzahl der Kanten |E| viel kleiner als |V|^2, oft etwa |E| ≈ |V|.
• Kruskal's Algorithmus: In spärlichen Graphen beträgt die Komplexität O(|E| log |E| ) ungefähr O(|V| log |V|).
• Prim's Algorithmus: In spärlichen Graphen beträgt die Komplexität O(|E| + |V| log |V| ) ungefähr O(|V| log |V|).
• Schlussfolgerung: Für spärliche Graphen sind sowohl Kruskal's als auch Prim's Algorithmus effizient, da sie ähnliche Komplexitäten aufweisen.

Zusammenfassung:

• Dichte Graphen: Prim's Algorithmus ist tendenziell effizienter.
• Spärliche Graphen: Beide Algorithmen sind effizient, aber Kruskal's Algorithmus ist ebenfalls eine gute Wahl.

d)

Erkläre, wie der Union-Find-Datentyp in Kruskal’s Algorithmus zur Zyklenvermeidung verwendet wird. Implementiere den Union-Find-Datentyp in Python.

Lösung:

Erklärung der Verwendung des Union-Find-Datentyps in Kruskal’s Algorithmus zur Zyklenvermeidung:

Der Union-Find-Datentyp (auch als disjunkte Mengen-Datentyp bekannt) wird in Kruskal's Algorithmus verwendet, um Zyklen zu vermeiden. Der Union-Find-Datentyp unterstützt zwei grundlegende Operationen:

• Find: Bestimmt, zu welcher Menge ein bestimmtes Element gehört. Diese Operation wird verwendet, um zu überprüfen, ob zwei Knoten im gleichen Teilbaum liegen.
• Union: Vereint zwei Mengen. Diese Operation wird verwendet, um zwei Knoten in derselben Menge zu verbinden, wenn sie durch eine Kante verbunden sind und keinen Zyklus bilden.

In Kruskal’s Algorithmus wird der Union-Find-Datentyp wie folgt angewendet:

1. Initialisiere den Union-Find-Datentyp mit jedem Knoten des Graphen als eigene separate Menge.
2. Sortiere alle Kanten des Graphen nach ihrem Gewicht.
3. Gehe jede Kante der Reihe nach durch. Für jede Kante (u, v):

• Überprüfe, ob die Knoten u und v in verschiedenen Mengen sind (mittels der Find-Operation).
• Falls ja, füge die Kante zum minimalen Spannbaum (MST) hinzu und vereinige die zwei Mengen (mittels der Union-Operation).
• Falls nein, ignoriere die Kante, da sie einen Zyklus bilden würde.

Implementierung des Union-Find-Datentyps in Python:

class UnionFind:

    def __init__(self, n):

        self.parent = list(range(n))

        self.rank = [0] * n

    def find(self, u):

        if self.parent[u] != u:

            self.parent[u] = self.find(self.parent[u])

        return self.parent[u]

    def union(self, u, v):

        root_u = self.find(u)

        root_v = self.find(v)

        if root_u != root_v:

            if self.rank[root_u] > self.rank[root_v]:

                self.parent[root_v] = root_u

            elif self.rank[root_u] < self.rank[root_v]:

                self.parent[root_u] = root_v

            else:

                self.parent[root_v] = root_u

                self.rank[root_u] += 1

Diese Python-Implementierung des Union-Find-Datentyps unterstützt die beiden zentralen Operationen `find` und `union`. Die `find`-Operation verwendet Pfadkompression, um die Struktur der Union-Find-Datenstruktur flach zu halten, und die `union`-Operation verwendet Union by Rank, um sicherzustellen, dass die kürzeren Bäume an die Wurzel der tieferen Bäume angehängt werden.

Aufgabe 4)

Gegeben sei das Problem der Berechnung der n-ten Fibonacci-Zahl unter Nutzung von Dynamischer Programmierung.

Die n-te Fibonacci-Zahl wird durch die rekursive Formel definiert:

• \( F(0) = 0 \)
• \( F(1) = 1 \)
• \( F(n) = F(n-1) + F(n-2) \) für \( n \geq 2 \)

Implementiere und analysiere eine Lösung unter Berücksichtigung der Grundprinzipien der Dynamischen Programmierung und Memoization.

a)

(a) Implementiere eine Top-Down (rekursive) Lösung mit Memoization für das Problem der Berechnung der n-ten Fibonacci-Zahl. Deine Lösung soll die Speicherung bereits berechneter Teilprobleme nutzen, um unnötige Berechnungen zu vermeiden.

def fibonacci_memo(n, memo={}): nbsp;nbsp;nbsp;nbsp;if n in memo: nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;return memo[n] nbsp;nbsp;nbsp;nbsp;if n == 0: nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;return 0 nbsp;nbsp;nbsp;nbsp;elif n == 1: nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;return 1 nbsp;nbsp;nbsp;nbsp;else: nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;memo[n] = fibonacci_memo(n-1, memo) + fibonacci_memo(n-2, memo) nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;return memo[n] 

Erkläre, wie die Memoization in Deinem Code implementiert ist und warum sie effizienter ist als eine einfache rekursive Lösung ohne Memoization.

Lösung:

Lass uns zuerst die Implementierung der Top-Down (rekursiven) Lösung mit Memoization für das Problem der Berechnung der n-ten Fibonacci-Zahl betrachten:

def fibonacci_memo(n, memo={}):    if n in memo:        return memo[n]    if n == 0:        return 0    elif n == 1:        return 1    else:        memo[n] = fibonacci_memo(n - 1, memo) + fibonacci_memo(n - 2, memo)        return memo[n]

Diese Umsetzung nutzt Memoization, um berechnete Werte zwischenzuspeichern und damit unnötige Berechnungen zu vermeiden.

• wenn der Wert für n bereits in dem Dictionary memo gespeichert ist, wird dieser direkt zurückgegeben. Dies spart Zeit, da bereits berechnete Werte wiederverwendet werden.
• wenn n gleich 0 ist, wird 0 zurückgegeben, und wenn n gleich 1 ist, wird 1 zurückgegeben - diese entsprechen den Basisfällen der Fibonacci-Reihe.
• ansonsten wird der Wert der n-ten Fibonacci-Zahl rekursiv berechnet und in das Dictionary memo eingefügt. Danach wird dieser Wert zurückgegeben.

Warum ist Memoization effizienter?

• Ohne Memoization: Eine einfache rekursive Lösung würde jedes Teilproblem mehrfach berechnen, was zu einer exponentiellen Zeitkomplexität führt (ungefähr O(2^n)).
• Mit Memoization: Durch das Speichern und Wiederverwenden bereits berechneter Werte wird die Anzahl der notwendigen Berechnungen signifikant reduziert. Dies führt zu einer linearen Zeitkomplexität, nämlich O(n).

So werden unnötige Berechnungen vermieden und die Effizienz der Berechnung der n-ten Fibonacci-Zahl signifikant verbessert.

b)

(b) Implementiere eine Bottom-Up (tabellarische) Lösung zur Berechnung der n-ten Fibonacci-Zahl. Vergleiche die Zeitkomplexität Deiner Bottom-Up-Lösung mit der Top-Down-Lösung und begründe, welche in der Regel effizienter ist.

def fibonacci_bottom_up(n): nbsp;nbsp;nbsp;nbsp;if n == 0: nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;return 0 nbsp;nbsp;nbsp;nbsp;elif n == 1: nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;return 1 nbsp;nbsp;nbsp;nbsp;fib = [0] * (n + 1) nbsp;nbsp;nbsp;nbsp;fib[1] = 1 nbsp;nbsp;nbsp;nbsp;for i in range(2, n + 1): nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;nbsp;fib[i] = fib[i-1] + fib[i-2] nbsp;nbsp;nbsp;nbsp;return fib[n] 

Vergleiche und kontrastiere die Effizienz Deiner beiden Ansätze und führe eine Analyse der Zeitkomplexität beider Methoden durch.

Lösung:

Nun betrachten wir die Implementierung einer Bottom-Up (tabellarischen) Lösung zur Berechnung der n-ten Fibonacci-Zahl:

def fibonacci_bottom_up(n):    if n == 0:        return 0    elif n == 1:        return 1    fib = [0] * (n + 1)    fib[1] = 1    for i in range(2, n + 1):        fib[i] = fib[i-1] + fib[i-2]    return fib[n]

Diese Umsetzung nutzt die Bottom-Up-Technik, um die n-te Fibonacci-Zahl zu berechnen.

• wenn n gleich 0 ist, wird 0 zurückgegeben, und wenn n gleich 1 ist, wird 1 zurückgegeben - diese entsprechen den Basisfällen der Fibonacci-Reihe.
• ansonsten wird ein Array fib der Größe n+1 initialisiert, wobei die ersten beiden Einträge auf 0 und 1 gesetzt werden.
• In einer Schleife wird jedes Element des Arrays fib als Summe der beiden vorangehenden Elemente berechnet.
• Zum Schluss wird der Wert fib[n] zurückgegeben, der die n-te Fibonacci-Zahl darstellt.

Vergleich der Zeitkomplexität beider Ansätze:

• Top-Down (mit Memoization): Die Zeitkomplexität ist O(n), da jedes Teilproblem nur einmal berechnet und dann zwischengespeichert wird.
• Bottom-Up (tabellarisch): Auch hier ist die Zeitkomplexität O(n), da die Berechnung iterativ und in linearer Zeit erfolgt.

Vergleich der Effizienz:

• Speicherbedarf: Beide Ansätze benötigen O(n) Speicherplatz, jedoch benötigt der Bottom-Up-Ansatz weniger Overhead und nutzt in der Regel weniger Speicher als der Top-Down-Ansatz.
• Zeitaufwand: Beide Techniken sind in der Zeitkomplexität effizient (O(n)). Allerdings kann der Bottom-Up-Ansatz in der Regel konstanter sein, da er keine rekursive Funktionsaufrufe hat und somit weniger Stack-Overhead verursacht.
• Praktische Nutzung: In der Praxis wird die Bottom-Up-Methode oft als effizienter angesehen, da sie einfacher zu implementieren und zu debuggen ist und bei hohen Werte von n stabiler läuft.

Insgesamt sind beide Methoden effizient und haben ihre jeweiligen Vorteile. Die Wahl zwischen Top-Down und Bottom-Up hängt oft von den spezifischen Anforderungen der Implementierung ab.