algorithm - 8个方向穿越矩阵迷宫

Question

You are given a matrix with 1s and 0s, where 0 represents free path and 1 represents blocked area. You can move in any of the 8 directions. Find the shortest path from source to destination.

我能够想出的解决方案，其中 dp[i,j] 存储距起始顶点的最小距离:

recursion(int i, int j , int sum)
{

  if(!issafe(i,j) || isvisited[i,j]) // within bounds
  return ;

  if(matrix(i,j)==0)//blocked
  return ;

  isvisited[i,j]=true;

  dp[i,j] = min(dp[i,j] , sum);
  // directions have usual meaning

  recursion(east ,sum+1);  // i , j+1
  recursion(north , sum+1);  //i-1 , j
  recursion(west , sum+1);
  recursion(south , sum+1);
  recursion(north-east , sum+1);
  recursion(north-west , sum+1);
  recursion(south-east , sum+1);
  recursion(south-west , sum+1);

  isvisited[i,j]=false;

return;
}  

现在我的疑问是假设我们可以从 8 个位置到达 [i,j]。一旦我从位置 1 到达它，说分钟。路径是 x 个单位，我立即递归地检查它的邻居。现在，我来自路径 2 并找到那分钟。路径(以前是 x)现在是 y 而不是 x，现在再次递归检查。所以，我在第 1 步做了额外的计算，这不是必需的。有没有什么方法可以让我在找到最小值后才递归检查邻居？当前单元格的路径(可从所有 8 个位置到达)？

Answer 1

这是一个 shortest path problem在非加权图中，可以通过 BFS 求解.

在这里你的图表是 G=(V,E) 其中

• V = { 矩阵中的所有单元格}
• E= { (v1,v2) |可以从单元格 v1 移动到单元格 v2 }

请注意，您的方法是 DFS 的变体, 使用附加数据 [dp 数组]

---

更高级的方法是 bi-directional搜索或A* algorithm (使用 manhattan distances 作为启发式函数)。

---

bfs伪代码:

BFS(source,destination):
  visited <- {} //empty dictionary
  queue <- new queue
  queue.add (source)
  visited.add(source,null)
  while (! queue.isEmpty()):
      v <- queue.pop()
      if v == destination:
         return getPath(visited, v)
      for each edge (v,u):
         if u is not a key in visited:
             visited.add(u,v)
             queue.add(u)

getPath(visited,v):
   list <- new linked list
   while (v != null):
      list.addFirst(v)
      v <- visited.get(v)
   return list

此解决方案的时间复杂度为 O(min{|V|,8^d}) - 其中 d 是最短路径的长度， |V| 是矩阵中的单元格数。