Das Problem des kürzesten Weges – Lösung

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

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

      Hinweis: A-D-C-F: 15, A-D-C-E-F: 14, A-D-E-F: 13

   2. Durch Ausprobieren aller (!) möglichen Wege. Sonst könnte es immer noch einen kürzeren Weg geben.

2. Suche alle Wege, die bei A beginnen und die jeden Knoten höchstens einmal besuchen. Berechne für jeden dieser Wege die Entfernung von A bis F.

3. 1. bei 3 Knoten: 2 Wege

   2. bei 4 Knoten: 1+2+2 = 5 Wege

   3. bei 5 Knoten: 1+5+5+5 = 16 Wege

   4. bei 6 Knoten: 1+16+16+16+16 = 1+4•16 = 65 Wege

   5. z.B.: bei 7 Knoten: 1+5•65 = 326 Wege

      bei 8 Knoten: 1+5•326 = 1957 Wege

      bei 9 Knoten: 1+5•1957 = 13.700 Wege

      bei 10 Knoten: 1+5•13.700 = 109.601 Wege

4. Ameisenregeln:

   

5. 1. 

      

   2. Kürzester Weg: A-B-E-F

   3. Weil alle Ameisen gleich schnell laufen und sie sich immer auf alle möglichen Wege aufteilen. Sie probieren also alle möglichen Wege aus. Allerdings nicht nacheinander, so wie wir das auf dem Papier machen würden, sondern gleichzeitig. Die Ameisen die zuerst am Ziel ankommen haben den schnellsten Weg gefunden. Es kann keinen schnelleren Weg geben.

   4. Ja, sie würden beide kürzesten Wege finden. Bsp.: A-B-F und A-D-C-F sind beide 15 Einheiten lang. Beide Trupps kommen gleichzeitig in F an.

      

6. Dijkstra-Algorithmus

   1. 1. 

         Die kürzeste Entfernung von Knoten A zu Knoten Z beträgt 13 und führt über den Weg A-C-D-E-G-H-Z.

      Man erkennt, dass der Algorithmus die kürzesten Entfernungen zu allen Knoten ermittelt:

      

7. Kürzester Weg von A zu allen anderen Knoten:

   

8. (a) beinhaltet auch (b)

   

9. Anna folgt über einen Zwischenschritt Bela, Daria, Emil, Hanna. Sie folgt über 2 Zwischenschritte Johann, Kevin, Giorgio.

   Es gibt niemanden, dem sie nicht indirekt folgt. (D.h. sie folgt jedem – zumindest indirekt.)

   Hinweis: Es kann in den Lösungen zu unterschiedlichen Wegmarkierungen kommen. Die 'Entfernung' ist aber in allen Lösungen gleich.

   

10. Die Antworten werden direkt dort auf den Internet-Seiten angezeigt.

11. 1. Individuell

    2. Der A*-Algorithmus findet den kürzesten Weg schneller, weil er die vermutete Entfernung berücksichtigt (z.B. die Luftlinienentfernung).

12. 1. Individuell, siehe Internet-Seiten

    2. Individuell, siehe Internet-Seiten

    3. Der A*-Algorithmus findet den kürzesten Weg schneller, weil er die vermutete Entfernung berücksichtigt (z.B. die Luftlinienentfernung).

Das Problem des kürzesten Weges – Lösung: Herunterladen [odt][273 KB]

Das Problem des kürzesten Weges – Lösung: Herunterladen [pdf][264 KB]

Weiter zu Präsentationen