Home » Algorithms

Travelling Salesman Problem



In this article, we will learn about the travelling salesman problem and prove that travelling salesman problem is the NP complete problem.
Submitted by Shivangi Jain, on July 29, 2018

Travelling Salesman problem

This problem can be stated as- "Given n number of cities and a travelling salesman has to visit each city. Then we have to find the shortest tour so that the travelling salesman can visit each and every city only once."

This travelling salesman problem is one of the examples of NP-Complete problems.

In the travelling salesman problem, we are given a complete undirected graph G = (V, E) that has a non-negative integer cost c (u, v) associated with each edge (u, v) belongs to E and we must find a tour of G with minimum cost.

Let C (A) denotes the total cost of the edges in the subset A is the subset E.

Travelling Salesman problem

Practically, it is always cheapest to go directly from a place w, going by way of any intermediate stop V can’t be expensive. Or say, cutting out an intermediate stop never increase the cost. This can be formalized that the cost function c satisfies the triangle inequality, if for all vertices u, v, w £ V .

C (u, w) <= c (u, v) + c (v, w)

This triangle inequality is natural one, and is many application it is automatically satisfied. In this problem, our tour starts from an initial state and completes after returning to original state passing through all intermediate states.

If the graph has n vertices, i.e., |V| = n, then the solution space S is given by S = { 1, π, 1, π: is a permutation of (2, 3, ..., n)}.

Then |S| = (n-1)!

The size of S can be reduced by restricting S so that (1, i1,...i2,i(n-1), 1) belongs to S if and only if (ij, ij + 1) £ E, 0 <= j <= n-1, and i0 = in = 1.

State space tree for this problem, for n = 4 and initial and final states 1.

Travelling Salesman problem






Comments and Discussions

Ad: Are you a blogger? Join our Blogging forum.




Quick links
Latest articles, Internship, Members
New...
Coding problems, Algorithms, Discrete Mathematics, Big data
Languages
C, C++, C++ STL, Java, Data Structure, C#.Net, Android, Kotlin, SQL
Web
PHP, Python, JavaScript, CSS, Ajax, Node.js, Web prog.
Programs
C, C++, DS, Java, C#, Python
Aptitude
C, C++, Java, DBMS
Interview
C, Embedded C, Java, SEO, HR
CS Subjects
CS Basics O.S. Networks DBMS Embedded Systems Cloud Computing Machine learning CS Organizations Linux DOS
More...
Articles, Puzzles, News/Updates


Recommended posts
C Tips & Tricks, C++ Tips & Tricks
Introduction to Linux (Its modes, Safety, Most popular Applications)
Linux Best Distros of 2018
C programming optimization techniques
Differences b/w C & Embedded C?
Embedded C Interview Q. & A.
C programming tips for Embedded Development
Basic rules of writing a C program
Important points (rules) to remember while writing C/C++ program
Top 5 Websites for solving programming challenges
Read more...


Others...
Computer G.K. (MCQ)
Most viewed pages...
Categories...



Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing » Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates

© https://www.includehelp.com some rights reserved.