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
Q. Explain any three methods or techniques of representing polynomials using arrays. Write which method is most efficient or effective for representing the following polynomials.

The advantage of list over Arrays is flexibility. Over flood is not a problem until the computer memory is bushed. When the individual record are quite large, it may be difficult t

Q. Write down an algorithm to insert a node in the beginning of the linked list.                         Ans: /* structure containing a link part and link part


reverse the order of elements on a stack S using two additional stacks using one additional stack

Determination of Time Complexity The RAM Model The random access model (RAM) of computation was devised through John von Neumann to study algorithms. In computer science,

ALGORITHM (Insertion of element into a linked list) Step 1 Begin the program Step 2 if the list is empty or any new element comes before the start (head) element, then add t

What do you mean by hash clash? Hashing is not perfect. Occasionally, a collision occurs when two different keys hash into the same hash value and are assigned to the same arra

Write an algorithm for compound interest.