Tag Archives: graaftheorie

De Chinese postbode en Pacman

In een eerdere post over de London tube en GPS waarin het allemaal gaat over “de kortste afstand voor een route”, leerde je al over grafentheorie. In deze post hadden we verschillende punten die via verschillende wegen te bereiken zijn. In het geval van ‘het spel’ rond het Londense metro-netwerk, moesten we zo snel mogelijk al deze punten bezoeken. Dit probleem staat bekend als het handelsreizigersprobleem (het is één van dé belangrijkste wiskundige problemen waar onderzoekers nu aan werken).

AfbeeldingEen andere moeilijke kwestie uit de grafentheorie is dat van “het Chinese postbode probleem”. Hierin is het van belang dat we niet enkel elk knooppunt bezoeken, maar ook elke verbinding moet bezocht worden. Je kan het schema, of de graaf, dus een beetje als een platte grond aanzien, waar elke lijn een straat is waarbij de postbode brieven moet posten, en elk knooppunt stelt een kruispunt voor. Bij elke verbinding staat ook een waarde die de lengte van deze straat voorstelt. Hoe hoger de waarde, hoe langer de straat. Iedereen wil zijn post zo snel mogelijk ontvangen dus ook hier is snelheid van belang. Met andere woorden ook nu zoeken we de kortste route. Verder mag de man, indien hij wil of niet anders kan, een straat meermaals bezoeken.
In het onderstaande voorbeeld zijn er dus 8 straten die de Chinese postbode zal moeten bedienen. Hiervoor zal hij 6 kruispunten tegenkomen.
AfbeeldingHoe vinden we nu de kortste route? We kunnen natuurlijk brutal force gebruiken om de oplossing te vinden. Dit wil zeggen, we testen alle mogelijke routes en bereken de lengte van elk van deze. Vanzelfsprekend is dit (zeker met een computerprogramma) voor ons voorbeeld een zeer haalbaar plan. Wanneer het werkgebied groter wordt tot de oppervlakte van een dorp of kleine stad, is het al lang niet meer mogelijk om het zo op te lossen, zelfs niet met de sterkste en snelste computers! We zullen een andere aanpak gebruiken.

Allereerst merken we op dat we voor onze kleine traject, zowel kruispunten hebben waar een even aantal straten op uitkomen (A en F), en we hebben ook een aantal kruispunten van oneven graad (B, C, D en E). Dit is belangrijk om weten omdat, “indien we meer dan 2 kruispunten van oneven graad hebben, we zeker zijn dat we straten meermaals moeten bezoeken”.
Probeer onderstaande voorbeelden maar eens in 1 beweging te tekenen, dus zonder je potlood/pen van het papier te halen, en zonder tweemaal over dezelfde lijn te gaan. Voor de eerste figuren 1,2 en 4 zal dit je na even proberen wel lukken, voor de laatste lukt dit nooit.
Merk ook op dat als, (zoals figuur 4) alle punten van even graad zijn, het niet uitmaakt waar je aan je figuur begint te tekenen. Vanuit elk begin punt zal de opdracht haalbaar zijn. Indien je 2 kruispunten hebt met oneven graad (figuur 1 en 2), kan je deze oefening enkel uitvoeren door te beginnen in een van deze ‘oneven’ kruispunten, en eindigt in het andere ‘oneven’ kruispunt.
AfbeeldingWe weten dus al dat onze postbode één of meer straten, tweemaal zullen moeten bezoeken. Om te weten welke straten hij meer dan eens zal  doorwandelen gaan we als volgt te werk:
Eerst voegen we even denkbeeldig straten toe, waardoor we ervoor zorgen dat punten met oneven graad ook even worden. Dat kunnen we op 3 verschillende manieren. Ofwel verbinden we kruispunten D-E en B-C, ofwel B-D en E-C, ofwel B-E en D-C.  Afbeelding
In elk van de drie gevallen merk je dat al de kruispunten nu van even graad zijn geworden. in poging 1 hebben we 2 straten toegevoegd van lengte 2 en 5, dus een totale toegevoegde waarde van 7. In poging 2 is de extra waarde (5+6)+2 = 13. In de derde en laatste poging werd er (5+3)+7 = 15 toegevoegd. We merken dus dat in de eerste poging het minste aan lengte werd toegevoegd. Deze straten, D-E en B-C, zijn diegene die de postbode meermaals zal moeten bewandelen.
Door deze stappen toe te passen hebben we nu een map gemaakt met allemaal even knooppunten. De postbode kan nu dus kiezen waar hij begint aan zijn dagelijkse ronde. (Zoals gezegd zou een route met 2 oneven kruispunten dus ook gekund hebben, maar dan kan de postbode niet kiezen waar hij begint en eindigt).
Niet enkel postbodes maken gebruik van dit algoritme, maar ook voor het opstellen van het traject voor bijvoorbeeld vuilniswagens kunnen via dit systeem geoptimaliseerd worden.

