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


Related Discussions:- Travelling salesman problem

Explain about greedy technique, Explain about greedy technique The  gre...

Explain about greedy technique The  greedy  method  suggests  constructing  a   solution  to  an  optimization  problem   by  a sequence of steps, every expanding a partially c

Briefly explain the prim''s algorithm, Question 1 Describe the following- ...

Question 1 Describe the following- Well known Sorting Algorithms Divide and Conquer Techniques Question 2 Describe in your own words the different asymptotic func

Create accessors for this data structure, Create a Money data structure tha...

Create a Money data structure that is made up of amount and currency. (a) Write a constructor for this data structure (b) Create accessors for this data structure (c) Writ

Explain in detail about the ruby arrays, Explain in detail about the Ruby a...

Explain in detail about the Ruby arrays Ruby arrays have many interesting and powerful methods. Besides indexing operations which go well beyond those discussed above, arrays h

If-then-else statements, In this example, suppose the statements are simple...

In this example, suppose the statements are simple unless illustrious otherwise. if-then-else statements if (cond) { sequence of statements 1 } else { sequence of st

Stack, write pseudocode to implement a queue with two stacks

write pseudocode to implement a queue with two stacks

Multikey file organization, what are the applications of multikey file orga...

what are the applications of multikey file organization?

The complexity ladder, The complexity Ladder: T(n) = O(1). It is ca...

The complexity Ladder: T(n) = O(1). It is called constant growth. T(n) does not raise at all as a function of n, it is a constant. For illustration, array access has this c

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd