2

迷路の生成には深さ優先探索を使用しています。

M*N 個の頂点の隣接行列は、DFS を使用してランダムな順序でトラバースされます。ランダムなルートを生成することにのみ関心があります。

頂点の数を減らしても問題なく動作しますが、それを使用すると StackOverflow Exception が発生します

 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

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 メソッドに含まれているものが含まれます。random()再帰する代わりに、結果によって決定される順序で、4 つの方向のいくつか (最大で 3 つだと思います) でキューを埋めます。

于 2011-04-29T00:06:44.297 に答える
1

(b) に関しては、少なくとも Sun/Oracle JVM では、-XssJVM へのコマンド ライン オプションでスタック サイズを増やすことができます。

于 2011-04-28T23:28:26.267 に答える
0

これがお役に立てば幸いです。

-Xss オプションを使用してスタック サイズを増やすか、コードを書き直すことができます。ここでいくつかのアイデアを得ることができます。

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

コード：

public void dfsPostOrderIterative(AdjGraph グラフ、AdjGraph.Node 頂点、Callback コールバック) { Stack toVisit = new Stack(); toVisit.push(new Level(Collections.singletonList(頂点)));

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 に答える