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
what is frequency count with examble

The space-complexity of the algorithm is a constant. It just needs space of three integers m, n and t. Thus, the space complexity is O(1). The time complexity based on the loop

Explain about Franklin Algorithm We mentioned how the number of possible comparisons of polygons grows as the square of the number of polygons in the scene. Many of the hidden-

Example: (Single rotation into AVL tree, while a new node is inserted into the AVL tree (LL Rotation)) Figure: LL Rotation The rectangles marked A, B & C are trees

What are the different ways of representing a graph? The different ways of representing a graph is: Adjacency list representation: This representation of graph having of an

Ask question #explain it beriflyMinimum 100 words accepted#

Q. What do you mean by the best case complexity of quick sort and outline why it is so. How would its worst case behaviour arise?

compare two functions n and 2n for various values of n. determine when second becomes larger than first

Binary Space Partition A binary space-partitioning (BSP) tree is an efficient method for determining object visibility by painting surfaces onto the screen from back to front,

what is alphanumerical code