Zur Haupt­na­vi­ga­ti­on sprin­gen [Alt]+[0] Zum Sei­ten­in­halt sprin­gen [Alt]+[1]

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

Be­grif­fe: ge­wich­te­te Kan­ten, Di­jk­s­tra-Al­go­rith­mus oder Bell­man-Ford-Al­go­rith­mus

Wenn es bei der Be­stim­mung des kür­zes­ten Pfa­des nicht nur um die An­zahl der be­nutz­ten Kan­ten, son­dern auch um deren Ge­wicht geht, muss der Al­go­rith­mus ver­än­dert wer­den. Das Ge­wicht kann dabei die Länge der Stre­cke zwi­schen zwei Punk­ten sein (kür­zes­te Stre­cke) oder auch der Zeit­be­darf (schnells­te Stre­cke).

Dies leis­ten der Di­jk­s­tra-Al­go­rith­mus, der den IMP-Schü­lern schon be­kannt sein müss­te, und der Bell­man-Ford-Al­go­rith­mus.

Di­jk­s­tra-Al­go­rith­mus: In IMP wurde der Al­go­rith­mus an­hand der Amei­sen-Ana­lo­gie (gemäß "Aben­teu­er In­for­ma­tik" von Jens Gal­len­ba­cher) ein­ge­führt. Um auch den IMP-Schü­lern einen an­de­ren Zu­gang zu bie­ten, kann jetzt der Al­go­rith­mus als Er­wei­te­rung des Al­go­rith­mus von Moore an­ge­se­hen wer­den: Man be­hält die Idee bei, dass beim nächs­ten Kno­ten die ak­tu­el­le Ent­fer­nung plus die Länge des Weges dort­hin ein­ge­tra­gen wer­den muss. Al­ler­dings kann es nun sein, dass eine be­reits ein­ge­tra­ge­ne Ent­fer­nung an­ge­passt wer­den muss, da man einen kür­ze­ren Weg ge­fun­den hat. Auch die Ab­ar­bei­tung der ToDo-Liste muss man mo­di­fi­zie­ren. Um si­cher­zu­stel­len, dass man nie einen Kno­ten be­ar­bei­tet, des­sen Ent­fer­nung zum Start­kno­ten nach­träg­lich noch­mals an­ge­passt wird, muss man immer den­je­ni­gen Kno­ten aus der ToDo-Liste aus­wäh­len, der die kür­zes­te Ent­fer­nung zum Start­kno­ten hat. Bei der Im­ple­men­ta­ti­on kann man das er­rei­chen, indem man die ToDo-Liste immer nach auf­stei­gen­den Ent­fer­nun­gen sor­tiert und dann den ers­ten Kno­ten nimmt. Das ist keine ef­fi­zi­en­te Im­ple­men­tie­rung, aber hier am leich­tes­ten zu be­werk­stel­li­gen.

Da die Er­wei­te­rung von Moore zu Di­jk­s­tra nicht so schwie­rig ist, wäre es an die­ser Stel­le mög­lich, die Schü­le­rin­nen und Schü­ler mit dem Quell­text von Moore star­ten und die Er­wei­te­rung des Di­jk­s­tra selbst im­ple­men­tie­ren zu las­sen. Al­ter­na­tiv kann auch der Moore-Al­go­rith­mus selbst aus­ge­hend von tex­tu­el­ler Be­schrei­bung oder Pseu­do­code im­ple­men­tiert wer­den.

Bell­man-Ford-Al­go­rith­mus:

Der Bell­man-Ford-Al­go­rith­mus geht ähn­lich vor. Wenn vom Start­kno­ten zu einem Kno­ten ein Pfad ge­fun­den wurde, wird bei den Nach­bar­kno­ten kon­trol­liert, ob der Weg über die­sen Kno­ten dort­hin kür­zer ist, als der bis­her kür­zes­te Weg. Man ver­sucht dabei aber nicht, die Be­ar­bei­tungs- rei­hen­fol­ge der Kno­ten so zu wäh­len, dass ein schon be­ar­bei­te­ter Kno­ten nicht er­neut be­ar­bei­tet wer­den muss. Statt­des­sen wer­den so viele Durch­gän­ge durch­ge­führt, dass nach­träg­li­che Än­de­run­gen an einem Kno­ten er­neut an alle Fol­ge­kno­ten wei­ter­ge­ge­ben wer­den kön­nen. In einem Durch­gang wird dabei jede Kante ein­mal be­trach­tet. Daher kann man eine Schlei­fe über alle Kan­ten statt einer Schlei­fe über alle Kno­ten ver­wen­den.

