Problem des kürzesten Pfades in ungewichteten Graphen
Begriffe: Breitensuche, Tiefensuche, gerichteter Graph
Claude Shannon, einer der Pioniere der Informatik, experimentierte zu Beginn der fünfziger Jahre als einer der Ersten mit künstlicher Intelligenz und baute "Theseus": eine Blechmaus, die auf magnetischen Rädern durch ein Metall-Labyrinth fährt5 . Die kupfernen Schnurrbarthaare des Spielzeugs berührten während seiner Odyssee die Aluminiumwände des Irrgartens. Shannons Maus wurde aus Erfahrung klug und fand nach diversen Fehlversuchen allein aus dem blechernen Gefängnis heraus6 . Die Maus fand zwar aus dem Labyrinth heraus, nutzte aber nicht unbedingt den kürzesten Weg. Das veranlasste Edward Moore 1957 zur Entwicklung eines Algorithmus, der diese Schwäche behebt. Er nannte ihn "Algorithmus A" (nicht zu verwechseln mit dem A*-Algorithmus). Er verwendete als einer der ersten Breitensuche, um in einem ungewichteten Graphen den kürzesten Weg zum Ausgang zu finden.
Zur Unterstützung der Idee der "Froschperspektive" wird der Algorithmus hier als Einstiegsbeispiel auf einen Frosch im Seerosenteich angewendet, der einen Weg sucht, um mit möglichst wenigen Sprüngen zu einem anderen Seerosenblatt zu kommen. Zunächst muss diese Situation als Graph modelliert werden. Dabei stellen die Blätter die Knoten des Graphen dar, eine Kanten gibt an, dass der Frosch direkt zu diesem Blatt springen kann. Bei der Modellierung muss die maximale Sprungweite des Frosches berücksichtigt werden.
Im Graphentester fügt man alle Kanten ein, von denen man vermutet, dass sie kürzer als die maximale Sprungweite sein könnten. An Start- und Endpunkt des schwarzen Balkens setzt man auch Knoten und verbindet sie mit einer Kante. Dann stellt man vorübergehend auf gewichtete Kanten und lässt automatisch alle Entfernungen bestimmen. Dann löscht man zu lange Kanten und deaktiviert die Gewichtung wieder. In der unplugged-Version muss man die Kantenlängen mit einem Lineal messen.
5 Claude Shannon demonstrates "Theseus" Machine Learning @ Bell Labs, https://www.youtube.com/watch?v=_9_AEVQ_p74 (abgerufen Sep. 2020)
6 Das Leben des Seltsamen, Frank Thadeusz in Spiegel online vom 02.11.2009,https://www.spiegel.de/spiegel/a-658498.html (abgerufen Sep. 2020)
Unterrichtsverlauf: Herunterladen [odt][298 KB]
Weiter zu Problem des kürzesten Pfades in gewichteten Graphen