Welke technieken zijn er om de kortste route te vinden bij een handelsreizigersprobleem?
Ik doe een begaafden programma op school maar ik snap er niet veel van. Dit kwintaal hebben we het over grafen, als praktische opdracht moeten we een handelsreizigersprobleem bedenken en de snelste route vinden. We moeten het zonder computer kunnen oplossen. Welke technieken kunnen we het beste gebruiken, en welk probleem is handig om te gebruiken.
Alvast bedankt,
Maurits
-
Vraag volgen
- Delen
-
-
Weet jij het antwoord?
Het handelsreizigersprobleem is een bekend probleem uit de complexiteitstheorie. De formulering is eenvoudig: vind de kortste route om alle gegeven plaatsen één keer te bezoeken. De oplossing is echter verre van eenvoudig. Het is een NP-moeilijk probleem, hetgeen (kort en misschien niet strikt genoeg geformuleerd) betekent dat er geen wezenlijk snellere oplossingsmethode bestaat dan alle mogelijkheden één voor één proberen. Je kunt natuurlijk wel wat winst behalen door routes waar je echt van het ene eind naar het andere springt en weer terug uit te sluiten. Je vindt al snel routes die redelijk in de buurt van het ideaal liggen. Maar wat is echt de kortste? En hoe toon je dat aan? Ik kan me voorstellen dat je voor een opdracht een voorbeeld verzint met 6 tot 8 steden en dan laat zien dat één route van alle mogelijke de kortste is. Dat kan nog net door alles uit te schrijven zonder computer. Maar bij grotere aantallen wordt het algauw onbegonnen werk. Zet er een opmerking bij dat er geen wezenlijk snellere methode bestaat om dit aan te pakken dan zul je vast goed scoren.
Stel zelf een vraag
Ben je op zoek naar het antwoord die ene vraag die je misschien al tijden achtervolgt?
