package edu.hawaii.ics.yucheng;
/**
* Implementation of a brute-force solver.
*/
class BruteForceSolver extends GraphSolver {
/** The graph input. */
private Graph myGraph;
/** A boolean matrix set to true when a vertex has been visited. */
private BooleanMatrix myMatrix;
/** The maximum goodness value determined so far. */
private int myMaxGoodness;
/** The percent complete. */
private int myPercentComplete;
/** The sequence of visited vertices implemented as a stack. */
private Stack<Vertex> mySequence;
/** The best solution found so far. */
private GraphSolution mySolution;
/** An array of vertices calculated by the A* algorithm. */
private PathFinder[] myStars;
/**
* Returns the amount of battery required to return to the base.
*
* @param x The current x coordinate.
*
* @param y The current y coordinate.
*
* @return The amount of battery required to return to the base.
*/
private int capacityToBase(final int x, final int y) {
return myStars[indexAt(x, y)].cost();
}
/**
* Computes the A* algorithm for all locations in the graph.
*/
private void computeStars() {
// Loop over each location, and compute the A* algorithm for its location.
myStars = new PathFinder[myGraph.width * myGraph.height];
for (int i = 0; i < myGraph.width; i++)
for (int j = 0; j < myGraph.height; j++)
myStars[indexAt(i, j)] = new PathFinder(myGraph, i, j);
}
/**
* Calculates and returns the arrival path based on a solution.
*
* @param solution The solution.
*
* @return The arrival path.
*/
private Vertex[] getArrival(final Vertex[] solution) {
assert null != solution;
// Check if the solution has at least one vertex.
if (solution.length == 0)
return new Vertex[0];
// And copy the A* result for the arrival.
final int lastSolutionIndex = solution.length - 1;
final int lastX = solution[lastSolutionIndex].x;
final int lastY = solution[lastSolutionIndex].y;
final PathFinder lastPathFinder = myStars[indexAt(lastX, lastY)];
final Vertex[] arrival = lastPathFinder.getPath();
return arrival;
}
/**
* Calculates and returns the departure path based on a solution.
*
* @param solution The solution.
*
* @return The departure path.
*/
private Vertex[] getDeparture(final Vertex[] solution) {
assert null != solution;
// Check if the solution has at least one vertex.
if (solution.length == 0)
return new Vertex[0];
// Otherwise, copy the A* result for the departure.
final int firstX = solution[0].x;
final int firstY = solution[0].y;
final PathFinder firstPathFinder = myStars[indexAt(firstX, firstY)];
final Vertex[] reversedDeparture = firstPathFinder.getPath();
final Vertex[] departure = new Vertex[reversedDeparture.length];
// The A* algorithm returns the arrival, so reverse the array.
for (int i = 0; i < departure.length; i++)
departure[i] = reversedDeparture[departure.length - (i + 1)];
return departure;
}
/**
* Returns the A* matrix index.
*
* @param x The x coordinate.
*
* @param y The y coordinate.
*
* @return The array index.
*/
private int indexAt(final int x, final int y) {
return myGraph.width * y + x;
}
/**
* Returns true if the battery consumption would exceed the maximum capacity
* if a vertex is visited.
*
* @param x The current x coordinate.
*
* @param y The current y coordinate.
*
* @param capacity The remaining battery capacity.
*
* @return True indicates the battery is exhausted.
*/
private boolean isBatteryExhausted(final int x, final int y,
final int capacity) {
return capacityToBase(x, y) + myGraph.consumption(x, y) > capacity;
}
/**
* Returns true if the specified coordinates are beyond the edges of the mesh
* graph.
*
* @param x The current x coordinate.
*
* @param y The current y coordinate.
*
* @return True indicates the specified coordinates are beyond the edges of
* the mesh graph.
*/
private boolean isBeyondEdge(final int x, final int y) {
return x < 0 || x >= myMatrix.columns || y < 0 || y >= myMatrix.rows;
}
/**
* Returns true if the specified coordinates are blocked.
*
* @param x The current x coordinate.
*
* @param y The current y coordinate.
*
* @return True indicates the specified coordinates are beyond the edges of
* the mesh graph.
*/
private boolean isBlocked(final int x, final int y) {
if (isBeyondEdge(x, y))
return true;
if (myGraph.isObstacle(x, y))
return true;
if (myGraph.base.equals(x, y))
return true;
return myMatrix.isMarked(y, x);
}
/**
* Saves the current path as the best path if the determined goodness is a
* maximum.
*
* @param goodness The goodness for the current path.
*/
private void saveMaximum(final int goodness) {
// Check if this is a maximum, and save the path if it is.
if (mySolution == null || goodness > myMaxGoodness) {
myMaxGoodness = goodness;
// Get the solution path from the stack.
final Vertex[] solution = new Vertex[mySequence.size()];
mySequence.toArray(solution);
final Vertex[] arrival = getArrival(solution);
final Vertex[] departure = getDeparture(solution);
mySolution = new GraphSolution(myGraph, solution, departure, arrival);
// Report progress when a new (better) solution is found.
reportProgress(null, mySolution);
}
}
/**
* Solves the specified graph and returns its solution.
*
* @param graphInput The graph input.
*
* @return The graph solution.
*/
@Override
public GraphSolution solve(final Graph graphInput) {
// Check for invalid input.
if (graphInput == null)
throw new NullPointerException("graphInput");
// Set up the class data used when finding the solution.
myGraph = graphInput;
myMatrix = new BooleanMatrix(graphInput.height, graphInput.width);
myMaxGoodness = Integer.MIN_VALUE;
mySolution = null;
mySequence = new Stack<Vertex>();
// Compute the A* algorithm paths before exploring solution paths.
computeStars();
try {
// Loop over all possible starting points and return the best solution.
return tryAllPaths();
} finally {
// Clean up the class data used while this method executes.
myGraph = null;
myMatrix = null;
myMaxGoodness = 0;
mySolution = null;
mySequence = null;
myStars = null;
}
}
/**
* Tries to find the best solution by looping over all possible starting
* points.
*
* @return The best possible solution or null if canceled.
*/
private GraphSolution tryAllPaths() {
// Use these values to determine the percent complete when sending
// progress.
int k = 0;
final int kMax = myGraph.width * myGraph.height;
// Loop over every possible starting point.
for (int i = 0; i < myGraph.width; i++)
for (int j = 0; j < myGraph.height; j++) {
// Determine the percent complete and send progress. Also, check if
// the solution has been canceled; if so return immediately.
myPercentComplete = k++ * 100 / kMax;
reportProgress(Integer.valueOf(myPercentComplete), null);
if (isCanceled())
return null;
// Special case: If the A* algorithm determined there is no path, then
// do not try this location.
if (!myStars[indexAt(i, j)].isFound())
continue;
// Try this starting point as a possible solution.
tryPath(i, j, 0, myGraph.capacity - capacityToBase(i, j));
}
// Return the best possible solution.
return mySolution;
}
/**
* Recursively determines if a path is optimal.
*
* @param x The current x coordinate in the graph.
*
* @param y The current y coordinate in the graph.
*
* @param goodness The current goodness of the path.
*
* @param capacity The current remaining battery capacity.
*/
private void tryPath(final int x, final int y, final int goodness,
final int capacity) {
// Return immediately if the solver has been canceled.
if (isCanceled())
return;
// Check for an end-case, and save the maximum value if it is found.
if (isBlocked(x, y) || isBatteryExhausted(x, y, capacity)) {
saveMaximum(goodness);
return;
}
// Push the current location onto the path stack, and mark the vertex as
// visited.
mySequence.push(new Vertex(x, y));
myMatrix.mark(y, x);
// Calculate a new goodness value and battery capacity.
final int newGoodness = goodness + myGraph.priority(x, y);
final int newCapacity = capacity - (1 + myGraph.consumption(x, y));
// Try all possible paths from this location.
tryPath(x - 1, y, newGoodness, newCapacity);
tryPath(x + 1, y, newGoodness, newCapacity);
tryPath(x, y - 1, newGoodness, newCapacity);
tryPath(x, y + 1, newGoodness, newCapacity);
// Pop off the vertex in the path, and unmark this vertex as visited.
mySequence.pop();
myMatrix.unmark(y, x);
}
}
