Travelling Salesman Problem : Assignment

Added on - Sep 2019

Trusted by 2+ million users,
1000+ happy students everyday
Showing pages 1 to 2 of 5 pages
ObjectivesDesignandimplementaprogramtosolvetheTravellingSalesmanProblemusingagreedy algorithmbased onnearestneighboursandabranch-and-bound algorithm;Useappropriatedatastructuresfordifferentalgorithms;Analysetheresultsofdifferentalgorithms.TaskYoushouldwriteasingleprogramwhichimplementsthegreedyalgorithmbasedonnearestneighbours andabranch-and-boundalgorithmtofindapproximateandoptimalsolutionsfortheTravelling Salesman Problem,respectively.ProgramYourprogramshouldreadasymmetricmatrixfrom atextfilethatdescribesweightededgesofan undirected,completegraphandfindtheHamiltoniancyclesusingthegreedy andbranch-and-bound algorithms.Yourprogramshouldalsoreadalistofcity namescorrespondingtotheverticesofthegraphrepresented bytheadjacencymatrix.The programwilldisplaythetourandrelatedinformation.Sincethisassignmentfocusesonthealgorithmicsolutionoftheproblem,STLorJavaCollectionor othercollectionframeworkoftheprogramminglanguageofyourchoicecanbeused.Libraryfunctions canalsobe used.Yourprogramshould bereadable andwellcommented.DataStructuresandAlgorithmsGreedyalgorithmStrategy:NearestneighbourBranch-and-boundalgorithmUpperbound:weightbynearestneighboursLowerbound:minimalweightwithoutconstraintsStrategies:1.Breadth-first;2.Depth-first.Choosesuitable datastructuresforthealgorithmsandstrategies,to bedescribedinyourreport.
Requirements(10marks)1.ProgramImplementthegreedyalgorithmand Branch-and-bound algorithmwithtwo strategies.(2,3and3marks,respectively)2.Report:a)CoverpageStudentnameSubjectcodeStudentnumberEmailID(0mark;yourassignmentwillnotbemarkedifthereis notthissection)b)Methodsandresultanalysis(nomorethan400words)Describethealgorithms,datastructuresandstructureofyourcode.Analyseanddiscussyourresultsfromthegreedyalgorithm andbranch-and-boundalgorithmandthe numberofnodesgeneratedwithtwostrategies.Stateaconclusionaboutthealgorithms andstrategies.(2marks)OtherrequirementsAllyourprogramsexcludinga4compileanda4runscriptswillhavethefollowingheader:/***Studentname:*Subjectcode:*Studentnumber:*EmailID:**(Thefollowingheadinggoesallplaceswhereappropriateif*allorpartofcodeinyourprogramisnotwrittenbyyou.)*Author:*Sources:(citationofthesources)*/Yourprogramscanbecompiledandexecutedwithbashscriptscalleda4compileanda4run,respectively, onUbuntusetupinthelab.Thescripta4runshouldbe configuredtorunforbothinputfiles(Australia_roads.txt and Australia_flights.txt)toproduceallresults.Failuretocompileandrunyourprogramtoproduceallresultsfromyourscriptswillreceive 0mark.
Desklib Logo
You are reading a preview
Upload your documents to download or

Become a Desklib member to get access