首页 > > 详细

代做CSE 104作业、代写Data Structures作业、Java程序设计作业调试、Java作业代做 代做SPSS|帮做C/C++编程

CSE 104 – Data Structures & Algorithms
Department of Computer Science and Software Engineering, Xi’an Jiaotong-Liverpool University
CSE104 Coursework 2
(Due date: 5pm 06/15/2020 China Time, online ICE submission ONLY)
Learning Outcomes
On successful completion of this assignment, students are expected to: - understand and be able to apply a variety of data structures, together with their internal
representation 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 efficient
implementation of an algorithm. Background information
This Coursework 2 is a continuation of Coursework 1, where you are required to further
develop algorithms for the travelling salesman problem (TSP). In case that some of you didn’t
work 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 TSP
that is able to improve upon an existing TSP routine continuously. You will be guided step by
step to complete this algorithm. Through this special journey, you will learn how more
complicated algorithms work and will be given chances to write your own ones. Current structure of the project
Open 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, it
contains several functions:
a. readFile() — loads the text files of TSP problems. b. solveProblem() — generates an initial routine by continuously choosing the
closest 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 is
a simplified version of printSolution(). It will be needed in this coursework. e. swapCity(), evalSwap(), evalSwap_SLOW_() and swapFirstImprove() — they will
be explained in the next section. f. improveRoutine() — the entry point of the “more complicated algorithm” that
you need to implement. 3. Main.java —This file contains the necessary code to make use of TSPSolver.
CSE 104 – Data Structures & Algorithms
Department of Computer Science and Software Engineering, Xi’an Jiaotong-Liverpool University
The 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 function
“solveProblem()” and a routine for this problem is generated. The routine is printed out to
allow us to check how much distance has the salesman travelled. So far, these are the functions
that already exist in the coursework 1. The next function is quite important: improveRoutine(). It takes in the routine we
generated previously and aims to further reduce its total distance travelled. Background information
To be able to understand what we are going to do in this coursework, you need some
background information about algorithms for TSP-like problems. You have already tested your
algorithm 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 as
problem instances. A valid routine that visits all cities of a problem instance exactly once is
often called a solution of the problem instance. As you already know, one problem instance of
TSP can have many different solutions. Let’s 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 1
and 3 to the slot between 4 and 5. After changing the order of visiting these cities, the total
distance is reduced by 10.
CSE 104 – Data Structures & Algorithms
Department of Computer Science and Software Engineering, Xi’an Jiaotong-Liverpool University
Based on this observation, we can infer that, after trying other different insertion slots
in 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 easier
for 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, or
reverse the visit sequence of a part of the routine etc.. Task 1: Finishing the first local search operator
There’s a class of algorithms called local search (LS). LS explores many solutions of a problem
instance by trying different possibilities of a single solution mutation strategy, such as moving
cities, swapping cities etc.. Just talking about how an algorithm works is not intuitive, below
shows 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 index1
and 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 “ArrayList
routine” can be seen outside of this function anyway.
CSE 104 – Data Structures & Algorithms
Department of Computer Science and Software Engineering, Xi’an Jiaotong-Liverpool University
Requirement 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. The
parameters 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 swap
operation is applied. A positive value means that the operation does reduce the total distance
of 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 new
total distance can be obtained. Then it swaps these two cities back to their original position in
the routine. The whole routine is checked twice in this process. This is very inefficient if the
routine has many cities. Requirement 2: Re-implement the “evalSwap()” function, so that it calculates the delta by only
examining the modified parts of the routine. The third function “swapFirstImprove()” is fully implemented. It iterates through all possibilities
of city swap operations for this routine. If it finds a swap operation that leads to shorter total
distance, it will apply the swap and return true. If, after trying all possibilities, there is no
beneficial swap operation found, it will return false. If you observe the code carefully, you can
see that both for-loops in this function start with index 1 instead of 0, and end at “routine.size() – 1”. That’s because the routine of TSP must start and end with city 0, changing the order of city
0 will break the routine. Make sure you avoid such mistakes when doing the Task 2. Task 2: Creating the second local search operator
In 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” to
the position right before index “to”. The index here refers to the index in the ArrayList. Here are
three examples of move operations:
CSE 104 – Data Structures & Algorithms
Department of Computer Science and Software Engineering, Xi’an Jiaotong-Liverpool University
Requirement 4: Implement the “evalMove()” function, which evaluates the effect of moving a
city from one index to another. It returns the delta value of the total distances, as explained
earlier. Designs that lead to less computational time yet still maintains the correctness will get
higher marks. Requirement 5: Implement the “moveFirstImprove()” function, which iterates through all
possibilities of city move operations for this routine. If it finds a move operation that leads to
shorter 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 ArrayList improveRoutine(ArrayList 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 the
algorithm of coursework 1 and returns an improved routine if possible. In its current state, this
function just called the two “xxxFirstImprove()” functions once. You can certainly improve upon
it. Requirement 6: Re-implement the “improveRoutine()” function so that it can explore more
solutions of TSP problem instances. Better solutions will result in higher marks for this part. You
do not have to use xxxFirstImprove() functions. Since in Task 3, you can make any decisions, it is impossible for me to investigate the code of
everybody and point out what could be improved. Your algorithm will instead be compared
with 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 & Algorithms
Department of Computer Science and Software Engineering, Xi’an Jiaotong-Liverpool University
I will use bash scripts to read the output of your programs. To ease my marking, your
program should not output anything when running. I will call the “printSolution()” function in
my own version of the main function. Thus, make sure that you delete any calls to
“System.out.print()” in TSPSolver and City classes, so that your diagnostic outputs do not
interfere with my bash script (except for the “printSolution()” function). Failing to do so will
disqualify yourself from the benchmarking and you will only get the base mark for Task 3 (up to
10%), 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 from
Coursework 1. About the benchmarking
This 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 total
64 GB of RAM
A 64-bit Linux with OpenJDK 11
Once I have collected all of your submissions, I will compile your programs and run against the
problem instances I have (Not just those files like C110_1.txt on ICE, but also other instances
that you have not been given). Your program will be given 5 minutes to solve each instance
using a single core of the aforementioned CPU. Once 5 minutes have reached, I will terminate
your program no matter whether it is still running or has finished. I will use my own Main.java
to call your “improveRoutine()” function exactly like below:
Then, the routine is printed and the total distance calculated by my own function will be stored
in 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 calculate
individual marks. Assume that your total distance is x, the shortest total distance found in
CSE104 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 I
reserve the right to change it. Task 4: Alternative data structure discussion
This 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 are
CSE 104 – Data Structures & Algorithms
Department of Computer Science and Software Engineering, Xi’an Jiaotong-Liverpool University
represented using LinkedList? Will the original code in task 3 run faster or slower? You need to
provide your justifications in the report. Coursework Submission
In this coursework, you will be given three template files: “Main.java”, “City.java” and
“TSPSolver.java”. You should add code into these files according to this coursework
specification. You are free to change Main.java in order to test your code. But Main.java will
NOT be examined. I will simply replace it with my version when marking the coursework. All of
your 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 I
provided on ICE. The submitted program solution should be well commented and include three
files: “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 submitted
separately from this report, with the module title and your name/student number & signed
declaration for non-plagiarism shown on the title page. Your report should explain your data
structure(s), what data structures/algorithms (rendered in pseudo code) you have designed and
how 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 major
algorithms in TSPSolver (i.e. cost of running time asymptotically). Mark distribution
The 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
  • 工作时间:8:00-23:00
  • 微信:codinghelp2

联系我们 - QQ: 99515681 微信:codinghelp2
© 2014 www.7daixie.com
程序代写网!