Ask a question to Desklib · AI bot

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

5 Pages1118 Words187 Views

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

## Found this document preview useful?

Related Documents
|3
|1133
|304

|18
|829
|98

|7
|1042
|184

|5
|1250
|54

|2
|501
|348

|6
|828
|262

### Support

#### +1-312 997 5479

Chat with our experts. we are online and ready to help.