Wählt man als An­zahl der Durch­gän­ge die Kno­ten­zahl des Gra­phen, stellt man si­cher, dass die kür­zes­ten Wege zu allen Kno­ten ge­fun­den wur­den. Im un­güns­tigs­ten Fall ver­läuft der längs­te kür­zes­te Weg zu einem Kno­ten über alle an­de­ren Kno­ten. Mehr Zwi­schen­schrit­te sind nicht mög­lich, da es im Nor­mal­fall nicht sinn­voll ist, einen Zy­klus (mehr­fach) zu durch­lau­fen. Nur bei Zy­klen, die ein ne­ga­ti­ves Kan­ten­ge­wicht haben, würde sich die Ge­samt­stre­cke durch den Zy­klus ver­kür­zen. Es würde sich loh­nen den Zy­klus immer wie­der zu durch­lau­fen. Daher er­kennt man diese (ver­bo­te­nen) Zy­klen daran, dass ein wei­te­rer Durch­gang nach Be­en­di­gung des Al­go­rith­mus eine wei­te­re Ver­bes­se­rung der Wege brin­gen würde. Ein­zel­ne Kan­ten mit ne­ga­ti­ven Kan­ten­ge­wich­ten sind aber er­laubt.

Bildquelle: Graphen mit negativen Kantengewichten: Der erste Graph ist nicht zulässig, da der rot markierte Zyklus das Gewicht -1 hat. (eigenes Werk)

Bild­quel­le: Gra­phen mit ne­ga­ti­ven Kan­ten­ge­wich­ten: Der erste Graph ist nicht zu­läs­sig, da der rot mar­kier­te Zy­klus das Ge­wicht -1 hat. (ei­ge­nes Werk) ZPG In­for­ma­tik [CC BY-NC-SA 3.0 DE], aus 2_­un­ter­richts­ver­lauf.odt

Am Ende soll­te auf jeden Fall das Schul­weg­bei­spiel mit dem Al­go­rith­mus aus­ge­wer­tet und mit dem ers­ten Ent­wurf ver­gli­chen wer­den. Man könn­te die Schü­ler auch noch wei­te­re Wege im Mo­dell ein­fü­gen (z.B. den Fried­hof) oder die Ge­wich­tung von Bun­des­stra­ßen oder Fuß­gän­ger­zo­nen im Mo­dell ver­än­dern las­sen und der Aus­wir­kung bei der Be­stim­mung der Wege un­ter­su­chen las­sen. Bei­spie­le mit ge­rich­te­ten Kan­ten oder ne­ga­ti­ven Ge­wich­ten be­fin­den sich im Ord­ner 04_­rou­ten­pla­nung.

Er­gän­zung: Dy­na­mi­sches Rou­ting (Dis­tanz-Vek­tor-Ver­fah­ren)

Die Lauf­zeit des Bell­man-Ford-Al­go­rith­mus ist schlech­ter als die des Di­jk­s­tra-Al­go­rith­mus. Seine große Stär­ke liegt aber darin, dass er auch funk­tio­niert, wenn man jeden Kno­ten als ei­gen­stän­di­gen Ak­teur be­trach­tet, der mit sei­nen Nach­bar­kno­ten kom­mu­ni­zie­ren kann. Er fragt seine Nach­barn immer wie­der nach deren Ent­fer­nung zum Start­kno­ten und passt seine ei­ge­ne Ent­fer­nung ge­ge­be­nen­falls an. Ma­chen das alle Kno­ten, stellt sich nach einer ge­wis­sen Zeit ein sta­bi­ler Zu­stand ein, in dem die kür­zes­ten Ent­fer­nun­gen vom bzw. zum Start­kno­ten be­kannt sind. Die Ge­samt­struk­tur des Gra­phen muss dazu nicht be­kannt sein. Jeder Kno­ten muss nur seine Nach­bar­kno­ten ken­nen.

Tauscht man nicht nur In­for­ma­ti­on über die Ent­fer­nung zu einem Kno­ten aus, son­dern zu allen Kno­ten (man über­gibt dann einen Dis­tanz-Vek­tor), kennt man am Ende die kür­zes­ten Ent­fer­nun­gen zu allen Kno­ten und weiß, über wel­chen nächs­ten Kno­ten der Weg ver­läuft. Diese In­for­ma­ti­on ist für das Rou­ting im In­ter­net not­wen­dig.

