NWERC Praktikum - Exam

Aufgabe 1)

Laufzeitanalyse von Algorithmen

Während des NWERC Praktikums hast Du verschiedene Aspekte der Laufzeitanalyse von Algorithmen kennengelernt. Dazu gehören die asymptotische Notation, die Klassifizierung der Laufzeit in Best-Case, Average-Case und Worst-Case Szenarien, sowie das Verständnis und die Anwendung unetrschiedlicher Laufzeitkomplexitätsklassen wie Polynomialzeit, NP und NP-Vollständigkeit. Ein weiteres wichtiges Werkzeug war das Master-Theorem zur Lösung von Rekursionsgleichungen der Form T(n) = aT(n/b) + f(n).

In der folgenden Aufgabe wirst Du diese Konzepte anwenden, um die Effizienz verschiedener Algorithmen zu analysieren und zu bewerten.

a)

1. Betrachte den folgenden rekursiven Algorithmus:

 def example_algorithm(n):     if n <= 1:         return 1    else:        return 2 * example_algorithm(n//2) + n 

Nutze das Master-Theorem, um die Laufzeit T(n) dieses Algorithmus zu bestimmen. Gehe dabei systematisch vor und identifiziere die Werte von a, b und f(n). Bestimme anschließend die asymptotische Laufzeit.

Lösung:

1. Betrachte den folgenden rekursiven Algorithmus:

 def example_algorithm(n):     if n <= 1:         return 1    else:        return 2 * example_algorithm(n//2) + n 

Um die Laufzeit T(n) des Algorithmus mittels des Master-Theorems zu analysieren, gehen wir systematisch vor:

• Zuerst identifizieren wir die Werte von a, b und f(n) in der rekursiven Gleichung T(n) = aT(n/b) + f(n).
• Identifizierung von a, b und f(n):

In unserem Algorithmus haben wir:

• a = 2 (da wir den rekursiven Aufruf zweimal machen)
• b = 2 (da wir n durch 2 teilen)
• f(n) = n (da wir n in jeder Rekursion addieren)

Wir haben also die rekursive Gleichung:

 T(n) = 2T(n/2) + n 

Jetzt wenden wir das Master-Theorem an. Es gibt drei Fälle zu berücksichtigen:

• Fall 1: Wenn f(n) = O(n^c) mit c < log_b(a), dann ist T(n) = O(n^log_b(a)).
• Fall 2: Wenn f(n) = O(n^c) mit c = log_b(a), dann ist T(n) = O(n^log_b(a) * log(n)).
• Fall 3: Wenn f(n) = O(n^c) mit c > log_b(a), dann ist T(n) = O(f(n)).

Zur Berechnung von log_b(a):

• log_b(a) = log_2(2) = 1

Nun vergleichen wir die Funktion f(n) = n mit n^log_b(a) = n^1 = n.

• In diesem Fall ist c = 1 und log_b(a) = 1, also sind wir im zweiten Fall des Master-Theorems.

Nach dem Master-Theorem haben wir im zweiten Fall für c = log_b(a):

• T(n) = O(n * log(n)) = O(n log n)

Die asymptotische Laufzeit des Algorithmus ist daher:

• O(n log n)

b)

2. Angenommen, Du hast drei Algorithmen A, B und C mit den folgenden Laufzeiten:

• A: O(n \log n)
• B: O(n^2)
• C: O(2^n)

Analysiere und vergleiche die Effizienz dieser Algorithmen in den verschiedenen Laufzeitszenarien (Best-Case, Average-Case, Worst-Case). Erkläre, welcher Algorithmus unter verschiedenen Eingabebedingungen bevorzugt werden sollte, und warum.

Lösung:

2. Analysieren und Vergleichen der Algorithmen A, B und C

• A: O(n \log n)
• B: O(n^2)
• C: O(2^n)

Um die Effizienz dieser Algorithmen in verschiedenen Laufzeitszenarien zu analysieren und zu vergleichen, betrachten wir die Best-Case, Average-Case und Worst-Case Laufzeit. Der Focus liegt auf der Vergleichbarkeit der asymptotischen Notation (Big-O) der gegebenen Laufzeiten.

• Algorithmus A (O(n \log n))

1. Best-Case: In vielen Algorithmen, die O(n \log n) als Worst-Case-Laufzeit haben, ist der Best-Case oftmals asymptotisch schneller. Zum Beispiel könnte der Best-Case für A O(n) sein, wenn der Algorithmus optimal funktioniert.
2. Average-Case: In der Regel bleibt die Average-Case-Laufzeit O(n \log n), da diese Laufzeit die durchschnittliche Effizienz über alle Eingaben hinweg darstellt.
3. Worst-Case: O(n \log n) ist bereits die worst-case Laufzeit.
4. Bevorzugung: Dieser Algorithmus ist effizient für große Eingabegrößen und bietet eine gute Balance zwischen Geschwindigkeit und Komplexität. Er wird bevorzugt für Anwendungen wie Sortieralgorithmen und Suchprobleme, da sie in der Regel eine log-lineare Zeitkomplexität aufweisen.

• Algorithmus B (O(n^2))

1. Best-Case: Möglicherweise O(n), wenn der Algorithmus mit einer bestimmten optimalen Eingabe arbeitet. Zum Beispiel könnte der Best-Case für eine einfache Schleife sein, dass es O(n) ist, wenn alle Elemente bereits sortiert sind oder nur wenige Operationen erforderlich sind.
2. Average-Case: O(n^2) ist in der Regel auch die Average-Case-Laufzeit, da quadratische Algorithmen häufig dieselbe Komplexität für den Durchschnittsfall aufweisen.
3. Worst-Case: O(n^2) ist die worst-case Laufzeit, was bedeutet, dass der Algorithmus im ungünstigsten Fall quadratisch wächst.
4. Bevorzugung: Diese Art von Algorithmus wird für moderate Eingabegrößen verwendet. Er ist in den meisten Fällen nicht so effizient wie Algorithmen der Ordnung O(n \log n), kann jedoch für einfache Probleme oder kleine Datensätze akzeptabel sein.

• Algorithmus C (O(2^n))

1. Best-Case: Der Best-Case kann sehr unterschiedlich sein, aber oft ist er immer noch exponentiell, da exponentielle Algorithmen wenig Spielraum für optimierte Szenarien haben. Möglicherweise könnte der Best-Case auf nur wenigen Operationen basieren, abhängig von der Problemstruktur, aber dies ist selten asymptotisch besser.
2. Average-Case: Für Algorithmen mit exponentieller Laufzeit ist der Average-Case normalerweise immer noch O(2^n). Die Komplexität hängt in der Regel nicht wesentlich von den Eingabedaten ab.
3. Worst-Case: O(2^n) ist die Worst-Case Laufzeit.
4. Bevorzugung: Diese Algorithmen sollten vermieden werden, wenn möglich, insbesondere bei großen Eingabedaten. Sie sind oft für Probleme der Klasse NP-Vollständigkeit relevant, wo keine bekannten polynomialen Lösungen existieren. Diese Algorithmen können in kleinen oder sehr spezifischen Anwendungsfällen eingesetzt werden, wo die Eingabegröße begrenzt werden kann.

Zusammenfassend:

• Algorithmus A ist am effizientesten für große Datensätze und bietet eine log-lineare Komplexität.
• Algorithmus B ist geeigneter für kleinere bis mittlere Datensätze und einfachere Probleme, bei denen eine quadratische Laufzeit vertretbar ist.
• Algorithmus C ist am wenigsten effizient und sollte nur in speziellen Fällen verwendet werden, da die exponentielle Laufzeit für große Eingabedaten untragbar ist.

Aufgabe 2)

