Utilisation de la récursion pour trouver des chemins dans un tableau 2D

Question

Je travaille sur un projet pour mon niveau A. Cela implique de trouver le débit maximal d'un réseau, et j'utilise javascript.

J'ai un tableau 2D, avec des valeurs dans le tableau représentant une distance entre les deux points. Un exemple du tableau:

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

Je pense que je dois utiliser une technique récursive pour trouver un chemin; ci-dessous est un pseudocode, en supposant que le tableau est 4x4. a est (0,0), b est (3,3). Je me demandais si c'était la bonne construction pour une première recherche en profondeur. Merci pour toute aide.

Answer 1

Considérer sérieusement l'utilisation de BFS. Edmonds-Karp est le Ford-Fulkerson mais la méthode de recherche de chemin est fixée - BFS, ce qui garantit le pire cas O (V * E^2), ce qui n'est pas le cas avec DFS. V est le nombre de sommets et E - le nombre d'arêtes. Si vous insistez toujours sur DFS, vous devez au moins vérifier que le noeud que vous visitez dans la boucle n'est pas encore visité pour empêcher la récursion éternelle. Vous pouvez utiliser un tableau booléen pour cela.

Answer 2

Pathfinding peut être facilement obtenue en utilisant l'algorithme de floodfill, qui peut être écrit sous une forme récursive

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, []); 

Cependant, cela est très inefficace et provoquera un débordement de pile une fois que vous arrivez à plus-ish grilles ... Une meilleure façon de le faire serait de faire une pile logicielle ...

En outre, il trouve seulement un chemin qui fonctionne, mais pas le chemin le plus efficace. Vous devrez ajouter le compte à l'algorithme [qui ne devrait pas prendre trop d'effort, je l'espère]