Die­ses Dis­tanz-Vek­tor-Ver­fah­ren kann man gut mit Schü­lern durch­spie­len, indem jeder Schü­ler einen Kno­ten "spielt" und eine Karte mit sei­nen Nach­bar­kno­ten und den Ge­wich­ten der Kan­ten dort­hin be­kommt. Der kom­plet­te Graph wird noch nicht be­nö­tigt/ge­zeigt. Die Schü­ler tei­len ihren Nach­barn ihren Dis­tanz-Vek­tor immer wie­der mit, bis sich keine Än­de­run­gen mehr er­ge­ben. Dann müss­ten die kür­zes­ten Ent­fer­nun­gen von allen Kno­ten zu jedem an­de­ren Kno­ten ge­fun­den sein. Dies über­prüft man durch Ein­blen­den des ge­sam­ten Gra­phen.

Mit Hilfe des Tools "Dis­tanz­Vek­torAl­go­rith­mus­Ge­ne­ra­tor.exe" (Ord­ner 06_­soft­ware) von Rai­ner Helf­rich (RP Tü­bin­gen) kann man für bis zu 14 Schü­ler einen Gra­phen zu­fäl­lig ge­ne­rie­ren und für jeden Schü­ler Excel-Vor­la­gen für die Rou­ting-Ta­bel­len und Dis­tanz­vek­to­ren er­zeu­gen las­sen. Zu­nächst gibt man die Namen der Schü­ler (einen pro Zeile) ein und ge­ne­riert einen Gra­phen. Die­sen kann man ab­spei­chern und spä­ter wie­der laden. Dann lässt man mit "Blät­ter er­zeu­gen" die Excel-Ta­bel­len er­stel­len und druckt sie aus. Für die Durch­füh­rung des Rol­len­spiels emp­fiehlt es sich zur bes­se­ren Über­sicht, wenn jeder Schü­ler zwei Ab­la­gen für „ein­ge­hen­de“ und „aus­ge­hen­de“ Dis­tanz­vek­tor-Blät­ter auf dem Tisch hat.

Nach­dem die Schü­ler das Rol­len­spiel be­en­det haben, kann man das Er­geb­nis kon­trol­lie­ren, indem man den Graph an­zeigt. Ein Dop­pel­klick auf einen Kno­ten des Gra­phen zeigt die kür­zes­ten Ent­fer­nun­gen zu den an­de­ren Kno­ten an. Wählt man einen Ziel­kno­ten rechts unten, wird der Pfad in der Gra­phen­an­sicht ge­zeigt.

Er­gän­zung: Ver­gleich mit an­de­ren Ver­fah­ren

Die Schü­le­rin­nen und Schü­ler haben in Com­pu­ter­spie­len oft Kon­takt mit Geg­nern, die sich ihre Wege zu einem selbst su­chen. Dabei kön­nen die Spiel­fi­gu­ren meist nicht nur ent­lang von Stra­ßen mit Kreu­zun­gen lau­fen, son­dern kreuz und quer über eine Karte be­we­gen. Je nach Un­ter­grund manch­mal schnel­ler oder lang­sa­mer. Die fol­gen­den bei­den Web­sei­ten zei­gen, dass auch in die­sem Fall die be­spro­che­nen Al­go­rith­men ver­wen­det wer­den kön­nen. Dabei wird ein qua­dra­ti­sches Ras­ter über die Karte ge­legt. Jedes Qua­drat ist ein Kno­ten. Je nach Ein­stel­lung sind nur die di­rekt da­ne­ben lie­gen­den Qua­dra­te oder auch die dia­go­nal an­gren­zen­den Qua­dra­te mit Kan­ten ver­bun­den.

Wegbestimmung mit PathFinding.js, Xueqiao Xu (MIT Licence)

Bild­quel­le: Weg­be­stim­mung mit Pa­th­Fin­ding.js, Xu­e­qiao Xu (MIT Li­cence), URL: https://​qiao.​git­hub.​io/​Pa­th­Fin­ding.​js/​vi­su­al/ (ab­ge­ru­fen 04.11.2020) ZPG In­for­ma­tik [CC BY-NC-SA 3.0 DE], aus 2_­un­ter­richts­ver­lauf.odt

Die App­lets zei­gen dabei schön, wie viele Kno­ten zur Be­stim­mung des Weges aus­ge­wer­tet wur­den. Au­ßer­dem kön­nen wei­te­re Al­go­rith­men aus­pro­biert wer­den (z.B. Best-First-Se­arch: ein Gree­dy-Al­go­rith­mus, der in jedem Schritt ver­sucht, die Ent­fer­nung zum Ziel zu mi­ni­mie­ren).

Pa­th­Fin­ding.js: https://​qiao.​git­hub.​io/​Pa­th­Fin­ding.​js/​vi­su­al/

In­tro­duc­tion to the A* Al­go­rithm: https://​www.​red​blob​game​s.​com/​pa­th­fin­ding/​a-​star/​int​rodu​ctio​n.​html

 

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

 

Wei­ter zu Do­mi­nie­ren­de Men­gen