Comments about "Travelling Salesman Problem" in Wikipedia
This document contains comments about the document Travelling salesman problem in Wikipedia
 The text in italics is copied from that url
 Immediate followed by some comments
In the last paragraph I explain my own opinion.
Contents
Introduction
At the beginning of this paragragh we read:

The travelling salesman problem (TSP) is a NPhard problem in combinatorial optimization studied in operations research and theoretical computer science.

For an explanation of NPHard in Wikipedia: NPhard
What is the point?

In the theory of computational complexity, the decision version of the TS belongs to the class of NPcomplete problems.

For a explanation of NPcomplete in Wikipedia: NPcomplete . also study
P versus NP problem
All NPComplete problems are NPHard but not all NPHard problems are NPComplete.
The question is how important is this difference in relation to the "travelling salesman problem"
1. History


Richard M. Karp showed in 1972 that the Hamiltonian cycle problem was NPcomplete, which implies the NPhardness of TSP. This supplied a mathematical explanation for the apparent computational difficulty of finding optimal tours.
It is very important to make a clear difference between:
 To find the solution of the problem i.e. the shortest route
 To find the fastest solution.
Both should give the same answer.
For all problems it is difficult to find the fastest algorithm because you never know what is the fastests.










4. Computing a solution
4.1 Computational complexity

The problem has been shown to be NPhard, and the decision problem version is NPcomplete.

First you clearly have to define what the difference is between the problem and the decision problem.
The "travelling salesman problem" is to find an algorithm which calculates the shortest route to connect all the towns once.
To write a program to implement such an algorithm to do that is easy.
The real chalenge is to find the fastest algorithm.







13. Further reading
See:
Reflection
If you want to give a comment you can use the following form Comment form
Created: 13 May 2011
Back to my home page Contents of This Document