Module exercise 11.5 (the weight distribution problem).
Note: Credit will not be given only for answers - show all your
work: your reasoning, steps you took to get your answer etc.
PART II: Implementation. In this part, implement the code in Module exercise 9.1.
PART III: Implementation:
In this part, you will implement three algorithms for a
variation of of the traveling salesperson problem.
In this variation, there are m salespersons who can
work in parallel. The goal is to subdivide the points,
and find a good tour for each salesperson. The objective is
to minimize the length of the worst tour among the salespersons.
Let's first formally define the problem:
The input is a number m (the number of salespersons)
and a collection of points on the 2D plane, that is,
a collection of n (x,y) pairs.
As a first step, take a look at how the input is
given to your algorithm. Your algorithm must implement
the MTSPAlgorithm
interface. The input, thus, is the number m and
an array of points, where each point is an instance
of the class Pointd.
Now consider what an algorithm must return as output.
Since each salesperson is assigned a subset of points,
the algorithm must return the collection of points
assigned to each particular salesperson. You are
required to return a 2D array such that row i
of the 2D array consists of the points assigned to
salesperson i.
Suppose the input has 20 points and 3 salespersons. You might
choose to assign the first one 10 points, the second one 7
points and the third one 3 points. If you put these
points into a 2D array, and suppose that array is
called assignedPoints. Then,
assignedPoints[0] is of type Pointd[]
and assignedPoints[0].length == 10. Similarly,
assignedPoints[1].length == 7
and assignedPoints[2].length == 3. Thus,
assignedPoints is an uneven, staggered array.
It is always the case that assignedPoints.length == m.
Next, for each row of the 2D array, the numbers in that
row are to represent the tour order for that row.
Thus, if assignedPoints[1] is the array {4, 12, 9, 6, 18, 3, 5}
then, this means that salesperson 1 (the second salesperson)
was assigned points 4, 12, 9, 6, 18, 3, 5 and that the
tour for this salesperson is the order given by 4, 12, 9, 6, 18, 3, 5.
Note that each tour has unique indices (that is, no point is
repeated, including the end).
You might wonder if it's possible to assign no points to
some salespersons (if that helps). Yes, indeed, you can. You can
assign any number of points to any salesperson. To assign zero
points, make the row pointer null.
Clearly, there is some optimal assignment of points to
salespersons, and after assignment, some optimal tour for each
salesperson (among the points assigned to that salesperson).
Your goal is not to find the absolute optimum, but to
try and find "good" assignments and tours.
You will implement three algorithms:
A "naive" algorithm in Naive.java that merely
divides the points more or less evenly among the salespersons
("more or less" because m may not exactly divide
the number of points).
A "greedy" algorithm in Greedy.java
that will execute in polynomial time.
Note: implement a "greedy constructive" algorithm (that builds a solution
step by step) as opposed to a "greedy-local-search" algorithm
(that explores the state space).
The third is an algorithm that you design, with the objective of beating
the above two algorithms. Implement this in
a file called MyAlgorithm.java
Keep in mind that you are not only divvying up the points amongst
the salespersons but also deciding their order (the tour) for each salesperson.
Implementation details:
Your three classes will need to implement the
MTSPAlgorithm
interface.
The interface has only one method:
int[][] computeTours (int m, Pointd[] points)
Use the mtsp.props properties
file to run your algorithm in the test environment.
Note that the test environment does not do much correctness-testing.
The nature of optimization problems is that any dumb algorithm can produce
a valid assignment - the value comes from the quality of the assignment.
Thus, you need to submit evidence that your non-naive algorithms are
doing "some good". Compare the quality of solution produced and time
taken to produce the solutions for these algorithms.
Submit an example (in the PDF) to show that your greedy algorithm does
not always produce the optimal solution.
Analyse the running time (in order-notation, in your PDF) of your greedy
algorithm.
Include documentation to explain how your own algorithm works.
Use an illustrative example.
Submission:
Parts I, II and III are due at the same time.
For this assignment and others, you will need to follow
the usual submission instructions
carefully.