Problem description: A travelling salesman wants to make a tour of the cities and returns back to the starting point. What is the minimum length tour?

• Formal Definition:

o   Input: A set S = {P₁, P_2, ..., P_n} of n points representing the locations of n cities. The coordinates of P_i is (x_i, y_i). For simplicity, the coordinates x_i and  y_i are integers in [0..1000), i.e.,  0  ≤ x_i, y_i  ≤ 999, i= 1,2,..,n. The distance between P_i and Pj is defined as |x_i- x_j|+|y_i- y_j|.

o    Output: A TSP tour that starts from P₁, visit all the cities (P_i, i=2,3..,n) and return back to starting point P₁

o    Objective: Minimize the total length of the TSP tour.

HEURISTICS

• Minimum Spanning Tree (MST) Based Heuristic

1. Construct a MST, T, for the points in S from starting point P₁;
2. Traverse around T to get the initial TSP tour for S;
3. Exploit the triangular inequality and remove unnecessary visits in the TSP tour.
4. Compute the length of the tour.

• Nearest Neighbour Heuristic

1. current position ← P₁;
2. Loop for n-1 steps

1. At each step, choose to visit next the city that is closest to the current position;
2. Update the current position;

o   Including the closing edge (back to P₁) in the tour;

o   Compute the length of the tour.

TASKS

1.  Implement the MST Based Heuristic;

2.  Implement the Nearest Neighbour Heuristic;

3.  Implement a function, randomSetGenerator that will generate a set of random points on the L1-metric Plane.

4.  Conduct the following experiment for n=100

o   Repeat the following for 10 times

§   Call randomSetGenerator to generate a set S of n random points.

• Feed S to the MST Based Heuristic. Record the length of the tour and the execution time.

• Feed S to the Nearest Neighbour Heuristic. Record the length of the tour and the execution time.

o   Compute the average length of the tour and the average execution time for the MST Based Heuristic.

o   Compute the average length of the tour and the average execution time for the Nearest Neighbour Heuristic.

5.  Repeat the above experiments for n = 200, 300, 400, 500, 600, 700, 800, 900 and 1000. Collect the statistics (average length of the tour and average execution time) from the experiments. Compare the two heuristics in term of the average length of the tour and average execution time. 

 

Posted Date: 2/20/2013 1:19:59 AM | Location : United States

Ask an Expert

Related Discussions:- Minimum spanning tree based heuristic, Assignment Help, Ask Question on Minimum spanning tree based heuristic, Get Answer, Expert's Help, Minimum spanning tree based heuristic Discussions

Write discussion on Minimum spanning tree based heuristic
Your posts are moderated

Write your message here..

Related Questions

Jframe , In this assignment I would like to have java code that would have ... In this assignment I would like to have java code that would have either JFrame or something similar with multiple buttons like "BaseCase", "CoalLosses", "Demand", "NoCT,nuclear",

Recursive Division Maze Generation, can you tell me what the code for a 2d ... can you tell me what the code for a 2d random java array using Recursive Division Maze Generation

Inheritance, Inheritance - is the inclusion of state and behavior of a ba... Inheritance - is the inclusion of state and behavior of a base class in a derived class so that they are accessible in that derived class. The key benefit of Inheritance is that

Describe in brief about the polymorphism, Describe Polymorphism? Polymo... Describe Polymorphism? Polymorphism can be referred as one name many forms. It's the ability of methods to behave differently, depending upon object who is calling it. Key feat

Texas holdem poker java game source code, Texas Hold'em Poker Java Game Sou... Texas Hold'em Poker Java Game Source Code Project Description: I am seeking Java source code for a Texas Hold'em Poker game. The game could have client and server side mod

Cadence design systems, Cadence Design Systems:   Role Working ... Cadence Design Systems:   Role Working on tickets including debugging of unix based applications Installations of unix based tools/utlity Installation

Elaborate the + operator and its constraints with example, Elaborate the ‘+... Elaborate the ‘+ ' operator and its constraints along with the help of examples? The + Operator Used on Strings. The + operator could also be used to add string variables or te

J, object object

Develop a school java project, Develop a School java project Project Des... Develop a School java project Project Description: Programming java, threads. Not so hard but requires knowledgeSkills required: Java

Dialog window in Oracle by Java stored procedure, Is it possible to create ... Is it possible to create any dialog window in Oracle in Java stored procedure?