Использование рекурсии для поиска путей в двумерном массиве - PullRequest
Новая
       20

Использование рекурсии для поиска путей в двумерном массиве

0 голосов
/ 13 апреля 2010

Я работаю над проектом для моего уровня А. Это включает в себя поиск максимального потока в сети, и я использую JavaScript.

У меня есть 2D-массив со значениями в массиве, представляющими расстояние между двумя точками. Пример массива: 

0 2 2 0
0 0 1 2
0 0 0 2
0 0 0 0

Я думаю, что мне нужно использовать рекурсивную технику, чтобы найти путь; ниже - некоторый псевдокод, предполагая, что массив 4x4. a равно (0,0), b равно (3,3). 

function search(a,b)
  from a to b
    if element(i,j) != 0 then
      store value of element
      search(j,3)

Мне было интересно, была ли это правильная конструкция для поиска в глубину. Спасибо за любую помощь.

Ответы [ 2 ]

1 голос
/ 13 апреля 2010

Нахождение пути может быть легко достигнуто с помощью алгоритма заливки, который можно записать в рекурсивной форме как 

function floodFill(x, y, prevPoints)
{
 var prevPoints = prevPoints.concat([]); //make a copy of the points list since JS uses ref

 if(grid[x][y].isExit) return prevPoints;
 grid[x][y].accessed = true;
 prevPoints.push([x, y]);

 var result;
 var cfr; //cellfillresult
 if(grid[x+1][y].isPath && !grid[x+1][y].accessed) cfr = floodFill(x+1, y, prevPoints);
 if(cfr != null) result = cfr;

 if(grid[x-1][y].isPath && !grid[x-1][y].accessed) cfr = floodFill(x-1, y, prevPoints);
 if(cfr != null) result = cfr;

 if(grid[x][y+1].isPath && !grid[x][y+1].accessed) cfr = floodFill(x, y+1, prevPoints);
 if(cfr != null) result = cfr;

 if(grid[x][y-1].isPath && !grid[x][y-1].accessed) cfr = floodFill(x, y-1, prevPoints);
 if(cfr != null) result = cfr;

 return result;
}

var pathToExit = floodFill(entranceX, entranceY, []);

Однако это крайне неэффективно и приведет к переполнению стека, как только вы доберетесь до сеток большего размера ... Лучший способ сделать это - создать программный стек ...

Кроме того, он находит только работающий путь, но не самый эффективный путь. Вам нужно будет добавить подсчет в алгоритм [который, надеюсь, не потребует слишком много усилий]

1 голос
/ 13 апреля 2010

Серьезно подумайте об использовании BFS. Edmonds-Karp - это Ford-Fulkerson , но метод поиска пути исправлен - BFS, что гарантирует наихудший случай O (V * E ^ 2), что не относится к DFS , V - количество вершин, E - количество ребер. Если вы все еще настаиваете на DFS, то по крайней мере вы должны проверить, что узел, который вы посещаете следующим в цикле, еще не посещен, чтобы предотвратить вечную рекурсию. Вы можете использовать для него логический массив.

...