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

What is meant through semantic error, What is meant through semantic error?... What is meant through semantic error? It is an error that a developer encounters while a statement is executed but it was not intended through him (the developer). Such errors ar

Prepare a game in corona, Prepare a Game in Corona (for Android and IOS) ... Prepare a Game in Corona (for Android and IOS) Project Description: We are looking to prepare a game for mobile platform similar to Zombie Smasher for iOS and Android. Eve

Please answer this, Assignment Help >> JAVA Programming Learning Outcomes:... Assignment Help >> JAVA Programming Learning Outcomes: 1. Use different program control statements in a programming language 2. Demonstrate the use of arrays with a programming

Applet, how to create a face with nose using applet how to create a face with nose using applet

Pessimistic and Optimistic concurrency control?,

Write html and javascript code which displays a textbox, Write HTML and Jav... Write HTML and JavaScript code which displays a textbox and button on a web page? While user enters text in the text box and clicks the button it displays in that text in the m

Need java assignment for course, Need Java Assignment for course Project... Need Java Assignment for course Project Description: I want to get an assignment done. Involves building on a minesweeper game written in Java. You subsequent code is to be u

SWING, Application using Swing API Application using Swing API

Converting strings to numeric primitive data types, Converting Strings to N... Converting Strings to Numeric Primitive Data Types To convert a string which is containing digits to a primitive data type, wrapper classes can help. parseXxx method can be u

Create a general design for a class-implement and test, Objectives 1.  ... Objectives 1.      To design and implement a simple class. 2.      To write a test program to create instances of your class and demonstrate its behaviour. 3.      To col