3 ms·

with the TSP, any permutation of the list of cities is a correct solution. They just differ in length of the tour. An optimal solution S has len(S) = min {len

with the TSP, any permutation of the list of cities is a correct solution. They just differ in length of the tour. An optimal solution S has len(S) = min {len(P) | P in Perm(cities)}

thaumasiotes 7y ago
No, the correct solution is the one that achieves the minimum travel cost[1]. If any route at all was a correct solution, the problem wouldn't be NP-complete -- it would be the much easier problem of "determine whether a path exists between two nodes in a graph". [1] It's actually easier to analyze the version of the problem which asks you to find any solution of length less than some constant L.
- toolslive 7y ago
  So your view is that the heuristic methods (NN, 2-opt,...) do not yield a solution?
  - thaumasiotes 7y ago
    They do not necessarily yield a correct solution. For example, under a heuristic approach, if you ask "is there a path of length < L?", you may get the answer "no" when the actual answer is "yes". You seem to be confused over the difference between "solution", in the sense of the answer to a well-defined mathematical problem, and "solution", in the sense of "what do I say to my boss?"
    - toolslive 7y ago
      At least Wikipedia disagrees with your view. https://en.wikipedia.org/wiki/Travelling_salesman_problem#Heuristic_and_approximation_algorithms 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.
      - thaumasiotes 7y ago
        > 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?"

with the TSP, any permutation of the list of cities is a correct solution. They just differ in length of the tour. An optimal solution S has len(S) = min {len(P) | P in Perm(cities)}

thaumasiotes 7y ago

No, the correct solution is the one that achieves the minimum travel cost[1]. If any route at all was a correct solution, the problem wouldn't be NP-complete -- it would be the much easier problem of "determine whether a path exists between two nodes in a graph". [1] It's actually easier to analyze the version of the problem which asks you to find any solution of length less than some constant L.

toolslive 7y ago
So your view is that the heuristic methods (NN, 2-opt,...) do not yield a solution?
- thaumasiotes 7y ago
  They do not necessarily yield a correct solution. For example, under a heuristic approach, if you ask "is there a path of length < L?", you may get the answer "no" when the actual answer is "yes". You seem to be confused over the difference between "solution", in the sense of the answer to a well-defined mathematical problem, and "solution", in the sense of "what do I say to my boss?"
  - toolslive 7y ago
    At least Wikipedia disagrees with your view. https://en.wikipedia.org/wiki/Travelling_salesman_problem#Heuristic_and_approximation_algorithms 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.
    - thaumasiotes 7y ago
      > 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?"