Ask a question to Desklib · AI bot

Ask NowBETA

A Programming Approach to Solving the Travelling Salesman Problem Using a Gree

5 Pages1118 Words187 Views
   

Added on  2019-09-22

About This Document

Objectives Design and implement a program to solve the Travelling Salesman Problem using a greedy algorithm based on nearest neighbours and a branch-and-bound algorithm; Use appropriate data structures for different algorithms; Analyse the results of different algorithms. Task You should write a single program which implements the greedy algorithm based on nearest neighbours and a branch-and-bound algorithm to find approximate and optimal solutions for the Travelling Salesman Problem, respectively.
BookmarkShareRelated Documents
ObjectivesDesignandimplementaprogramtosolvetheTravellingSalesmanProblemusingagreedy algorithmbased onnearestneighboursanda branch-and-bound algorithm;Useappropriate datastructures fordifferentalgorithms;Analyse the resultsofdifferentalgorithms.TaskYoushouldwriteasingleprogramwhichimplementsthegreedyalgorithmbasedonnearestneighbours andabranch-and-boundalgorithmtofindapproximateandoptimal solutionsfortheTravelling Salesman Problem, respectively.ProgramYourprogramshouldreadasymmetricmatrixfrom atextfilethatdescribesweightededgesofan undirected,completegraphandfind theHamiltoniancyclesusing thegreedy andbranch-and-bound algorithms.Yourprogramshouldalsoreadalistofcity namescorresponding to theverticesofthe graph represented bytheadjacencymatrix.The programwilldisplaythe tourand related information.Since thisassignmentfocusesonthealgorithmicsolutionoftheproblem,STLorJavaCollectionor othercollectionframeworkoftheprogramminglanguageofyourchoicecanbeused.Libraryfunctions can also be used.Yourprogramshould bereadable and wellcommented.DataStructuresandAlgorithmsGreedyalgorithmStrategy:NearestneighbourBranch-and-boundalgorithmUpperbound:weightbynearestneighboursLowerbound:minimalweightwithoutconstraintsStrategies:1. Breadth-first;2. Depth-first.Choosesuitable datastructuresforthealgorithms andstrategies, to be describedinyour report.
A Programming Approach to Solving the Travelling Salesman Problem Using a Gree_1
Requirements(10marks)1. ProgramImplement the greedy algorithmand Branch-and-bound algorithmwithtwo strategies.(2,3and3marks,respectively)2. Report: a)CoverpageStudentname Subjectcode StudentnumberEmailID(0 mark;yourassignment willnotbe marked ifthereis notthis section)b)Methodsand resultanalysis(no more than400words)Describethealgorithms,datastructuresandstructureofyourcode.Analyseanddiscuss yourresultsfromthegreedyalgorithm andbranch-and-boundalgorithm andthe numberofnodesgeneratedwithtwostrategies.Stateaconclusionaboutthealgorithms and strategies. (2marks)OtherrequirementsAllyourprogramsexcludinga4compileanda4runscripts willhavethefollowingheader:/***Studentname:*Subjectcode:*Studentnumber:*EmailID:**(Thefollowingheadinggoesallplaceswhereappropriateif* allorpartofcodeinyourprogramisnotwrittenbyyou.)*Author:*Sources:(citationofthesources)*/Yourprogramscanbecompiledandexecutedwithbashscriptscalleda4compileanda4run, respectively, on Ubuntusetup in the lab.Thescript a4runshould be configuredtorunforbothinputfiles (Australia_roads.txt and Australia_flights.txt)toproduceallresults.Failuretocompileandrunyourprogramtoproduceallresultsfromyourscriptswill receive 0 mark.
A Programming Approach to Solving the Travelling Salesman Problem Using a Gree_2

Found this document preview useful?

Related Documents
Assignment on Data Structures and Algorithms (Doc)
|3
|1133
|304

Parallel Distributed Branch and bound solution in rmi PDF
|18
|829
|98

Solving a Color Maze using DFS
|7
|1042
|184

Assignment - Girvan-Newman Algorithm | Spark Framework
|5
|1250
|54

Programming, Algorithms and Data Structure: Weekly Tasks and Exercises
|2
|501
|348

Program Design for Network Routing using Dijkstra's Algorithm
|6
|828
|262