Programmiertechnik II SS26, Übung 5

Pro Übung gibt es 20 Punkte. Für die Zulassung zur Prüfung müssen in allen Übungen mindestens 50% der Punkte insgesamt sowie mindestens 25% in jeder einzelnen Übung erzielt werden.

Der Code für diese Aufgabe kann als Repository geklont und lokal kompiliert werden. Es ist dafür nötig, die Git-Submodule zu initialisieren und zu aktualisieren (wichtig‼️):

git submodule update --init

Anschließend kann

make tests

im Projektordner ausgeführt werden, um die Tests zu kompilieren. (Der Code kann unabhängig von den Tests mit make all kompiliert werden.)

Hinweis: Hilfestellung zum Setup des Development-Environments und des Debuggers finden Sie in Übung 1.

Einleitung

Hinweis: Für Sie haben wir relevante Klassen aus der VL in vlib hinterlegt - nutzen und erweitern Sie diese bei Bedarf.

Diese Übung behandelt den A*-Algorithmus, eine Erweiterung von Dijkstra, die z. B. in Navigationssystemen zur Routenberechnung eingesetzt wird. A* ergänzt die bisherigen Pfadkosten um eine Heuristik, also eine Schätzung der verbleibenden Kosten zum Ziel. Dadurch werden vielversprechende Knoten bevorzugt und der Suchraum deutlich reduziert – idealerweise bei O(1)-Berechnung der Heuristik. In dieser Übung verwenden Sie den Algorithmus zum Routing im weltweiten Netz aus Flughäfen und Flugverbindungen.

A* kombiniert die Optimalität von Dijkstra mit der Effizienz einer Greedy-Suche, indem in der Prioritätswarteschlange sowohl die bisherigen Kosten als auch die geschätzte Distanz zum Ziel berücksichtigt werden.

Damit die Optimalität garantiert bleibt, muss die Heuristik:

• zulässig sein: Sie darf die tatsächlichen Restkosten niemals überschätzen.
• konsistent sein: Für jeden Knoten $v$ und jeden Nachfolgeknoten $v'$ von $v$ gilt $h(v)\leq C( v , v' )+h(v')$. Dabei sind $C(v,v')$ die tatsächlichen Kosten, um von $v$ nach $v'$ zu kommen.

Eine zulässige, aber nicht konsistente Heuristik ist mit höherer Laufzeit möglich, würde jedoch in der von uns angestrebten Implementierung zu falschen Ergebnissen führen.

Ablauf des A*-Algorithmus

Eingabe:

• ein gerichteter gewichteter Graph mit ausschließlich positiven Kantengewichten $G=(V,E)$
• ein Startknoten $v_S\in V$
• ein Zielknoten $v_Z\in V$
• eine Heuristik $h(v): V \to \mathbb{R}$

Ausgabe:

• den kürzesten Pfad $P_s=(v_s, ..., v_z)$ von $v_s$ nach $v_z$ als Liste von Knoten, wenn ein Pfad existiert
• einen leeren Pfad $P_s=()$, sonst

Ablauf:

1. Initialisiere eine Menge $V_O$ aller offenen Knoten mit dem Startknoten als einziges Element
2. Initialisiere eine leere Menge $V_C$ aller geschlossenen Knoten
3. Initialisiere eine Map $C: V\to \mathbb{R}$, welche jedem Knoten die bisher bekannten Pfadkosten $g(v)$ vom Start zuordnet.
   • Setze die Kosten aller Knoten auf $+\infty$, außer für den Startknoten - dieser hat Kosten $C(v_s)=g(v_s)=0$
4. Initialisiere eine Map $P: V\to V$, in welcher gespeichert wird, welcher Knoten der Elternknoten eines Knotens ist.
   • Hinweis: Eine Map zwischen den Knoten-Indizes
