当在2D ArrayList中搜索深度优先时，如何解决“OutofMemoryError：Java堆空间”？

Question

我正在用Java编写一个人工智能游戏。我有一个(2D)arraylist表示GridWorld。在gridworld中有随机放置的对象。对象由黑色方块表示（您不能越过黑色方块）。

public class DepthFirstAI {
  private int nodeCounter = 0;

  // run this function for each move
  private Node<ArrayList<ArrayList<Color>>> buildTree(Node<ArrayList<ArrayList<Color>>> tree) {
        if(nodeCounter > 0) {
            leaves.clear();
            getLeaves(tree);

            for(Node<ArrayList<ArrayList<Color>>> child : leaves) {
                child.addChild(bla(child).getData()); // add new childs (based on the possible directions) to the node
            }
        } else {
            tree = bla(tree);
        }

        nodeCounter++;
        return tree;
    }

    public Node<ArrayList<ArrayList<Color>>> bla(Node<ArrayList<ArrayList<Color>>> node) {
        ArrayList<ArrayList<Color>> grid = node.getData().getValue();

        int roboX = roomGUI.player.x; // x location of player
        int roboY = roomGUI.player.y; // y location of player


        // Add possible directions (top, left, right, bottom) to directionsList
        .......

            Directions[] directions = directionsList.toArray(new Directions[0]);
            for (Directions d : directions) { // Create new child for each possible direction with the new grid + the name of the direction
                switch (d) {
                    case TOP: {
                        ArrayList<ArrayList<Color>> tempGrid = grid;
                        // Color squares visited by player
                        .....

                        Pair<Directions, ArrayList<ArrayList<Color>>> child = new Pair<>(Directions.TOP, tempGrid);
                        node.addChild(child);
                        break;
                    }
                    case BOTTOM: {
                        ...
                        break;
                    }
                    case RIGHT: {
                        ...
                        break;
                    }
                    case LEFT: {
                        ...
                        break;
                    }
                }
            }
        }
        return tree;
    }

public class Node<T> {
        private ArrayList<Node<T>> children = new ArrayList<Node<T>>();
        private Node<T> parent = null;
        private Pair<Directions, ArrayList<ArrayList<Color>>> data = null;

        public Node(Pair<Directions, ArrayList<ArrayList<Color>>> data) {
            this.data = data;
        }

        public Node(Pair<Directions, ArrayList<ArrayList<Color>>> data, Node<T> parent) {
            this.data = data;
            this.parent = parent;
        }

        public ArrayList<Node<T>> getChildren() {
            return children;
        }

        public boolean hasChildren() {
            return children.size() > 0;
        }

        public void setParent(Node<T> parent) {
            this.parent = parent;
        }

        public void addChild(Pair<Directions, ArrayList<ArrayList<Color>>> data) {
            Node<T> child = new Node<T>(data);
            this.children.add(child);
        }

        public Pair<Directions, ArrayList<ArrayList<Color>>> getData() {
            return this.data;
        }

        public void setData(Pair<Directions, ArrayList<ArrayList<Color>>> data) {
            this.data = data;
        }

        public boolean isRoot() {
            return (this.parent == null);
        }

        public boolean isLeaf() {
            return this.children.size() == 0;
        }

        public void removeParent() {
            this.parent = null;
        }
    }
}

我如何能够创建一个具有所有可能选项的树来找到最短路径？

Answer 1

不是看你的代码，而是看一般的问题，你想看看使用部分扩展的思想。（例如部分扩展a*-pea*)其思想是，在每次移动时生成所有后继，但随后丢弃它们以节省内存，只保留当前后继的索引。（为了节省时间，你可以保留多个。）然后，当你想探索下一个孩子的时候，你就再生继任者并继续下去。

当您有很多继任者时，这有可能解决内存问题。（假设您的问题实际上不是由垃圾收集或代码中的其他bug引起的。）但是，请注意，即使解决了空间问题，树也可能太大，无法有效地搜索。许多DFS问题随着树的深度呈指数增长，所以在真正小的问题上尝试一下，以确保它首先工作。