Ошибка StackOverflow: как я могу избежать этого или превратить эту DFS в итеративную? - PullRequest
Новая
       38

Ошибка StackOverflow: как я могу избежать этого или превратить эту DFS в итеративную?

2 голосов
/ 29 апреля 2011

Я использую Поиск в глубину для создания лабиринта.

Матрица смежности M * N вершин перемещается в случайном порядке с использованием DFS, меня интересует только генерация случайного маршрута.

Эта вещь прекрасно работает с уменьшенным количеством вершин, но я получаю исключение StackOverflow при использовании его с 

 Graph theGraph = new Graph(1000,1000);

Вопросы: a) Как я могу изменитьэто рекурсивные вызовы с использованием стека?

б) Есть ли способ выделить больше памяти стеку вызовов методов? 

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 ]

2 голосов
/ 29 апреля 2011

Некоторый псевдокод: 

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

В основном:

  • Вставить все возможные направления в стеке в случайном порядке
  • Выбрать верхний элемент
  • Перейдите туда
  • Повторяйте до тех пор, пока стек не станет пустым (и не будет больше посещаемых узлов)

Не думаю, что увеличение предела стека является хорошим решением вашей проблемы.

1 голос
/ 29 апреля 2011

Вы должны будете преобразовать рекурсивную реализацию в итеративную.Часто (и я думаю, что и здесь) рекурсивный алгоритм гораздо проще понять, чем итеративный, выполняющий те же действия.

В принципе, вам необходимо заменить стек вызова методов 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().

1 голос
/ 29 апреля 2011

Что касается (b), по крайней мере с JVM Sun / Oracle вы можете увеличить размер стека с помощью опции командной строки -Xss до JVM.

0 голосов
/ 26 июля 2013

Надеюсь, вы найдете это полезным.

Вы можете увеличить размер стека с помощью опции -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 (новый уровень (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++;
    }
}

}

...