5. Solange: $V_O \neq \emptyset$
   1. $v_i$ sei der offene Knoten mit den geringsten geschätzten Gesamtkosten $f(v)=g(v)+h(v)$
      • also der Knoten mit der geringsten Summe aus bekannten Kosten $g(v)$ bis zum Knoten und geschätzten Restkosten $h(v)$ bis $v_z$
      • Hinweis: Sie können eine IndexMinPQ nutzen, um die Selektion effizient zu gestalten.
      • Falls $v_i$ der Zielknoten $v_z$ ist, beende und gib den Pfad von $v_s$ nach $v_z$ aus $P$ zurück.
   2. Füge $v_i$ in $V_C$ ein
   3. Für jeden Nachbarn $n_k$ von $v_i$:
      • Wenn $n_k\in V_C$, dann fahre mit der Schleife fort
      • Berechne die Kosten für den Pfad $(v_s,..., v_i, n_k)$
      • Wenn die Kosten geringer sind als die in $C$ hinterlegten Kosten:
        • Aktualisiere die Kosten für $n_k$ in $C$
        • Setze $P(n_k)=v_i$, also $v_i$ als Elternknoten von $n_k$
        • Füge $n_k$ in $V_O$ ein
6. Falls $v_z$ nicht erreicht wurde, gib einen leeren Pfad zurück

Aufgabe 1: Datenverarbeitung

Zu modifizierende Dateien: src/weighted_struct_digraph.h, src/airport.cpp, src/airport.h

Aufgabe 1.1 (2p): Implementieren Sie in src/weighted_struct_digraph.h die Klasse WeightedStructDigraph, eine Erweiterung von SymbolDigraph (siehe src/vlib/symbol_digraph.h), in der das Flugnetz gespeichert werden soll:

• Knoten sollen den generischen Template-Typ Node haben (z. B. beliebige Structs)
  • entsprechend liefert name_of einen Node zurück statt std::string
• Kanten sind gewichtet (nutzen Sie die Klassen EdgeWeightedDigraph und Edge aus vlib)
  • Implementieren Sie die Methode add_edge, um nach der Konstruktion Kanten im internen Graphen hinzufügen zu können
• Konstruktor mit Parameter Bag zur Initialisierung der Knoten
• Implementieren Sie ansonsten die gleichen Methoden und Operatoren wie SymbolDigraph (siehe auch TODO-Kommentar)

Hinweis: Ihre Structs müssen für einen RBTree die Operatoren <,>,= implementieren.

Aufgabe 1.2 (4p): Implementieren Sie in src/airport.cpp die Methode load_data zum Laden des Graphen sowie das Struct Airport in airport.h mit allen Attributen, die Sie im Laufe dieser Übung benötigen (Name, OpenFlights-airport id, Breiten- und Längengrad, IATA-Code). Die Knoten (Flughäfen) werden aus data/airports.csv und die Kanten aus data/routes.csv geladen. Nutzen Sie die Spalte Time als Kantengewicht.

Hinweis: Die Struktur der Daten ist in data/DATASOURCE.md beschrieben.

Aufgabe 2: A* Algorithmus

Zu modifizierende Dateien: src/a_star.h, src/distances.h, src/routing_cli.cpp

Aufgabe 2.1 (6p): Implementieren Sie den A*-Algorithmus (auf WeightedStructDiGraph) entsprechend dem beschriebenen Ablauf in src/a_star.h. Nutzen Sie als Heuristik in dieser Aufgabe die euklidische Distanz, die Sie in src/distances.h::euclidean implementieren. Beachten Sie die Hinweise zu Heuristiken, um sicherzustellen, dass der Algorithmus korrekt terminiert.

Hinweis: Die Kantengewichte (Route Time) sind in Stunden (h) angegeben. Distanz-basierte Heuristiken liefern zunächst eine räumliche Entfernung (z. B. km oder Grad). Für $f(v)=g(v)+h(v)$ müssen beide Terme in derselben Einheit vorliegen. Rechnen Sie die Distanz-Heuristik daher in eine Zeitschätzung um, z. B. mit $h_{\text{time}}(v)=\frac{\text{Distanz}(v,v_z)}{v_{\max}}$ mit einer konservativen oberen Geschwindigkeitsgrenze $v_{\max} = 900 \frac{km}{h}$, sodass die Heuristik zulässig bleibt.

