Das Pro­blem des kür­zes­ten Weges – Di­jk­s­tra und die Amei­sen

Gra­phen sind den SuS aus IMP-Ma­the­ma­tik Klas­se 8 be­reits ge­läu­fig. Vor­aus­set­zung für die­ses Ka­pi­tel sind aber le­dig­lich die Be­grif­fe Kno­ten und Kante.

Als Ein­stieg eig­net sich eine Stra­ßen­kar­te, ver­bun­den mit dem Auf­trag, den kür­zes­ten Weg von einem Ort zu einem an­de­ren zu fin­den (siehe Prä­sen­ta­ti­on). Dabei kann the­ma­ti­siert wer­den:

• Die Länge der ge­zeich­ne­ten Stra­ßen muss nicht der tat­säch­li­chen Länge ent­spre­chen.
• Der Graph kann als Mo­dell der Wirk­lich­keit ge­se­hen wer­den, und damit die Pro­blem­stel­lung wei­ter ver­ein­fa­chen. Alle Dinge, die nicht zur Lö­sung des Pro­blems not­wen­dig sind, wer­den weg­ge­las­sen. Wirk­lich­keit → Stra­ßen­kar­te → Graph.
• Jede Stra­ßen­kar­te kann als Graph ge­zeich­net wer­den. Dabei ist jede Stra­ßen­kreu­zung als Kno­ten zu be­trach­ten, auch wenn sich dort keine Ort­schaft be­fin­det.
• Die Suche nach dem kür­zes­ten bzw. dem schnells­ten Weg un­ter­schei­den sich nicht. Der Un­ter­schied liegt nur in der Ein­heit der Kan­ten­be­schrif­tung (z.B. km, min).

Nach­fol­gend wird das Pro­blem auf dem Ar­beits­blatt struk­tu­riert be­trach­tet.

In Auf­ga­be 1 wird der kür­zes­te Weg in zwei über­sicht­li­chen Gra­phen ge­sucht. Die Frage, wie man si­cher sein kann, dass es kei­nen kür­ze­ren Weg gibt, lässt sich bei dem ers­ten Gra­phen ein­fach durch Auf­schrei­ben aller mög­li­chen Wege be­ant­wor­ten. Bei dem zwei­ten Gra­phen wer­den die meis­ten SuS ar­gu­men­tie­ren, dass ihr Weg der kür­zes­te sein muss. Falls ei­ni­ge Schü­ler nicht auf ABEF (12) kom­men, son­dern auf z.B. ADCF (15), ADCEF (14) oder ADEF (13), er­ken­nen sie un­mit­tel­bar, wie leicht man vom ei­ge­nen Er­geb­nis über­zeugt ist und den­noch falsch liegt. Bei die­sem zwei­ten Gra­phen ist die Brute-Force-Me­tho­de, näm­lich die Länge aller Wege zu er­mit­teln, sehr viel schwie­ri­ger, den­noch könn­ten sich man­che SuS her­aus­ge­for­dert füh­len, alle Wege zu fin­den.

In Auf­ga­be 2 wird de­fi­niert, was genau die Brute-Force-Me­tho­de zum Fin­den des kür­zes­ten Weges be­inhal­tet, näm­lich:

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

In Auf­ga­be 3 er­mit­teln die SuS nun die An­zahl aller mög­li­chen Wege in einem voll­stän­di­gen Graph, die bei A be­gin­nen und bei Z enden:

3 Kno­ten:

2 Wege

4 Kno­ten:

Z kann über drei Wege er­reicht wer­den:

di­rekt von A, von B kom­mend, von C kom­mend.

Also gibt es 1+2+2 = 5 ver­schie­de­ne Wege von A nach Z.

5 Kno­ten:

Z kann über 4 ver­schie­de­ne Wege er­reicht wer­den: Di­rekt von A aus, von B, von C, von D kom­mend.

• Um von A nach Z zu ge­lan­gen, gibt es genau einen Weg.
• Um im Graph ABCD von A nach B zu ge­lan­gen, gibt es 5 Wege.
• Um im Graph ABCD von A nach C zu ge­lan­gen, gibt es 5 Wege.
• Um im Graph ABCD von A nach D zu ge­lan­gen, gibt es 5 Wege.

