handelsreizgersprobleem

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 probleem werd voor het eerste geformuleerd in 1930 en is een van de meest bestudeerde optimalisatieproblemen. Hierbij worden steeds nieuwe algoritmen ontwikkeld om circuits met steeds meer punten te optimaliseren. De meest bekende toepassing van dit probleem is het ontwerpen van printplaten.