4
\$\begingroup\$

I am writing a solved for 15 puzzle game which will find the solution path to any NxN board. For easier boards the algorithm works great solving almost any 3x3 boards, most 4x4 boards, but when I go 5x5 and higher I will often run out of memory. This is the implementation:

@WorkerThread
public Solution findPath(Board board){
    //Keeps the lowest F value node at the head of queue.

    //MinMaxPriorityQueue<Node> queue = MinMaxPriorityQueue.orderedBy(new AStarNodeComparator()).maximumSize(1000).create();
    PriorityQueue<Node> queue = new PriorityQueue<>(1000, new AStarNodeComparator());

    Node start = new Node(board, 0, null, heuristic);
    Set<Integer> closeSet = new HashSet<>();
    Set<Integer> openSet = new HashSet<>(); //Set of nodes to be evaluted

    queue.add(start);
    openSet.add(start.getId());
    Node goalNode = null;

    long startTime = System.currentTimeMillis();
    while(openSet.size() > 0){
        Node parent = queue.remove(); //Node that should have lowest f score.

        if(parent.getBoardObj().isGoal()) {
            goalNode = parent;
            break;
        }

        openSet.remove(parent.getId());
        closeSet.add(parent.getId());

        for(Node neighborNode :findNeighbors(parent)){
            if(!closeSet.contains(neighborNode.getId())){

                if(!openSet.contains(neighborNode.getId()) || neighborNode.getFValue() < parent.getFValue()){
                    //not in the open set.
                    openSet.add(neighborNode.getId());
                    queue.add(neighborNode);

                }
            }
        }
    }
    return new Solution(goalNode,System.currentTimeMillis()-startTime);
}

private ArrayList<Node> findNeighbors(Node parent){
    ArrayList<Node> neighbors = new ArrayList<>();
    for(int neighbor : parent.getBoardObj().findNeighbors(parent.getBoardObj().getBoard())) {
        Board board = new Board(parent.getBoardObj().getBoard(), parent.getBoardObj().getGridSize());
        Node neighborNode = new Node(board, parent.getMoves(), parent, heuristic);
        parent.getBoardObj().takeMoveAction(neighbor, neighborNode);
        neighbors.add(neighborNode);
    }
    return neighbors;
}

I use getId() as a key to determine if a board is the same or not. This is definitely ideal but best I could think of in a pinch:

public int getId(){
    int hashCode = 0;
    if(boardObj.getBoard() != null) {
        for(int i=0; i<boardObj.getBoard().length; i++){
            for(int j=0; j<boardObj.getBoard()[0].length; j++){
                int value = boardObj.getBoard()[i][j];
                hashCode = 31 * hashCode + ((value%2==0)? -value : value);
            }
        }

    }
    return hashCode;
}

The Comparator:

public class AStarNodeComparator implements Comparator<Node>{
    @Override
    public int compare(Node b1, Node b2) {
        int b1Priority = b1.getFValue();
        int b2Priority = b2.getFValue();
        if(b1Priority < b2Priority){
            return -1;
        }else if(b1Priority > b2Priority){
            return 1;
        }else{
            return 0;
        }
    }
}

When the program fails it's because the priority queue often has 300,000+ Nodes hard referenced in memory. I tried using the Guava MinMaxPriorityQueue with no better results. How can I better optimize this algorithm to run on mobile devices?

*A side note I did implement IDAStar algorithm which never runs out of memory but sometimes it can take upwards of ~30 seconds to find the solution.

EDIT:

Node class:

public class Node {
    private final Heuristic heuristic;
    private Board boardObj;

    //g - value
    private int moves = 0;
    private Node previous = null;
    private PuzzleCoordinates zeroCoord,swapCoord;

    public Node(Board board, int moves, Node previous, Heuristic heuristic) {
        this.boardObj = board;
        this.moves = moves;
        this.previous = previous;
        this.heuristic = heuristic;
    }

    //Hash for the map.
    //This will probably fail in the long run but can't think of a better interm solution.
    public int getId(){
        int hashCode = 0;
        if(boardObj.getBoard() != null) {
            for(int i=0; i<boardObj.getBoard().length; i++){
                for(int j=0; j<boardObj.getBoard()[0].length; j++){
                    int value = boardObj.getBoard()[i][j];
                    hashCode = 31 * hashCode + ((value%2==0)? -value : value);
                }
            }

        }
        return hashCode;
    }
    public Board getBoardObj() {
        return boardObj;
    }

    public void setCoordinates(PuzzleCoordinates zeroCoord, PuzzleCoordinates swapCoord){
        this.zeroCoord = zeroCoord;
        this.swapCoord = swapCoord;
    }


