HOME
3H2
4HA1
4HA2
4HB2
5HA2
5HB1
5HB2
Jaaragenda
Rekenmachine
PTA 4H
PTA 5H
Pr.opdr. 4H
Webquests
Pr.opdr.
PWS 
Geschiedenis
Wiskunde
Links Wiskunde
De TAS
 

22.   Handelsreizigersprobleem

Aangemaakt door  G.A. Koeze, 2 februari 1999
Bron:   Rijksuniversiteit Utrecht

Een vertegenwoordiger moet op één dag naar Amsterdam, Alkmaar, Den Helder, Hilversum, Utrecht en IJmuiden. Wat is de kortste route? Deze vraag is al heel oud en wordt het handelsreizigersprobleem genoemd. Door alle mogelijkheden na te gaan is de oplossing natuurlijk wel te vinden. Maar of je de route zo kunt kiezen dat je alle steden precies 1 keer bezoekt, is in het algemeen een onopgelost probleem!

Voor handelsreizigers bestaat dit probleem natuurlijk niet echt. Het vinden van een antwoord is echter wel heel belangrijk om vergelijkbare problemen op te kunnen lossen bij moderne ontwikkelingen op het gebied van de informatietechnologie, zoals het werken met parallelle computers.

Een sterk vereenvoudigde vorm van het handelreizigersprobleem kun je wel oplossen.

Stel je hebt een heel groot netwerk van steden. Met het zogenaamde 'greedy algoritm' kun je de kortste weg tussen twee willekeurige steden uitrekenen. Het werkt als volgt: neem een stad. Teken naar de dichtstbijzijnde stad de kortste weg. Teken vervolgens naar de dan dichtstbijzijnde stad weer de kortste weg. Etc, etc. Je ziet een netwerk van kortste wegen ontstaan dat helemaal geen rondjes (circuits) bevat. Zo'n netwerk zonder rondjes heet een boom.Via de boom vind je het antwoord.

 

Vragen waar je aan kunt denken voor je werkstuk:

Onderzoek de geschiedenis van het handelsreizigersprobleem.

Stel je wilt 25 steden bezoeken. Op hoeveel verschillende volgordes kan dat? Hoe bepaal je op een snelle manier de kortste weg daartussen? Zelfs voor een computer is dat een hele klus.

Bepaal het netwerk van kortste verbindingen tussen alle provinciehoofdsteden van Nederland.

Bewijs dat jouw oplossing de beste is.

Voor wat voor soort vraagstukken zou de oplossing van het handelreizigersprobleem een uitkomst zijn?

Wat is het alternatief zolang het probleem onopgelost blijft?