Now that Wile has a dessert map, it is time to set a trap. The reasoning behind this trap is that if the RoadRunner is so fast, then it must need a lot of energy. Thus a way of catching the RoadRunner is to lure it into spending more energy than it gains.
Wile has bought a huge bag of corn from ACME. Using the excellent map that we have previously generated for Wile he will now attempt to place 15 portions of corn in a way so that the shortest possible path between all corn-portions is longer than the energy obtained from the corn allow the RoadRunner to traverse.
The RoadRunner can run 200 KM on each portion of corn, so now we need to calculate the minimum distance between the ten portions that Willie has placed and see if this is longer than 3000 KM, in which case Wile can eat.
The shortest route for the race trap
The solution should be implemented using PVM, and may be based on the sequential version below. The code shouldbe run on from one through 32 CPUs. The 15 coordinates that Wile uses must be tested and the resulting path must be the same, or better should you choose another heuristik.
The report should identify
the various choices that has been made as well as individual techniques
that has
been applied to improve
performance. And the impact of each should be documented. In addition the
scalabilityof your implementation should be discussed and the achieved
performance curve should be discussed.
Any optimization may be applied,
if and only if the result is correct and independent of the number of nodes
that
are used to achieve the
solution. Any optimization that is applied must be thoroughly described.