10-深度优先搜索

2.2.3　深度优先搜索

深度优先搜索（depth-first search，DFS）正如其名，搜索会尽可能地深入，如果碰到障碍就会回溯到最后一次的决策位置。下面将实现一个通用的深度优先搜索算法，它可以求解上述迷宫问题，还可以给其他问题复用。图2-4演示了迷宫中正在进行的深度优先搜索。

1．栈

深度优先搜索算法依赖栈这种数据结构。（如果你已读过了第1章中有关栈的内容，完全可以跳过本小节的内容。）栈是一种按照后进先出（LIFO）原则操作的数据结构。不妨想象一叠纸，顶部的最后一张纸是从栈中取出的第一张纸。通常，栈可以基于更简单的数据结构（如列表）来实现。这里的栈将基于Python的 list 类型来实现。

栈一般至少应包含两种操作：

• push() ——在栈顶部放入一个数据项；
• pop() ——移除栈顶部的数据项并将其返回。

下面将实现这两个操作，以及用于检查栈中是否还存在数据项的 empty 属性，具体代码如代码清单2-16所示。这些关于栈的代码将会被添加到本章之前用过的generic_search.py文件中。现在我们已经完成了所有必要的导入。

代码清单2-16　generic_search.py（续）

class Stack(Generic[T]):
    def __init__(self) -> None:
        self._container: List[T] = []
    @property
    def empty(self) -> bool:
        return not self._container  # not is true for empty container
    def push(self, item: T) -> None:
        self._container.append(item)
    def pop(self) -> T:
        return self._container.pop()  # LIFO
    def __repr__(self) -> str:
        return repr(self._container)

用Python的 List 实现栈十分地简单，只需一直在其右端添加数据项，并且始终从其最右端移除数据项。如果 List 中不再包含任何数据项，则 list 的 pop() 方法将会调用失败。因此如果 Stack 为空，则 Stack 的 pop() 方法同样也会失败。

2．DFS算法

在开始实现DFS算法之前，还需要来点儿花絮。这里需要一个 Node 类，用于在搜索时记录从一种状态到另一种状态（或从一个位置到另一个位置）的过程。不妨把 Node 视为对状态的封装。在求解迷宫问题时，这些状态就是 MazeLocation 类型。 Node 将被称作来自其 parent 的状态。 Node 类还会包含 cost 和 heuristic 属性，并实现了 __lt__() 方法，因此稍后在A*算法中能够得以复用。具体代码如代码清单2-17所示。

代码清单2-17　generic_search.py（续）

class Node(Generic[T]):
    def __init__(self, state: T, parent: Optional[Node], cost: float = 0.0, heuristic: 
     float  = 0.0) -> None:
      self.state: T = state
      self.parent: Optional[Node] = parent
      self.cost: float = cost
      self.heuristic: float = heuristic
    def __lt__(self, other: Node) -> bool:
        return (self.cost + self.heuristic) < (other.cost + other.heuristic)

提示 　 Optional 类型表示，参数化类型的值可以被变量引用，或变量可以引用 None 。

提示 　在文件顶部， from __future__ import annotations 允许 Node 在其方法的类型提示中引用自身。若没有这句话，就需要把类型提示放入引号作为字符串来使用（如 'Node' ）。在以后的Python的版本中，将不必导入 annotations 了。要获得更多信息，请参阅PEP 563“注释的延迟评估”（Postponed Evaluation of Annotations）。

深度优先搜索过程中需要记录两种数据结构：当前要搜索的状态栈（或“位置”），这里名为 frontier ；已搜索的状态集，这里名为 explored 。只要在 frontier 内还有状态需要访问，DFS就将持续检查该状态是否达到目标（如果某个状态已达到目标，则DFS将停止运行并将其返回）并把将要访问的状态添加到 frontier 中。它还会把已搜索的每个状态都打上标记 explored ，使得搜索不会陷入原地循环，不会再回到先前已访问的状态。如果 frontier 为空，则意味着没有要搜索的地方了。具体代码如代码清单2-18所示。

代码清单2-18　generic_search.py（续）

def dfs(initial: T, goal_test: Callable[[T], bool], successors: Callable[[T], List[T]]) 
 -> Optional[Node[T]]:
    # frontier is where we've yet to go
    frontier: Stack[Node[T]] = Stack()
    frontier.push(Node(initial, None))
    # explored is where we've been
    explored: Set[T] = {initial}
    # keep going while there is more to explore
    while not frontier.empty:
        current_node: Node[T] = frontier.pop()
        current_state: T = current_node.state
        # if we found the goal, we're done
        if goal_test(current_state):
            return current_node
        # check where we can go next and haven't explored
        for child in successors(current_state):
            if child in explored:  # skip children we already explored
            continue
        explored.add(child)
        frontier.push(Node(child, current_node))
    return None  # went through everything and never found goal

如果 dfs() 执行成功，则返回封装了目标状态的 Node 。从该 Node 开始，利用 parent 属性向前遍历，即可重现由起点到目标点的路径。具体代码如代码清单2-19所示。

代码清单2-19　generic_search.py（续）

def node_to_path(node:Node[T]) -> List[T]:
    path: List[T] = [node.state]
    # work backwards from end to front
    while node.parent is not None:
        node = node.parent
        path.append(node.state)
    path.reverse()
    return path

为了便于显示，如果在迷宫上标上搜索成功的路径、起点状态和目标状态，就很有意义了。若能移除一条路径以便对同一个迷宫尝试不同的搜索算法，也是很有意义的事情。因此应该在maze.py的 Maze 类中添加代码清单2-20所示的两个方法。

代码清单2-20　maze.py（续）

def mark(self, path: List[MazeLocation]):
    for maze_location in path:
        self._grid[maze_location.row][maze_location.column] = Cell.PATH
    self._grid[self.start.row][self.start.column] = Cell.START
    self._grid[self.goal.row][self.goal.column] = Cell.GOAL
def clear(self, path: List[MazeLocation]):
    for maze_location in path:
        self._grid[maze_location.row][maze_location.column] = Cell.EMPTY
    self._grid[self.start.row][self.start.column] = Cell.START
    self._grid[self.goal.row][self.goal.column] = Cell.GOAL

本节内容有点多了，现在终于可以求解迷宫了。具体代码如代码清单2-21所示。

代码清单2-21　maze.py（续）

if __name__ == "__main__":
    # Test DFS
    m: Maze = Maze()
    print(m)
    solution1: Optional[Node[MazeLocation]] = dfs(m.start, m.goal_test, m.successors)
    if solution1 is None:
        print("No solution found using depth-first search!")
    else:
        path1: List[MazeLocation] = node_to_path(solution1)
        m.mark(path1)
        print(m)
        m.clear(path1)

成功的解将类似于如下形式：

S****X X
 X  *****
       X*
 XX******X
  X*
  X**X
 X  *****
         *
      X  *X
         *G

星号代表深度优先搜索函数找到的路径，从起点至目标点。请记住，因为每一个迷宫都是随机生成的，所以并非每个迷宫都有解。