Travelling salesman problem, Data Structure & Algorithms

Assignment Help:

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! = ? (2ⁿ) (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.

Related Discussions:- Travelling salesman problem

Interest, I=PR/12 numbers of years : Interest Rate up to 1 years : 5...

I=PR/12 numbers of years : Interest Rate up to 1 years : 5.50 Up to 5 years : 6.50 More than 5 year : 6.75 please design an algorithm based on the above information

Develop a material requirements plan, The below figure illustrates the BOM ...

The below figure illustrates the BOM (Bill of Materials) for product A. The MPS (Material requirements Planning) start row in the master production schedule for product A calls for

Homework, Write a recursive function the computes the number of digits in a...

Write a recursive function the computes the number of digits in a positive integer n. For example if n = 6598, the function should return 4. Find a variant expression and a thresho

Sparse matrix, How sparse matrix stored in the memory of a computer?

How sparse matrix stored in the memory of a computer?

Array vs. ordinary variable, Q. Describe what do you understand by the term...

Q. Describe what do you understand by the term array? How does an array vary from an ordinary variable? How are the arrays represented in the specific memory?

Algorithm for stack using array, write an algorithm for stack using array p...

write an algorithm for stack using array performing the operations as insertion ,deletion , display,isempty,isfull.

Stack, implement multiple stacks ina single dimensional array. write algori...

implement multiple stacks ina single dimensional array. write algorithams for various stack operation for them.

Queue, algorithm for insertion in a queue using pointers

algorithm for insertion in a queue using pointers

Implementation of dequeue, Dequeue (a double ended queue) is an abstract da...

Dequeue (a double ended queue) is an abstract data type alike to queue, where insertion and deletion of elements are allowed at both of the ends. Like a linear queue & a circular q

Depth First Search Through Un-weighted Connected Graph , Q. Write down the ...

Q. Write down the algorithm which does depth first search through an un-weighted connected graph. In an un-weighted graph, would breadth first search or depth first search or neith

Write Your Message!

Name

Email id

Message

Verfication Code

User Account

All Pages