Re:Ant Colony Optimization Visualization for the Travelling ...
by thaumasiotes on Friday December 13, 2019 @09:04AM
(#21781565)
> At least Wikipedia disagrees with your view.
This is a strange thing to say, given the definition provided in the link you cite:
> The travelling salesman problem (also called the travelling salesperson problem or TSP) asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city and returns to the origin city?"
https://en.wikipedia.org/wiki/Travelling_salesman_problem#He...
I'm not confused. For the ACO, Genetic algorithms,... approaches you still need to show that the tour that was found has the lowest possible length... which you cannot without iterating all tours (or doing a branch and bound, which is the same but you prune bad partial tours early).
Obviously, people typically work with well known problems where the best tour is already known. They then typically determine the quality of their 'solution' as the relative difference to the best tour in some metric.