Minimum spanning tree based heuristic, JAVA Programming

Assignment Help:

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. 

 


Related Discussions:- Minimum spanning tree based heuristic

Decision structures, for $9.95 per month, 10 hours of access are provided.A...

for $9.95 per month, 10 hours of access are provided.Additional hours are $2.00 per hour

Program to calculate the value into hours and minutes, Specifically, you'll...

Specifically, you'll create a program that will hold minutes worked and assign a value. Calculate the value into hours and minutes. Display the result as shown in Figure 2. Reme

What is resuscitation trolley explain their features, What is Resuscitation...

What is Resuscitation Trolley explain their features? A proper resuscitation kit is mandatory for the ICU. In addition to trolleys that can be moved around the ICU there should

Need android - ios pdf reader, Project Description: Our project consists...

Project Description: Our project consists of a plain application, both for iPad/iOS (Newsstand app) and Android 4.x which will download PDF magazines from the internet, after ha

What is the basic difference between threads and processes? , A process is ...

A process is an execution of a code but a thread is a single execution sequence within the process. A process may contain multiple threads. A thread is sometimes named a lightweigh

Coding, code for error correction and detection using even odd parity

code for error correction and detection using even odd parity

Write a java windowed application, For this assignment, you will write a Ja...

For this assignment, you will write a Java windowed application to do online quiz on general knowledge and the application also displays the quiz result. Overview of the applic

Arraya, what is arrays and how do they operate

what is arrays and how do they operate

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",

Java application to simulate a bank system, Write a Java application to sim...

Write a Java application to simulate a bank system. In the system, customers can open new bank accounts with the bank, and register/use an online account to manage their bank accou

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd