Java代写/algorithm代写/算法作业代写：这是一个利用java实现具体算法实现的作业
Seating Chart Optimizer
Recent education research suggests that seating arrangements are the single most important factor in student learning. Students who are seated near friends exhibit better concentration, perform better on tests, and express greater satisfaction with the classroom experience.
This research has inspired EduCorp’s latest product: SitRite3K. SitRite3K will automate the tedious process of developing seating charts to maximize learning outcomes. After a teacher enters a list of students, along with each student’s seating preferences, the program will display an optimized seating chart that places students near their preferred classmates.
The user interface group has already completed a cutting-edge GUI front-end for the SitRite3K system. It will be your responsibility to program the optimization logic.
Your goal for this project is to complete a SeatingChart class that represents a rectangular seating arrangement and provides the functionality for optimizing seating assignments.
The following UML diagram illustrates how SeatingChart relates to the existing classes developed for PA1:
SeatingChart
The SeatingChart class represents a grid of seating locations as a two-dimensional array of Student objects. It is not necessary for every entry to contain a Student: null entries are used to represent empty seats.
The SeatingChart class must conform to the following UML diagram:
You are free to add additional private helper methods, but the public methods must match the UML specification exactly.
Detailed Requirements
Constructor
The constructor must instantiate the two dimensional array seats. It is not the responsibility of the constructor to populate seats with Student objects. Initially, all entries should be null, representing an empty seating chart. No data validation is required for the constructor arguments.
getRows, getColumns
These methods must return the number of rows and columns in the SeatingChart.
getStudent
This method must return a reference to the student at the indicated location. If the location is invalid, this method must return null. A location is invalid if it is outside the bounds of the seating chart.
placeStudent
This method must place the provided student into seats at the indicated location.
· The row and column of the provided Student object must be updated to reflect the student’s new location.
· If there was already a student in the indicated location, the existing student must be replaced. That student’s row and column must not be modified. (For students who are
no longer in the seating chart, the row and column values represent their last valid position.)
· If the indicated location is invalid, this method must have no effect.
· If the provided student reference is null, then a null value should be stored in the indicated location.
getTotalUnhappiness
This method must return the sum of the unhappiness values of all Student objects stored in the seating chart.
swap
This method must swap the students at the two indicated locations. If either location is invalid, then this method must have no effect. Empty seats (null entries) should not be treated as a special case. It must be possible to swap a Student with a null or vice-versa.
stepGreedy
This method must iterate once through the entire seating chart, performing local seating changes where those changes will decrease the total unhappiness of the classroom. This method must conform to the following pseudocode:
for each row in the seating chart, starting with row 0, do:
for each column in the seating chart, starting with column 0, do:
Determine which neighbor, if swapped with the value at the
current location, would lead to the largest decrease in total
unhappiness. Perform that swap if the decrease will be greater
than zero.
In this pseudocode, “neighbor” refers to one of the eight (or fewer) valid locations immediately surrounding a chart position.
The logic above is guaranteed to decrease the total unhappiness of the classroom, or to leave the total unchanged if there are no local swaps that would help.
It is possible to encounter a tie when searching for the most advantageous swap. In the case of a tie, your algorithm must select the first neighbor encountered in a row-major-order traversal of the neighbors. Be careful! If you use a different mechanism for breaking ties your program will appear to work correctly, but it will not pass our submission tests.
solveGreedy
It may be necessary to call the stepGreedy method multiple times before the students reach a configuration where no further improvements are possible. The solveGreedy method must repeatedly call stepGreedy until no additional improvements occur.
Note that the seating chart optimization algorithm expressed in the stepGreedy and solveGreedy methods is not guaranteed to find the best possible arrangement of students. It is easy for this algorithm to get stuck in a sub-optimal configuration that cannot be improved through local swaps. See the “Going Further” section below for more information.
Provided Code and Configuration Files
A .jar file is a compressed archive that can hold any number of Java classes in either source or binary form (as .java files or as .class files). For this project, SitRite3K.jar contains classes that may be used to visualize the operation of your completed code. The following two classes are provided:
· SitRite3K This class contains the main for the SitRite3K application. It provides a graphical interface to the functionality provided by your SeatingChart class.
· SeatingChartUtils This class provides utility methods for working with SeatingChart objects. You shouldn’t need to interact with this class directly, but here is the Javadoc in case you are curious: SeatingChartUtils. This documentation describes the file format for loading configuration files in case you want to create your own files for testing.
The following steps should allow you to access these classes within an Eclipse project:
1. Create a new folder named “lib” in your Java project. Download the .jar file and drag it into the newly-created folder.
2. Right click the .jar file and select Build Path -> Add to Build Path.
3. There should now be a “Referenced Libraries” entry in your project explorer. Expanding that entry should allow you to inspect the details of the archive. All classes included in that archive are now available within your project.
Here are a few classroom configuration files that you may use for testing. Unhappiness values are rounded to two decimal places.
· small.txt – A tiny example with only four students.
o Initial unhappiness: 5.24
o Greedy Unhappiness: 4.00
o Optimal unhappiness: 4.00
· small_sparse.txt – The same four students in a larger classroom. This example includes empty seats.
o Initial unhappiness: 6.00
o Greedy Unhappiness: 4.00
o Optimal unhappiness: 4.00
· small_tie.txt – This is an example where you may get a different result depending on how you handle ties. If your code is breaking ties correctly, Sara should switch places with Robert.
o Initial unhappiness: 1.41
o Greedy Unhappiness: 1.00
o Optimal unhappiness: 1.00
· pairs.txt – Eight pairs of friends in a 4×4 seating chart.
o Initial unhappiness: 31.66
o Greedy Unhappiness: 17.66
o Optimal unhappiness: 16.00
· easy_cliques.txt – Four groups of four seated in a 4×4 seating chart.
o Initial unhappiness: 107.24
o Greedy Unhappiness: 67.31
o Optimal unhappiness: 54.63
· hard_cliques.txt – Sixty groups of four in a 12×20 seating chart.
o Initial unhappiness: 6445.05
o Greedy Unhappiness: 948.80
o Optimal unhappiness: 819.41
· challenge.txt – 252 students with randomly determined friend lists containing between zero and ten friends each.
o Initial unhappiness: 12658.74
o Greedy Unhappiness: 3406.59
o Optimal unhappiness: ?????