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

Card, Create a class called DeckOfCards that stores 52 objects of the Card ... Create a class called DeckOfCards that stores 52 objects of the Card class. Include methods to shuffle the deck, deal a deck, and report the number of cards left in the deck. The s

What is an iterator, What is an Iterator? Some of the collection classe... What is an Iterator? Some of the collection classes give traversal of their contents via a java.util.Iterator interface. This interface permits you to walk through a collection

Write a short Java application that stores words in an Array, Write a short... Write a short Java application that stores words in an Array or ArrayList. You get to pick the number of words to store. Generate a random number between 0 (inclusive) and the leng

#title.basics, what is java what is java

Area under the curve, Write a program to find the area under the curve y = ... Write a program to find the area under the curve y = f(x) between x = a and x = b, integrate y = f(x) between the limits of a and b. The area under a curve between two points can b

Illustrate dynamic vs. static class loading?, 1. "Classes are statically lo... 1. "Classes are statically loaded with Java's "new" operator." This would imply that static methods could be executed without the class being loaded. 2. "Unlike the static loa

It, Implement a program that can compute your taxes (assume year 2012, as- ... Implement a program that can compute your taxes (assume year 2012, as- sume a form 1040EZ). The form should ask for your ling status (single, married), income, deductions and cred

Design a payroll system, For your project, you will be designing a payroll ... For your project, you will be designing a payroll system for a company. The company will use the system to generate payroll reports based on different kinds of employees in the com

Java and Arrays, AskWrite an application that uses an Array to store 10mess... AskWrite an application that uses an Array to store 10messages of type String. You will store this Array with 10 messages of your choosing. For example, a message could be “I love

What is the data normalization also define its goal, What is the Data Norma... What is the Data Normalization? Also define its goal. Data normalization is to sort out complex data within easy form. It uses to simplify the complex information to form it mo