12-A搜索

2.2.5　A*搜索

给洋葱层层剥皮可能会非常耗时，广度优先搜索正是如此。和BFS一样，A搜索旨在找到从起点状态到目标状态的最短路径。与以上BFS的实现不同，A搜索将结合运用代价函数和启发函数，把搜索集中到最有可能快速抵达目标的路径上。

代价函数g(n) 会检查抵达指定状态的成本。在求解迷宫的场景中，成本是指之前已经走过多少步才到达当前状态。启发式信息计算函数h(n) 则给出了从当前状态到目标状态的成本估算。可以证明，如果h(n)是一个可接受的启发式信息（admissible heuristic），那么找到的最终路径将是最优解。可接受的启发式信息永远不会高估抵达目标的成本。在二维平面上，直线距离启发式信息就是一个例子，因为直线总是最短的路径^[1]。

到达任一状态所需的总成本为f(n)，它只是合并了g(n)和h(n)而已。实际上，f(n) = g(n) + h(n)。当从 frontier 选取要探索的下一个状态时，A*搜索将选择f(n)最低的状态，这正是它与BFS和DFS的区别。

1．优先队列

为了在 frontier 上选出f(n)最低的状态，A*搜索用优先队列（priority queue）作为存储 frontier 的数据结构。优先队列能使其数据元素维持某种内部顺序，以便使首先弹出的元素始终是优先级最高的元素。在本例中，优先级最高的数据项是f(n)最低的那个。通常这意味着内部将会采用二叉堆，使得压入和弹出操作的复杂度均为O(lg n)。

Python的标准库中包含了 heappush() 函数和 heappop() 函数，这些函数将读取一个列表并将其维护为二叉堆。用这些标准库函数构建一个很薄的封装器，即可实现一个优先队列。 PriorityQueue 类将与 Stack 类和 Queue 类很相似，只是修改了 push() 方法和 pop() 方法，以便可以利用 heappush() 和 heappop() 。具体代码如代码清单2-25所示。

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

