Zur Haupt­na­vi­ga­ti­on sprin­gen [Alt]+[0] Zum Sei­ten­in­halt sprin­gen [Alt]+[1]

Auf­ga­ben

    1. Er­mitt­le mit dem Di­jk­s­tra-Al­go­rith­mus den kür­zes­ten Weg von A nach Z.

      Graph Dijkstra-Algorithmus

    2. Wel­ches sind die kür­zes­ten Wege von A zu allen an­de­ren Kno­ten?

  2. (a), (b) Er­mitt­le mit dem Di­jk­s­tra-Al­go­rith­mus den kür­zes­ten Weg von A zu allen an­de­ren Kno­ten.

    **(c) Er­mitt­le mit dem Di­jk­s­tra-Al­go­rith­mus den kür­zes­ten Weg von Ka nach Ma.

    Graph Dijkstra-Algorithmus

    1. Ein Ta­xi­fah­rer ver­zwei­felt an den vie­len Ein­bahn­stra­ßen in der Stadt. Für jede Stra­ße hat er sich die Fahr­zeit no­tiert und möch­te sich nun einen Plan ma­chen, wie er am schnells­ten von sei­nem Taxi­stand zum Hotel, zum Markt­platz und zum Rathaus kommt. Hilf ihm.

    2. (Er­mitt­le auch die kür­zes­ten Fahr­zei­ten zu Bahn­hof, Uni, Kino, Stern­war­te und Park.

      Graph Dijkstra-Algorithmus

  4. In so­zia­len Netz­wer­ken kann man an­de­ren Usern fol­gen und an­de­re User kön­nen einem sel­ber fol­gen. Hier sind ei­ni­ge Ju­gend­li­che mit ihren Fol­lo­wer-Be­zie­hun­gen:

    • Anna folgt Char­lot­te, Fiona
    • Bela folgt Char­lot­te, Jo­hann
    • Char­lot­te folgt Bela, Fiona, Daria
    • Daria folgt Char­lot­te, Emil
    • Emil folgt Daria, Fiona, Kevin
    • Fiona folgt Char­lot­te, Emil, Hanna, Daria
    • Gior­gio folgt Emil
    • Hanna folgt Anna, Fiona, Kevin, Gior­gio
    • Jo­hann folgt Bela
    • Kevin folgt Char­lot­te, Emil

    Über wie viele Zwi­schen­schrit­te folgt Anna den an­de­ren Ju­gend­li­chen?

  5. ** Gehe zur Seite: https://​www-​m9.​ma.​tum.​de/​graph-​al­go­rithms/​spp-​di­jk­s­tra/​in­dex_​de.​html1 und be­ar­bei­te (a) 'For­schungs­auf­ga­be 3' und (b) 'Wei­te­res'.

  6. ** Der A*-Al­go­rith­mus (sprich: „A Stern Al­go­rith­mus“)

    Gehe zur Seite: https://​qiao.​git­hub.​io/​Pa­th­Fin­ding.​js/​vi­su­al/2

    1. Pro­bie­re dort den Di­jk­s­tra- und den A*-Al­go­rith­mus aus.

    2. Setze ein Hin­der­nis zwi­schen Start und Ziel­kno­ten. Wie ver­hal­ten sich Di­jk­s­tra- und A*-Al­go­rith­mus nun? Wie be­ur­teilst du das Ver­hal­ten?

  7. ** Der A*-Al­go­rith­mus (sprich: „A Stern Al­go­rith­mus“)

    Öffne die Seite: https://​www-​m9.​ma.​tum.​de/​graph-​al­go­rithms/​spp-​a-​star/​in­dex_​de.​html3

    1. Kli­cke auf den Rei­ter „Be­schrei­bung des Al­go­rith­mus“ und lies die Be­schrei­bung des A* Al­go­rith­mus.

    2. Kli­cke auf den Rei­ter „For­schungs­auf­ga­be 2“ und führe den Al­go­rith­mus Schritt für Schritt aus. Viel­leicht hilft es dir, den­sel­ben Gra­phen mit dem Di­jk­s­tra-Al­go­rith­mus zu be­ar­bei­ten. Dann gehe zu „For­schungs­auf­ga­ben 1“.

    3. Er­klä­re, wel­che Vor­tei­le der A*-Al­go­rith­mus ge­gen­über dem Di­jk­s­tra-Al­go­rith­mus bie­tet.

1 Ab­ge­ru­fen am 28.04.19

2 Ab­ge­ru­fen am 28.04.19

3 Ab­ge­ru­fen am 28.04.19

 

 

Das Pro­blem des kür­zes­ten Weges – Di­jk­s­tra und die Amei­sen: Her­un­ter­la­den [odt][1 MB]

Das Pro­blem des kür­zes­ten Weges – Di­jk­s­tra und die Amei­sen: Her­un­ter­la­den [pdf][523 KB]

 

Wei­ter zu Vor­la­gen Tausch­ord­ner