Also gibt es 1+5+5+5 = 16 ver­schie­de­ne Wege von A nach Z.

6 Kno­ten:

1+16+16+16+16 = 1+3•16 = 65 Wege

7 Kno­ten:

...

Bei 100 Koten sind es be­reits 2,56•10¹⁵⁴ ver­schie­de­ne Wege.

In Deutsch­land gibt es zum Ver­gleich 10.848 Ge­mein­den (Stand 2019). Jeder Ort ist mit ei­ni­gen Orten über Wege ver­bun­den, aber nicht allen. Trotz­dem ist leicht ein­sich­tig, dass Zahl der mög­li­chen Wege zwi­schen zwei Orten sehr groß sein kann und die Be­rech­nung aller mög­li­chen Wege (viel) zu lange dau­ert.

Die Brute-Force-Me­tho­de ist also grund­sätz­lich ein guter An­satz, um mit Si­cher­heit den kür­zes­ten Weg zu fin­den, aber in der Rea­li­tät nicht ge­eig­net, um z.B. in einem Na­vi­ga­ti­ons­ge­rät ver­wen­det zu wer­den.

Bevor nun der Di­jk­s­tra-Al­go­rith­mus ein­ge­führt wird, wird das Amei­sen-Ver­hal­ten zum Fin­den des kür­zes­ten Weges be­han­delt, das das Prin­zip sehr an­schau­lich dar­stellt.¹ Das bie­tet neben der Ver­an­schau­li­chung eine Ver­net­zung mit der Bio­lo­gie, sowie die Er­kennt­nis, dass Vor­gän­ge, wenn sie in einen völ­lig an­de­ren Be­reich über­tra­gen wer­den, zu er­staun­li­chen Er­geb­nis­sen füh­ren kön­nen.

Wenn Amei­sen von ihrem Bau zu einer Fut­ter­quel­le lau­fen, dann lau­fen sie nach einer Weile auf dem kür­zes­ten Weg. Sie zei­gen dabei fol­gen­des Ver­hal­ten: sie tei­len sich auf und lau­fen vom Bau aus in alle mög­li­chen Rich­tun­gen los. Kom­men sie zu einem Ab­zweig, dann teilt sich der Trupp auf und in jede mög­li­che Rich­tung lau­fen Amei­sen-Trupps wei­ter. So ver­fah­ren sie an jedem Kno­ten-Punkt, wenn meh­re­re Rich­tun­gen mög­lich sind. Kom­men Amei­sen zu einem Kno­ten-Punkt, an dem be­reits Amei­sen sind, dann wis­sen sie, dass die an­de­ren Amei­sen einen schnel­le­ren Weg ge­fun­den haben (und sie sel­ber kön­nen um­keh­ren). Tref­fen zwei Amei­sen­trupps auf­ein­an­der, wäh­rend sie einen Weg ent­lang­lau­fen, so ist klar, dass die­ser Weg aus bei­den Rich­tun­gen be­trach­tet, un­ge­eig­net ist, um schnell zum Ziel zu kom­men. Beide Trupps kön­nen um­keh­ren und einen an­de­ren Weg su­chen. Die Amei­se, die als erste am Ziel an­kommt, hat den kür­zes­ten Weg ge­fun­den.

Vor­aus­set­zung ist, dass es sehr viele Amei­sen gibt, und dass sich alle gleich schnell be­we­gen.

Die­ser 'Al­go­rith­mus' kommt der Rea­li­tät sehr nahe. In der Natur mar­kie­ren Amei­sen ihre Wege mit Phe­ro­mo­nen. Auf einem sehr lan­gen Weg kom­men sie sel­te­ner ent­lang – weil sie dafür län­ger be­nö­ti­gen – und die Phe­ro­mon-Spur ver­fliegt schnel­ler. Auf einem kur­zen Weg, kom­men Amei­sen häu­fi­ger ent­lang, weil die Ent­fer­nung kür­zer ist, des­halb ist die Phe­ro­mon-Spur in­ten­si­ver.

