Pro­blem des kür­zes­ten Pfa­des in un­ge­wich­te­ten Gra­phen

Be­grif­fe: Brei­ten­su­che, Tie­fen­su­che, ge­rich­te­ter Graph

Clau­de Shan­non, einer der Pio­nie­re der In­for­ma­tik, ex­pe­ri­men­tier­te zu Be­ginn der fünf­zi­ger Jahre als einer der Ers­ten mit künst­li­cher In­tel­li­genz und baute "The­seus": eine Blech­maus, die auf ma­gne­ti­schen Rä­dern durch ein Me­tall-La­by­rinth fährt⁵ . Die kup­fer­nen Schnurr­bart­haa­re des Spiel­zeugs be­rühr­ten wäh­rend sei­ner Odys­see die Alu­mi­ni­um­wän­de des Irr­gar­tens. Shan­nons Maus wurde aus Er­fah­rung klug und fand nach di­ver­sen Fehl­ver­su­chen al­lein aus dem ble­cher­nen Ge­fäng­nis her­aus⁶ . Die Maus fand zwar aus dem La­by­rinth her­aus, nutz­te aber nicht un­be­dingt den kür­zes­ten Weg. Das ver­an­lass­te Ed­ward Moore 1957 zur Ent­wick­lung eines Al­go­rith­mus, der diese Schwä­che be­hebt. Er nann­te ihn "Al­go­rith­mus A" (nicht zu ver­wech­seln mit dem A*-Al­go­rith­mus). Er ver­wen­de­te als einer der ers­ten Brei­ten­su­che, um in einem un­ge­wich­te­ten Gra­phen den kür­zes­ten Weg zum Aus­gang zu fin­den.

Zur Un­ter­stüt­zung der Idee der "Frosch­per­spek­ti­ve" wird der Al­go­rith­mus hier als Ein­stiegs­bei­spiel auf einen Frosch im See­ro­sen­teich an­ge­wen­det, der einen Weg sucht, um mit mög­lichst we­ni­gen Sprün­gen zu einem an­de­ren See­ro­sen­blatt zu kom­men. Zu­nächst muss diese Si­tua­ti­on als Graph mo­del­liert wer­den. Dabei stel­len die Blät­ter die Kno­ten des Gra­phen dar, eine Kan­ten gibt an, dass der Frosch di­rekt zu die­sem Blatt sprin­gen kann. Bei der Mo­del­lie­rung muss die ma­xi­ma­le Sprung­wei­te des Fro­sches be­rück­sich­tigt wer­den.

Im Gra­phen­tes­ter fügt man alle Kan­ten ein, von denen man ver­mu­tet, dass sie kür­zer als die ma­xi­ma­le Sprung­wei­te sein könn­ten. An Start- und End­punkt des schwar­zen Bal­kens setzt man auch Kno­ten und ver­bin­det sie mit einer Kante. Dann stellt man vor­über­ge­hend auf ge­wich­te­te Kan­ten und lässt au­to­ma­tisch alle Ent­fer­nun­gen be­stim­men. Dann löscht man zu lange Kan­ten und de­ak­ti­viert die Ge­wich­tung wie­der. In der un­plug­ged-Ver­si­on muss man die Kan­ten­län­gen mit einem Li­ne­al mes­sen.

⁵ Clau­de Shan­non de­mons­tra­tes "The­seus" Ma­chi­ne Learning @ Bell Labs, https://​www.​youtube.​com/​watch?​v=_​9_​AEVQ_​p74 (ab­ge­ru­fen Sep. 2020)

⁶ Das Leben des Selt­sa­men, Frank Tha­de­usz in Spie­gel on­line vom 02.11.2009,https://​www.​spie­gel.​de/​spie­gel/​a-​658498.​html (ab­ge­ru­fen Sep. 2020)

Un­ter­richts­ver­lauf: Her­un­ter­la­den [odt][298 KB]

Wei­ter zu Pro­blem des kür­zes­ten Pfa­des in ge­wich­te­ten Gra­phen