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
1. The following is a recursive algorithm to calculate the k -th power of 2. Input k a natural number Output kth power of 2 Algorithem: If k =0then return 1 Else return 2* po

hello, i need help in data mining assignment using sas em and crisp-dm

Q. Give the algorithm to build a binary tree where the yields of preorder and post order traversal are given to us.

what is queues? how it work? and why it used? i want an assignment on queue .....

How to create an General Tree and how to search general tree?

In order to get the contents of a Binary search tree in ascending order, one has to traverse it in In-order

Q. Make a BST for the given sequence of numbers. 45,32,90,34,68,72,15,24,30,66,11,50,10 Traverse the BST formed in  Pre- order, Inorder and Postorder.

Type of Qualitative Method: Different  qualitative methods are suitable for different  types of study. Quite often we can  combine  qualitative and quantitative  methods. Many

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

Simplifying Assumptions of wire frame representation Neglect colour - consider Intensity: For now we shall forget about colour and restrict our discussion just to the intensi