Auf dem Ar­beits­blatt sind die we­sent­li­chen Ele­men­te des Al­go­rith­mus auf­ge­schrie­ben. Die Fall­un­ter­schei­dung, falls meh­re­re Trupps auf­ein­an­der­tref­fen no­tie­ren die SuS sel­ber. Zu­nächst er­weckt es den Ein­druck, dass es drei ver­schie­de­ne Fälle gibt: (1.) ein Trupp trifft, wäh­rend er sich auf einem Weg be­fin­det auf einen an­de­ren. (3.) ein Trupp kommt zu einem Ort, an dem be­reits Amei­sen sind. (2.) Zwei Trupps kom­men gleich­zei­tig an einem Ort an.

Der Fall 2, bei dem zwei Trupps gleich­zei­tig an einem Ort an­kom­men, be­deu­tet, dass beide Wege gleich schnell sind. Dann ver­ei­nen sich die bei­den Trupps und tei­len sich, wie ein ein­zel­ner Trupp, auf die ver­blei­ben­den Wege auf. Daher muss die­ser Fall nicht ge­son­dert be­trach­tet wer­den.

Der Fall 3 kann gar nicht auf­tre­ten (ob­wohl er zur Er­klä­rung des Ver­hal­tens als we­sent­lich er­scheint). Wenn ein Trupp zu einem Ort kommt, dann teilt er sich auf und läuft auf allen mög­li­chen Wegen wei­ter, also auch auf dem Weg, auf dem die lang­sa­me­ren Amei­sen ge­ra­de an­mar­schie­ren, und damit han­delt es sich um Fall 1.

In Auf­ga­be 3 si­mu­lie­ren die SuS das Amei­sen-Ver­hal­ten Schritt für Schritt. Das kann zu­nächst ge­mein­sam an der Tafel be­gon­nen wer­den und dann von den SuS selbst­stän­dig zu Ende ge­führt wer­den.

Die Frage, wie man das Amei­sen-Ver­hal­ten in einen com­pu­ter­taug­li­chen Al­go­rith­mus über­füh­ren kann, führt zum Di­jk­s­tra-Al­go­rith­mus.

Hin­weis: Der Amei­sen-Al­go­rith­mus ist nur zur Ver­an­schau­li­chung ge­dacht, re­le­vant ist der Di­jk­s­tra-Al­go­rith­mus.

Die SuS ana­ly­sie­ren zu­nächst den vor­ge­ge­be­nen Al­go­rith­mus, indem sie ihn auf einen ein­fa­chen Gra­phen an­wen­den. Das kann ge­mein­sam an der Tafel er­fol­gen oder in Klein­grup­pen.

Hin­weis:

Beim Über­gang vom Amei­sen­ver­hal­ten zum Di­jk­s­tra-Al­go­rith­mus kön­nen ei­ni­ge Schü­ler Schwie­rig­kei­ten haben, weil die Al­go­rith­men nicht exakt gleich sind: Die Amei­sen lau­fen alle gleich­zei­tig. Es gibt sehr viele Amei­sen, die gleich­zei­tig in alle Rich­tun­gen lau­fen. Der Di­jk­s­tra-Al­go­rith­mus hin­ge­gen wer­tet immer nur einen Kno­ten aus und be­stimmt die Ent­fer­nun­gen zu den Nach­bar­kno­ten. Dabei kann es durch­aus vor­kom­men, dass man zu­nächst zu große Zah­len bei einem Kno­ten ein­trägt. Das pas­siert bei den Amei­sen nicht, da den Amei­sen schon un­ter­wegs an­de­re Amei­sen ent­ge­gen­kom­men. Daher tritt der Ar­beits­schritt des Ver­glei­chens mit den schon ein­ge­tra­ge­nen Wer­ten und ggf. An­pas­sung des bis­her bes­ten Weges bei den Amei­sen über­haupt nicht auf. Man kann der Ver­wir­rung vor­beu­gen, indem man dar­auf hin­weist, dass Di­jk­stras Al­go­rith­mus auf der prin­zi­pi­el­len Idee des Amei­sen­ver­hal­tens auf­baut, al­ler­dings so ge­stal­tet ist, dass er sinn­voll auf einem Com­pu­ter aus­ge­führt wer­den kann. Even­tu­ell kann man mit den SuS die Un­ter­schie­de zwi­schen bei­den Al­go­rith­men her­aus­ar­bei­ten.

