WisFaq!

De digitale vraagbaak voor het wiskundeonderwijs

HOME

samengevat

\require{AMSmath}

Handelsreizigersprobleem

Hoe lichten we dit getal toe bij een 25*25 netwerk? het gaat om dit getal : 6,2*10^15
En hoe berekenen we met dit getal in een 30*30 netwerk?
En hoe lang duurt het voor een computer dit te berekenen? We moeten namelijk een schatting geven van de tijd die de computer erover doet.

Weet u misschien ook of er andere oplossingen zijn voor het handelsreizigersprobleem?

alvast bedankt!,

Eefje
Leerling bovenbouw havo-vwo - woensdag 8 juni 2005

Antwoord

Ik denk dat 'het getal' dat je hier bedoelt, het aantal mogelijke 'paden' is. Bij 25 punten, heb je 25 keuzes voor het eerste element, 24 voor het tweede, enzovoort. Totaal levert dit 25x24x23x...x1=25!=1,6*10^15 mogelijkheden. Bij 30 punten, is dit 30!=2,7*10^32 (merk op hoeveel groter dit is!)

Een redelijke schatting van de tijd die een computer hierover doet, is om te stellen dat er respectievelijk 24 en 29 optellingen per pad worden gemaakt. Dit zijn dus 3,7*10^26 en 7,7*10^33 optellingen. Als we er van uitgaan dat elke optelling 1 basisbewerking is, kun je dit vergelijken met zo'n 2.5*10^9 bewerkingen per seconde voor een nieuwe PC, of 2,75*10^13 bewerkingen per seconde voor de supercomputer van LOFAR, die op dit moment de snelste computer van Europa is. Je kunt je schatting maar het beste in jaren doen...

Wat betreft andere oplossingen: Er zijn geen snelle oplossingen bekend die altijd werken - en waarschijnlijk zijn die er ook niet. Wat wel bestaat, zijn methoden die heel snel een 'redelijk goed' resultaat geven. Hiervan kun je er in onderstaande link (Engelstalig) een aantal vinden.

Zie The traveling salesman problem

Vragen naar aanleiding van dit antwoord? Klik rechts..!
woensdag 8 juni 2005