Zur Hauptnavigation springen [Alt]+[0] Zum Seiteninhalt springen [Alt]+[1]

Aufgaben

    1. Ermittle mit dem Dijkstra-Algorithmus den kürzesten Weg von A nach Z.

      Graph Dijkstra-Algorithmus

    2. Welches sind die kürzesten Wege von A zu allen anderen Knoten?

  2. (a), (b) Ermittle mit dem Dijkstra-Algorithmus den kürzesten Weg von A zu allen anderen Knoten.

    **(c) Ermittle mit dem Dijkstra-Algorithmus den kürzesten Weg von Ka nach Ma.

    Graph Dijkstra-Algorithmus

    1. Ein Taxifahrer verzweifelt an den vielen Einbahnstraßen in der Stadt. Für jede Straße hat er sich die Fahrzeit notiert und möchte sich nun einen Plan machen, wie er am schnellsten von seinem Taxistand zum Hotel, zum Marktplatz und zum Rathaus kommt. Hilf ihm.

    2. (Ermittle auch die kürzesten Fahrzeiten zu Bahnhof, Uni, Kino, Sternwarte und Park.

      Graph Dijkstra-Algorithmus

  4. In sozialen Netzwerken kann man anderen Usern folgen und andere User können einem selber folgen. Hier sind einige Jugendliche mit ihren Follower-Beziehungen:

    • Anna folgt Charlotte, Fiona
    • Bela folgt Charlotte, Johann
    • Charlotte folgt Bela, Fiona, Daria
    • Daria folgt Charlotte, Emil
    • Emil folgt Daria, Fiona, Kevin
    • Fiona folgt Charlotte, Emil, Hanna, Daria
    • Giorgio folgt Emil
    • Hanna folgt Anna, Fiona, Kevin, Giorgio
    • Johann folgt Bela
    • Kevin folgt Charlotte, Emil

    Über wie viele Zwischenschritte folgt Anna den anderen Jugendlichen?

  5. ** Gehe zur Seite: https://www-m9.ma.tum.de/graph-algorithms/spp-dijkstra/index_de.html1 und bearbeite (a) 'Forschungsaufgabe 3' und (b) 'Weiteres'.

  6. ** Der A*-Algorithmus (sprich: „A Stern Algorithmus“)

    Gehe zur Seite: https://qiao.github.io/PathFinding.js/visual/2

    1. Probiere dort den Dijkstra- und den A*-Algorithmus aus.

    2. Setze ein Hindernis zwischen Start und Zielknoten. Wie verhalten sich Dijkstra- und A*-Algorithmus nun? Wie beurteilst du das Verhalten?

  7. ** Der A*-Algorithmus (sprich: „A Stern Algorithmus“)

    Öffne die Seite: https://www-m9.ma.tum.de/graph-algorithms/spp-a-star/index_de.html3

    1. Klicke auf den Reiter „Beschreibung des Algorithmus“ und lies die Beschreibung des A* Algorithmus.

    2. Klicke auf den Reiter „Forschungsaufgabe 2“ und führe den Algorithmus Schritt für Schritt aus. Vielleicht hilft es dir, denselben Graphen mit dem Dijkstra-Algorithmus zu bearbeiten. Dann gehe zu „Forschungsaufgaben 1“.

    3. Erkläre, welche Vorteile der A*-Algorithmus gegenüber dem Dijkstra-Algorithmus bietet.

1 Abgerufen am 28.04.19

2 Abgerufen am 28.04.19

3 Abgerufen am 28.04.19

 

 

Das Problem des kürzesten Weges – Dijkstra und die Ameisen: Herunterladen [odt][1 MB]

Das Problem des kürzesten Weges – Dijkstra und die Ameisen: Herunterladen [pdf][523 KB]

 

Weiter zu Vorlagen Tauschordner