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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s