使用深度优先搜索的迷宫中的最短距离

Question

给定一个 MxN 矩阵，其中每个元素可以是 'o'、's' 或 'g'（'s' 和 'g'独一无二。只有一个起点和一个终点)。

假设起始单元格 's' 始终位于 (0,0)。

我们想要找到起始单元格 's' 到目标单元格 'g' 之间的最短距离，同时避开障碍物 'o'。

示例：

['s', ' ', ' ', ' ', ' ']
[' ', ' ', 'o', 'o', 'o']
['o', ' ', 'o', ' ', ' ']
[' ', ' ', ' ', 'o', ' ']
[' ', ' ', ' ', 'g', ' ']

从's'到'g'的最短距离是7.

我知道我们可以使用广度优先搜索或hadlock算法轻松解决这个问题。但是，我很难理解为什么我的深度优先搜索 不起作用 .

我正在写Python，我的代码如下。

class Solution:
   :type maze: list of list
   :type start: tuple
   :type end: tuple
   :rtype: int
   def findShortestDistance(self, maze, start, end):
      self.shortest=math.inf

      #set the default value of visited to be False
      self.visited=defaultdict(lambda: False)

      self.maze=maze
      self.rows=len(maze)
      self.cols=len(maze[0])
      self.depthFirstSearch(0,0,0)
      return self.shortest

   def depthFirstSearch(self, i, j, numStep):
      if i<0 or j<0 or i>=self.rows or j>=self.cols:
         return
      elif self.maze[i][j]=='o':
         return
      elif self.maze[i][j]=='g':
         self.shortest=min(self.shortest,numStep)
         return
      elif self.visited[(i,j)]:
         return

      self.visited[(i,j)]=True

      self.depthFirstSearch(i-1,j,numStep+1)
      self.depthFirstSearch(i,j-1,numStep+1)
      self.depthFirstSearch(i,j+1,numStep+1)
      self.depthFirstSearch(i+1,j,numStep+1)

      self.visited[(i,j)]=False

我真的不明白为什么这行不通，但我无法通过这个问题的几个隐藏测试用例。

另外，谁能告诉我这个算法的运行时间？在我看来是指数级的。

Answer 1

嗯，DFS 在这里不是一个好主意，因为您将不断地重新访问相同的子路径，并且还因为您将不得不探索所有可能的路径以找到最短的路径。一般来说，当您遇到重复工作的递归问题时，您应该考虑动态编程。不过，在这种特定情况下，您可以使用 DFS，这实际上与您针对此问题使用标准 DP 解决方案所做的非常相似。

现在关于您的实施的一些说明：

通常要避免突变，尤其是在函数算法中。使用具有副作用的递归函数而不是 return 值有点奇怪，尽管可以说它有助于减小堆栈的大小。
我发现很难计算复杂度。它基本上等于任何长度的有效路径的数量，所以这是相当大的，特别是当障碍物很少时，因为有许多长度大致等于 n*m.
我找不到你的逻辑本身的问题。您确定它不仅仅是在失败的测试中超时吗？

Answer 2

你这个逻辑的问题在于，你将节点标记为未访问增加了不必要的搜索，可以肯定的是，如果A点和Dest之间的最短浴不能长于B 和 Dest 之间通过 A

的最短路径

使用以下内容

class Solution:
   def findShortestDistance(self, maze, start, end):
        self.shortest=math.inf

        #set the default value of visited to be False
        self.visited=defaultdict(lambda: False)

        self.maze=maze
        self.rows=len(maze)
        self.cols=len(maze[0])
        self.depthFirstSearch(0,0,0)
        return self.shortest

   def depthFirstSearch(self, i, j, numStep):
        if i<0 or j<0 or i>=self.rows or j>=self.cols:
            return
        elif self.maze[i][j]=='o':
            return
        elif self.maze[i][j]=='g':
            self.shortest=min(self.shortest,numStep)
            return
        elif self.visited[(i,j)]:
            return

        self.visited[(i,j)] = True
        print("{} {}".format(i,j))
        self.depthFirstSearch(i-1,j,numStep+1)
        self.depthFirstSearch(i,j-1,numStep+1)
        self.depthFirstSearch(i,j+1,numStep+1)
        self.depthFirstSearch(i+1,j,numStep+1)

        return

使用深度优先搜索的迷宫中的最短距离

Shortest distance in maze using depth first search

algorithm

depth-first-search

breadth-first-search