WisFaq!

Wat is de naieve methode?

Ik zou graag willen weten wat de naieve methode inhoudt en hoe deze PRECIES werkt...

niels
5-1-2004

Antwoord

Het handelreizigersprobleem?

Voor het eerste deel van de probleemstelling zou je kunnen beginnen door eens na te gaan hoeveel tijd het kost om alle mogelijke routes te onderzoeken. Stel je hebt achtereenvolgens een route met eerst 2 steden, dan met 3 steden, vervolgens 4 steden en je wilt alle mogelijke routes narekenen. Eerst zul je moeten bepalen hoeveel mogelijke routes er zijn bij 2, 3, 4 etcetera steden. Stel dat je dan per onderzochte route een duizendste seconde rekent (immers, een pc kan zo'n berekening van de totale afstand van een route snel uitvoeren). Het lijkt zo weinig, deze een duizendste seconde, maar maak maar eens een tabel voor n=1 tot en met n=20 steden met de daarbij horende totale rekentijden.

Maar ik geef toe het is een gok!

Zie Het handelsreizigersprobleem [http://www.math.rug.nl/didactiek/Dijkstra/Handelsreiziger.htm]

WvR
5-1-2004