class PriorityQueue(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:
        heappush(self._container, item)  # in by priority
    def pop(self) -> T:
        return heappop(self._container)  # out by priority
    def __repr__(self) -> str:
        return repr(self._container)

为了确定某元素相对于其他同类元素的优先级， heappush() 和 heappop() 用“<”操作符进行比较。这就是之前需要在 Node 上实现 __lt__() 的原因。通过查看相应的f(n)即可对 Node 进行相互比较，f(n)只是简单地把 cost 属性和 heuristic 属性相加而已。

2．启发式信息

启发式信息（heuristics）是对问题解决方式的一种直觉^[2]。在求解迷宫问题时，启发式信息旨在选取下一次搜索的最佳迷宫位置，最终是为了抵达目标。换句话说，这是一种有根据的猜测，猜测 frontier 上的哪些节点最接近目标位置。如前所述，如果A搜索采用的启发式信息能够生成相对准确的结果且为可接受的（永远不会高估距离），那么A将会得出最短路径。追求更短距离的启发式信息最终会导致搜索更多的状态，而追求接近实际距离（但不会高估，以免不可接受）的启发式信息搜索的状态会比较少。因此，理想的启发式信息应该是尽可能接近真实距离，而不会过分高估。

3．欧氏距离

在几何学中，两点之间的最短路径就是直线。因此在求解迷宫问题时，直线启发式信息总是可接受的，这很有道理。由毕达哥拉斯定理推导出来的欧氏距离（Euclidean distance）表明：。对本节的迷宫问题而言，x的差相当于两个迷宫位置的列的差， y的差相当于行的差。请注意，要回到maze.py中去实现本函数。具体代码如代码清单2-26所示。

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

def euclidean_distance(goal: MazeLocation) -> Callable[[MazeLocation], float]:
    def distance(ml: MazeLocation) -> float:
        xdist: int = ml.column - goal.column
        ydist: int = ml.row - goal.row
        return sqrt((xdist * xdist) + (ydist * ydist))
    return distance

euclidean_distance() 函数将返回另一个函数。类似Python这种支持把函数视为“一等公民”的编程语言，能够支持这种有趣的做法。 distance() 将获取（capture） euclidean_distance() 传入的 goal MazeLocation ，“ 获取”的意思是每次调用 distance() 时， distance() 都可以引用此变量（持久性）。返回的函数用到了 goal 进行计算。这种做法可以创建参数较少的函数。返回的 distance() 函数只用迷宫起始位置作为参数，并持久地“看到” goal 。

图2-6演示了网格环境（如同曼哈顿的街道）下的欧氏距离。

图2-6　欧氏距离是从起点到目标点的直线距离

4．曼哈顿距离

欧氏距离非常有用，但对于此处的问题（只能朝4个方向中的一个方向移动的迷宫），我们还可以处理得更好。曼哈顿距离（Manhattan distance）源自在曼哈顿的街道上行走，曼哈顿是纽约最著名的行政区，以网格模式分布。要从曼哈顿的任一地点到另一地点，需要走过一定数量的横向街区和纵向街区（曼哈顿几乎不存在对角线的街道）。所谓曼哈顿距离，其实就是获得两个迷宫位置之间的行数差，并将其与列数差相加而得到。图2-7演示了曼哈顿距离。

图2-7　曼哈顿距离不涉及对角线。路径必须沿着水平线或垂直线前进

具体代码如代码清单2-27所示。

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

def manhattan_distance(goal: MazeLocation) -> Callable[[MazeLocation], float]:
    def distance(ml: MazeLocation) -> float:
        xdist: int = abs(ml.column - goal.column)
        ydist: int = abs(ml.row - goal.row)
        return (xdist + ydist)
    return distance

因为这种启发式信息能够更准确地契合在迷宫中移动的实际情况（沿垂直和水平方向移动而不是沿对角线移动），所以它比欧氏距离更为接近从迷宫某位置到目标位置的实际距离。因此，如果A搜索与曼哈顿距离组合使用，其遍历的迷宫状态就会比A搜索与欧氏距离的组合要遍历的迷宫状态要少一些。结果路径仍会是最优解，因为对于在其中仅允许朝4种方向移动的迷宫而言，曼哈顿距离是可接受的（永远不会高估距离）。

5．A*算法

从BFS转为A*搜索，需要进行一些小的改动。第1处改动是把 frontier 从队列改为优先队列，这样 frontier 就会弹出f(n)最低的节点。第2处改动是把已探索的状态集改为字典类型。用了字典将能跟踪记录每一个可能被访问节点的最低成本（g(n)）。用了启发函数后，如果启发计算结果不一致，则某些节点可能会被访问两次。如果在新的方向上找到节点的成本比按之前的路线访问的成本要低，我们将会采用新的路线。

为简单起见，函数 astar() 没有把代价函数用作参数，而只是把在迷宫中的每一跳的成本简单地视为1。每个新 Node 都被赋予了由此简单公式算出的成本值，以及由作为参数传给搜索函数 heuristic() 的新函数计算出来的启发分值。除这些改动之外， astar() 与 bfs() 极其相似，不妨将它们放在一起做一个比较。具体代码如代码清单2-28所示。

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

def astar(initial: T, goal_test: Callable[[T], bool], successors: Callable[[T],
 List[T]], heuristic: Callable[[T], float]) -> Optional[Node[T]]:
    # frontier is where we've yet to go
    frontier: PriorityQueue[Node[T]] = PriorityQueue()
    frontier.push(Node(initial, None, 0.0, heuristic(initial)))
    # explored is where we've been
    explored: Dict[T, float] = {initial: 0.0}
    # 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):
            # 1 assumes a grid, need a cost function for more sophisticated apps
            new_cost: float = current_node.cost + 1  
            if child not in explored or explored[child] > new_cost:
                explored[child] = new_cost
                frontier.push(Node(child, current_node, new_cost, heuristic(child)))
    return None  # went through everything and never found goal

恭喜。到这里为止，不仅迷宫问题的解法介绍完毕，还介绍了一些可供多种不同搜索应用程序使用的通用搜索函数。DFS和BFS适用于小型的数据集和状态空间，这种情况下的性能并没那么重要。在某些情况下，DFS的性能会优于BFS，但BFS的优势是始终能提供最佳的路径。有趣的是，BFS和DFS的实现代码是一样的，差别仅仅是不用栈而用了队列。稍微复杂一点的A*搜索算法会与高质量、保证一致性、可接受的启发式信息组合，不仅可以提供最佳路径，而且性能也远远优于BFS。因为这3个函数都是以通用方式实现的，所以只需要一句 import generic_search 即可让几乎所有搜索空间都能使用它们。

下面用maze.py测试部分中的同一个迷宫对 astar() 进行测试,具体代码如代码清单2-29所示。

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

# Test A*
distance: Callable[[MazeLocation], float] = manhattan_distance(m.goal)
solution3: Optional[Node[MazeLocation]] = astar(m.start, m.goal_test, m.successors,
 distance)
if solution3 is None:
    print("No solution found using A*!")
else:
    path3: List[MazeLocation] = node_to_path(solution3)
    m.mark(path3)
    print(m)

有趣的是，即便 bfs() 和 astar() 都找到了最佳路径（长度相等），以下的 astar() 输出与 bfs() 也略有不同。因为有了启发式信息， astar() 立即由对角线走向了目标位置。最终它搜索的状态将比 bfs() 更少，从而拥有更高的性能。如果想自行证明这一点，请为每个状态添加计数器。

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