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

Data Structure, Ask consider the file name cars.text each line in the file ...

Ask consider the file name cars.text each line in the file contains information about a car ( year,company,manufacture,model name,type) 1-read the file 2-add each car which is repr

frequenty count of function, Ask question find frequency count of function...

Ask question find frequency count of function- {for(i=1;i {for(j=1;j {for(k=1;k } } }

Best case, for i=1 to n if a[i}>7 for j=2 to n a[j]=a{j}+j for n=2 to n a...

for i=1 to n if a[i}>7 for j=2 to n a[j]=a{j}+j for n=2 to n a[k]=a[j]+i else if a[1]>4 && a[1] for 2 to a[1] a[j]= a{j]+5 else for 2to n a[j]=a[j]+i ..

Multiple Queues in a single dimension array, Implement multiple queues in a...

Implement multiple queues in a single dimensional array. Write algorithms for various queue operations for them.

Acyclic graph, Tree is a widely used data structure employed for representi...

Tree is a widely used data structure employed for representing several problems. We studied tree like a special case of acyclic graph. Though, rooted trees are most prominent of al

linear-expected-time algorithm, Implement a linear-expected-time algorithm...

Implement a linear-expected-time algorithm for selecting the k th smallest element Algorithm description 1. If |S| = 1, then k = 1 and return the element in S as the an

Infix to postfix, [(a+b)/(c+d)^(e+f)]+(g+h)/i

[(a+b)/(c+d)^(e+f)]+(g+h)/i

Conversion of general trees into the binary trees, By taking an appropriate...

By taking an appropriate example explain how a general tree can be represented as a Binary Tree. C onversio

Determine the algorithm for z-buffer method, Algorithm for Z-Buffer Method ...

Algorithm for Z-Buffer Method (a) Initialize every pixel in the viewport to the smallest value of z, namely z0 the z-value of the rear clipping plane or "back-ground". Store a

Single pointer pointing to the tail of the queue, Can a Queue be shown by c...

Can a Queue be shown by circular linked list with only single pointer pointing to the tail of the queue? Yes a Queue can be shown by a circular linked list with only single p

Write Your Message!

Name

Email id

Message

Verfication Code

User Account

All Pages