Java: рандомизация порядка рекурсивных вызовов методов

#java #random #depth-first-search #maze

#java #Случайный #поиск в глубину #Лабиринт

Вопрос:

Для генерации лабиринта DFS в Java я хочу рандомизировать порядок, в котором выполняются рекурсивные вызовы DFS:

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

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

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

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

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

Как я могу это сделать?

Ответ №1:

Включите вызов класса Random:

 Random r = new Random();
for (int rows=i; rows<M; rows  )
    for (int cols=j; cols<N; cols  ) {
        bool found = false;
        while (!found)
            switch (r.next() % 4) {
                case 0: if(northValid) { DFS(iNorth,j); found = true; } break;
                case 1: if(southValid) { DFS(iSouth,j); found = true; } break;
                case 2: if(eastValid)  { DFS(i, jEast); found = true; } break;
                case 3: if(westValid)  { DFS(i, jWest); found = true; } break;
            }
    }

Обратите внимание, что, используя этот подход, вам нужно перебирать переключатель, пока он не упрется в доступную стену, а затем продолжить. Это немного неэффективно, но довольно просто.

Ответ №2:

Псевдокод:

 for (int rows=i; rows<M; rows  )
{
    for (int cols=j; cols<N; cols  )
    {
        // Generate a random number between 0 to 3 => %4
        switch(randomNumber)
        {
            case 0:  DFS(iNorth,j);
                     break;
            // ...

            case 3:  DFS(i,jWest);
                     break; 

            default: break;
        }
    }
}

Ответ №3:

В итоге я использовал это:

  Double lottery = Math.random();

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


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

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

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

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


        }

       else if (lottery<0.5D)  
       {

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

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

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

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


       }

Сработало хорошо, спасибо за ответы.