A* Algorithm while solving Sliding Tile puzzle executes for a very long time

Question

While trying to run the code for 24 Tile puzzle and above, the code executes for a very long time (Greater than 3 minutes) (It runs pretty quick for 8 Tile puzzle). 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 hashcode :

    @Override
    public int hashCode() {
        return Arrays.hashCode(allCells);       
    }

And this is the code for 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 am not sure why does it take so long for my A* implementation to compute for 24 tile puzzle and up. How can I optimize my code to compute faster, also is there any bug that is causing it to take so long?

If you are interested in the entire code, it can be found here

What is your expectated runtime? Ratner and Warmuth state that they [extend the 8-puzzle and the 15- puzzle to an `n x n` board and show that finding a shortest solution for the extended puzzle is NP-hard and is thus believed to be computationally infeasible](https://users.soe.ucsc.edu/~manfred/pubs/J15.pdf). So I would expect a bad runtime behaviour. — Turing85, Jun 28 '15 at 08:48

score 2 · Answer 1 · answered Jun 28 '15 at 09:22

2

As Turing85 has mentioned, this is an NP-complete problem, so it's unlikely that you will have a fast runtime.

I would suggest that you can do the following:

Try to use different heuristic
Try to use bidirectional search

answered Jun 28 '15 at 09:22

Ivan Mushketyk

8,107
7
50
67

score 1 · Answer 2 · answered May 29 '18 at 08:56

1

I know this is an old question, but I just had the same problem.

Apparently, Arrays.hashCode(allCells); is really really slow, and using another hash code can make the algorithm run much faster.

Try this answer for alternative hash.

answered May 29 '18 at 08:56

nogmos

859
1
8
12

A* Algorithm while solving Sliding Tile puzzle executes for a very long time

2 Answers2