    @Nullable
    public PuzzleCoordinates getZeroCoord() {
        return zeroCoord;
    }


    @Nullable
    public PuzzleCoordinates getSwapCoord() {
        return swapCoord;
    }

    public int getMoves() {
        return moves;
    }

    public void incrementMoves(){
        moves += 1;
    }

    public Node getPrevious() {
        return previous;
    }

    // G + H
    public int getFValue(){
        return moves+heuristic.manhattan(boardObj.getBoard());
    }

    public void setBoardObj(Board boardObj) {
        this.boardObj = boardObj;
    }

    public void setMoves(int moves) {
        this.moves = moves;
    }

    public void setPrevious(Node previous) {
        this.previous = previous;
    }
}
\$\endgroup\$
  • \$\begingroup\$ Can you post your node class? \$\endgroup\$ – itscharlieb Jun 24 '15 at 3:03
  • \$\begingroup\$ Can you post your Node and Board classes? One Node must be quite large for 300,000 nodes to use up all of memory. \$\endgroup\$ – JS1 Jun 26 '15 at 19:38
  • \$\begingroup\$ @JS1 I've posted the node class. The problem is that you need to store the path so you find have a route. So each node will have a parent node some basically creating a linked list of up too 60+ nodes. \$\endgroup\$ – Nick Jun 28 '15 at 17:15
  • 1
    \$\begingroup\$ A* is a poor choice of algorithm for the 15 puzzle. See §6 of this answer, or this answer with references. \$\endgroup\$ – Gareth Rees Jun 28 '15 at 17:55
3
\$\begingroup\$

Bug

            if(!openSet.contains(neighborNode.getId()) || neighborNode.getFValue() < parent.getFValue()){
                //not in the open set.
                openSet.add(neighborNode.getId());
                queue.add(neighborNode);

            }

This will add a node to the queue twice if its FValue is less than the previous node's FValue.

Did you perhaps mean to say &&?

            if (!openSet.contains(neighborNode.getId()) && neighborNode.getFValue() < parent.getFValue()){
                //not in the open set.
                openSet.add(neighborNode.getId());
                queue.add(neighborNode);
            }

Then you'd only add it to the openSet if it's not in the openSet now and it has a lower FValue.

A side effect of that is that you could replace openSet and closeSet with one queued set. That would save removing and adding on every iteration. You'd only add. You'd also only need one if. You'd also have to change

while(openSet.size() > 0){

to something like

while (!queue.isEmpty()) {
\$\endgroup\$
3
\$\begingroup\$

Hash value collisions

Your hash function might be causing your problems. As you are only using the hash value (getId()) in the closed and open set (as opposed to a Node that implements hashCode and equals to resolve hash value collisions), a hash value collision will appear as the node has already been visited even though it might not have been. Meaning that you skip parts of the search space, parts that could contain the solution. This could result in that you simply miss the easy solutions and keep on searching for a long time.

For a 5x5 problem there exists 25 unique tiles (the empty tile counted as a tile), so you have 25! ~= 1.55E+25 unique board combinations. Using a 32bit integer as a hash code, at most 2^32 ~= 4.29E+9 unique board combinations can be represented without a collision.

So for each hash value there exists ~= 3.61E+15 (=1.55E25/4.29E9) boards that have collisions. Or put the other way, if you pick two random boards the likely hood of a collision is:

collidingBoards/totalBoards = 2.33E-10 (=3.61E+15/1.55E+25 = 1/4.29E9).

If you evaluate 300 000 nodes, we can estimate a upper bound of the chance to not get a collision anywhere in the table by:

1 - (1 - 2.33E-10)^300000 = 0.00007 or 0.007% chance.

So you are very unlikely to have correct closed/open sets after 300 000 iterations. Remember with A* you're searching for the optimal solution and you will expand a lot of nodes to find it; As opposed to if you're just looking for a solution then you'll take the first solution you find (greedy best-first search will do this quickly).

The closed set is not necessary (and neither is the open)

The purpose of the closed set is to guarantee that you do not expand the same state twice as the consistency of the heuristic guarantees that the first time you expand a node is the best way to expand it. It is just an optimization.

If you get rid of the closed set you will still find the optimal solution but you may expand each state multiple times. However as A* remembers the cost to get to a specific state you're going to expand better (less costly) paths first.

If you don't have the closed set, you can simply remove the open set as it is essentially the same as your fringe of nodes to expand.

This should help you on larger problems, but running out of memory after 300k nodes sounds odd, which brings the next point:

Adjust your JVM memory limits

If I'm not mistaken the default memory limit on some JVM's is quite low, you can increase this by passing -Xms2G for example as command line argument to java.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.