Greedy-Algorithmen sind Algorithmusparadigmen, die in jeder Phase die lokal optimale Wahl treffen, mit der Hoffnung, die global optimale Lösung zu finden. Die Komplexität ist oft geringer als bei dynamischer Programmierung, und sie werden eingesetzt, um Optimierungsprobleme zu lösen. Beispiele für Greedy-Algorithmen sind Prim's Algorithmus, Kruskal's Algorithmus und die Huffman-Codierung. Diese Algorithmen bauen ihre Lösungen auf vorherigen Entscheidungen auf und sind besonders geeignet für Probleme, die die Greedy-Eigenschaft (Optimalitätsprinzip) besitzen.

a)

(a) Betrachte das folgendes Problem: Du möchtest ein Mindest-Spannbaum (Minimum Spanning Tree, MST) für einen gegebenen zusammenhängenden, ungerichteten Graphen mit den Knoten

• 1, 2, 3, 4 und 5

und deren Gewicht wie folgt ist:

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

Wende Kruskal's Algorithmus an, um den MST zu berechnen. Stelle dabei sicher, dass du alle Zwischenschritte erläuterst und das Endergebnis klar darstellst.

Lösung:

Teilaufgabe (a): Mindest-Spannbaum (Minimum Spanning Tree, MST) mit Kruskal's Algorithmus

Um den Mindest-Spannbaum (MST) eines Graphen mit Kruskal's Algorithmus zu berechnen, müssen wir wie folgt vorgehen:

• Alle Kanten des Graphen in aufsteigender Reihenfolge ihrer Gewichte sortieren.
• Die kleinste noch nicht betrachtete Kante wählen und sie in den MST aufnehmen, sofern sie keinen Zyklus bildet.
• Diesen Vorgang wiederholen, bis der MST alle Knoten des Graphen enthält.

