handelsreizgersprobleem

chris cambré, Nov 22, 2017

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 [url=https://lirias.kuleuven.be/bitstream/123456789/269896/1/art.pdf]Het harde probleem van de handelsreiziger[/url].


  • 1. 3 punten
  • 2. 4 punten
  • 3. 5 punten
  • 4. Europese steden

1.

3 punten

graaf en circuit met drie punten
Een graaf waarin elk van de drie niet collineaire punten met elkaar verbonden zijn, vormt een driehoek.[br]Een circuit dat één keer elk van de drie punten aandoet, volgt gewoon de drie verbindingen. Het maakt niet uit waar je begint en of je tegen de klok in of met de klok mee draait.
Versleep een of meerdere punten en zie hoe de lengte van het circuit mee verandert.
– chris cambré

2.

–

3.

–

4.

–

Information