python - 如何用dfs找到最长的最小跳跃？

Question

我想在这个问题中找到问题的所有最佳路径

The frog's longest Smallest Jump

使用非递归深度优先搜索 (dfs)。基本上每 block 石头都是图的一个顶点，目标顶点到达对岸。

在伪代码中它会像下面这样(使用 dfs 的递归实现)

dfs( currentLocation, visited):
  if currentLocation is opposite bank:
     return (best jump 0, empty path)
  for each rock R not in visited set: // treat opposite bank as a rock here
     (maxHop, path) = dfs( R, visited + currentLocation )
     hop = distance( currentLocation, R)
     path = [R] + path
     if hop > maxHop then maxHop = hop
     # find best hop, path pair  over all R
     if longest < best_jump: 
                 best_jump = longest 
                 best_path = (i, j, k)
return (best hop, best path)

我无法弄清楚如何调整以下 dfs 的非递归 python 实现

def dfs_paths(graph, start, goal):
    stack = [(start, [start])]
    while stack:
        (vertex, path) = stack.pop()
        for next in graph[vertex].difference(set(path)):
            if next == goal:
                yield path + [next]
            else:
                stack.append((next, path + [next]))

考虑跳数长度。此实现中的图形是一个字典，如

 graph = {'A': set(['B', 'C']),
          'B': set(['A', 'D', 'E']),
          'C': set(['A', 'F']),
          'D': set(['B']),
          'E': set(['B', 'F']),
          'F': set(['C', 'E'])}

但在跳跃问题中，我需要用石头和远岸的表示来替换字符。然后我可以通过

paths=list(dfs_paths(graph, start_goal, end_goal))

Answer 1

解决这个问题可能很耗时的原因是，例如，如果您的图表中有一个必须使用的“瓶颈”跳跃，那么如果该跳跃是所有跳跃中最长的，那么您需要打印出所有图表中的可能路径。因此，鉴于此，最好的解决方案可能是首先解决最短可能最长跳跃的长度，然后获取图形并删除长度大于该长度的所有边，然后 DFS 跟踪当前路径，打印出使用受限边集的所有可能路径。这将为您提供所有最佳路径的集合。