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

Use of weblogic platform in project, Use of WebLogic Platform in Project: ... Use of WebLogic Platform in Project: Technologies Tools: Weblogic 8.1, Solaris 9, MQ Series 6.0, iplanet 6.1, Mercury Test Director. Project Overview: Wellington Manag

Java Thread, What is use of join in Java Threading What is use of join in Java Threading

Use array to store values in a program, 1) Listing of the source code ( nam... 1) Listing of the source code ( named Rainfall.java ) for your program 2) Two sample output/execution/runs of your program Optional Group Work: This assignment may be done in

I want school management project, I want School Management project Proje... I want School Management project Project Description: An easy school management project which able to store all data about students like fees structure, admission details and

Make changes to an editable pdf form, Make Changes to an Editable PDF Form ... Make Changes to an Editable PDF Form Project Description: I need for someone who is able to make some changes to PDF forms. Skills required: Data Processing, Data Entry

Define testing with respect to programming, Define testing with respect to ... Define testing with respect to programming? Testing is the process through that we try to determine the presence defects in a program. Testing is an significant step in soft

Describe java operators, Describe java operators? An operator is a symb... Describe java operators? An operator is a symbol which operates on one or more arguments to generate a result. The Hello World program is so easy it doesn't use any operators,

Write a java client by using arraylists, 1. The purpose of this problem is ... 1. The purpose of this problem is to practice using ArrayLists.Write a Java client file containing a mainmethod plus other methods as needed to solve the following problem (no clas

What is constructor, What is Constructor? A constructor is used to init... What is Constructor? A constructor is used to initialize a newly created object. It's called just after memory is allocated for the object. It can be used to initial

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