Im gegebenen Graphen haben wir folgende Kanten und deren Gewichte:

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

Nun sortieren wir die Kanten nach ihren Gewichten in aufsteigender Reihenfolge:

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

Wir fügen nun schrittweise die Kanten zum MST hinzu, wobei wir darauf achten, keine Zyklen zu erzeugen:

1. Kante (2, 3, 1): Diese Kante wird hinzugefügt, da sie den ersten Schritt darstellt und keine Zyklen entstehen können. MST: {(2, 3, 1)}
2. Kante (4, 5, 1): Keine Zyklen entstehen, wird hinzugefügt. MST: {(2, 3, 1), (4, 5, 1)}
3. Kante (1, 2, 2): Keine Zyklen entstehen, wird hinzugefügt. MST: {(2, 3, 1), (4, 5, 1), (1, 2, 2)}
4. Kante (1, 3, 3): Diese Kante wird hinzugefügt, da sie keine Zyklen bildet. MST: {(2, 3, 1), (4, 5, 1), (1, 2, 2), (1, 3, 3)}
5. Kante (2, 4, 4): Diese Kante wird nicht hinzugefügt, da sie einen Zyklus mit den bereits hinzugefügten Kanten (2, 3, 1) und (1, 2, 2) erzeugen würde.
6. Kante (3, 4, 5): Diese Kante wird nicht hinzugefügt, da sie ebenfalls einen Zyklus erzeugen würde.
7. Kante (3, 5, 6): Wird nicht hinzugefügt, da der MST bereits alle Knoten enthält.

Abschließend besteht der MST aus den Kanten:

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

Dies ist der Minimum Spanning Tree (MST) des gegebenen Graphen nach Kruskal's Algorithmus.

b)

(b) Analysiere, ob das folgende 0-1-Rucksackproblem die Greedy-Eigenschaft (Optimalitätsprinzip) erfüllt:

• Gegeben sind die Gegenstände A, B, C mit den Gewichten 2, 3, 4 und den Werten 3, 4, 5.
• Der maximale Gewichtswert des Rucksacks beträgt 6.

Überlege, ob ein Greedy-Algorithmus hier die global optimale Lösung liefert und beweise Deine Überlegungen mathematisch, indem Du die Greedy-Eigenschaft analysierst. Vergleiche auch die Lösung, die durch einen Greedy-Algorithmus erreicht wird, mit der global optimalen Lösung.

Lösung:

Teilaufgabe (b): Analyse des 0-1-Rucksackproblems und die Greedy-Eigenschaft

Um zu analysieren, ob das 0-1-Rucksackproblem die Greedy-Eigenschaft erfüllt, betrachten wir die folgenden Details:

• Gegeben sind die Gegenstände A, B, C mit den Gewichten 2, 3, 4 und den Werten 3, 4, 5.
• Der maximale Gewichtswert des Rucksacks beträgt 6.

Ein Greedy-Algorithmus würde hier die Gegenstände nach ihrem Wert-Gewicht-Verhältnis sortieren und die Gegenstände mit dem höchsten Verhältnis auswählen, solange der Rucksack nicht überladen wird.

Berechnen wir die Wert-Gewicht-Verhältnisse:

• Gegenstand A: Wert = 3, Gewicht = 2 → \(\frac{3}{2} = 1.5\)
• Gegenstand B: Wert = 4, Gewicht = 3 → \(\frac{4}{3} ≈ 1.33\)
• Gegenstand C: Wert = 5, Gewicht = 4 → \(\frac{5}{4} = 1.25\)

Sortieren wir die Gegenstände nach dem Wert-Gewicht-Verhältnis in absteigender Reihenfolge:

• A (1.5)
• B (1.33)
• C (1.25)

Wir fügen nun die Gegenstände gemäß dem Greedy-Algorithmus hinzu:

1. Wähle Gegenstand A: Gewicht = 2, Wert = 3. Aktuelles Gewicht im Rucksack = 2.
2. Wähle Gegenstand B: Gewicht = 3, Wert = 4. Aktuelles Gewicht im Rucksack = 5.
3. Gegenstand C kann nicht gewählt werden, weil das Gesamtgewicht im Rucksack dann 9 wäre, was größer als 6 ist.

Der Wert des Rucksacks mit der Greedy-Strategie beträgt: 3 (Wert von A) + 4 (Wert von B) = 7.

Nun berechnen wir die globale optimale Lösung durch vollständige Enumeration aller möglichen Kombinationen:

• {A, B}: Gesamtgewicht = 5, Gesamtwert = 7
• {A, C}: Gesamtgewicht = 6, Gesamtwert = 8
• {B, C}: Gesamtgewicht = 7 (zu schwer, nicht möglich)
• Nur A: Gesamtgewicht = 2, Gesamtwert = 3
• Nur B: Gesamtgewicht = 3, Gesamtwert = 4
• Nur C: Gesamtgewicht = 4, Gesamtwert = 5
• {A, B, C}: Gesamtgewicht = 9 (zu schwer, nicht möglich)

