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. Which sorting algorithm can be easily adaptable for singly linked lists? Explain your answer as well.        Ans: The simple Insertion sort is sim

Program will demonstrate the insertion of an element at desired position /* Inserting an element into contiguous list (Linear Array) at particular position */ /* contiguous_

An interesting application or implementation of trees is the playing of games such as tie-tac-toe, chess, nim, kalam, chess, go etc. We can depict the sequence of possible moves

Sort the following array of elements using quick sort: 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8.

write a COBOL program to find the biggest of two numbers

As we talked in class, a program with two integer variables is universal. Now, we consider a special form of four variableprograms. Let G = (V; E) be a directed graph, where V is a

Q.1 What is an algorithm? What are the characteristics of a good algorithm? Q.2 How do you find the complexity of an algorithm? What is the relation between the time and space c

what is the impoartance of average case analysis of algorithm

Illustrates the program segment for Quick sort. It uses recursion. Program 1: Quick Sort Quicksort(A,m,n) int A[ ],m,n { int i, j, k; if m { i=m; j=n+1; k

Q. Compare and contrast various sorting techniques or methods with respect to the memory space and the computing time.