使用深度优先搜索的迷宫中的最短距离
Shortest distance in maze using depth first search
给定一个 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
我真的不明白为什么这行不通,但我无法通过这个问题的几个隐藏测试用例。
另外,谁能告诉我这个算法的运行时间?在我看来是指数级的。
嗯,DFS 在这里不是一个好主意,因为您将不断地重新访问相同的子路径,并且还因为您将不得不探索所有可能的路径以找到最短的路径。一般来说,当您遇到重复工作的递归问题时,您应该考虑动态编程。不过,在这种特定情况下,您可以使用 DFS,这实际上与您针对此问题使用标准 DP 解决方案所做的非常相似。
现在关于您的实施的一些说明:
- 通常要避免突变,尤其是在函数算法中。使用具有副作用的递归函数而不是 return 值有点奇怪,尽管可以说它有助于减小堆栈的大小。
- 我发现很难计算复杂度。它基本上等于任何长度的有效路径的数量,所以这是相当大的,特别是当障碍物很少时,因为有许多长度大致等于
n*m
. 的路径
- 我找不到你的逻辑本身的问题。您确定它不仅仅是在失败的测试中超时吗?
你这个逻辑的问题在于,你将节点标记为未访问增加了不必要的搜索,可以肯定的是,如果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
给定一个 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
我真的不明白为什么这行不通,但我无法通过这个问题的几个隐藏测试用例。
另外,谁能告诉我这个算法的运行时间?在我看来是指数级的。
嗯,DFS 在这里不是一个好主意,因为您将不断地重新访问相同的子路径,并且还因为您将不得不探索所有可能的路径以找到最短的路径。一般来说,当您遇到重复工作的递归问题时,您应该考虑动态编程。不过,在这种特定情况下,您可以使用 DFS,这实际上与您针对此问题使用标准 DP 解决方案所做的非常相似。
现在关于您的实施的一些说明:
- 通常要避免突变,尤其是在函数算法中。使用具有副作用的递归函数而不是 return 值有点奇怪,尽管可以说它有助于减小堆栈的大小。
- 我发现很难计算复杂度。它基本上等于任何长度的有效路径的数量,所以这是相当大的,特别是当障碍物很少时,因为有许多长度大致等于
n*m
. 的路径
- 我找不到你的逻辑本身的问题。您确定它不仅仅是在失败的测试中超时吗?
你这个逻辑的问题在于,你将节点标记为未访问增加了不必要的搜索,可以肯定的是,如果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