Die globale optimale Lösung: {A, C} mit einem Gesamtwert von 8, da dies das höchste Gewicht <= 6 ist.

Somit erkennen wir, dass der Greedy-Algorithmus beim 0-1-Rucksackproblem nicht die globale optimale Lösung liefert, da {A, C} einen höheren Gesamtwert (8) besitzt als {A, B} (7).

Begründung: Die Greedy-Eigenschaft erfüllt das 0-1-Rucksackproblem nicht, weil die lokale Entscheidung, den Gegenstand mit dem höchsten Wert-Gewicht-Verhältnis zu wählen, nicht immer zu der globalen optimalen Lösung führt. Im obigen Fall hat der Greedy-Algorithmus versagt, die Kombination mit dem maximalen Wert innerhalb des Rucksacklimits zu finden.

Aufgabe 3)

Du arbeitest an einem Projekt im Rahmen des 'NWERC Praktikum' an der Universität Erlangen-Nürnberg. Zu deinen Aufgaben gehört die Implementierung und Analyse von dynamischen Programmieralgorithmen. Eines der häufigsten Probleme, das du lösen musst, ist das klassische Rucksackproblem. Gegeben sind n Gegenstände mit jeweils einem Gewicht und einem Wert, sowie ein Rucksack, der ein maximal tragbares Gewicht hat. Ziel ist es, den maximalen Wert der Gegenstände im Rucksack zu finden, ohne das tragbare Gewicht zu überschreiten.

a)

Implementiere das Rucksackproblem mit einem Bottom-Up-Ansatz. Schreibe eine Python-Funktion

def knapsack(values, weights, W)

, die als Eingabe eine Liste von Werten values, eine Liste von Gewichten weights und das maximale Gewicht W des Rucksacks bekommt. Die Funktion soll den maximalen Wert zurückgeben, der in den Rucksack gepackt werden kann. Nutze eine DP-Tabelle, um Zwischenresultate zu speichern. Achte auf eine effiziente Implementierung hinsichtlich Laufzeit und Speicherbedarf.

Lösung:

Um das Rucksackproblem mit einem Bottom-Up-Ansatz zu lösen, kannst Du eine dynamische Programmierung (DP) verwenden. Wir erstellen eine DP-Tabelle, die alle möglichen Kombinationen von Gegenständen und Gewichten darstellt, um den maximalen Wert zu berechnen. Hier ist ein schrittweiser Ansatz:

• Erstelle eine DP-Tabelle (2D-Liste), wobei die Zeilen die Gegenstände und die Spalten die Gewichte darstellen.
• Initialisiere die Tabelle mit Nullen. Dies ist unser Basisfall, wobei kein Gegenstand ausgewählt wird oder das Gewicht Null ist.
• Fülle die Tabelle, indem Du den maximalen Wert berechnest, den Du bis zu diesem Gewicht mit den verfügbaren Gegenständen erzielen kannst.

Hier ist die Implementierung in Python:

  def knapsack(values, weights, W): n = len(values) # Anzahl der Gegenstände # Erstellen der DP-Tabelle dp = [[0 for x in range(W + 1)] for x in range(n + 1)] # Füllen der DP-Tabelle for i in range(n + 1): for w in range(W + 1): if i == 0 or w == 0: dp[i][w] = 0 elif weights[i - 1] <= w: dp[i][w] = max(values[i - 1] + dp[i - 1][w - weights[i - 1]], dp[i - 1][w]) else: dp[i][w] = dp[i - 1][w] return dp[n][W] # Beispielwerte values = [60, 100, 120] weights = [10, 20, 30] W = 50 print(knapsack(values, weights, W)) # Output sollte 220 sein  

Die spiegenden Punkte des Codes sind:

• Die Funktion erstellt eine DP-Tabelle dp, die mit Nullen initialisiert ist.
• Das äußere for-Schleife läuft über die Gegenstände, das innere for-Schleife über die möglichen Gewichte.
• Wenn ein Gegenstand ausgewählt wird (sein Gewicht kleiner oder gleich dem aktuellen Gewicht w ist), berechnet die Funktion den maximalen Wert, indem sie den Wert des aktuellen Gegenstands und den Wert der verbleibenden Kapazität vergleicht.
• Wenn ein Gegenstand nicht ausgewählt wird (sein Gewicht größer als das aktuelle Gewicht w ist), wird der Wert aus der vorherigen Zeile übernommen.

Am Ende gibt die Funktion den maximalen Wert zurück, der in den Rucksack gepackt werden kann.

