A * The algorithm for solving the Sliding Tile puzzle takes a very long time
When trying to run the code for puzzle 24 and above, the code takes a very long time (over 3 minutes) (it runs pretty fast for 8 puzzles). The code can be found below.
while (openQueue.isEmpty() == false) {
State queueHead = openQueue.remove();
openMap.remove(queueHead.hashCode());
closedMap.put(queueHead.hashCode(), queueHead);
State queueHeadState = queueHead;
if (Constants.debug) {
System.out.println("Popped State");
HeuristicSolverUtility.printState(queueHead);
}
// If reached goal state . Termination condition.
if (queueHead.equals(goalState)) {
break;
} else {
List<Action> listOfPossibleActions = queueHeadState
.getPossibleActions();
Iterator<Action> actIter = listOfPossibleActions.iterator();
while (actIter.hasNext()) {
// Here it performs Tile UP, DOWN, LEFT and RIGHT operations
Action actionOnState = actIter.next();
StateP newState = actionOnState.applyTo(queueHeadState);
newState.setHeuristicCost((double) ManhattanDistance
.calculate(newState));
newState.setParent(queueHead);
newState.setAction(actionOnState);
if (!closedMap.containsKey(newState.hashCode()) && !openMap.containsKey(newState.hashCode())) {
openQueue.offer(newState);
openMap.put(newState.hashCode(), newState);
} else if (openMap.containsKey(newState.hashCode())) {
System.out.println("State found in Open Map");
State stateFetchedFromOpenMap = openMap.get(newState.hashCode());
if (stateFetchedFromOpenMap.getPathCost() > newState.getPathCost()) {
openMap.remove(stateFetchedFromOpenMap.hashCode());
openMap.put(newState.hashCode(), newState);
openQueue.remove(stateFetchedFromOpenMap);
openQueue.add(newState);
}
}
}
}
}
This is my hash code:
@Override
public int hashCode() {
return Arrays.hashCode(allCells);
}
And this is the code for the Priority Queue Comparator: -
public static class HeuristicComparator implements Comparator<State> {
public int compare(State o1, State o2) {
Double result;
result = o1.getKey() - o2.getKey();
if (result == 0.0) {
// Ties among minimal f values are resolved in favor of the
// deepest node in the search tree
// i.e. the closest node to the goal
result = (double) (o2.getPathCost() - o1.getPathCost());
}
if (result > 0.0) {
return 1;
}
return -1;
}
}
I'm not sure why it takes so long for my A * implementation to compute 24 puzzles and up. How can I optimize my code to compute faster, also is there any error causing it to take so long?
If you are interested in all the code, it can be found here
+3
source to share
1 answer
As Turing85 already mentioned, this is an NP-complete issue, so it is unlikely that you will have fast execution times.
I would suggest that you can do the following:
- Try using a different heuristic
- Try using bi-directional search
+2
source to share