Aufgabe 2.2 (4p): Schreiben Sie in src/routing_cli.cpp ein CLI, das als Argumente zwei IATA-Codes von Flughäfen erhält und die schnellste Verbindung zwischen den Flughäfen in unseren Daten findet. src/routing_cli.cpp kann mit make routing-compile kompiliert oder mit make routing kompiliert und ausgeführt werden. (Argumente können auch via make routing ARGS="<argument1> <argument2>" übergeben werden.)

• die erste Zeile ist der Pfad als Kette von IATA-Codes, getrennt durch -.
  • falls der Pfad nicht existiert, soll die Ausgabe ein - in dieser Zeile sein.
• die zweite Zeile ist die Reisedauer in h.
  • falls der Pfad nicht existiert, soll die Ausgabe inf für die Reisedauer sein.

Beispiel (CLI):

make routing ARGS="LAX TXL"

Beispiel (Pfad existiert):

LAX-DUS-TXL
19.6579h

Beispiel (Pfad existiert nicht):

-
inf

Implementierungsdetail: Das CLI ist IATA-basiert (Ein- und Ausgabe), intern werden Knoten jedoch über die OpenFlights-airport id identifiziert, da auch data/routes.csv die Kanten über diese IDs referenziert. Hinweis: Sie können die CLI auch mit make routing-compile kompilieren und dann mit ./out/routing LAX TXL selbst ausführen.

Aufgabe 3: Andere Distanzen & Heuristiken

Zu modifizierende Dateien: src/distances.h, A3.md

Das euklidische Distanzmaß ist eine einfache und effektive Heuristik, setzt jedoch eine flache Ebene voraus. Da die Erde ein Ellipsoid ist und sich ihre Oberfläche nicht verzerrungsfrei auf eine Fläche projizieren lässt, ist diese Annahme nur näherungsweise korrekt.

Aufgabe 3.1 (2p): Implementieren Sie drei weitere Distanzmaße für alternative Heuristiken in src/distances.h:

• Geodätische Distanz mittels der Haversine-Formel (Pfad über die Oberfläche eines Ellipsoids)
• Manhattan-Distanz, auch Taxifahrerdistanz oder L1-Norm
• Out-Degree: Je höher der Out-Degree, desto besser, da wir so zu zentralen Hubs fliegen können, die mehr mögliche Verbindungen abbilden

Aufgabe 3.2 (2p): Vergleichen Sie die Laufzeit und Korrektheit verschiedener Heuristiken basierend auf den Distanzmaßen. Vergleichen Sie jeweils die Laufzeit für verschiedene existierende Pfade und Pfade, die im Graphen nicht existieren. Versuchen Sie, Beispiele für Pfade zu finden, in denen die Heuristiken falsche Ergebnisse liefern. Notieren Sie Ihre Ergebnisse in A3.md im Stammverzeichnis Ihres Repositories.

Hinweis: Sie können sich mit Hilfe Ihres CLI eine Sammlung von interessanten Pfaden zusammenstellen. Hinweis: Denken Sie daran, dass die Heuristiken zulässig sein sollen. Hinweis: Die Out-Degree-Distanz ist nicht konsistent. Können Sie einen Fall generieren, in dem der gefundene Weg nicht der kürzeste ist? Hinweis: Die Zeit können Sie auf Linux / macOS mit Hilfe des Kommandozeilenbefehls time oder innerhalb Ihres Codes mit Hilfe von std::chrono messen.

Abgabehinweise

• Bearbeiten Sie die mit // TODO markierten Stellen im Code.
• Für die in der Aufgabenstellung beschriebenen Datentypen und Algorithmen sollen die eigenen bzw. vorgegebenen Implementierungen genutzt werden. Davon abgesehen darf die STL verwendet werden. Notieren Sie sich für das Testatgespräch: Welche Teile der STL könnten theoretisch benutzt werden, um die Aufgaben zu implementieren?
• Korrekte Speicherverwaltung (new/delete, new[]/delete[] oder ggf. Initialisierung im Stack) gehört zur Aufgabenstellung :)
• Die Tests sollen alle grün sein (make tests), sind aber in erster Linie eine Hilfestellung und keine Garantie für volle Punktzahl - dafür gibt es die Testatgespräche.