In de titel vermelde ik ook het spel PacMan. Dit legendarische spelletjes draait om een geel happend figuurtje die zo snel mogelijk een veld met bolletjes moet opeten, zonder op zijn beurt zelf opgepeuzeld te worden door de spoken, Inky, Blinky, Pinky of Clyde. Ook zijn speelveld kan je bekijken als een groot stratenplan. Het is niet zo dat er een tijdslimiet op het spel staat, maar hoe sneller je rond bent, hoe minder risico je loopt om opgegeten te worden natuurlijk. Dus ook hier is een kortste/snelste route interessant.

Afbeelding
Ik heb eenzelfde oefening gemaakt op dit ‘stratenplan’ en heb een resultaat bekomen.
Op de linkse figuur zie je de route die je moet afleggen. Rechts zie je dan in het groen de bollen die je 1 maal passeert. In het rood staan de plaatsen waar je 2 maal voorbij moet. Je ziet dat Pacman ook over 8 zwarte vakken gaat waar geen punten staan (ter hoogte van het rode spookje). In totaal zijn er 240 gewone + 4 Super-bollen te rapen. In principe moet je dus op ‘slechts’ 244 vakjes belanden. In mijn traject passeer je 10 zwarte + 187 groene bollen (die je dus 1 maal passeert) + 57 rode bollen (die je dus 2x passeert) = 311 vakjes.  Zo heb ik ‘slechts’ 67 moves (27,46%) teveel gemaakt.

pacmantom pac-mantom              

Indien je beter kan… alle antwoorden en suggesties zijn welkom!

DAAROM WISKUNDE

Giedts Tom

Advertisements

Leave a comment

Filed under andere

London tube en GPS

De meesten kennen of gebruiken wel eens een GPS-navigatie systeem. De toepassing waarover dit artikel zal gaan is die van “plan je route”. Met deze applicatie kan je een reis plannen waarbij je verschillende punten moet passeren. Bijvoorbeeld je vertrekt in Antwerpen, je rijdt naar Brussel en wil het postkantoor van Wilrijk bezoeken én Technopolis in Mechelen. Je GPS zal nu een optimale route voorstellen, … met behulp van wiskunde.

AfbeeldingDe tak van de wiskunde die hier gebruikt wordt is de grafentheorie. Het voorbeeld dat ik hierboven gaf heeft natuurlijk een zeer logische oplossing en vergt geen hogere wiskunde. Je passeert eerst even het postkantoor in Wilrijk, en springt binnen in technopolis te Mechelen, waar je toch moet passeren om in Brussel te raken. Het zou nogal gek zijn dat je GPS je eerst naar Technopolis laat rijden, om dan terug te komen tot Wilrijk, waarna je van daar naar Brussel rijdt. Dit zou je veel meer tijd en brandstof kosten dan het logische, eerste plan. Maar als je enkele tientallen tussenstops moet maken is het al wat moeilijker om de kortste/snelste reisroute te berekenen.