b)

Analysiere die Komplexität der von dir implementierten Lösung. Erkläre, warum der Bottom-Up-Ansatz im Vergleich zum Top-Down-Ansatz (mit Memoisierung) sinnvoll ist. Berechne die Zeitkomplexität und Speicherkomplexität der Lösung. Begründe deine Antwort mit einer formalen Analyse und vergleiche sie mit dem Top-Down-Ansatz. Nutze dabei folgende Informationen:

• Die Anzahl der Gegenstände ist n.
• Das maximale Gewicht ist W.

Lösung:

Im Folgenden analysieren wir die Komplexität der Bottom-Up-Ansatzlösung des Rucksackproblems und vergleichen sie mit dem Top-Down-Ansatz (mit Memoisierung). Dabei betrachten wir sowohl die Zeit- als auch die Speicherkomplexität.

Bottom-Up-Ansatz

Der Bottom-Up-Ansatz verwendet dynamische Programmierung, um eine DP-Tabelle zu füllen, die die Werte aller Zwischenlösungen enthält. Hier sind die Details:

• Zeitkomplexität: Die Zeitkomplexität ergibt sich aus den verschachtelten Schleifen, die jeweils bis n und W verlaufen.
  • Die äußere Schleife läuft über die Anzahl der Gegenstände, also O(\text{n}).
  • Die innere Schleife läuft über das maximale Gewicht, also O(W).
  Daher ist die gesamte Zeitkomplexität des Bottom-Up-Ansatzes: O(nW).
• Speicherkomplexität: Die Speicherkomplexität ist ebenfalls abhängig von der Größe der DP-Tabelle, die eine Größe von (n+1) x (W+1) hat. Das bedeutet: O(nW).

Top-Down-Ansatz (mit Memoisierung)

Beim Top-Down-Ansatz wird rekursiv gearbeitet, und Ergebnisse von Zwischenlösungen werden in einer Memoisierungstabelle gespeichert, um Redundanzen zu vermeiden.

• Zeitkomplexität: Die maximale Anzahl der Unterprobleme entspricht der Anzahl der Einträge in der Memoisierungstabelle, also n x W. Jedes Unterproblem wird im schlimmsten Fall einmal berechnet, was zu einer Zeitkomplexität von O(nW) führt.
• Speicherkomplexität: Auch hier ist die Speicherkomplexität wegen der Memoisierungstabelle O(nW).

Vergleich und Fazit

• Beide Ansätze (Bottom-Up und Top-Down mit Memoisierung) haben dieselbe Zeit- und Speicherkomplexität von O(nW).
• Der Bottom-Up-Ansatz kann manchmal effizienter sein, da er in vielen modernen Prozessoren besser mit speicherorientierten Operationen umgehen kann, was die tatsächliche Laufzeit positiv beeinflussen könnte.
• Der Bottom-Up-Ansatz ist in der Regel einfacher zu implementieren und zu verstehen, da er iterative statt rekursive Methoden verwendet und damit Probleme wie Stack Overflow vermeidet, die bei sehr tiefen rekursiven Aufrufen auftreten können.

Aufgabe 4)

Angenommen, Du arbeitest an einem Navigationssystem, das eine Karte als Graph darstellt. Du sollst nun Algorithmen implementieren, die dem Benutzer den kürzesten Weg von einem Startpunkt zu einem Zielpunkt berechnen. Verwende hierfür sowohl den Dijkstra-Algorithmus als auch den A*-Algorithmus. Die Graphen bestehen aus Knoten und Kanten mit nichtnegativen Gewichten.

a)

Implementiere den Dijkstra-Algorithmus in Python, der die kürzesten Wege von einem Startknoten zu allen anderen Knoten in einem gerichteten Graphen mit nichtnegativen Kantengewichten berechnet. Verwende dabei die folgende Signatur:

def dijkstra(graph, start):

Für die Darstellung des Graphen kannst Du ein Dictionary verwenden, wobei die Schlüssel die Knoten und die Werte die benachbarten Knoten und die entsprechenden Kantenlängen sind. Ein Beispiel für einen Graphen wäre:

{'A': {'B': 1, 'C': 4}, 'B': {'C': 2, 'D': 5}, 'C': {'D': 1}, 'D': {}}

. Der Algorithmus soll eine Dictionary zurückgeben, das die kürzesten Distanzen vom Startknoten zu jedem anderen Knoten enthält.

Lösung:

Um den Dijkstra-Algorithmus zu implementieren, folgen wir diesen Schritten:

• Initialisiere die Distanz zu allen Knoten als unendlich, außer dem Startknoten, dessen Distanz gleich 0 ist.
• Verwende eine Prioritätswarteschlange, um den Knoten mit der aktuell kürzesten Distanz auszuwählen.
• Aktualisiere die Distanzen zu den benachbarten Knoten dieses Knotens.
• Wiederhole den Prozess, bis alle Knoten besucht wurden.
• Gib die kürzesten Distanzen zu jedem Knoten zurück.

