3 - algoritmen voor routebepaling

Inleiding

Een veel voorkomend probleem is het bepalen van een route die aan bepaalde voorwaarden voldoet. Het bekendste voorbeeld is wellicht het bepalen van de kortste of snelste route van A naar B, zoals dat bijvoorbeeld in een autonavigatiesysteem ("TomTom") plaatsvindt.

Enkele andere voorbeelden zijn:

• het bepalen van een aantrekkelijke route van A naar B - voor een toeristisch uitje;
• het bepalen van de kortste (of snelste) route langs een aantal plaatsen - bijvoorbeeld voor een pakjesbezorger;
• het bepalen van een aantrekkelijke route van A naar B (of van A naar A) met een bepaalde afstand - bijvoorbeeld voor een wandeling, fietstocht, of hardlooprondje.

We zullen verschillende vormen van het routeplanningprobleem gebruiken om het begrip algoritme en een aantal eigenschappen daarvan te laten zien.

Concepten die hier aan de orde komen zijn onder andere: algoritmisch probleem, specificatie, algoritme, programma, uitvoering, efficiëntie van een algoritme, complexiteit ofwel schaalbaarheid van een algoritme, idem van een algoritmisch probleem, enz.

Representeren van het wegennet: grafen

Voor het uitwerken van een routeplanningsprobleem is een eerste vraag, hoe we het wegennet kunnen representeren waarover we de route willen bepalen. Meestal wordt een wegennet voorgesteld door een kaart, maar voor ons doel bevat een kaart te veel informatie, en bovendien vormt die niet een handige representatie voor de verschillende algoritmen. We zijn eigenlijk alleen geïnteresseerd in de punten (zoals A en B) en in de verbindingen (wegen) tussen de punten; van deze verbindingen moeten we de lengte weten, en mogelijke andere eigenschappen zoals de gangbare reistijd (voor het bepalen van de snelste route), of de toeristische aantrekkelijkheid, de veiligheid, enz.. Naast punten die met benoemde (woon)plaatsen overeen komen, moeten we ook rekening houden met de punten die wegen verbinden, zoals kruispunten. We komen dan tot een representatie die alleen bestaat uit punten en verbindingen tussen deze punten, waarbij per verbinding een lengte gegeven is, of mogelijk de andere genoemde eigenschappen. Zo'n representatie heet in de wiskunde ook wel een graaf. (Zie bijvoorbeeld: http://nl.wikipedia.org/wiki/Grafentheorie.) Er zijn allerlei specifieke soorten van grafen mogelijk, vaak afhankelijk van de eigenschappen van de verbindingen. De verbindingen kunnen bijvoorbeeld gericht zijn ("eenrichtingsverkeer"); in dat geval spreken we over een gerichte graaf; de verbindingen kunnen ook ongericht zijn, we spreken dan over een ongerichte graaf. In dit deel gaan we uit van ongerichte grafen, tenzij anders vermeld. Voor de routebepalingsproblemen zijn de verbindingen "gewogen" met de lengte van de verbinding, of bijvoorbeeld met de reistijd. Het gewicht van de verbinding -lengte or reistijd- is in dit geval altijd niet-negatief. Het is ook mogelijk om te generaliseren tot grafen waarvan de verbindingen ook negatieve gewichten kunnen hebben, maar dat laten we hier buiten beschouwing.

Intermezzo: abstracte kaarten

Een kaart vormt een eerste abstractie van de werkelijkheid: allerlei irrelevante details worden weggelaten, en relevante details worden aangedikt. In het geval van een kaart speelt bijvoorbeeld de geografische positie een rol, en de aard van de omliggende natuur. Voor sommige soorten kaarten worden nog meer details weggelaten, en ligt de nadruk vooral op de verbindingen. Een goed voorbeeld hiervan zijn de huidige metrokaarten: deze geven eigenlijk alleen de stations en de verbindingen weer, zijn niet "op schaal" getekend; ook kloppen de onderlinge posities van de stations op de kaart niet noodzakelijk met de geografische posities. Dit geldt in het bijzonder voor de kaarten die in de metro's zelf te zien zijn.

Opgave: het ontwerp van de metrokaart zoals die door het GVB in Amsterdam gebruikt wordt, en door vele andere metro's, is ooit bedacht voor de metro van een bepaalde stad - welke? Kun je het oorspronkelijk ontwerp terugvinden? Kun je ook vinden hoe de metrokaarten er voor die tijd uitzagen?

