Beste,
Ik ben (eindelijk) begonnen met mijn profielwerkstuk over het handelsreizigersprobleem. Nu liep ik bij de uitleg van het probleem al direct tegen een probleem aan. Hoe kan ik correct berekenen hoelang het berekenen van iets gaat duren als de kloksnelheid van de processor gegevens zijn en het aantal werkende cores.
Zie hieronder mijn tekst:
Om rechtstreeks de snelste route te berekenen zou je elke mogelijke routes na moeten gaan daarna moeten kijken bij welke oplossing de afstand het kortste is1. Er zijn als er n steden zijn n! routes. Ook wel de faculteit van het aantal steden. Met n=5 heb je 5! oplossingen. Dit komt neer op 1x2x3x4x5 = 120 oplossingen. Dit is nog makkelijk op te lossen. Heb je 20 steden heb je 20! oplossingen. Dit komt neer op 2.432.902.008.176.640.000 oplossingen. Voor 120 oplossingen heb je al een computer nodig, en is dat prima te doen met een computer.
---vanaf hier ben ik onzeker over de correctheid---
want er moeten 2,5x10^18 antwoorden komen, maar die som bestaat uit afstand1 + afstand2 + .... + afstand19 (of 20, correct me if i'm wrong), dus reken je dan 19 dingen uit, of 1 ding. Het is mij niet compleet duidelijk. En als de getallen groter worden, kost het dan ook meer tijd/moeite/ticks, en verschilt het dan ook nog per processor-structuur? anyways hier onder gaat mijn tekst verder.
Voor ongeveer 2,5x10^18 oplossingen heb je een aardig krachtige computer nodig. Een quad-core processor geklokt op 4Ghz, wat redelijk gangbaar is voor consumenten computers, zal hier aardig lang over doen. 4Ghz is 10^9 hertz. Zoveel sommen kan één kern van de processor per seconde uitrekenen. Er zijn 4 kernen, dus wordt het rekensommetje het aantal sommen die uitgerekend moeten worden gedeeld door het aantal sommen die per seconde uitgerekend worden. (2,5x10^18)/(4x4x10^9) = 156.250.000 seconden. Dit komt neer op bijna 5 jaar non-stop rekenen. En dan moet er nog bepaald worden welk van de 2,5x10^18 oplossingen de kleinste waarde heeft. Praktisch gezien heb je hier helemaal niets aan.
Hopelijk kan iemand mij op weg helpen.
Groeten,
Caspar