StackOverflow 오류 :이 DFS를 반복적으로 사용하지 않거나 회피하려면 어떻게해야합니까?

Question

저는 미로 생성을위한 Depth First Search를 사용하고 있습니다.

M * N 정점의 인접 행렬은 DFS를 사용하여 임의의 순서로 이동하며, 임의의 경로 생성에만 관심이 있습니다.

것은 정점의 수가 감소와 함께 잘 작동하지만

Graph theGraph = new Graph(1000,1000); 

질문에 그것을 사용할 때이 StackOverflow의 예외를 받고 있어요 : A) 나는 반복이 재귀 호출을 변경할 수있는 방법 스택을 사용하는 사람?

b) 메서드 호출 스택에 더 많은 메모리를 할당 할 수있는 방법이 있습니까? (b)는, 적어도 썬/오라클 JVM과 함께, 당신은 JVM에 -Xss 명령 줄 옵션을 사용하여 스택 크기를 증가시킬 수와 관련하여

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



    } 

} 

Answer 1

.

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

:

• 밀어 임의의 순서로
• 의 스택에 모든 가능한 방향은 맨 위 항목이
• 반복
• 이동까지 선택 스택이 비어있다 (더 이상 방문 할 노드가 없음)

스택 제한을 늘리는 것이 문제에 대한 좋은 해결책이라고 생각하지 않습니다.

Answer 3

반복적 구현을 ​​반복적 구현으로 변환해야합니다. 종종 반복 알고리즘은 동일한 것을하는 반복적 인 알고리즘보다 훨씬 이해하기 쉽다.

원칙적으로 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 방법에 포함되어있는 논리가 포함됩니다. 재귀 대신에 큐의 일부를 4 개의 방향 (최대 3 개)으로 채우고, 결과는 random()입니다.

Answer 4

도움이 되셨기를 바랍니다.

-Xss 옵션을 사용하여 스택 크기를 늘리거나 코드를 다시 작성할 수 있습니다. 여기에 아이디어를 얻을 수 있습니다.

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

번호 :

공개 무효 dfsPostOrderIterative (AdjGraph 그래프 AdjGraph.Node 정점 콜백 콜백) { 스택 toVisit = 새로운 스택(); toVisit.push (새 레벨 (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++; 
    } 
} 

}