WisFaq!

De digitale vraagbaak voor het wiskundeonderwijs

HOME

samengevat

\require{AMSmath}

Algoritme

Hoe bereken je hoeveel wegen een 25x25 netwerk heeft? En hoe bereken je dan de korste route van A naar B in een 25x25 netwerk?
Anne
Leerling bovenbouw havo-vwo - woensdag 12 januari 2005

Antwoord

Hallo,

Bedoel je met netwerk een raster waarin elk lijntje een stuk weg voorstelt?

Zoals hier voorgesteld voor een 4x4?

Het aantal wegen ligt aan de voorwaarden, mag je meerdere keren over eenzelfde weg (zoja, oneindig aantal), mag je 'terugkeren', ...

Voor de kortste route ga ik ervan uit dat je A & B in de hoekpunten plaatst, op een diagonaal - bvb A linksonder en B rechtsboven.
Onder 'kortste' versta ik dan zo weinig mogelijk van die 'kleine wegen' (de verbindingsstukken).
In dat geval is er meer dan één korte weg. In een 25x25 zal je immers altijd minstens 50 stappen moeten doen, als je er precies 50 doet om van A naar B te gaan dan heb je een kortste weg.

Je kan je dan wel nog afvragen hoeveel van die 'korte wegen' (van 50 stappen) er zijn.
Eerst moet je dan nadenken over de voorwaarden om een 'korte weg' te zijn. Die is redelijk eenvoudig, zolang je geen stap naar links en geen stap naar onder zet ga je uiteindelijk in 50 stappen in B geraken. Het komt er dus op aan alleen naar boven en naar rechts te bewegen.

Om het aantal te weten zijn er 3 mogelijkheden:
- je telt ze (al moeilijk voor een 4x4, ondoenbaar voor een 25x25)
- je gaat op elk kruispunt, linksonder te beginnen, noteren op hoeveel manier je daar kan geraken en gaat zo verder tot rechtsboven. Dit is ook al vrij lastig voor een 25x25.
- de laatste methode is de snelste, maar vereist wel dat je al van permutaties hebt gehoord. (rekenen met faculteiten)

Stel je hebt een 3x3, dan zou je een route kunnen beschrijven aan de hand van een 6-letter-'woord', elke letter symboliseert dan de richting.
Bijvoorbeeld, eerst 3x omhoog en dan 3x naar rechts wordt dan:
bbbrrr (b voor boven en r voor rechts)
Terwijl eerst één pas naar rechts, dan helemaal naar boven en weer 2 rechts geeft:
rbbbrr
Enzovoort.

Nu kan je makkelijk zien dat je alle mogelijke korte wegen krijgt door in dat letterwoord de letters van plaatsen te verwisselen zodat je een nieuw 'woord' krijgt. Dit zijn permutaties.

In het geval van een 25*25 geeft het aantal wegen dan:
50!/(25!*25!) = 126410606437752

Je had het misschien niet verwacht, maar in een 25x25 zijn er zoveel verschillende korte wegen!

mvg,
Tom

Vragen naar aanleiding van dit antwoord? Klik rechts..!
donderdag 13 januari 2005