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. Write  down the  algorithm  to  insert  an  element  to  a  max-heap  which  is  represented sequentially.           Ans: The algorithm to insert an element "newkey" to

Q. Explain the term hashing? Explain any five well known hash functions.                         Ans: Hashing method provides us the direct access of record from the f

Write a detailed description of a function that takes in an integer as an argument, then prints out the squares of all positive integers whose squares are less than the input. (The

Two broad classes of collision resolution techniques are A) open addressing and B) chaining

if two relations R and S are joined, then the non matching tuples of both R and S are ignored in

The best algorithm to solve a given problem is one that requires less space in memory and takes less time to complete its execution. But in practice it is not always possible to

In a circular linked list There is no beginning and no end.

Importance of Object-Oriented over java Java is basically based on OOP notions of classes and objects. Java uses a formal OOP type system that should be obeyed at compile-t

example of stack using flowchart

how to convert 12 hour format into 24 hour format using c program