在二维数组列表中搜索深度优先时如何解决"OutOfMemoryError: Java heap space"？

Question

我正在用Java编程一个AI游戏。我有一个(2d(数组列表，它代表网格世界。在网格世界中，有随机放置的对象。对象由黑色方块表示(并且不能在黑色方块上行走(。

我想找到给所有方块上色的最短路径。类看起来是这样的：

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

在运行代码时，第10次移动(约1.000.000(后有太多剩余，导致应用程序失败，出现以下异常：java.lang.OutOfMemoryError:java堆空间。我知道出了什么问题以及为什么(因为树中可能有太多项目(，但我不知道如何解决这个问题。

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

Answer 1

不考虑您的代码，而是考虑一般问题，您希望使用部分扩展的思想。(例如部分展开A*-PEA*(这个想法是，你在每次移动时生成所有后继，但为了节省内存，然后把它们扔掉，只保留当前后继的索引。(为了节省时间，你可以保留多个。(然后，当你想探索下一个孩子时，你可以重新生成继任者并继续。

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