我無法從迷宮中找到最短路徑（廣度優先搜索）

Question

我有一個以矩陣形式表示的迷宮。有一個起點和一個終點。我只能圍繞包含零的單元格移動。我寫了一個可以找到所有可用路徑的函數。但該功能找不到最短路徑。請幫助完成該功能。

matrix = [ 
 
    [0, 1, 0, 1, 0], 
 
    [0, 0, 1, 0, 0], 
 
    [0, 0, 1, 1, 0], 
 
    [0, 0, 0, 0, 0], 
 
    [0, 1, 0, 1, 0] 
 
]; 
 

 
var start = [4,0]; 
 
var end = [1,1]; 
 

 

 
function findWay(position, end) 
 
{ 
 

 
\t var queue = []; 
 

 
\t var visited = []; 
 

 
\t matrix[position[0]][position[1]] = 1; 
 
     visited.push(position); 
 
    \t queue.push(position); 
 

 
    while(queue.length > 0){ 
 

 
    \t var pos = queue.shift(); 
 

 
\t \t var direction = [ [ pos[0] + 1, pos[1] ], [ pos[0], pos[1] + 1 ], 
 
\t     [ pos[0] - 1, pos[1] ], [ pos[0], pos[1] - 1 ] ]; 
 

 
    \t for(var i = 0; i < direction.length; i++){ 
 

 
\t \t  if (direction[i][0] < 0 || direction[i][0] >= matrix[0].length) continue; 
 
\t \t  if (direction[i][1] < 0 || direction[i][1] >= matrix[0].length) continue; 
 

 
\t \t  if (direction[i][0] == end[0] && direction[i][1] == end[1]) return visited; 
 
\t \t  if (matrix[direction[i][0]][direction[i][1]] != 0) continue; 
 

 
\t \t  matrix[direction[i][0]][direction[i][1]] = 1; 
 
\t \t  visited.push(direction[i]); 
 
\t \t  queue.push(direction[i]); 
 

 
    \t } 
 

 
    } 
 

 
    return visited; 
 

 
} 
 

 
findWay(start, end);

Answer 1

變化背後的想法是，一定要記住，每一步你走路徑。當您向隊列中添加新點時，請添加路徑。

通過此路徑，您可以檢查當您進行下一步時是否已經訪問了一個點。然後，您不必操縱矩陣/迷宮來記住訪問點。

如果找到新點，請將新點和路徑添加到隊列中。如果這個點包含在你的路徑中，那麼你會遇到死衚衕，並且不會將它添加到隊列中。

如果你採取了一個步驟，並結束，添加相應的路徑與終點到你的'有效路徑'列表。如果您只對最短路徑感興趣，則第一條有效路徑應該是最短路徑中的一條。

如果你想要所有人，打破如果你的隊列是空的，因爲最終你會訪問每個路徑的每一個點。

function findWay(position, end) 
{ 
    var queue = []; 
    var validpaths = []; 

    // New points, where we did not check the surroundings: 
    // remember the position and how we got there 
    // initially our starting point and a path containing only this point 
    queue.push({pos: position, path: [position]}); 

    // as long as we have unchecked points 
    while(queue.length > 0){ 

     // get next position to check viable directions 
     var obj = queue.shift(); 
     var pos = obj.pos; 
     var path = obj.path; 

     // all points in each direction 
     var direction = [ [ pos[0] + 1, pos[1] ], [ pos[0], pos[1] + 1 ], 
        [ pos[0] - 1, pos[1] ], [ pos[0], pos[1] - 1 ] ]; 

     for(var i = 0; i < direction.length; i++){ 

      // check if out of bounds or in a "wall" 
      if (direction[i][0] < 0 || direction[i][0] >= matrix[0].length) continue; 
      if (direction[i][1] < 0 || direction[i][1] >= matrix[0].length) continue; 
      if (matrix[direction[i][0]][direction[i][1]] != 0) continue; 

      // check if we were at this point with this path already: 
      var visited = false; 
      for (var j = 0; j < path.length; j ++) { 
       if ((path[j][0] == direction[i][0] && path[j][1] == direction[i][1])) { 
        visited = true; 
        break; 
       } 
      } 
      if (visited) continue; 

      // copy path 
      var newpath = path.slice(0); 
      // add new point 
      newpath.push(direction[i]); 

      // check if we are at end 
      if (direction[i][0] != end[0] || direction[i][1] != end[1]) { 
      // remember position and the path to it 
      queue.push({pos: direction[i], path: newpath}); 
      } else { 
      // remember this path from start to end 
      validpaths.push(newpath); 
      // break here if you want only one shortest path 
      } 

     } 
    } 
    return validpaths; 
} 

var paths = findWay(start, end);