2

我正在使用深度优先搜索来生成迷宫。

使用 DFS 以随机顺序遍历 M*N 个顶点的邻接矩阵，我只对生成随机路由感兴趣。

这个东西在减少顶点数量的情况下工作得很好，但是在使用它时我得到了一个 StackOverflow 异常

 Graph theGraph = new Graph(1000,1000);

问题： a）如何使用堆栈将此递归调用更改为迭代调用？

b）有没有办法为方法调用堆栈分配更多内存？

class IJ {

        int i;
        int j;

        IJ (int i,int j){
            i = this.i;
            j= this.j;

        }

}


class Graph {

    int M;
    int N;

    int adjacencyMatrix[][];

    ArrayList <IJ> orderOfVisits;

    Graph(int M,int N){

        this.M=M;
        this.N=N;
        adjacencyMatrix=new int[M][N];

        for (int i=0; i<M; i++)
            for (int j=0;j<N;j++){
                    adjacencyMatrix[i][j]=-1; //mark all vertices as not visited
            }

        orderOfVisits = new ArrayList<IJ>();

    }

 void DFS(int i, int j){ // i,j identifies the vertex

     boolean northValid= false;
     boolean southValid= false;
     boolean eastValid = false;
     boolean westValid = false;


     int iNorth, jNorth;
     int iSouth, jSouth;
     int iEast, jEast;
     int iWest, jWest;

     iNorth=i-1;
     if (!(iNorth<0)) northValid=true;

     iSouth=i+1;
     if(!((iSouth)>=M)) southValid=true;

     jEast=j+1;
     if(!((jEast)>=N)) eastValid=true;

     jWest= j-1;
     if (!(jWest<0)) westValid=true;


    if (adjacencyMatrix[i][j]==-1){ //if the vertex is unvisited

        adjacencyMatrix[i][j]=0; //mark the vertex as visited
        IJ ij = new IJ(i,j);
        orderOfVisits.add(ij); //add the vertex to the visit list
        System.out.println("Visit i,j: " + i +" " +j);



        Double lottery = Math.random();

       for (int rows=i; rows<M; rows++)
           for (int cols=j; cols<N; cols++){


        if (lottery>0.75D){
            if(northValid)
            {
                DFS(iNorth,j);
            }

            if(southValid){
                DFS(iSouth,j);
            }

            if(eastValid){
                DFS(i, jEast);
            }

            if(westValid){
                DFS(i,jWest);
            }


        }

       else if (lottery<0.25D)
       {

            if(westValid){
                DFS(i,jWest);
            }

             if(eastValid){
                DFS(i, jEast);
            }

             if(southValid){
                DFS(iSouth,j);
            }

            if(northValid)
            {
                DFS(iNorth,j);
            }

       }

       else if ((lottery>=0.25D)&&(lottery<0.5D))
       {

             if(southValid){
                DFS(iSouth,j);
            }

             if(eastValid){
                DFS(i, jEast);
            }

            if(westValid){
                DFS(i,jWest);
            }

            if(northValid){
                DFS(iNorth,j);
            }

       }

        else if ((lottery>=0.5D)&&(lottery<=0.75D))
       {

            if(eastValid){
                DFS(i, jEast);
            }

            if(westValid){
                DFS(i,jWest);
            }

            if(southValid){
                DFS(iSouth,j);
            }

            if(northValid){
                DFS(iNorth,j);
            }

       }

    }

 } //end nested for

} //end DFS

//
}


public class Main {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application logic here



    Graph theGraph = new Graph(1000,1000);
    theGraph.DFS(0,0);



    }

}
4

4 回答 4

2

一些伪代码：

Stack<IJ> nodesToVisit;

nodesToVisit.Push(new IJ(0, 1));
nodesToVisit.Push(new IJ(1, 0));

while (nodesToVisit.Count > 0)
{
    var ij = nodesToVisit.Pop();
    if (visited ij) 
       continue;
    .... mark ij visited
    ... check north/south/east/west validity
    List<IJ> directions = new List<IJ>();
    if (canGoNorth)
        directions.Add(new IJ(iNorth, j));
    if (canGoSouth)
        directions.Add(new IJ(iSouth, j));
    if (canGoEast)
        directions.Add(new IJ(i, jEast));
    if (canGoWest)
        directions.Add(new IJ(i, jWest));
    ... randomize list
    foreach (direction in directions)
       nodesToVisit.Push(direction);
}

