handelsreizgersprobleem
- Auteur:
- chris cambré
- Onderwerp:
- Grafiek
Wat is het kortste circuit op een graaf dat juist één keer langs elk punt passeert?
Dit probleem wordt 'het handelsreizigersprobleem' (travelling salesman problem) genoemd, naar een handelaar die wil uitzoeken hoe hij de route langs zijn klanten kan optimaliseren.
Het optimaliseren van een reisroute is vermoedelijk al eeuwenoud, maar het werd voor het eerst als 'het handelsreizigersprobleem' geformaliseerd in 1930 en werd een van de meest bestudeerde optimalisatieproblemen. Hierbij worden steeds nieuwe algoritmen ontwikkeld om circuits met steeds meer punten te optimaliseren. Een bekende toepassing van dit probleem is het produceren van printplaten, waarbij men de bewegingen van een boorkop boven de printplaats wil minimaliseren.
Wil je weten waarom dit probleem zo hardnekking is om op te lossen, lees dan het artikel Het harde probleem van de handelsreiziger.
