tijdsduur uitvoeren berekening (n!) (handelsreizigersprobleem)

manuel

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

MatthijsDamen

Hoi Caspar,

Moeilijk onderwerp heb je gekozen! Maar zo te zien heb je er al behoorlijk wat tijd ingestoken. Uit je verhaal kan ik nog niet helemaal halen wat je vraag precies is? Wil je bepalen hoeveel tijd het kost om het handelsreizigers probleem op te lossen met n steden? Zo ja, waarom wil je dit doen? Of wil je de tijd die het kost om het uit te rekenen vergelijken met andere oplossingsmethodes?

Zoals je zelf al hebt gemerkt is het behoorlijk lastig om precies uit te rekenen hoe lang een computer over een bepaalde berekening doet. Wat er vaak gedaan wordt is bepaalde berekening vergelijken. Je doet dus twee verschillende berekening (oplossingsmethodes) op dezelfde computer, zodat je de tijd die het kost kunt vergelijken. Dit is dus een relatieve vergelijking in plaats van een absolute.

Ik hoop dat je wat aan deze informatie hebt.

Groeten,
Matthijs