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 en Figen
8-6-2005
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 [http://www.win.tue.nl/~leen/OW/2P350/Week8/week8.pdf]
AE
8-6-2005
#39090 - Praktische opdrachten - Leerling bovenbouw havo-vwo