Betekenis van handelsreizigersprobleem | Babel Free

Definities

een bekend informaticavraagstuk: Gegeven n steden samen met de afstand tussen ieder paar van deze steden, vind dan de kortste weg die precies één keer langs iedere stad komt.

Equivalenten

Voorbeelden

“Er bestaat een grote groep van problemen die heel eenvoudig lijken, maar waar geen efficiënt algoritme voor bestaat. Berucht is het handelsreizigersprobleem. Een handelsreiziger wil naar verschillende steden om zijn handel naar klanten te brengen. Tijd en benzine kosten geld, dus vraagt de handelsreiziger zich af wat de kortste route is waarbij hij langs al deze steden komt.”

“In zijn artikel liet Dorigo als eerste zien hoe je de spoorzoekerskwaliteiten van mieren kunt gebruiken om het zogeheten handelsreizigersprobleem op te lossen. Dat vermaarde wiskundige vraagstuk is even simpel te formuleren als onmogelijk tot in de puntjes uit te rekenen: wat is de korste weg voor een handelsreiziger om een reeks steden in een gebied éénmaal te bezoeken?”

ERK-niveau