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

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

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

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

标签： algorithmdepth-first-searchbreadth-first-search

Answer 1

您的逻辑问题是您将节点标记为未访问会增加不必要的搜索，可以肯定的是，如果点 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