Design and implement an algorithm for finding the best tour

Assignment Help Data Structure & Algorithms
Reference no: EM131076807

Project: The Travelling Salesman Problem (TSP)

Project Specification

Your group will design and implement an algorithm (or algorithms) for finding the best tour you can. TSP is not a problem for which you will be able to easily find optimal solutions. It is difficult. Your goal is to find the best solution you can in a certaintime frame. You may want to start with some local search heuristics. There is much literature on methods to "solve" TSP please cite any sources you use. Use any programming language you want that runs on flip2.engr.oregonstate.edu.

Your program must:

• Accept problem instances on the command line

• Name the output file as the input file's name with .tour appended (for example input
tsp_example_1.txt will output tsp_example_1.txt.tour)

• Compile/Execute correctly and without debugging on flip2.engr.oreognstate.eduaccording to specifications and any documentation you provide.

Input specifications:

• A problem instance will always be given to you as a text file.

• Each line defines a city and each line has three numbers separated by white space.

o The first number is the city identifier
o The second number is the city's x-coordinate
o The third number is the city's y-coordinate.

Output specifications:

• You must output your solution into another text file with n + 1 line, where n is the number of cities.

• The first line is the length of the tour your program computes.

• The next n lines should contain the city identifiers in the order they are visited by your tour.

o Each city must be listed exactly once in this list.

o This is the certificate for your solution and your solutions will be checked. If they are not valid you will not receive credit for them.

Example instances: We have provided you with three example instances. They are available on Canvas and are provided according to the input specifications.

• tsp_example_[*].txt Input files

• tsp_example_[*].txt.tour Example outputs corresponding to these three input cases. The optimal tour lengths for example instances 1, 2, and 3 are 108159, 2579 and 1573084, respectively. Clearly these do not match the values in the tour files. You should use these values to evaluate your algorithm. For full credit it is required that the ratio of

(Your solution)/(optimal solution) <= 1.25.

Testing

A testing procedure tsp-verifier.py is given that we will use to verify your solutions. Usage to test example an instance is: (NOTE: requires TSPAllVisitied.py)

python tsp-verifier.py inputfilename solutionfilename

You should test that your outputs are correct. By "correct" we mean that the distances have been computed correctly not that the solution is optimal.

Competition

We will hold a completion. The competition will require your program to find the best solution possible to one or more test instances within a fixed amount of time (e.g. 3 minutes). The competition instances will be available on Monday 5/30/16 at 8:00 am PST. You will not be told the optimal tour length for these instances. You will post your results to the competition instances tothe competition discussion board.

Project Report

You will submit a project report containing the following:

• A description of at least three different methods/algorithms for solving the Traveling Salesman Problem. Summarize any research you did.

• A verbal description of your algorithm(s) as completely as possible. You may select more than one algorithm to implement.

• A discussion on why you selected the algorithm(s).

• Pseudo code

• Your "best" tours for the three example instances and the time it took to obtain these tours.

• Your best tours for the competition test instance(s).

Reference no: EM131076807

Questions Cloud

Purchase a product is simply good marketing : Some say that targeting any group of consumers who are willing and able to purchase a product is simply good marketing.
Website design and implementation plan : Provide detailed plans regarding the type of website you would like to develop for your e-business. For this assignment you will provide a presentation that contains a detailed discussion of an implementation plan.
Should is blank be public protected or private explain : What small change(s) would you make to the classes to ensure that the correct version of isExpression is called?
Convenience product-heterogeneous shopping product : Choose the Product Classification that defines this product based on the previously defined target market. Explain your rationale. Choose between Convenience Product, Heterogeneous Shopping Product, Homogenous Shopping Product, Specialty Product, ..
Design and implement an algorithm for finding the best tour : Your group will design and implement an algorithm (or algorithms) for finding the best tour you can. TSP is not a problem for which you will be able to easily find optimal solutions.
Explain historical issues that have contributed to problems : Discuss the data and information that you have collected while conducting research on your topic. Discuss how the data relates to the problems and challenges in crime and criminology.
Generation to commercialization : Outline the steps you will take to bring your product to market from idea generation to commercialization, using a multi-step product development process.
Which of these objects can invoke the method fuel type : Which of these objects can invoke the method fuel Type ?
How fast is the height of the water increasing : A cylindrical tank with radius 5 m is being filled with water at a rate of 3m3/min. How fast is the height of the water increasing? Remember to define your variables

Reviews

Write a Review

 

Data Structure & Algorithms Questions & Answers

  Write down a 3-4 page apa formatted paper describing

write 3-4 page apa formatted paper discussing whether in the next few years rdbms will be replaced completely partially

  Identifying the location of rubric objectives

Code Comments are used to identify the location of rubric objectives, Code Formatting is used to raise the readability of the HTML Code.

  Create an assignment on powerpoint presentation

consists of  (4) sections:- a written project plan, revised business requirements document, project plan PowerPoint presentation, and a finalized project plan.

  Steps of asymmetric encryption algorithms to read message

Using only asymmetric encryption algorithms write down any steps taken by Bob which permit him to read the message.

  Bubble sort and quick sort in ascending order

Quick sort in ascending order, with partition choosing pivot in the middle of the sub-array.

  Define a structure type

Define a structure type to represent a single CD. The year must be stored as an integer, all other fields should be strings. Because memory space will be an issue you may not assume a length for the string fields, but must dynamically allocate app..

  Discussion on clustering and data mining

Clustering is generally used along with classification in some applications. In such a case, typically clustering is applied to a dataset to recognize natural grouping of the objects in the dataset,

  Function implements a two-d orthographic projection matrix

The function implements a 2D orthographic projection matrix, which is used for the. In this question you need to implement the function worldToViewportTransform

  Create long queue-customers dequeue to next counter

Write a program to simulate a grocery store checkout counter. Construct one long queue from which customers dequeue to the next available counter.

  Question about arrays, vector and stl

Suppose if x denotes the mean of a sequence of numbers x1, x2,.....xn, variance is the average of the squares of the deviations of numbers from the mean.

  Design and implement an efficient algorithm of an intergers

Design and implement an efficient algorithm that gives a set of S of an intergers and another x, determines whether or not there exist two elements in S whose sum is exactly x

  Compute a shortest-path

Compute a shortest-path from u to v (instead of from u to all the nodes). One way to speed up Dijkstra's algorithm might be to run the algorithm u and from v at the same time.

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