Beide Al­go­rith­men lie­fern eine Baum-Struk­tur, nach­dem die un­brauch­ba­ren Wege ent­fernt bzw. als un­brauch­bar mar­kiert wur­den. Die­ser Baum zeigt, be­gin­nend bei der Wur­zel (Start­ort), die kür­zes­ten Wege zu allen an­de­ren Orten.

Hin­wei­se zum Di­jk­s­tra-Al­go­rith­mus:

Um die Dar­stel­lung mög­lichst über­schau­bar zu hal­ten und Red­un­danz zu ver­mei­den, wurde bei der Be­schrei­bung des Di­jk­s­tra-Al­go­rith­mus auf den Ein­trag der un­end­li­chen Ent­fer­nung an jedem Kno­ten zu Be­ginn ver­zich­tet. Eben­so auf den Ein­trag des je­wei­li­gen Vor­gän­ger-Kno­tens. Wenn man mehr Nähe zu der pro­gramm­tech­ni­schen Um­set­zung her­stel­len möch­te, kann man z.B. die re­le­van­ten Wege als Pfeil dar­stel­len (ge­rich­te­te Kan­ten). Al­ter­na­tiv kann an jeden Kno­ten auch zu­sätz­lich der Vor­gän­ger­kno­ten ver­merkt wer­den.

Grund­sätz­lich ist der Di­jk­s­tra-Al­go­rith­mus dann zu Ende, wenn es keine nicht­mar­kier­ten Kno­ten mehr gibt. Damit fin­det der Al­go­rith­mus die kür­zes­ten Wege vom Start-Kno­ten zu allen an­de­ren Kno­ten. Bei der Suche des kür­zes­ten Weges vom Start zum Ziel, kann man den Di­jk­s­tra- Al­go­rith­mus vor­zei­tig be­en­den, näm­lich so­bald der ak­tu­el­le Kno­ten gleich dem Ziel­kno­ten ist.

Der Di­jk­s­tra-Al­go­rith­mus lie­fert nur dann den kür­zes­ten Weg, wenn die die Kan­ten­ge­wich­te po­si­tiv sind. Da die SuS wahr­schein­lich nicht auf die Idee von ne­ga­ti­ven Kan­ten­ge­wich­ten kom­men, muss das nicht wei­ter the­ma­ti­siert wer­den.

In Auf­ga­be 2 ste­hen zwei Gra­phen zur An­wen­dung des Al­go­rith­mus zur Ver­fü­gung. Man kann zu­sätz­lich die bei­den Gra­phen des letz­ten Ar­beits­blat­tes ver­wen­den und damit ggf. Unter­schiede zum Amei­sen­ver­hal­ten her­aus­ar­bei­ten. Ein zu­sätz­li­cher kom­ple­xe­rer Graph (2(c)) ist op­tio­nal und etwas her­aus­for­dernd.

In Auf­ga­be 3 wird ein Stra­ßen­netz dar­ge­stellt, in dem 'Ein­bahn­stra­ßen' ent­hal­ten sind.

Der Al­go­rith­mus kann wie ge­wohnt aus­ge­führt wer­den, es müs­sen le­dig­lich die Rich­tun­gen der Pfei­le be­ach­tet wer­den.

Hin­weis:

Bei ge­rich­te­ten Gra­phen sind die Kan­ten als Pfei­le dar­ge­stellt, die an­ge­ben, in wel­che Rich­tung die Be­zie­hung gilt. Dies kann als 'Ein­bahn­stra­ße' in­ter­pre­tiert wer­den. Gehen die Pfei­le in beide Rich­tun­gen, gilt auch die Be­zie­hung in beide Rich­tun­gen. Bei un­ge­rich­te­ten Gra­phen, gehen die Pfei­le immer in beide Rich­tun­gen und wer­den daher weg­ge­las­sen. Die Kante wird als Linie dar­ge­stellt. Als wei­te­re Dif­fe­ren­zie­rung kann die Dar­stel­lung eines ge­rich­te­ten bzw. eines un­ge­rich­te­ten Gra­phen als Ta­bel­le the­ma­ti­siert wer­den.