Hier ist der Python-Code zur Implementierung des Dijkstra-Algorithmus:

import heapq

def dijkstra(graph, start):    # Initialisiere die Distanzen zu allen Knoten als unendlich    distances = {node: float('inf') for node in graph}    # Setze die Distanz zum Startknoten auf 0    distances[start] = 0    # Initialisiere die Prioritätswarteschlange mit dem Startknoten    priority_queue = [(0, start)]        while priority_queue:        # Wähle den Knoten mit der kürzesten Distanz        current_distance, current_node = heapq.heappop(priority_queue)                # Falls die aktuelle Distanz größer ist als die gespeicherte Distanz, ignoriere diesen Eintrag        if current_distance > distances[current_node]:            continue                # Aktualisiere die Distanzen der Nachbarn        for neighbor, weight in graph[current_node].items():            distance = current_distance + weight            # Falls eine kürzere Distanz gefunden wird, aktualisiere sie            if distance < distances[neighbor]:                distances[neighbor] = distance                heapq.heappush(priority_queue, (distance, neighbor))        return distances

Ein Beispiel für die Verwendung dieser Funktion mit dem gegebenen Graphen wäre:

graph = {'A': {'B': 1, 'C': 4}, 'B': {'C': 2, 'D': 5}, 'C': {'D': 1}, 'D': {}}

start_node = 'A'

distances = dijkstra(graph, start_node)

print(distances)

Das wird die kürzesten Distanzen vom Startknoten 'A' zu allen anderen Knoten im Graphen ausgeben. Du wirst folgendes Ergebnis erhalten:

{'A': 0, 'B': 1, 'C': 3, 'D': 4}

Jeder Wert in dem Dictionary repräsentiert die kürzeste Entfernung von 'A' zu dem jeweiligen Knoten.

b)

Leite die Komplexität des Dijkstra-Algorithmus mathematisch her und beschreibe, unter welchen Bedingungen der Algorithmus optimal läuft. Berücksichtige dabei die Verwendung einer Prioritätswarteschlange.

Lösung:

Der Dijkstra-Algorithmus berechnet die kürzesten Wege in einem Graphen mit nichtnegativen Kantengewichten. Die Komplexität des Algorithmus hängt maßgeblich von der verwendeten Datenstruktur zur Verwaltung der Prioritätswarteschlange ab. Hier leiten wir die Komplexität mathematisch her und erläutern die Bedingungen, unter denen der Algorithmus optimal läuft.

Mathematische Herleitung der Komplexität:

• Initialisierung: Die Initialisierung der Distanzen für alle Knoten auf unendlich (außer dem Startknoten) benötigt \(O(V)\)-Zeit, wobei \(V\) die Anzahl der Knoten im Graphen ist.
• Verwendung einer Prioritätswarteschlange: Bei jeder Iteration wählen wir den Knoten mit der kürzesten Distanz aus der Prioritätswarteschlange aus. Dies geschieht effizient mit einer Heap-Datenstruktur (z.B. Min-Heap).
• Heap-Operationen: Einfüge- und Extrahiervorgänge (push und pop) auf einem Heap benötigen jeweils \(O(\log V)\)-Zeit.
• Schleifendurchläufe: Jeder Knoten wird genau einmal zur Prioritätswarteschlange hinzugefügt und einmal entfernt, was \(O(V)\)-Extraktionen mit je \(O(\log V)\)-Zeit ergibt. Dies führt zu einer Gesamtzeit von \(O(V \, \log V)\) für die Extraktionen.
• Kantenbearbeitung: Jede Kante im Graphen wird genau einmal auf Lockerung überprüft. Die Lockerungsoperation (Aktualisieren der Distanz und Einfügen in die Warteschlange) erfordert \(O(\log V)\)-Zeit. Da jede Kante einmal bearbeitet wird, führt dies zu \(O(E \, \log V)\)-Operationen, wobei \(E\) die Anzahl der Kanten ist.

Die Gesamtlaufzeit des Dijkstra-Algorithmus ergibt sich durch die Kombination der obigen Operationen:

Gesamtlaufzeit: \[O(V \, \log V) + O(E \, \log V) = O((V + E) \, \log V)\]

Bedingungen für optimale Laufzeit:

