Minimum spanning tree based heuristic, JAVA Programming

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 = {P1, P2, ..., Pn} of n points representing the locations of n cities. The coordinates of Pi is (xi, yi). For simplicity, the coordinates xi and  yi are integers in [0..1000), i.e.,  0  ≤ xi, yi  ≤ 999, i= 1,2,..,n. The distance between Pi and Pj is defined as |xi- xj|+|yi- yj|.

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

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 P1;
  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 ← P1;
  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 P1) 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







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
Related Questions
Integration: Neo4J, OpenGeo, Ikanow Project Description: I have an ongoing project to loosely integrate a variety of existing Open Source products: OpenGeo (geospatial server

(Package Inheritance Hierarchy) Package-delivery services, such as FedEx®, DHL® and UPS®, offer a number of different shipping options, each with specific costs associated. Create

An RMI "service" could well be any Java method that can be invoked remotely. The other service is the JRMP RMI naming service which is a lookup service.

Hi, I have an android sdk assignment which is due monday night. The user will enter the following information. url address www.google.com user name huh@gmail.com password 12

You are asked to write a Java program to calculate the commercial value of the stamps owned by a philatelist. Each philatelist has a name and a collection of stamps. The stamps can

Sudoku Class (Simple Version) The Sudoku class will encapsulate the minimum necessary data and logic to manipulate, print, and set the SudCells , in anticipation of a high

Write names of the DoS attack's phases? DoS (Denail of service): DoS attach has in total 3 kinds of phases and below they are listed: 1. Search 2. Arm 3. Attack

Develop a code for fibonacci series

To load a text-file, read it line by line, and return the total number of alphanumeric tokens it contains and skip over the comments and double-quoted strings in the text-file whil

10.13 (CarbonFootprint Interface: Polymorphism) Using interfaces, as you learned in this chapter, you can specify similar behaviors for possibly disparate classes. Governments and