” 写作CSE 104程序、 辅导Data Structures程序CSE 104 Data Structures AlgorithmsDepartment of Computer Science and Software Engineering, Xian Jiaotong-Liverpool UniversityCSE104 Coursework 2(Due date: 5pm 06/15/2020 China Time, online ICE submission ONLY)Learning OutcomesOn successful completion of this assignment, students are expected to: – understand and be able to apply a variety of data structures, together with their internalrepresentation and algorithms; – be able to make informed choices between alternative ways of implementation,justifying choices on grounds such as time and space complexity; – be able to select, with justification, appropriate data structures to ensure efficientimplementation of an algorithm. Background informationThis Coursework 2 is a continuation of Coursework 1, where you are required to furtherdevelop algorithms for the travelling salesman problem (TSP). In case that some of you didntwork out the first coursework, this coursework will be based on the solution of Coursework 1, which has been uploaded on the ICE page.In this coursework, you are required to develop a more advanced algorithm for the TSPthat is able to improve upon an existing TSP routine continuously. You will be guided step bystep to complete this algorithm. Through this special journey, you will learn how morecomplicated algorithms work and will be given chances to write your own ones. Current structure of the projectOpen the project zip file for Coursework 2, it should contain three files:1. City.java Represents a city in TSP and stores its information. 2. TSPSolver This is the file that we worked on in coursework 1. At the current stage, itcontains several functions:a. readFile() loads the text files of TSP problems. b. solveProblem() generates an initial routine by continuously choosing theclosest city to visit. c. printSolution() prints a routine and returns the total distance of that routine. d. evaluateSolution() calculates then returns the total distance of a routine, it isa simplified version of printSolution(). It will be needed in this coursework. e. swapCity(), evalSwap(), evalSwap_SLOW_() and swapFirstImprove() they willbe explained in the next section. f. improveRoutine() the entry point of the more complicated algorithm that 写作CSE 104作业、 辅导Data Structures作业、Java程序设计作业调试、Java作业 写作you need to implement. 3. Main.java This file contains the necessary code to make use of TSPSolver.CSE 104 Data Structures AlgorithmsDepartment of Computer Science and Software Engineering, Xian Jiaotong-Liverpool UniversityThe overall work flow in Main is described below:We first read in a text file using the file path provided in the first argument of our java program(which is args[0]). The list of cities read by the function is then passed to another functionsolveProblem() and a routine for this problem is generated. The routine is printed out toallow us to check how much distance has the salesman travelled. So far, these are the functionsthat already exist in the coursework 1. The next function is quite important: improveRoutine(). It takes in the routine wegenerated previously and aims to further reduce its total distance travelled. Background informationTo be able to understand what we are going to do in this coursework, you need somebackground information about algorithms for TSP-like problems. You have already tested youralgorithm against several sample files like below in the coursework 1:Each file contains a long list of cities and you need to visit. These files are often referred to asproblem instances. A valid routine that visits all cities of a problem instance exactly once isoften called a solution of the problem instance. As you already know, one problem instance ofTSP can have many different solutions. Lets look at two different solutions for a simple TSP:The difference between these two solutions is that the city 2 is moved from the slot between 1and 3 to the slot between 4 and 5. After changing the order of visiting these cities, the totaldistance is reduced by 10.CSE 104 Data Structures AlgorithmsDepartment of Computer Science and Software Engineering, Xian Jiaotong-Liverpool UniversityBased on this observation, we can infer that, after trying other different insertion slotsin this routine, it is possible to find other better solutions that has less total distance. Calculating the total distance of a routine is very tiresome for human beings but is much easierfor computers. That is an advantage that we must make full use of when designing algorithms. Apart from moving cities, there are other strategies like swapping cities in the routine, orreverse the visit sequence of a part of the routine etc.. Task 1: Finishing the first local search operatorTheres a class of algorithms called local search (LS). LS explores many solutions of a probleminstance by trying different possibilities of a single solution mutation strategy, such as movingcities, swapping cities etc.. Just talking about how an algorithm works is not intuitive, belowshows one LS I have partially implemented, it is available in the TSPSolver.java:In the code example above, swapCity() should simply swap the two cities indicated by index1and index2 in the routine and then exit. An example of a swap operation is shown below:This function does not need to return anything as the changes made to the ArrayListCityroutine can be seen outside of this function anyway.CSE 104 Data Structures AlgorithmsDepartment of Computer Science and Software Engineering, Xian Jiaotong-Liverpool UniversityRequirement 1: Implement the swapCity() function. This is a warm-up task for you. The second function evalSwap() is designed to evaluate the effect of swapping two cities. Theparameters of this function is the same as swapCity(). Its output is oldDistance newDistance, which indicates how much travelling distance will be reduced if such a swapoperation is applied. A positive value means that the operation does reduce the total distanceof the current routine, while a negative value means a worse solution is obtained. We will call oldDistance newDistance delta from now on.In its current implementation, evalSwap() actually applies the swap so that the newtotal distance can be obtained. Then it swaps these two cities back to their original position inthe routine. The whole routine is checked twice in this process. This is very inefficient if theroutine has many cities. Requirement 2: Re-implement the evalSwap() function, so that it calculates the delta by onlyexamining the modified parts of the routine. The third function swapFirstImprove() is fully implemented. It iterates through all possibilitiesof city swap operations for this routine. If it finds a swap operation that leads to shorter totaldistance, it will apply the swap and return true. If, after trying all possibilities, there is nobeneficial swap operation found, it will return false. If you observe the code carefully, you cansee that both for-loops in this function start with index 1 instead of 0, and end at routine.size() 1. Thats because the routine of TSP must start and end with city 0, changing the order of city0 will break the routine. Make sure you avoid such mistakes when doing the Task 2. Task 2: Creating the second local search operatorIn this task, you are required to create another local search operator, just like the one in task 1.Requirement 3: Implement the moveCity() function, which moves the city at index from tothe position right before index to. The index here refers to the index in the ArrayList. Here arethree examples of move operations:CSE 104 Data Structures AlgorithmsDepartment of Computer Science and Software Engineering, Xian Jiaotong-Liverpool UniversityRequirement 4: Implement the evalMove() function, which evaluates the effect of moving acity from one index to another. It returns the delta value of the total distances, as explainedearlier. Designs that lead to less computational time yet still maintains the correctness will gethigher marks. Requirement 5: Implement the moveFirstImprove() function, which iterates through allpossibilities of city move operations for this routine. If it finds a move operation that leads toshorter total distance, it will apply the move and return true. If, after trying all possibilities, there is no beneficial move operation found, it will return false. Task 3: Putting them together!Once you have finished Task 1 and Task 2. You are ready to tackle the final part of this project:public static ArrayListCity improveRoutine(ArrayListCity routine) {// Can you improve this simple algorithm a bit?swapFirstImprove(routine);moveFirstImprove(routine);return routine;}The improveRoutine() function takes in, as its parameter, the routine generated by thealgorithm of coursework 1 And returns an improved routine if possible. In its current state, thisfunction just called the two xxxFirstImprove() functions once. You can certainly improve uponit. Requirement 6: Re-implement the improveRoutine() function so that it can explore moresolutions of TSP problem instances. Better solutions will result in higher marks for this part. Youdo not have to use xxxFirstImprove() functions. Since in Task 3, you can make any decisions, it is impossible for me to investigate the code ofeverybody and point out what could be improved. Your algorithm will instead be comparedwith each other and whoever is ranked at the first will get the full mark for benchmarking (20%). You are allowed to add your own functions or inner classes in TSPSolver.java or City.java.CSE 104 Data Structures AlgorithmsDepartment of Computer Science and Software Engineering, Xian Jiaotong-Liverpool UniversityI will use bash scripts to read the output of your programs. To ease my marking, yourprogram should not output anything when running. I will call the printSolution() function inmy own version of the main function. Thus, make sure that you delete any calls toSystem.out.print() in TSPSolver and City classes, so that your diagnostic outputs do notinterfere with my bash script (except for the printSolution() function). Failing to do so willdisqualify yourself from the benchmarking and you will only get the base mark for Task 3 (up to10%), given that the algorithm Works correctly. That is, the only function that is allowed to call System.out.print() or other console output functions is the printSolution() function fromCoursework 1. About the benchmarkingThis is the hardware that I will use for the benchmarking:Dual Intel Xeon Processor E5-2680 v2 (25M Cache, 2.80 GHz) 10 cores each, 20 cores in total64 GB of RAMA 64-bit Linux with OpenJDK 11Once I have collected all of your submissions, I will compile your programs and run against theproblem instances I have (Not just those files like C110_1.txt on ICE, but also other instancesthat you have not been given). Your program will be given 5 minutes to solve each instanceusing a single core of the aforementioned CPU. Once 5 minutes have reached, I will terminateyour program no matter whether it is still running or has finished. I will use my own Main.javato call your improveRoutine() function exactly like below:Then, the routine is printed and the total distance calculated by my own function will be storedin a text file. (this is to prevent someone cheating on the results)Once all total distances are collected, I will use the following method to calculateindividual marks. Assume that your total distance is x, the shortest total distance found inCSE104 is L, and an upper bound U (decided by me):Currently, I plan to use the total distance of solveProblem() as the upper bound U. But Ireserve the right to change it. Task 4: Alternative data structure discussionThis is the final task For you. Currently, ArrayLists are used to represent the routine of TSP. ArrayList uses array as its internal data structure. What will happen if the routines areCSE 104 Data Structures AlgorithmsDepartment of Computer Science and Software Engineering, Xian Jiaotong-Liverpool Universityrepresented using LinkedList? Will the original code in task 3 run faster or slower? You need toprovide your justifications in the report. Coursework SubmissionIn this coursework, you will be given three template files: Main.java, City.java andTSPSolver.java. You should add code into these files according to this courseworkspecification. You are free to change Main.java in order to test your code. But Main.java willNOT be examined. I will simply replace it with my version when marking the coursework. All ofyour implementations Should be placed into the City class and the TSPSolver class. You should submit your Java program code files together with your report to the entry Iprovided on ICE. The submitted program solution should be well commented and include threefiles: City.java, TSPSolver.java and a 4-page report with a file name Report.pdf or Report.doc (or docx). The report should not exceed 4 pages, without counting your .java files submittedseparately from this report, with the module title and your name/student number signeddeclaration for non-plagiarism shown on the title page. Your report should explain your datastructure(s), what data structures/algorithms (rendered in pseudo code) you have designed andhow they are tested and used in your programs. You should also analyse the space complexity(i.e. memory costs) of your data structures and the complexity of your city-visit majoralgorithms in TSPSolver (i.e. cost of running time asymptotically). Mark distributionThe mark distribution (100% total) is arranged as follows:1. The task 1 worth up to 15%. 2. The task 2 worth up to 30%. 3. The task 3 worth up to 30%: 10% for attempting this task (with visible efforts) and 20%comes from the benchmark. 4. Your report worth up to 25%. This assignment: 50% of the overall marks.如有需要，请加QQ：99515681 或邮箱：99515681@qq.com
“
添加老师微信回复‘’官网 辅导‘’获取专业老师帮助，或点击联系老师1对1在线指导。
