Travelling salesman problem, Data Structure & Algorithms

Example 3: Travelling Salesman problem

Given: n associated cities and distances among them

Find: tour of minimum length that visits all of city.

Solutions: How several tours are possible?

n*(n -1)...*1 = n!

Because  n! > 2(n-1)

Therefore n! = ? (2n) (lower bound)

As of now, there is no algorithm that determines a tour of minimum length plus covers all of the cities in polynomial time.  But, there are many very good heuristic algorithms.

Posted Date: 4/4/2013 6:19:50 AM | Location : United States







Related Discussions:- Travelling salesman problem, Assignment Help, Ask Question on Travelling salesman problem, Get Answer, Expert's Help, Travelling salesman problem Discussions

Write discussion on Travelling salesman problem
Your posts are moderated
Related Questions
Taking a suitable example explains how a general tree can be shown as a Binary Tree. Conversion of general trees to binary trees: A general tree can be changed into an equiv

Define null values.  In some cases a particular entity might not have an applicable value for an attribute or if we do not know the value of an attribute for a particular entit

What is Solid modeling Solid modeling is the most powerful of the 3-D modeling technique. It provides the user with complete information about the model. Defining an object wit

how to do a merge sorting

Q. Give the adjacency matrix for the graph drawn below:                                                 Ans: Adjacency matrix for the graph given to us


Implement multiple stacks in a single dimensional array. Write algorithms for various stack operations for them.

A  BST is traversed in the following order recursively: Right, root, left e output sequence will be in In Descending order

H o w can you r ot a t e a B i n a r y Tr e e? E x pl a i n r i g h t a n d l eft r ot a tion s by taking an e x a mpl e.   If after

Algorithm for deletion of any element from the circular queue: Step-1: If queue is empty then say "queue is empty" & quit; else continue Step-2: Delete the "front" element