(Kaart van de metro van Amsterdam; bron: WikiMedia)

Kaarten op het web

Op het web worden op veel plaatsen kaarten gebruikt; Google maps is wel een van de bekendste. Naast de commerciële kaarten, zijn er ook "open" kaarten. Wat voor de web-encycelopdieën Wikipedia is, is Openstreetmap (http://www.openstreetmap.org/ ; http://www.openstreetmap.nl) voor de kaarten: iedereen kan helpen deze kaarten te verbeteren en uit te breiden, en het gebruik ervan is "vrij". De informatie van Openstreetmap is vrij toegankelijk, ook op het niveau waarop de kaarten gemaakt worden. De elementaire kaartgegevens zijn bijvoorbeeld in XML-formaat te krijgen door de export-functie. (Hint: probeer dit eens voor de kaart in de buurt van je huis of je school, ingezoomd tot het hoogste niveau. Wat kun je daarin herkennen?) Een uitleg van de basiselementen is bijvoorbeeld te vinden op de bijbehorende Wiki-site, zie http://wiki.openstreetmap.org, bijvoorbeeld: http://wiki.openstreetmap.org/wiki/Map_Features.

Kortste-pad probleem

Het eerste probleem dat we behandelen is het zoeken van het kortste pad tussen twee punten. Dit is een van de bekendste algoritmische problemen, waarvoor ook een zeer bekend algoritme bestaat, in 1959 gepubliceerd door de Nederlandse informaticus Edsger Dijkstra. De "verjaardag" van dit algoritme in 2009 is dan ook met enig vertoon gevierd. Een uitleg van dit algoritme wordt gegeven in Dijkstra's algoritme.

Opgave. Bij Openstreetmap worden ook een aantal routeringsprogramma's genoemd; welke daarvan maken gebruik van een variant van Dijkstra's algoritme?

Over algoritmen en algoritmische problemen

Het probleem van het bepalen van de kortste route van A naar B heet een algoritmisch probleem: dit is een probleem dat (in principe) opgelost kan worden door middel van een algoritme. Voor een algoritmisch probleem zijn meerdere algoritmen als oplossing mogelijk; deze oplossingen kunnen bijvoorbeeld verschillen in hun efficiëntie en hun schaalbaarheid ("complexiteit"). We kunnen soms ook uitspraken doen over het algoritmische probleem, bijvoorbeeld wat de minimale complexiteit (ofwel de maximale schaalbaarheid) van het best mogelijke algoritme is - zonder dat we mogelijk het beste algoritme kennen.

Routeplanning voor de pakjesbezorging

Een volgend probleem voor routebepaling is het probleem van de pakjesbezorger: wat is de kortste (of snelste) route langs een aantal punten (waar een pakje bezorgd of gehaald moet worden). We kunnen in dit geval de graaf reduceren tot de punten die bezocht moeten worden; de afstand van de kortste weg tussen elk tweetal punten kunnen we als gewicht van de verbinding opnemen. De vraag is nu: wat is de kortste route langs alle punten in de graaf?

Dit probleem staat in de literatuur bekend als het handelsreizigersprobleem, of Traveling Salesman Problem; zie bijvoorbeeld Wikipedia: http://nl.wikipedia.org/wiki/Handelsreizigersprobleem.

Voor het bepalen van de kortste route door alle punten gebruiken we een brute-kracht methode: we bepalen alle mogelijke routes, dat wil zeggen, alle permutaties van de punten in de graaf, en onthouden de route met de kortste lengte tot nu toe. Dit algoritme is verder uitgewerkt op de pagina TravelingSalesman.

Dit lijkt een "domme" methode - en is dat in zekere zin ook, maar het blijkt dat er geen efficiënte (polynomiale) methode is die gegarandeerd met de optimale oplossing komt. (Zie bijvoorbeeld de Engelse Wikipedia:http://en.wikipedia.org/wiki/Travelling_salesman_problem). Er zijn wel vele slimme manieren om de optimale oplossing op een efficiënte manier te benaderen. Enkele daarvan zijn geïnspireerd op methodes die in de levende natuur gebruikt worden, zoals genetische algoritmen of routebepaling volgens de manier van een mierenkolonie.

Routeplanning voor een looprondje

(Dit onderdeel moet nog ingevuld worden.)