Продвинутая рекурсия в Java

Question

Я просто не могу освоить рекурсию, особенно на сложных примерах. Я был бы очень признателен, если бы кому-то понадобилось время, чтобы объяснить это. У меня буквально есть 4 листа бумаги, заполненные мной, отслеживающие эту функцию, но я понятия не имею, как их собрать.

public static String shortestPath(int x, int y, int tX, int tY,boolean blocked[][]) {

        if(x>blocked.length-1 || y>blocked[0].length-1 || x<0 || y<0 )
            return null;
        if(blocked[x][y]==true)
            return null;
        if(x==tX && y==tY)
            return "";

        String paths[]=new String[4];
        blocked[x][y]=true; //this just means this coordinate is blocked, so dont use it
        paths[0]=shortestPath(x, y+1, tX, tY, blocked);
        paths[1]=shortestPath(x, y-1, tX, tY, blocked);
        paths[2]=shortestPath(x+1, y, tX, tY, blocked);
        paths[3]=shortestPath(x-1, y, tX, tY, blocked);
        blocked[x][y] = false;
        int result=findShortestString(paths, 0, 3); 
//findShortestString just takes an array of strings, 
//with 0 being the lo index and 3 being the hi, 
//and returns the index that contains the string with the shortest length.
        //5
        if(paths[result]==null)
           return null;
        else{

           if(result==0)
                return 'N' + paths[result];
           if(result==1)
                return 'S' + paths[result];
           if(result==2)
                return 'E' + paths[result];
           if(result==3)
                return 'W' + paths[result];}

        return paths[result];

То, что делает этот код, это, учитывая параметры x и y, он сообщает вам кратчайшую комбинацию ходов, которую вы должны сделать (NSWE для севера, юга, запада, востока), чтобы достичь параметров tX и tY , Код работает отлично, но я понятия не имею, как.

Когда я пытаюсь отследить, какие пути [0] вычисляются, он всегда обнуляется, потому что y всегда будет увеличиваться до тех пор, пока не выйдет за пределы, в которых он возвращает ноль. Это тот же случай для путей [1] [2] и [3], все они возвращаются к нулю, не так ли? Итак, как, черт возьми, эта функция работает?

Answer 1

Сначала попробуйте на тривиально маленьком примере - сетка 1x1 без заблокированных ячеек. Как и ожидалось, никаких шагов не предпринимается. x == tX и y == tY, поэтому вы возвращаете пустую строку. Пока все хорошо.

Теперь посмотрите на сетку 2x2, где вы находитесь в северо-западном углу, а пункт назначения - NE.

| @ | ^ |
| o | o |

Когда вы пытаетесь пойти на восток и установить paths[0], он вызывает shortestPath, блокируя вашу текущую ячейку и устанавливая новое местоположение на то, что находится под вами. Теперь у вас есть

| X | ^ |
| @ | o |

В этом вызове он попытается перейти к N, W, S и E. Не обращайте внимания на простоту, что движение на восток происходит раньше, чем на запад, поэтому мы можем сразу завершить остальные 3 направления - все они снова вызывают shortestPath в неверном месте (2 из границ, 1 вы были) и немедленно верните null. Вы идете на восток с новой сеткой и местоположением, подобным этому:

| X | ^ |
| X | @ |

Снова 3 направления возвращаются null. Только север даст вам желаемый конечный результат. Когда вы пытаетесь перейти туда, вы снова вызываете shortestPath, который немедленно возвращает пустую строку, потому что доска теперь выглядит так:

| X | @^ |
| X | X  |

Теперь мы можем обернуть стек вызовов:

1. Поскольку paths[1] была пустой строкой, а остальные 3 были null, result равен 1 (я полагаю, именно так работает ваша строковая функция). Таким образом, вы возвращаете "N" на предыдущий вызов.
2. Предыдущий вызов покажет, что paths[0] == null, paths[1] == null, paths[3] == null, но критически paths[2] равно "N". Следовательно, result будет равно 2, и вы вернете "EN" к предыдущему вызову.

Поскольку теперь вы возвращаетесь к самому первому вызову shortestPath, который завершает первый сделанный нами выбор - идти на юг от начальной позиции. Но у нас также был еще один выбор - идти на восток. Итак, вы следуете за этим деревом, и оно просто "".

Затем следует последний шаг, где вы видите, какая строка меньше, и получаете, что "", конечно, меньше, чем "EN". Таким образом, result равно 2, и поэтому вы начинаете строку с "E", а "E" - ваш окончательный ответ.

Теперь используйте это, чтобы выяснить более крупные примеры. Это помогает нарисовать дерево решений и состояние платы на каждом узле. И когда вы доберетесь до листьев, начертите стрелки, возвращающиеся к родительскому узлу, представляющему возвращаемые значения. Это очень поможет.

Answer 2

Это не так сложно.

Эта часть проверяет, действительны ли параметры x или y (либо в границах, либо не заблокированы)

if(x>blocked.length-1 || y>blocked[0].length-1 || x<0 || y<0 )
   return null;
if(blocked[x][y]==true)
   return null;

Здесь проверяется, достигла ли позицияпункт назначения

if(x==tX && y==tY)
   return "";

Теперь для рекурсивной части эта функция возвращается в четыре другие функции, каждая для доступного направления NSWE относительно текущей позиции:

String paths[]=new String[4];
blocked[x][y]=true; //this just means this coordinate is blocked, so dont use it
paths[0]=shortestPath(x, y+1, tX, tY, blocked);
paths[1]=shortestPath(x, y-1, tX, tY, blocked);
paths[2]=shortestPath(x+1, y, tX, tY, blocked);
paths[3]=shortestPath(x-1, y, tX, tY, blocked);
blocked[x][y] = false;
int result=findShortestString(paths, 0, 3);

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

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

Текущая позиция рекурсии помечается как заблокированная, поэтому алгоритм не возвращается к ранее посещенной позиции.

if(paths[result]==null)
    return null;

Этот параметр проверяет, не нашел ли findShortestString допустимый путь.

В конце путь найден относительно текущей позиции в рекурсииnded к направлению повторяющегося вызова, который нашел кратчайший путь.

Пример: допустим, карта имеет только один действительный путь к пункту назначения, все остальные позиции блокируются.Начальная позиция [0] [0] и пункт назначения [1] [1] (x + 1 = N, y + 1 = E) MAP:

(y-line increases upwards, x-column increases rightwards)
0D
SX

S-start
X-blocked
0-not blocked
D-destination

Первый вызов:

-x,y are within boundaries and are not the destination
-blocks current positions([0][0])
-calls function for y = y+1 -> is blocked (returns NULL)
-calls function for y = y-1 -> out of boundaries (returns NULL)
-calls function for x = x+1 -> path is ok

RECURSION:

-blocks current position[1][0]
-calls function for y = y+1 -> Destination!(returns "")
-calls function for y = y-1 -> out of boundaries(returns NULL)
-calls function for x = x+1 -> out of boundaries(returns NULL)
-calls function for x = x-1 -> blocked(returns NULL) (this would be the starting position)
Since paths[0] has the shortest string("") and the result is 'N'+""

(назад к первой итерации)

-calls function for x = x-1 -> out of boundaries(returns NULL)

Поскольку paths [2] имеет самую короткую строку, результат равен 'E' +'N'.Это правильно.

Поскольку y = y + 1 всегда вызывается первым, рекурсия выполняется до тех пор, пока она не выйдет за пределы.Затем он проверит другие позиции вокруг последней позиции и т. Д.

Answer 3

Пытаясь угадать, о чем вы думаете -

Возможно, вы изображаете 4 пути выполнения:

путь 0: shorttestPath (x, y + 1, tX, tY, заблокирован) -> shorttestPath (x, y + 1, tX, tY, заблокирован) -> ...

путь 1: shorttestPath (x, y-1, tX, tY, заблокирован) -> shorttestPath (x, y-1, tX, tY, заблокирован) -> ...

путь 2: shorttestPath (x + 1, y, tX, tY, заблокирован) -> shorttestPath (x + 1, y, tX, tY, заблокирован) -> ...

путь 3: shorttestPath (x-1, y, tX, tY, заблокирован) -> shorttestPath (x-1, y, tX, tY, заблокирован) -> ...

В действительности пути исполнения образуют дерево. Каждый вызов к shorttestPath порождает еще 4 вызова к shorttestPath, вызов «path0», вызов «path1», вызов «path2» и вызов «path3».

Итак, вы получите один путь выполнения, который будет path0, path0, path0 ... который вернет ноль.

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

Когда рекурсия возвращается к первому вызову ShorttestPath, пути [0] будут содержать кратчайший путь, чье ПЕРВОЕ перемещение было shorttestPath (x, y + 1, tX, tY, заблокировано), путь [1] кратчайший путь, ПЕРВЫЙ ход был кратчайшим путем (x, y-1, tX, tY, заблокирован) и т. д.