Denk maar aan bedrijven zoals DHL of UPS. Zij hebben elke dag vele mensen op de baan die her en der pakjes moeten leveren. Als je elke werknemer elke dag enkele minuten sneller kan laten leveren door een optimale reisweg, kan je dit op enkele jaren miljoenen euro’s besparen. Dit wederom door besparing op brandstof en slijtage aan de banden door minder kilometers en omdat je dagelijks meer klanten kan bedienen natuurlijk.
De route die de chauffeurs moeten berekenen kan je zien als een wiskundige graaf. Hierbij beeld je elke bestemming af met een punt of cirkel, en elke weg tussen deze bestemmingen geven we weer als de lijnen die de cirkels verbinden.
AfbeeldingStel dat we bijvoorbeeld aan al de posten (“a” tot en met “i”) moeten leveren. Hoe weten we nu in welke volgorde dit het snelste zal gebeuren? Veronderstel dat ons startpunt in a ligt. Vertrekt onze bestelwagen richting punt b gevolgd door c of e, of doen we eerst d, om van daar naar i te rijden….., er zijn onnoemelijk veel opties. Ze allemaal 1 voor 1 afgaan kan letterlijk jaren duren. Eind jaren 90 berekenden wiskundigen de snelste manier om alle Duitse steden te bezoeken, 15.112 in totaal. Met behulp van computers vonden ze de oplossing, maar dit duurde geen uren, dagen of weken, maar liefst 22.6 jaar de tijd! Ze deden dit niet met zomaar een pc. Het klusje werd geklaard door meer dan 100 processors.

Een eerste stap richting de oplossing is de wegen een waarde geven. Deze waarde kan toegekend worden aan het aantal kilometers van de verbindingen… een weg met een waarde 20 is bijvoorbeeld 20 kilometer lang, één met waarde 10 is maar de helft zolang enz…. Als tijd je belangrijkste zorg is kan je bijvoorbeeld autosnelwegen een waarde 5 geven (ze nemen weinig tijd in beslag), en straten in drukke centra geef je een waarde van bijvoorbeeld 20 (hier ben je 4 maal zoveel tijd kwijt dan op de snelweg)…
Je kan ook een combinatie maken van tijd en afstand efficiëntie natuurlijk…
AfbeeldingNu kan je een wiskundig algoritme gebruiken om te bepalen welke route te nemen. Er zijn meerdere van deze algoritmes in de omgang, maar het bekendste zal Dijkstra’s algoritme zijn (dit wordt door de meeste GPS-systemen gebruikt). Indien je het algoritme in zijn werk wil zien kan je deze of deze site eens bezoeken. Simpel opgelost toch?…
Het probleem is dat het voor oefeningen met een groot aantal steden zelfs voor een computer zeer lang kan duren om de meest efficiënte volgorde te zoeken. Verder hebben we ook nog geen bewijs gevonden dat het wiskundige algoritme wel degelijk dé beste oplossing biedt. Het sluit vele oplossingen uit, en geeft je een van de betere antwoorden, maar het is dus nog steeds niet wiskundig bewezen dat het de allerbeste oplossing is.
Dit probleem is gekend als het handelsreizigersprobleem en een van de meest bekende en moeilijkste openstaande problemen in de wiskunde.

AfbeeldingIndien je denkt een systeem te hebben gevonden om dit raadsel te ontrafelen (of toch ook een heel goede benadering) kan je je misschien eens wagen aan de tube-challenge. Het is een wedstrijd rond het bekende metro systeem van Londen. Het hele ondergrondse tramnet telt er nu al 270 stations. De opzet van de wedstrijd is heel makkelijk: hoe snel kan jij alle stations bezoeken door enkel gebruik te maken van de trams die ertussen pendelen. Als je van de figuur van de leveranciers tracht te achterhalen hoeveel mogelijkheden er zijn, of de inspanningen leest rond het berekenen van het handelsreizigersprobleem, zal je ondervinden hoe immens moeilijk deze wedstrijd wel is. (voor de geïnteresseerden, het record staat nu op 13 uur, 20 minuten en 27 seconden).
De kaart van “the tube” zoals ze het hele ondergrondse tram-net (met het beroemde “mind the gap”) daar noemen wordt trouwens meestal weergegeven als een graaf. de bolletjes zijn de stations en de tramlijnen die ze verbinden zijn de gekleurde lijnen (zie boven).
Ook het Antwerpse openbare vervoersplan heeft nu zulk een weergave (zie onder).
Afbeelding
Misschien kunnen we de stad Antwerpen en de lijn wel warm maken voor een gelijkaardig idee. Wie kan er het snelst alle Antwerpse stations bezoeken? Een leuk idee om stad, openbaar vervoer én wiskunde te promoten.

DAAROM WISKUNDE
(lees ook Wiskunde en camerabewaking)

Giedts Tom

1 Comment

Filed under andere, Toepassingen voor elke dag, wiskunde in de natuur