| Note for English speakers: |
|---|
Do not read the text below,
but take this Workshop text. |
Workshop
Routeplannen met Wybe
In 1959 bedacht de Nederlandse Wiskundige Edsger Wybe Dijkstra,
hoe een computer routes kan uitrekenen.
Zijn uitvinding is nog altijd de basis van routeplanners
(zoals een TomTom, MIO of Garmin).
Hoe werkt het berekenen van routes?
Is daaraan nog iets te verbeteren?
Hoe kun jij daaraan bijdragen?
Op die vragen willen we ingaan in deze leeractiviteit.
Bij deze workshop hoort een diapresentatie.
De presentatie is gemaakt door Gerard Tel van de Universiteit Utrecht.
Een ZIP file RoutePlanner
bevat het Wybe programma en voorbeeld-kaarten.
Het programma Wybe is gemaakt door Bas den Heijer
van de Universiteit Utrecht.
Hier is een werkblad met
opdrachten
waarmee je de demo kunt uitproberen.
Hier is de ZIP file met bestanden:
RoutePlanner.
Een demonstratie-programma Wybe is gemaakt door
Bas den Heijer van de Universiteit Utrecht.
Je kunt het routeplan-programma Wybe gebruiken,
maar je moet het eerst op je computer zetten.
Klik op de link en kies openen in Windows explorer (Verkenner).
Sleep de map RoutePlanner naar het Bureaublad
(of een andere locatie) om hem uit te pakken.
Open die map en start de applicatie Wybe.
Als je het programma opstart,
krijg je een schermpje te zien zoals hiernaast is afgebeeld.
(Deze afbeelding is alleen een screenshot en werkt niet!!)
Op het scherm zijn deze controls te gebruiken:
- Kaartkeuze: Staat in het begin op Tom (Kortst).
Hiermee kies je tussen verschillende kaarten.
Je kunt ook zelf kaarten maken.
- Info: Achtergrond van Wybe.
- Startknop: Linksonderin, hiermee start je de routeberekening.
- Wachtrij: Kies (Lijst, Boom, of Mens) hoe de volgende
definitieve knoop gekozen wordt.
Bij keuze Mens moet je zelf de knoop kiezen door aanklikken.
- Stapknop en snelheidsschuif:
Zet de schuif helemaal naar rechts voor supersnel rekenen,
naar links om het stap voor stap te doen met de stapknop.
- Uitleg: Bij elke rekenstap zegt Wybe waar hij mee bezig is.
- Startvlag: Klik op de startvlag en dan op een knoop
om het beginpunt te kiezen.
(De start- en eindvlag kunnen nooit op dezelfde plaats staan.)
- Eindvlag: Klik op de eindvlag en dan op een knoop
om de bestemming te kiezen.
Misschien heb je wel eens ergens gelezen over
het algoritme van Dijkstra,
of de diapresentatie
bekeken.
- Begrip van het algoritme:
Heb je de uitleg en werking van het algoritme begrepen?
Zet de kaartkeuze op Tom (kortst),
de snelheidsschuif helemaal naar links,
en druk op de startknop.
Nu moet je voor elke stap van de berekening
op de stapknop drukken.
Probeer voor elke stap te bedenken,
wat er gaat gebeuren.
(Steeds nadat er een knoop is blauw gemaakt,
worden de schattingen van zijn buren herzien.)
- Routestrategieën:
Een routeplanner voor auto of fiets berekent niet
altijd de kortste route:
je kunt ook de snelste kiezen, minimaal brandstofverbruik,
vermijden van onverharde wegen of veerboten, etc.
Hoe zou dat werken?
Door te kiezen voor de kaarten Tom (Snelst)
en Tom (Schoonst) kun je erachter komen,
dat dit op precies dezelfde manier werkt.
Alleen de getallen die bij de wegstukjes staan, zijn anders
(en betekenen iets anders, bv. minuten ipv kilometers).
- Actieve knopen en laagste schatting:
Hoe vindt de computer toch steeds weer de laagste schatting?
Alle knopen met een schatting worden bijgehouden in een wachtrij,
die op verschillende manieren kan zijn georganiseerd.
Kies de kaart Rooster 2,
zet de snelheidsschuif naar rechts en de wachtrij op mens-wachtrij.
Nu moet je zelf steeds op de knoop met laagste schatting klikken!
Je merkt nu wel, dat je steeds een bepaalde zone
rondom het startpunt in de gaten moet houden.
Bij elke knoop die je blauw maakt kan er in die zone iets veranderen,
maar de meeste knopen blijven hetzelfde.
De knopen met schatting noemen we de actieve knopen
en die worden door de computer bijgehouden in een lijst.
Hoeveel knopen kunnen er tegelijk actief zijn?
De lengte van de actieve lijst kan ongeveer de wortel
zijn van het totale aantal knopen.
Voor de kaart van Europa, met tientallen miljoenen knopen,
kunnen er dus wel vijfduizend tot tienduizen knopen tegelijk actief zijn.
De lijst-wachtrij houdt wel bij, welke knopen actief zijn,
maar bekijkt in elke ronde alle knopen opnieuw.
De boom-wachtrij houdt niet alleen bij welke knopen
actief zijn, maar ook, welke daarvan lage en hoge
schattingen hebben.
Bij veranderingen van schattingen moet je dat bijwerken,
maar het zoeken van de laagste schatting gaat wel veel sneller.
- Geen richtingsgevoel:
Kijk naar de kaart Klungelig;
je zult al snel tot de conclusie komen dat je vanaf het beginpunt
naar links moet, dat is de enige route.
Maar Wybe ziet dat niet! Wybe berekent eerst de afstand
naar alle knopen rechts, want Wybe heeft geen richtingsgevoel
en is ook niet visueel.
Verwissel de begin- en eindvlag en bereken opnieuw de route.
Zou het altijd beter zijn om bij het eindpunt van je route te starten?
- Negatief gewicht:
Op de kaart Negatief gewicht komt een wegstukje voor
met lengte -20.
Kan zoiets wel?
De routeberekening werkt in ieder geval niet goed,
want Wybe beweert dat de afstand 10 is,
terwijl een route met lengte 4 bestaat.
Je hebt in de informatica vaak wiskunde nodig
om bewijzen of beredeneringen op te zetten
over je programma.
Door precies te beredeneren waarom Wybe
de goede route berekent, kom je erachter dat dit alleen
zo is, wanneer er geen negatieve lengtes zijn.
- De routeboom:
Je hebt misschien wel gemerkt, dat Wybe niet alleen
de kortste weg naar het doel bepaalt, maar ook naar een heleboel
andere punten tussen start en doel.
Op de laatste dia van de diavoorstelling zie je zo'n
routeboom voor het Universiteitscentrum De Uithof bij Utrecht,
waar onze opleiding Informatica te vinden is.
Ook zonder routeplanner kun je ons dus gemakkelijk vinden!
Als je alle opdrachten hierboven een paar keer hebt gedaan....
dan heb je dat wel een beetje gezien.
Maar je kunt ook zelf kaarten maken voor Wybe!
De meegeleverde kaarten zijn gewoon tekstbestanden
waarvan de naam eindigt op .graph.txt.
Als je dubbelklikt op
atomafstand.graph.txt,
wordt het bestand geopend en kun je zien hoe het is opgebouwd.