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
Difference among Prism's and Kruskal's Algorithm In Kruskal's algorithm, the set A is a forest. The safe edge added to A is always a least-weight edge in the paragraph that lin

Explain th term input and output-  Pseudocode Input and output indicated by the use of terms input number, print total, output total, print "result is" x and so on.

Hear is given a set of input representing the nodes of a binary tree, write a non recursive algorithm that must be able to give the output in three traversal orders. Write down an

Q. Devise a representation for a given list where insertions and deletions can be made at both the ends. Such a structure is called Deque (which means Double ended queue). Write fu

Illumination of wire frame The colour or shade that a surface appears to the human eye depends primarily on three  factors : Colour and strength of incoming illumination

Write a program for reversing the Linked list

algorithm of output restricted queue.

In the amortized analysis, the time needed to perform a set of operations is the average of all operations performed. Amortized analysis considers as a long sequence of operations

Definition: A set of data values & related operations that are accurately specified independent of any particular implementation. As the data values and operations are described

This notation bounds a function to in constant factors. We say f(n) = Θ(g(n)) if there presents positive constants n 0 , c 1 and c 2 such that to the right of n 0 the value of f