In Auf­ga­be 4 wer­den kür­zes­te Wege über­tra­gen auf Be­zie­hun­gen in so­zia­len Netz­wer­ken.

Die Auf­ga­ben 5-7 ste­hen zur Dif­fe­ren­zie­rung oder Er­gän­zung zur Ver­fü­gung.

In Auf­ga­be 5 wird in einem Tool des Lehr­stuhls M9 der TU Mün­chen der Di­jk­s­tra-Al­go­rith­mus Schritt für Schritt aus­ge­führt und er­klärt². Es sind leich­te Kon­troll­fra­gen zu be­ant­wor­ten. Unter 'Wei­te­res' wer­den wei­te­re Pro­blem­stel­lun­gen ver­tieft: Wie sieht der (Pseu­do-)Code des Al­go­rith­mus aus? Wie schnell ist der Al­go­rith­mus? Be­rech­net der Al­go­rith­mus wirk­lich die kür­zes­ten Wege? Wie löst man das Pro­blem ne­ga­ti­ver Kan­ten­kos­ten? Wo finde ich noch mehr In­for­ma­tio­nen zu Gra­phal­go­rith­men?

In Auf­ga­be 6 wird der A*-Al­go­rith­mus vi­sua­li­siert. Zwi­schen Start und Ziel kann man zu­nächst ein ver­ti­ka­les Hin­der­nis set­zen und führt dann nach­ein­an­der den Di­jk­s­tra- und der A*-Al­go­rith­mus aus.³

In Auf­ga­be 7 kann der A*- Al­go­rith­mus von den SuS näher un­ter­sucht wer­den.⁴

Zu­satz­ma­te­ri­al

• Eine wei­te­re Seite zum A*-Al­go­rith­mus:

  http://​www.​geo​simu​lati​on.​de/​me­tho­den/​a_​stern_​al­go­rith­mus.​htm⁵

• Sehr an­schau­li­cher Ver­gleich von meh­re­ren kür­zes­ter-Weg-Al­go­rith­men:

  https://​www.​red​blob​game​s.​com/​pa­th­fin­ding/​a-​star/​int​rodu​ctio​n.​html⁶

• Tool zum Tes­ten des Di­jk­s­tra-Al­go­rith­mus: Ma­te­ri­al → Soft­ware → Di­jk­s­tra.jar1⁷

  Tool zum Er­stel­len von Gra­phen: Ma­te­ri­al → Soft­ware → Gra­phE­di­tor.jar

 

¹ Die­ses Vor­ge­hen ori­en­tiert sich an Jens Gal­len­ba­cher: Aben­teu­er In­for­ma­tik. Sprin­ger, Hei­del­berg, 2017

² https://​www-​m9.​ma.​tum.​de/​graph-​al­go­rithms/​spp-​di­jk­s­tra/​in­dex_​de.​html (ab­ge­ru­fen am 28.04.19)

³ https://​qiao.​git­hub.​io/​Pa­th­Fin­ding.​js/​vi­su­al/ (ab­ge­ru­fen am 28.04.19)

⁴ https://​www-​m9.​ma.​tum.​de/​graph-​al­go­rithms/​spp-​a-​star/​in­dex_​de.​html (ab­ge­ru­fen am 28.04.19)

⁵ Ab­ge­ru­fen am 28.04.19

⁶ Ab­ge­ru­fen am 28.04.19

⁷ Er­stellt von Dirk Zech­nal, Tom Schal­ler

 

 

Un­ter­richts­gang: Her­un­ter­la­den [odt][1 MB]

Un­ter­richts­gang: Her­un­ter­la­den [pdf][824 KB]

 

Wei­ter zu Ko­pier­vor­la­gen