基本上：

  • 以随机顺序将所有可能的方向推入堆栈
  • 选择最上面的项目
  • 去那里
  • 重复直到堆栈为空（不再访问节点）

我不认为增加堆栈限制是解决问题的好方法。

于 2011-04-28T23:46:40.980 回答
1

关于 (b)，至少对于 Sun/Oracle JVM，您可以使用-XssJVM 的命令行选项来增加堆栈大小。

于 2011-04-28T23:28:26.267 回答
1

您必须将递归实现转换为迭代实现。通常（我也认为在这里）递归算法比做同样事情的迭代算法更容易理解。

原则上，您需要将 Java 方法调用堆栈替换为包含必要信息的显式数据结构（堆栈等）。

在您的情况下，它将是当前节点，以及要访问的剩余邻居节点的列表，按照它们应该被访问的顺序。

class DFSNode {
   DFSNode parent;
   int x, y;
   Queue<Direction> neighborsToVisit;
   DFSNode(DFSNode p, int x, int y) {
      this.parent = p; this.x = x; this.y = y;
      this.neighborsToVisit = new ArrayDeque(3);
   }
}

enum Direction {

   // TODO: check the numbers
   NORTH(0,1), SOUTH(0,-1), EAST(1,0), WEST(-1,0);

   Direction(int dX, dY) {
      deltaX = dX; deltaY = dY;
   }

   private int deltaX, deltaY;

   int nextX(int x) { return x + deltaX; }
   int nextY(int y) { return y + deltaY; }
}

void visitNode(DFSNode node) {
    // TODO: check which adjacent directions are valid,
    // randomize the order of these adjacent directions,
    // fill them in the queue.
}

void visitGraph(int x, int y) {
   DFSNode currentNode = new DFSNode(null,x,y);
   visitNode(currentNode);
   while(currentNode != null) {
      Direction dir = currentNode.neighboursToVisit.poll();
      if(dir == null) {
         // all neighbours of this node already visited
         // ==> trackback to parent (and end if this is root node)
         currentNode = currentNode.parent;
         continue;
      }
      currentNode = new DFSNode(currentNode, dir.nextX(currentNode.x), dir.nextY(currentNode.y));
      visitNode(currentNode);
   }
}

将visitNode包含主要逻辑，即现在在您的 DFS 方法中的内容。它不是递归，而是按照结果确定的顺序用四个方向中的一些（我认为最多 3 个）填充队列random()。

于 2011-04-29T00:06:44.297 回答
0

我希望你会发现这很有帮助。

您可以使用 -Xss 选项增加堆栈大小或重写代码。你可以在这里得到一些想法。

http://www.vvlasov.com/2013/07/post-order-iterative-dfs-traversal.html

代码：

public void dfsPostOrderIterative(AdjGraph 图，AdjGraph.Node 顶点，回调回调) { Stack toVisit = new Stack(); toVisit.push(new Level(Collections.singletonList(vertex)));

while (!toVisit.isEmpty()) {
    Level level = toVisit.peek();

    if (level.index >= level.nodes.size()) {
        toVisit.pop();
        continue;
    }

    AdjGraph.Node node = level.nodes.get(level.index);

    if (!node.isVisited()) {
        if (node.isChildrenExplored()) {
            node.markVisited();
            callback.nodeVisited(graph, node);
            level.index++;
        } else {
            List<AdjGraph.Node> edges = graph.edges(node);
            List<AdjGraph.Node> outgoing = Lists.newArrayList(Collections2.filter(edges, new Predicate<AdjGraph.Node>() {
                @Override
                public boolean apply(AdjGraph.Node input) {
                    return !input.isChildrenExplored();
                }
            }));

            if (outgoing.size() > 0)
                toVisit.add(new Level(outgoing));
            node.markChildrenExplored();
        }
    } else {
        level.index++;
    }
}

}

于 2013-07-26T07:04:43.937 回答