如何解决大输入的 Java 堆空间错误

Question

您好，我正在使用广度优先搜索实现最短路径迷宫求解器算法。当我输入大型拼图 320x320 时，它给出异常错误。请帮忙。（堆空间分配给2gb）

这是错误，

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

这是我代码的一部分，

//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;
    }

是否必须进行任何代码更改以减少代码中的内存消耗？

Answer 1

问题是您需要跟踪访问过的点，这样您就不会再次将它们添加到队列中。为此，您首先需要将 equals 和 hashCode 方法添加到您的 Point 中，以便我们可以保留一组它们。无需过多讨论细节，这就是它的样子（由 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);
}

主要思想是，除了队列之外，您还保留一组已访问的节点，这样您就不必将它们重新添加到队列。

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);
   }
}

下面是一个示例，展示了它的外观。这可能看起来有点奇怪，但我决定保持它的通用性以实现可重用，因为您可能并不总是想使用 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;
}

从这里开始，为您可能遇到的任何 BFS 问题制作一个适配器并不是太困难。例如：

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)
}