How to solve Java heap space error for large inputs

Question

Hi im implementing shortest path maze solver algorithm using breadth first search. when i input large scale puzzle 320x320 it gives exeption error. please help.(Heap space allocated to 2gb)

this is the error,

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
    at Maze.getPathBFS(Maze.java:58)
    at Maze.main(Maze.java:132)

this is part of my code,

//data structure to store matrix cell coordinates
    private static class Point {
        int x;
        int y;
        Point parent;

        public Point(int x, int y, Point parent) {
            this.x = x;
            this.y = y;
            this.parent = parent;
        }

        public Point getParent() {
            return this.parent;
        }

        public String toString() {
            return "x = " + x + " y = " + y;
        }
    }   
//queue to store cells
    public static Queue<Point> path = new LinkedList<>();

    // BFS algorithm to acquire the shortest path to destination
    public static Point getPathBFS(int x, int y, String[][] graph) {

        //start point
        path.add(new Point(x, y, null));

        while (!path.isEmpty()) {
            Point point = path.remove();


            //finding destination coordinate
            if (graph[point.x][point.y].equals("F")) {
                return point;
            }

            //checking neighbour cells for path and add path to the queue
            if (isValid(point.x + 1, point.y, graph)) { //checking down cell is valid to visit
                graph[point.x][point.y] = "-1"; // mark reached cell
                Point nextP = new Point(point.x + 1, point.y, point);
                path.add(nextP);
            }

            if (isValid(point.x - 1, point.y, graph)) {//checking Up cell is valid to visit
                graph[point.x][point.y] = "-1";
                Point nextP = new Point(point.x - 1, point.y, point);
                path.add(nextP);
            }

            if (isValid(point.x, point.y + 1, graph)) { //checking Right cell is valid to visit
                graph[point.x][point.y] = "-1";
                Point nextP = new Point(point.x, point.y + 1, point);
                path.add(nextP);
            }

            if (isValid(point.x, point.y - 1, graph)) { //checking left cell is valid to visit
                graph[point.x][point.y] = "-1";
                Point nextP = new Point(point.x, point.y - 1, point);
                path.add(nextP);
            }

        }
        return null;
    }

is there any code change must be done to reduce memory consumption in the code?

Answer 1

The issue is you need to keep track of visited points so you don't add them to the queue again. To do that you first need to add equals and hashCode methods to your Point so we can keep a set of them. Without going too much into the details, here is what that would look like (generated by Intellij):

@Override
public boolean equals(Object o) {
    if (this == o) return true;
    if (o == null || getClass() != o.getClass()) return false;
    Point point = (Point) o;
    return x == point.x && y == point.y;
}

@Override
public int hashCode() {
    return Objects.hash(x, y);
}

The main idea is that in addition to your queue, you also keep a set of visited nodes so you don't re-add them to the queue.

Set<Point> visited = new HashSet<>();

while (queue has points left) {
   Point next = pop back of queue
   // Add this point so we don't visit it again later
   visited.add(next);
   
   for (Point x adjacent to next) {
       if (visited.contains(x)) continue;
       queue.add(x);
   }
}

Now here is an example of how that might look. This might look a little weird, but I decided to keep it generic for re-usability since you may not always want to use Point.

@FunctionalInterface
public interface ExpandNode<T> {
    Stream<T> expand(T position);
}

@FunctionalInterface
public interface EndCondition<T> {
    boolean isEndPoint(T position);
}

private static class NodePath<T> {
    final T node;
    final NodePath<T> previous;

    NodePath(T node, NodePath<T> previous) {
        this.node = node;
        this.previous = previous;
    }
}

public static <T> List<T> performBFS(T initial, EndCondition<T> endCondition, ExpandNode<T> expander) {
    // Keep queue as a local variable to prevent weird side effects from multiple threads using performBFS
    Deque<NodePath<T>> queue = new ArrayDeque<>();
    queue.push(new NodePath<>(initial, null));

    // Keep set of visited nodes so we don't revisit locations
    Set<T> visited = new HashSet<>();

    while (!queue.isEmpty()) {
        NodePath<T> next = queue.getFirst();
        visited.add(next.node);

        // If we are at the end unwind the path to get the list of nodes
        if (endCondition.isEndPoint(next.node)) {
            List<T> nodes = new ArrayList<>();
            nodes.add(next.node);

            while (next.previous != null) {
                next = next.previous;
                nodes.add(next.node);
            }

            Collections.reverse(nodes);
            return nodes;
        }


        NodePath<T> finalNext = next;
        expander.expand(next.node)
                .filter(node -> !visited.contains(node))
                .forEach(node -> queue.addLast(new NodePath<>(node, finalNext)));
    }

    return null;
}

From there it isn't too difficult to make an adapter for any BFS problem you might have. For example:

public static List<Point> getPathBFS(Point start, String[][] graph) {
    Point[] offsets = {
            new Point(-1, 0),
            new Point(0, -1),
            new Point(1, 0),
            new Point(0, 1)
    };
    
    EndCondition<Point> endCondition = position -> graph[position.x][position.y].equals("F");
    
    ExpandNode<Point> expander = position -> Stream.of(offsets)
            .filter(offset -> isValid(position.x + offset.x, position.y + offset.y, graph))
            .map(offset -> new Point(position.x + offset.x, position.y + offset.y));
    
    return performBFS(start, endCondition, expander)
}