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
Your first task will be to come up with an appropriate data structure for representing numbers of arbitrary potential length in base 215. You will have to deal with large negative

#questionalgorithm for implementing multiple\e queues in a single dimensional array

Thus far, we have seen the demonstration of a single queue, but several practical applications in computer science needs several queues. Multi queue is data structure in which mult

Program segment for All pairs shortest paths algorithm AllPairsShortestPaths(int N, Matrix C, Matrix P, Matrix D) { int i, j, k if i = j then C[i][j] = 0  for ( i =

Define min-heap A min-heap is a complete binary tree in which each element is less than or equal to its children. All the principal properties of heaps remain valid for min-hea

While BFS is applied, the vertices of the graph are divided into two categories. The vertices, that are visited as part of the search & those vertices that are not visited as part

Write a program to simulate searching over a hashed file, with different assumptions for the sizeof file pages.Write a program to perform equality search operations on the hashed f

what is frequency count with examble

Data records are stored in some particular sequence e.g., order of arrival value of key field etc. Records of sequential file cannot be randomly accessed i.e., to access the n th

implement multiple stack in single dimensionl array.write algorithms for various stack operation for them