Итеративная глубина углубления первого поиска в массиве 2d

Question

Я пытаюсь реализовать итеративный поиск углублений в 2-мерном массиве (лабиринте).

static void Run_Ids(int x, int y) 
    { 
     int depth_limit = 0; 

     while(!cutoff) 
     { 
      out.println("Doing search at depth: " + depth_limit);    
      depthLimitedSearch(x, y, depth_limit); 
      depth_limit++; 
     }  
    } 

И вот мой первый поиск глубины с использованием стека. По какой-то причине это происходит между двумя ячейками. Он не расширяется, как должен. Я думаю, что здесь что-то не так с моим алгоритмом DFS.

static void depthLimitedSearch(int x, int y, int depth){   
    Pair successor; //pair is the x, y co-ordinate 
    successor = starting(); //set the successor to starting cell 

    stack = new Stack<>(); 
    int i = 0; 
    stack.push(successor); 

    while (!stack.isEmpty()) 
    { 
     out.println("i level: " + i); 
     Pair parent = stack.peek(); //pop it here? 

     if (parent.x == Environment.goal[0] && parent.y == Environment.goal[1]){ //check to see if it is the goal 
      cutoff = true; 
      out.println("goal found ");     
      break; 
     } 
     if (i == depth){ 
      //stack.pop(); //pop here? 
      break; 
     } 
     else{ 

      Pair leftPos,rightPos,upPos,downPos; 
      leftPos = leftPosition(parent.x, parent.y); 
      rightPos = rightPosition(parent.x, parent.y); 
      upPos = upPosition(parent.x, parent.y); 
      downPos = downPosition(parent.x, parent.y); 


      if(Environment.isMovePossible(rightPos.x, rightPos.y)) 
             //if it can go right 
        stack.push(rightPos); 

      if(Environment.isMovePossible(leftPos.x, leftPos.y)) 
             // if it can go left 
        stack.push(leftPos); 

      if(Environment.isMovePossible(downPos.x, downPos.y)) 
            //if it can go down 
        stack.push(downPos); 

      if(Environment.isMovePossible(upPos.x, upPos.y))     
             //if it can go up 
        stack.push(upPos); 


      stack.pop();   //pop here? 


     } //else  

     i++; 

    }//while  
} 

Я не так много опыта стека, и я путаюсь, куда толкать его и куда совать. если кто-то здесь может указать мне в правильном направлении, это было бы здорово!

Answer 1

Думаю, вам нужно пометить позиции массива, которые вы уже посетили, чтобы избежать повторного посещения их. Не нажимайте на стек любые позиции, которые вы уже посетили.

Без этого, вы, скорее всего, в конечном итоге в бесконечном цикле:

Например, предположим, что из вашего начального положения вы можете заранее во всех направлениях - влево, вправо, вверх и вниз. Таким образом, вы нажимаете эти 4 позиции, а затем выталкиваете последний, который вы нажали - вниз.

Теперь, пока вниз - действующее направление, вы продолжите движение вниз. Когда вы достигнете положения, из которого вы не можете опуститься, вы нажмете следующие правильные направления, которые включают вверх (направление, из которого вы только что пришли).

Поскольку вы выдвигаетесь в стек непосредственно перед тем, как нажимать вниз, когда вы достигнете положения, в котором вы не можете надавить, вверх будет нажата последняя позиция, что означает, что вы затем откроете позицию вверх и перейдите в позицию, из которой вы пришли.

Оттуда вы вернетесь вниз, а затем выполните резервное копирование в бесконечном цикле.