Das Pro­blem des kür­zes­ten Weges – Lö­sung

1. 1. (I) A-D-C-F: 10

      (II) A-B-E-F: 12

      Hin­weis: A-D-C-F: 15, A-D-C-E-F: 14, A-D-E-F: 13

   2. Durch Aus­pro­bie­ren aller (!) mög­li­chen Wege. Sonst könn­te es immer noch einen kür­ze­ren Weg geben.

2. Suche alle Wege, die bei A be­gin­nen und die jeden Kno­ten höchs­tens ein­mal be­su­chen. Be­rech­ne für jeden die­ser Wege die Ent­fer­nung von A bis F.

3. 1. bei 3 Kno­ten: 2 Wege

   2. bei 4 Kno­ten: 1+2+2 = 5 Wege

   3. bei 5 Kno­ten: 1+5+5+5 = 16 Wege

   4. bei 6 Kno­ten: 1+16+16+16+16 = 1+4•16 = 65 Wege

   5. z.B.: bei 7 Kno­ten: 1+5•65 = 326 Wege

      bei 8 Kno­ten: 1+5•326 = 1957 Wege

      bei 9 Kno­ten: 1+5•1957 = 13.700 Wege

      bei 10 Kno­ten: 1+5•13.700 = 109.601 Wege

4. Amei­sen­re­geln:

   

5. 1. 

      

   2. Kür­zes­ter Weg: A-B-E-F

   3. Weil alle Amei­sen gleich schnell lau­fen und sie sich immer auf alle mög­li­chen Wege auf­tei­len. Sie pro­bie­ren also alle mög­li­chen Wege aus. Al­ler­dings nicht nach­ein­an­der, so wie wir das auf dem Pa­pier ma­chen wür­den, son­dern gleich­zei­tig. Die Amei­sen die zu­erst am Ziel an­kom­men haben den schnells­ten Weg ge­fun­den. Es kann kei­nen schnel­le­ren Weg geben.

   4. Ja, sie wür­den beide kür­zes­ten Wege fin­den. Bsp.: A-B-F und A-D-C-F sind beide 15 Ein­hei­ten lang. Beide Trupps kom­men gleich­zei­tig in F an.

      

6. Di­jk­s­tra-Al­go­rith­mus

   1. 1. 

         Die kür­zes­te Ent­fer­nung von Kno­ten A zu Kno­ten Z be­trägt 13 und führt über den Weg A-C-D-E-G-H-Z.

      Man er­kennt, dass der Al­go­rith­mus die kür­zes­ten Ent­fer­nun­gen zu allen Kno­ten er­mit­telt:

      

7. Kür­zes­ter Weg von A zu allen an­de­ren Kno­ten:

   

8. (a) be­inhal­tet auch (b)

   

9. Anna folgt über einen Zwi­schen­schritt Bela, Daria, Emil, Hanna. Sie folgt über 2 Zwi­schen­schrit­te Jo­hann, Kevin, Gior­gio.

   Es gibt nie­man­den, dem sie nicht in­di­rekt folgt. (D.h. sie folgt jedem – zu­min­dest in­di­rekt.)

   Hin­weis: Es kann in den Lö­sun­gen zu un­ter­schied­li­chen Weg­mar­kie­run­gen kom­men. Die 'Ent­fer­nung' ist aber in allen Lö­sun­gen gleich.

   

10. Die Ant­wor­ten wer­den di­rekt dort auf den In­ter­net-Sei­ten an­ge­zeigt.

11. 1. In­di­vi­du­ell

    2. Der A*-Al­go­rith­mus fin­det den kür­zes­ten Weg schnel­ler, weil er die ver­mu­te­te Ent­fer­nung be­rück­sich­tigt (z.B. die Luft­li­ni­en­ent­fer­nung).

12. 1. In­di­vi­du­ell, siehe In­ter­net-Sei­ten

    2. In­di­vi­du­ell, siehe In­ter­net-Sei­ten

    3. Der A*-Al­go­rith­mus fin­det den kür­zes­ten Weg schnel­ler, weil er die ver­mu­te­te Ent­fer­nung be­rück­sich­tigt (z.B. die Luft­li­ni­en­ent­fer­nung).

Das Pro­blem des kür­zes­ten Weges – Lö­sung: Her­un­ter­la­den [odt][273 KB]

Das Pro­blem des kür­zes­ten Weges – Lö­sung: Her­un­ter­la­den [pdf][264 KB]

Wei­ter zu Prä­sen­ta­tio­nen