Advanced Recursion in 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]; 

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

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

Answer 1

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

Теперь посмотрите на сетку 2x2, где вы находитесь в углу NW, а пункт назначения - 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] is "N". Поэтому result будет 2, и вы вернете "EN" к более раннему звонку.

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

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

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

Answer 2

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

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

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

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

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

путь 3: shortestPath (х-1, у, Тх, TY, заблокирован) -> shortestPath (х-1, у, Тх, TY, блокированных) -> ...

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

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

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

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

Answer 3

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

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

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(), вероятно, возвращает null, если каждая строка равна NULL, поэтому цель не может быть достигнута из исходной позиции этой рекурсии.

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

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

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

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

Пример: Допустим, что карта имеет только один действительный путь к пункту назначения, все остальные позиции находятся в режиме bocked. Исходное положение является [0] [0] и адресат [1] [1] (х + 1 = Н, у + 1 = Е) КАРТА:

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

Поскольку пути [2] имеют кратчайшую строку, результатом является «E» + «N». Что правильно.

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