Comments about "Travelling Salesman Problem" in Wikipedia

This document contains comments about the document Travelling salesman problem in Wikipedia
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 NP-hard problem in combinatorial optimization studied in operations research and theoretical computer science.
For an explanation of NP-Hard in Wikipedia: NP-hard
What is the point?
In the theory of computational complexity, the decision version of the TS belongs to the class of NP-complete problems.
For a explanation of NP-complete in Wikipedia: NP-complete . also study P versus NP problem
All NP-Complete problems are NP-Hard but not all NP-Hard problems are NP-Complete.
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 NP-complete, which implies the NP-hardness 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: 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 NP-hard, and the decision problem version is NP-complete.
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