使用遞歸在2D數組中查找路徑

我正在爲A級別的項目工作。它涉及到查找網絡的最大流量，並使用javascript。使用遞歸在2D數組中查找路徑

我有一個2D數組，數組中的值表示兩點之間的距離。陣列的一個例子：

我想我需要使用遞歸技術來查找路徑;下面是一些僞代碼，假設數組是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)

我想知道這是否是深度優先搜索的正確結構。謝謝你的幫助。

來源

2010-04-13 rikkit

對不起，數組中的值代表兩點之間的距離？二維數組中的單個位置僅指定一個點，對嗎？ – tloflin 2010-04-13 17:27:11

想象一下行和列標題（ABCD），所以三點和一點是C和A之間的距離。 – rikkit 2010-04-19 10:43:22

認真考慮使用BFS。 Edmonds-Karp是Ford-Fulkerson，但路徑尋找方法是固定的 - BFS，它保證最壞情況O（V * E^2），這與DFS不同。 V是頂點數和E - 邊數。如果你仍然堅持DFS，那麼至少你應該檢查你在循環中下一個訪問的節點還沒有被訪問以防止永久遞歸。你可以爲它使用一個布爾數組。

來源

2010-04-13 17:21:02

尋路可以利用此時，floodFill算法，它可以在一個遞歸形式寫成

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

但是可以輕鬆實現，這是非常低效的，並會導致堆棧溢出一旦你到大十歲上下網格...一個更好的方法來做到這一點將是一個軟件堆棧...

而且，它只發現一個工作的路徑，但不是最有效的路徑。你必須添加計算算法[這不應該花費太多的努力，希望]

來源

2010-04-13 17:51:04 Warty

使用遞歸在2D數組中查找路徑

回答

相關問題