0

我正在用 java 做一个 8 块益智游戏，我做 DFS 以找到解决方案的分配命令，从随机状态开始。

我有一个 Node 类，每个 Node 对象都知道它使用 int[][] 处于什么状态以及它的父节点是什么。它还知道它可以向哪个方向移动（左、右、上、下）

     goal state:     start state (random):
     [0 1 2]         [1 8 0]
     [3 4 5]         [3 7 4]
     [6 7 8]         [2 5 6]

从单个节点开始，开始节点，我的程序为其所有可能的子节点创建一个节点。它检查空白方块可以移动的可用方向，它检查它是否不会回到已经属于另一个节点的状态。所以在上面的例子中，起始节点会展开如下：

          [1 8 0]
      A)  [3 7 4]
          [2 5 6]
         /       \
    [1 0 8]     [1 8 4]
B)  [3 7 4]     [3 7 0]  C)
    [2 5 6]     [2 5 6]
   /   /       /       \
...  ...  [1 8 4]     [1 8 4]
      D)  [3 0 7]     [3 7 6]  E)
          [2 5 6]     [2 5 0]
         /  /  /       /    \
     ... ... ... [1 8 4]     NO
             F)  [3 7 6]     CHILD
                 [2 0 5]
                /       \
             ...         ...

我处理这个问题的方法是我探索第一个节点并将它的所有子节点推入堆栈，这发生在递归方法中，循环扩展每个节点直到达到目标状态或达到截止（我提供给避免永远循环）

stack = [A]
pop()
stack = []
A -> B
push(B)
stack = [B]
A -> C
push(C)
stack = [C|B]
A -> NO MORE CHILDREN
pop()
stack = [B]
C -> D
push(D)
stack = [D|B]
C -> E
push(E)
stack = [E|D|B|]
C -> NO MORE CHILDREN
pop()
stack = [D|B|]
E -> F
push(F)
stack = [F|D|B]
E -> NO MORE CHILDREN
pup()
stack = [D|B]

只要我的截止值不太高，代码就可以正常工作，如果它比我得到错误：java.lang.StackOverflowError

我究竟做错了什么？

public void expand(Node parent, int cutoff){
  cutoff--;

  int[][] currentState = parent.getState();

  if(Arrays.deepEquals(currentState, goalState)){
    found = true;
    goalNode = parent;
  }


  if(cutoff>0 && !found){
    if(parent.up){
      Node child = createUPnode();
      child.setParent(parent);
      stack.push(child);
      parent.up = false;
      expand(parent, cutoff)
    }
    else if(parent.right){
      Node child = createRIGHTnode();
      child.setParent(parent);
      stack.push(child);
      parent.right = false;
      expand(parent, cutoff)
    }
    else if(parent.down){
      Node child = createDOWNnode();
      child.setParent(parent);
      stack.push(child);
      parent.down = false;
      expand(parent, cutoff)
    }
    else if(parent.left){
      Node child = createLEFTnode();
      child.setParent(parent);
      stack.push(child);
      parent.left = false;
      expand(parent, cutoff)
    }
    else{
      Node nextNode = stack.pop();
      expand(nextNode, cutoff);
    }
  }
  else{
    System.out.println("CUTOFF REACHED");
  }
}
4

2 回答 2

1

帖子“什么是堆栈溢出错误？” 包含很多关于在 Java 中可能导致 StackOverflowError 的信息。这种错误的最常见原因是错误的递归调用（导致无限循环）。您似乎已经通过为您的递归调用引入一个截止值来防止这种情况发生expand()。

但即使使用此分隔符，堆栈大小也可能太小而无法处理递归调用。我相信你有两个选择：

1）为您的截止值使用“足够小”的值（这实际上有效，正如您已经写的那样）但这会限制您的搜索深度。

2）增加JVM的堆栈大小。您可以通过将标志添加-Xss1024k为 VM 参数来执行此操作。有关如何增加堆栈大小的更多信息，请阅读Java 堆栈溢出错误 - 如何在 Eclipse 中增加堆栈大小？

于 2011-05-03T11:09:51.080 回答
0

使用 a 实现 DFS 或 BFS 很简单Dequeue，无需任何递归，只需循环，从出队的头部读取并为尾部 (BFS) 生成新的解决方案。要使用 DSF，请将孩子添加到头部。

我认为您应该使用广度优先搜索来找到最短的解决方案，对吗？

如果您确定深度优先搜索（我认为这没什么意义），您可以取消递归并使用dequeue您创建的（而不是调用堆栈）。不需要重复调​​用。只是循环：通过弹出一个节点开始每个循环，生成它的子节点并将它们推到出队的头部，然后重新开始。如果dequeue为空，则没有解决方案...

在大多数情况下，最好在将生成的解决方案添加到队列末尾之前检查是否已经生成了生成的解决方案，以减少内存使用。使用普通集合，HashSet 可能比 TreeSet 更快——记住要Node.equals()正确实现Node.hashCode()。

我想在这种情况下，普通的LinkedList将是最有效Dequeue的 - 但为什么不测试自己。

于 2011-05-03T12:07:42.883 回答