• Sparse Graphen: Der Algorithmus läuft optimal in sparse Graphen, also Graphen, bei denen \(E \approx V\) ist. In dichten Graphen, bei denen \(E\) quadratisch in \(V\) sein kann, wird die Laufzeit weniger effizient.
• Effiziente Implementierung der Prioritätswarteschlange: Die Verwendung von effizienten Datenstrukturen wie Fibonacci-Heaps kann die amortisierte Laufzeit für Einfüge- und Extraktionen weiter reduzieren. Beispielsweise kann mit einem Fibonacci-Heap die amortisierte Zeit für eine Extraktion auf \(O(\log V)\) reduziert werden, jedoch auf Kosten einer höheren Implementierungskomplexität.
• Vergleich mit A\*: Bei sehr großen Graphen oder navigationsspezifischen Problemen, bei denen der Zielknoten bekannt ist, kann der A\*-Algorithmus besser sein. A\* verwendet heuristische Informationen zum Zielknoten und kann dadurch den Suchraum effizienter einschränken.

Insgesamt beträgt die Zeitkomplexität des Dijkstra-Algorithmus also \(O((V + E) \, \log V)\), und der Algorithmus läuft optimal in sparse Graphen sowie bei Verwendung effizienter Implementierungen der Prioritätswarteschlange.

c)

Implementiere den A*-Algorithmus in Python. Verwende dafür die folgende Signatur:

def astar(graph, start, goal, heuristic):

Du kannst denselben Graphen-Darstellungsansatz wie im Dijkstra-Algorithmus verwenden. Die Heuristik-Funktion wird als zusätzlicher Parameter übergeben und gibt eine Schätzung der Kosten vom aktuellen Knoten zum Zielknoten an. Ein einfaches Beispiel für eine Heuristik-Funktion könnte die euklidische Distanz sein.

Lösung:

Der A\textsuperscript{*}-Algorithmus ist ein weiterer bekannter Algorithmus zur Berechnung der kürzesten Wege, der Heuristiken verwendet, um die Suche effizienter zu gestalten. Im Vergleich zum Dijkstra-Algorithmus, der nur den aktuellen Kostenwert berücksichtigt, verwendet der A\textsuperscript{*}-Algorithmus eine Heuristik-Funktion, um eine Schätzung der verbleibenden Kosten zum Zielknoten zu geben. Hier ist eine Python-Implementierung des A\textsuperscript{*}-Algorithmus:

Für die Implementierung benötigen wir:

• Eine Prioritätswarteschlange zur Auswahl des nächsten Knotens basierend auf den geschätzten Gesamtkosten (aktueller Pfadkostenwert + Heuristikwert).
• Ein Dictionary zur Speicherung der aktuell kürzesten bekannten Pfadkosten zu jedem Knoten.
• Ein Dictionary für die Rückverfolgbarkeit des Pfades.

Hier ist der Python-Code:

import heapq

def astar(graph, start, goal, heuristic):  # Initialisiere die Prioritätswarteschlange mit dem Startknoten  priority_queue = [(0 + heuristic(start, goal), 0, start, None)]  # Initialisiere die Distanzen zum Startknoten auf 0 und alle anderen Knoten auf unendlich  distances = {node: float('inf') for node in graph}  distances[start] = 0  # Dictionary zur Rückverfolgung des Pfades  came_from = {start: None}  while priority_queue:    # Wähle den Knoten mit den niedrigsten geschätzten Gesamtkosten (f = g + h)    estimated_total_cost, current_distance, current_node, parent = heapq.heappop(priority_queue)    # Falls das Ziel erreicht ist, rekonstruiere den Pfad und gib ihn zurück    if current_node == goal:      path = []      while current_node is not None:        path.append(current_node)        current_node = came_from[current_node]      return path[::-1]  # Umkehren des Pfades für die richtige Reihenfolge    # Falls die aktuelle Distanz größer ist als die gespeicherte Distanz, ignoriere diesen Eintrag    if current_distance > distances[current_node]:      continue    # Aktualisiere die Distanzen der Nachbarn und füge sie in die Prioritätswarteschlange ein    for neighbor, weight in graph[current_node].items():      distance = current_distance + weight      if distance < distances[neighbor]:        distances[neighbor] = distance        came_from[neighbor] = current_node        estimated_total_cost = distance + heuristic(neighbor, goal)        heapq.heappush(priority_queue, (estimated_total_cost, distance, neighbor, current_node))  return None  # Falls kein Pfad gefunden wurde, gib None zurück

Beispiel einer Heuristik-Funktion (euklidische Distanz):

import math

def heuristic(a, b):  (x1, y1) = a  (x2, y2) = b  return math.sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2)

Beispiel zur Verwendung des A\textsuperscript{*}-Algorithmus mit einem Graphen:

graph = {  'A': {'B': 1, 'C': 4},  'B': {'C': 2, 'D': 5},  'C': {'D': 1},  'D': {}}

start_node = 'A'

goal_node = 'D'

