+1-415-315-9853

info@mywordsolution.com

## Programming

 C/C++ Java DOT NET Python Assembly C Sharp Perl COBOL Visual Basic CAD/CAM Object Oriented Programming Asp.NET PHP JSP Shell Scripting Java Script Ajax CSS/HTML Joomla Wordpress Megento Photoshop DBMS PL-SQL Oracle MS-SQL MS-ACCESS My-SQL SYBASE FOXPRO Excel Programming Language Mobile Applications

Home >> Java

TRAVELLING SALESMAN (TSP) PROBLEM ON THE L1-METRIC PLANE

• Problem description: A travelling salesman desires to make a tour of the cities and returns back to the starting point. What is the minimum length of the tour?

• Formal Definition:

- Input: A set S = {P1, P2, …, Pn} of n points representing the locations of n cities. The coordinates of Pi is (xi, yi). For straightforwardness, 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|.

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

- Objective: Minimize the total length of TSP tour.

HEURISTICS

• Minimum Spanning Tree (MST) Based Heuristic

- Construct a MST, T, for the points in S from beginning point P1;

- Traverse around T to get the initial TSP tour for S;

- Exploit the triangular inequality and remove needless visits in the TSP tour.

- Evaluate the length of the tour.

• Nearest Neighbor Heuristic

- Present position ← P1;

- Loop for n-1 steps

- At each step, desire to visit next the city that is closest to the current position;

- Update present position;

- Including closing edge (back to P1) in the tour;

- Evaluate the length of the tour.

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 subsequent experiment for n=100

- Repeat the following for 10 times

- Call randomSetGenerator to generate a set S of n random points.

• Feed S to 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 implementation time.

- Evaluate the average length of the tour and the average execution time for the MST Based Heuristic.

- Evaluate 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.

Programming language: recommend Java.

Java, Programming

• Category:- Java
• Reference No.:- M91646

Have any Question?

## Related Questions in Java

### Java programming using ide netbeansdetailed question must

Java programming using IDE NetBeans Detailed Question: Must use file operations, exception handling, recursive programming (to calculate averages), and encapsulation (or inheritance) in the program Must have four java fi ...

### Write a java program non-gui preferred to demonstrate the

Write a Java program (non-GUI preferred) to demonstrate the use of Iterator. The program should allow a user to do the following: Allow the reading of a collection of animal objects from an external file. Output on scree ...

### Question awhy is it important to avoid the use of reserved

Question A Why is it important to avoid the use of reserved words as you define variables, functions, methods, or identifiers? Do you have any get-arounds to the use of these reserved words that you like to use? (max 80 ...

### Design your own java class that includes at least 3 data

Design your own Java Class that includes at least 3 data fields, 2 constructors and 4 methods. When designing your class, pick an object that you are familiar with and make it your own, realistic, yet simple design with ...

### Write a java program that prints asks the user to enter a

Write a Java program that prints asks the user to enter a positive value (1 less than or equal to 200) and print each number up to that line, 1 per line with the following changes (SNAP CRACKLE POP). • If a number is *** ...

### Javapizzacontactlistat the beginning of all your programs

JavaPizza ContactList At the beginning of all your programs, put a comment box that includes the program name, your name, and a brief description of the program. Example: /************************************************ ...

### Assignment 1overviewthis is an individual assignment that

Assignment 1 Overview This is an individual assignment that requires you to design, develop and test a small procedural Java program. Timelines and Expectations Learning Outcomes Assessed The following course learning ou ...

### Java program 1write a java application that generates a

Java Program 1 Write a Java application that generates a 3-digit random number 100 times. Display the output for each of the generated numbers and the sum of all 100 numbers. Demonstrate your code compiles and runs witho ...

### Java programthis assignment will count as both homework and

Java Program This assignment will count as both homework and lab. Develop a program that will allow the user to display the starting line and the bench for a basketball team. The user will also have the option of swappin ...

### Java program for profhudaneed help with java program just

Java program for Prof.Huda Need help with java program ... just apply an example how i want my assignmemt to look like . you can use the same code to do the program .. by the way i"m using JCreater .. The assignment is : ...

• 13,132 Experts

## Looking for Assignment Help?

Start excelling in your Courses, Get help with Assignment

Write us your full requirement for evaluation and you will receive response within 20 minutes turnaround time.

### WalMart Identification of theory and critical discussion

Drawing on the prescribed text and/or relevant academic literature, produce a paper which discusses the nature of group

### Section onea in an atwood machine suppose two objects of

SECTION ONE (a) In an Atwood Machine, suppose two objects of unequal mass are hung vertically over a frictionless

### Part 1you work in hr for a company that operates a factory

Part 1: You work in HR for a company that operates a factory manufacturing fiberglass. There are several hundred empl

### Details on advanced accounting paperthis paper is intended

DETAILS ON ADVANCED ACCOUNTING PAPER This paper is intended for students to apply the theoretical knowledge around ac

### Create a provider database and related reports and queries

Create a provider database and related reports and queries to capture contact information for potential PC component pro