Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- faecher:informatik:oberstufe:graphen:zpg:kuerzeste_pfade:kpfad_kantenzahl:start [21.11.2022 18:08] – [Quacki der Frosch] Frank Schiebel
+++ faecher:informatik:oberstufe:graphen:zpg:kuerzeste_pfade:kpfad_kantenzahl:start [29.08.2024 14:32] (aktuell) – Marco Kuemmel
@@ Zeile 14: / Zeile 14: @@
 Hilf ihm bei der Antwort! Dabei muss die maximale Sprungweite (schwarzer Balken im Bild)
 berücksichtigt werden. Die Entfernung wird immer von Mitte zur Mitte der Blätter gemessen.
+----
+{{:aufgabe.png?nolink  |}}
+=== (A1) Modellierung als Graph ===
+Öffne im Graphentester die Datei ''03_routenplanung/01_seerosenteich.csv''. Sie enthält eine Grafik des Teichs. Du kannst den Graphen im Bearbeitungsmodus des Graphentesters direkt auf den Teich zeichnen.
+++++ Lösung |
+{{ :faecher:informatik:oberstufe:graphen:zpg:kuerzeste_pfade:kpfad_kantenzahl:lsg_teich_graph.png?400 |}}
+++++
+-----
+<callout type="warning" icon="true">
+Problem: Kürzeste Entfernung in ungewichteten Graphen\\
+\\
+  * **Eingabe:** Ein Graph und ein Startknoten
+  * **Ausgabe:** Die Entfernung in der Einheit "Kanten" zwischen dem Startknoten und jedem Knoten des Graphen.
+</callout>
+{{:aufgabe.png?nolink  |}}
+=== (A2) Angepasste Breitensuche ===
+Das Problem kann man mit einer "angepassten Breitensuche" lösen. Wie?
+  * Schreibe den Algorithmus für die Breitensuche als Pseudocode auf.((Du kannst [[faecher:informatik:oberstufe:graphen:zpg:kuerzeste_pfade:traversierungen:start#implementation|hier]] spicken, wenn du es vergessen hast))
+  * Was kannst du ändern, um dir die "Ebenenweise" Bearbeitung der Knoten bei der Breitensuche zunutze zu machen, um den Abstand jedes Knotens vom Startknoten zu ermitteln?
+++++ Hilfestellung |
+Wie ergibt sich die Anzahl der notwendigen Sprünge zu einem Blatt, wenn man weiß, dass man
+zu einem benachbarten Blatt fünf Sprünge (n Sprünge) braucht? Formuliere diese Aussage auch
+mit Knoten und Kanten.
+++++
+----
+{{:aufgabe.png?nolink  |}}
+=== (A3) Implementation ===
+Implementiere den Algorithmus der erweiterten Breitensuche (Algorithmus von Mooore) im Graphentester.
+<btn type="info">[[faecher:informatik:oberstufe:graphen:zpg:hilfekarten:start|Hilfe Grafentester]]</btn>
+++++ Lösungsvorschlag |
+<code java>
+public void fuehreAlgorithmusAus() {
+    gr = getGraph();
+    for(Knoten k : gr.getAlleKnoten()) {
+            k.setWert(Double.POSITIVE_INFINITY);
+    }
+    info("Setze alle Entfernungen auf unendlich");
+    Queue<Knoten> q = new LinkedList<>();
+    q.add(getStartKnoten());
+    getStartKnoten().setMarkiert(true);
+    getStartKnoten().setWert(0);
+    info("  - Markiere und reihe ein: " + getStartKnoten().getInfotext());
+    step();
+    while(!q.isEmpty()) {
+        Knoten v = q.remove();
+        v.setFarbe(3);
+        v.setBesucht(true);
+        info("Bearbeite " + v.getInfotext());
+        step();
+        for(Knoten w: gr.getNachbarknoten(v)) {
+            if(!w.isMarkiert()) {
+                info("  - Markiere und reihe ein: " + w.getInfotext());
+                w.setMarkiert(true);
+                w.setWert(v.getIntWert()+1);
+                q.add(w);
+                step();
+                info("  - Markiere Kante von " + v.getInfotext() + " nach " + w.getInfotext());
+                gr.getKante(v,w).setMarkiert(true);
+            }
+        }
+    }
+}
+</code>
+++++
+----
+{{ :faecher:informatik:oberstufe:graphen:zpg:kuerzeste_pfade:kpfad_kantenzahl:auswahl_008.png?400&nolink|}}
+{{:aufgabe.png?nolink  |}}
+=== (A4) ===
+Für viele Anwendungen verwendet man **gerichtete** Graphen,
+d.h. die Kanten haben eine Richtung (z.B. bei einem
+Stadtplan mit Einbahnstraßen). Die Kanten dürfen dann nur
+in der vorgegebenen Richtung durchlaufen werden.
+  * Bestimme die Entfernungen in nebenstehendem Graphen vom markierten Knoten aus.
+  * Entscheide, ob der Algorithmus verändert werden muss, um auf gerichtete Graphen angewendet werden zu können.
+Du kannst deine Ergebnisse im Graphentester nachvollziehen, wenn du den Graph ''03_routenplanung/01_einbahnstrassen.csv'' lädst.