def simple_heuristic(node, goal_node):  heuristics = {    'A': 4,    'B': 2,    'C': 1,    'D': 0  }  return heuristics[node]  path = astar(graph, start_node, goal_node, simple_heuristic)

print(path)

Dies druckt den kürzesten Pfad von 'A' nach 'D' unter Verwendung der A\textsuperscript{*}-Suche aus.

d)

Erkläre den Unterschied zwischen der Dijkstra- und der A*-Heuristik. Diskutiere in welchen Fällen der A*-Algorithmus möglicherweise schneller ist als der Dijkstra-Algorithmus und wann die Wahl der Heuristik entscheidend ist. Gibt es Situationen, in denen A* keine besseren Ergebnisse als Dijkstra liefert? Begründe Deine Antwort mit Beispielen.

Lösung:

Unterschied zwischen Dijkstra- und A*-Heuristik:

• Dijkstra-Algorithmus: Der Dijkstra-Algorithmus berechnet die kürzesten Wege von einem Startknoten zu allen anderen Knoten in einem Graphen mit nichtnegativen Kantengewichten. Er verwendet eine Prioritätswarteschlange, um den Knoten mit der kürzesten aktuellen Distanz (den geringsten Gesamtkosten) auszuwählen und iterativ zu bearbeiten. Dijkstra berücksichtigt keine zusätzliche Heuristik, nur die tatsächlich berechneten Kosten (d.h. zurückgelegte Weglänge).
• A*-Algorithmus: Der A*-Algorithmus ist eine Erweiterung des Dijkstra-Algorithmus, die eine Heuristik zur Abschätzung der verbleibenden Kosten zum Zielknoten verwendet. Der A*-Algorithmus wählt den Knoten basierend auf der Summe der bisher zurückgelegten Weglänge (Kosten) und der Heuristik (geschätzte verbleibende Kosten). Dadurch versucht er, die Suche effizienter zu gestalten, indem er die Knoten zuerst untersucht, die näher am Ziel zu sein scheinen.

In welchen Fällen ist der A*-Algorithmus möglicherweise schneller?

• Der A*-Algorithmus ist oft schneller, wenn eine geeignete Heuristik verwendet wird, die die Suchrichtung effektiv auf das Ziel lenkt. Dies ist besonders dann der Fall, wenn die Heuristik eine gute Schätzung der geringen verbleibenden Kosten zum Zielknoten gibt.
• In navigationsspezifischen Problemen, wie der Pfadfindung in Karten, kann eine gute Heuristik (z.B. Luftlinienentfernung) dazu führen, dass der A*-Algorithmus deutlich weniger Knoten erforscht und somit schneller ist als der Dijkstra-Algorithmus.
• Ein Beispiel ist die Pfadfindung in einem 2D-Raster. Wenn der Start- und der Zielknoten weit auseinander liegen, kann der A*-Algorithmus mit einer euklidischen oder Manhattan-Distanz-Heuristik effizienter nach kürzeren Wegen suchen.

Wann ist die Wahl der Heuristik entscheidend?

• Die Wahl der Heuristik ist entscheidend für die Effizienz des A*-Algorithmus. Eine geeignete Heuristik sollte zulässige (d.h. nicht überschätzende) und am besten gleichmäßige Schätzungen liefern.
• Eine zu konservative Heuristik (die zu geringe Kosten schätzt) verhält sich ähnlich wie der Dijkstra-Algorithmus und bietet keine wesentlichen Geschwindigkeitsvorteile.
• Eine überoptimistische Heuristik (die zu hohe Kosten schätzt) kann zu inkorrekten Ergebnissen führen, da der Algorithmus dann möglicherweise nicht den wirklich kürzesten Pfad findet.

Gibt es Situationen, in denen A* keine besseren Ergebnisse als Dijkstra liefert?

• Ja, wenn keine geeignete Heuristik vorhanden ist oder wenn die Heuristik schlecht gewählt ist (z.B. wenn sie immer null ist), verhält sich der A*-Algorithmus wie der Dijkstra-Algorithmus. In diesem Fall bieten beide Algorithmen die gleiche Leistung.
• Ein typisches Beispiel ist die kürzeste Wegsuche in einem Netz von Eisenbahngleisen, wenn die Heuristik keiner direkten und zugelassenen Schätzung der reisenden Distanz liefern kann.

Zusammengefasst:

• Der Dijkstra-Algorithmus berechnet die kürzesten Wege ohne Heuristik.
• Der A*-Algorithmus nutzt eine Heuristik, um die Suche zu beschleunigen.
• Der A*-Algorithmus kann schneller sein, wenn eine geeignete Heuristik verwendet wird.
• Die Wahl der Heuristik ist entscheidend für die Effizienz des A*-Algorithmus.
• Ohne eine geeignete Heuristik liefert der A*-Algorithmus keine besseren Ergebnisse als Dijkstra.