“搜索”是一個宏大的主題，本書通篇都可被稱為“用Python解決經典的搜索問題”。本章將介紹每個程序員都應該知曉的核心搜索算法。別看標題很響亮，但本章內容其實稱不上全面。

2.1　DNA搜索

在計算機軟件中，基因通常會表示為字符A、C、G和T的序列。每個字母代表一種核苷酸（nucleotide），3個核苷酸的組合稱作密碼子（codon）。如圖2-1所示，密碼子的編碼決定了氨基酸的種類，多個氨基酸一起形成了蛋白質（protein）。生物信息學軟件的一個經典任務就是在基因中找到某個特定的密碼子。

 

圖2-1　核苷酸由A、C、G和T之一表示。密碼子由3個核苷酸組成，基因由多個密碼子組成

2.1.1　DNA的存儲方案

核苷酸可以表示為包含4種狀態的簡單類型IntEnum，如代碼清單2-1所示。

代碼清單2-1　dna_search.py

from enum import IntEnum
from typing import Tuple, List

Nucleotide: IntEnum = IntEnum('Nucleotide', ('A', 'C', 'G', 'T'))

Nucleotide的類型是IntEnum，而不僅僅是Enum，因為IntEnum“免費”提供了比較運算符（<、>=等）。為了使要實現的搜索算法能完成這些操作，需要數據類型支持這些運算符。從typing包中導入Tuple和List，是為了獲得類型提示提供的支持。

如代碼清單2-2所示，Codon可以定義為包含3個Nucleotide的元組，Gene可以定義為Codon的列表。

代碼清單2-2　dna_search.py（續）

Codon = Tuple[Nucleotide, Nucleotide, Nucleotide]  # type alias for codons
Gene = List[Codon]  # type alias for genes

注意　盡管稍后需要對Codon進行相互比較，但是此處并不需要為Codon定義顯式地實現了“<”操作符的自定義類，這是因為只要組成元組的元素類型是可比較的，Python就內置支持元組的比較操作。

互聯網上的基因數據通常都是以文件格式提供的，其中包含了代表基因序列中所有核苷酸的超長字符串。下面將為某個虛構的基因定義這樣一個字符串，并將其命名為gene_str，具體代碼如代碼清單2-3所示。

代碼清單2-3　dna_search.py（續）

gene_str: str = "ACGTGGCTCTCTAACGTACGTACGTACGGGGTTTATATATACCCTAGGACTCCCTTT"

這里還需要一個實用函數把str轉換為Gene。具體代碼如代碼清單2-4所示。

代碼清單2-4　dna_search.py（續）

def string_to_gene(s: str) -> Gene:
    gene: Gene = []
    for i in range(0, len(s), 3):
        if (i + 2) >= len(s):  # don't run off end!
           return gene
        #  initialize codon out of three nucleotides
        codon: Codon = (Nucleotide[s[i]], Nucleotide[s[i + 1]], Nucleotide[s[i + 2]])
        gene.Append(codon)  # add codon to gene
    return gene

string_to_gene()遍歷給定的str，把每3個字符轉換為Codon，并將其追加到新建的Gene的末尾。如果該函數發現從正在讀取的s的當前位置開始不夠放下兩個Nucleotide的位置（參見循環中的if語句），就說明已經到達不完整基因的末尾了，于是最后一個或兩個核苷酸就會被跳過。

string_to_gene()可用于把str類型的gene_str轉換為Gene。具體代碼如代碼清單2-5所示。

代碼清單2-5　dna_search.py（續）

my_gene: Gene = string_to_gene(gene_str)

2.1.2　線性搜索

基因需要執行的一項基本操作就是搜索指定的密碼子，目標就是簡單地查找該密碼子是否存在于基因中。

線性搜索（linear search）算法將按照原始數據結構的順序遍歷搜索空間（search space）中的每個元素，直到找到搜索內容或到達數據結構的末尾。其實對搜索而言，線性搜索是最簡單、最自然、最顯而易見的方式。在最壞的情況下，線性搜索將需要遍歷數據結構中的每個元素，因此它的復雜度為O(n)，其中n是數據結構中元素的數量，如圖2-2所示。

 

圖2-2　在最壞情況下，線性搜索將需要遍歷數組的每個元素

線性搜索函數的定義非常簡單。它只需要遍歷數據結構中的每個元素，并檢查每個元素是否與所查找的數據相等。代碼清單2-6所示的代碼就對Gene和Codon定義了這樣一個函數，然后嘗試對my_gene和名為acg和gat的Codon對象調用這個函數。

代碼清單2-6　dna_search.py（續）

def linear_contains(gene: Gene, key_codon: Codon) -> bool:
    for codon in gene:
        if codon == key_codon:
            return True
    return False

acg: Codon = (Nucleotide.A, Nucleotide.C, Nucleotide.G)
gat: Codon = (Nucleotide.G, Nucleotide.A, Nucleotide.T)
print(linear_contains(my_gene, acg))  # True
print(linear_contains(my_gene, gat))  # False

注意　上述函數僅供演示。Python內置的序列類型（list、tuple、range）都已實現了__contains__()方法，這樣就能簡單地用in操作符在其中搜索某個指定的數據項。實際上，in運算符可以與任何已實現__contains__()方法的類型一起使用。例如，執行print(acg in my_gene)語句即可在my_gene中搜索acg并打印出結果。

2.1.3　二分搜索

有一種搜索方法比查看每個元素速度快，但需要提前了解數據結構的順序。如果我們知道某數據結構已經排過序，并且可以通過數據項的索引直接訪問其中的每一個數據項，就可以執行二分搜索（binary search）。根據這一標準，已排序的Python List是二分搜索的理想對象。

二分搜索的原理如下：查看一定范圍內有序元素的中間位置的元素，將其與所查找的元素進行比較，根據比較結果將搜索范圍縮小一半，然后重復上述過程。下面看一個具體的例子。

假定有一個按字母順序排列的單詞List，類似于["cat", "dog", "kangaroo", "llama", "rabbit", "rat", "zebra"]，要查找的單詞是“rat”。

（1）可以確定在這7個單詞的列表中，中間位置的元素為“llama”。

（2）可以確定按字母順序“rat”將排在“llama”之后，因此它一定位于“llama”之后的一半（近似）列表中。（如果在本步中已經找到“rat”，就應該返回它的位置；如果發現所查找的單詞排在當前的中間單詞之前，就可以確信它位于“llama”之前的一半列表中。）

（3）可以對“rat”有可能存在其中的半個列表再次執行第1步和第2步。這半個列表事實上就成了新的目標列表。這些步驟會持續執行下去，直至找到“rat”或者當前搜索范圍中不再包含待查找的元素（意味著該單詞列表中不存在“rat”）。

圖2-3展示了二分搜索的過程。請注意，與線性搜索不同，它不需要搜索每個元素。

 

圖2-3　最壞情況下，二分搜索僅會遍歷lg(n)個列表元素

二分搜索將搜索空間不停地減半，因此它的最壞情況運行時間為O(lg n)。但是這里還有個排序問題。與線性搜索不同，二分搜索需要對有序的數據結構才能進行搜索，而排序是需要時間的。實際上，最好的排序算法也需要O(n lg n)的時間才能完成。如果我們只打算運行一次搜索，并且原數據結構未經排序，那么可能進行線性搜索就比較合理。但如果要進行多次搜索，那么用于排序所付出的時間成本就是值得的，獲得的收益來自每次搜索大幅減少的時間成本。

為基因和密碼子編寫二分搜索函數，與為其他類型的數據編寫搜索函數沒什么區別，因為同為Codon類型的數據可以相互比較，而Gene類型只不過是一個List。具體代碼如代碼清單2-7所示。

代碼清單2-7　dna_search.py（續）

def binary_contains(gene: Gene, key_codon: Codon) -> bool:
    low: int = 0
    high: int = len(gene) - 1
    while low <= high:  # while there is still a search space
        mid: int = (low + high) // 2
        if gene[mid] < key_codon:
            low = mid + 1
        elif gene[mid] > key_codon:
            high = mid - 1
        else:
            return True
    return False

下面就逐行過一遍這個函數。

low: int = 0
high: int = len(gene) - 1

首先看一下包含整個列表（gene）的范圍。

while low <= high:

只要還有可供搜索的列表范圍，搜索就會持續下去。當low大于high時，意味著列表中不再包含需要查看的槽位（slot）了。

mid: int = (low + high) // 2

我們用整除法和在小學就學過的簡單均值公式計算中間位置mid。

if gene[mid] < key_codon:
    low = mid + 1

如果要查找的元素大于當前搜索范圍的中間位置元素，我們就修改下一次循環迭代時要搜索的范圍，方法是將low移到當前中間位置元素后面的位置。下面是把下一次迭代的搜索范圍減半的代碼。

elif gene[mid] > key_codon:
    high = mid - 1

類似地，如果要查找的元素小于中間位置元素之前，就將當前搜索范圍反向減半。

else:
    return True

如果當前查找的元素既不小于也不大于中間位置元素，就表示它就是要找的元素！當然，如果循環迭代完畢，就會返回False，以表明沒有找到，這里就不重現代碼了。

下面可以嘗試用同一份基因數據和密碼子運行函數了，但必須記得先進行排序。具體代碼如代碼清單2-8所示。

代碼清單2-8　dna_search.py（續）

my_sorted_gene: Gene = sorted(my_gene)
print(binary_contains(my_sorted_gene, acg))  # True
print(binary_contains(my_sorted_gene, gat))  # False

提示　可以用Python標準庫中的bisect模塊構建高性能的二分搜索方案。

2.1.4　通用示例

函數linear_contains()和binary_contains()可以廣泛應用于幾乎所有Python序列。以下通用版本與之前的版本幾乎完全相同，只不過有一些名稱和類型提示信息有一些變化。具體代碼如代碼清單2-9所示。

注意　代碼清單2-9中有很多導入的類型。本章后續有很多通用搜索算法都將復用generic_search.py文件，這樣就可以避免導入的麻煩。

注意　在往下繼續之前，需要用pip install typing_extensions或pip3 install typing_extensions安裝typing_extensions模塊，具體命令取決于Python解釋器的配置方式。這里需要通過該模塊獲得Protocol類型，Python后續版本的標準庫中將會包含這個類型（PEP 544已有明確說明）。因此在Python的后續版本中，應該不需要再導入typing_extensions模塊了，并且會用from typing import Protocol替換from typing_extensions import Protocol。

代碼清單2-9　generic_search.py

from __future__ import annotations
from typing import TypeVar, Iterable, Sequence, Generic, List, Callable, Set, Deque, 
    Dict, Any, Optional
from typing_extensions import Protocol
from heapq import heappush, heappop

T = TypeVar('T')

def linear_contains(iterable: Iterable[T], key: T) -> bool:
    for item in iterable:
        if item == key:
            return True
    return False

C = TypeVar("C", bound="Comparable")

class Comparable(Protocol):
    def __eq__(self, other: Any) -> bool:
       ...
    def __lt__(self: C, other: C) -> bool:
       ...
    def __gt__(self: C, other: C) -> bool:
        return (not self < other) and self != other

    def __le__(self: C, other: C) -> bool:
        return self < other or self == other

    def __ge__(self: C, other: C) -> bool:
        return not self < other

def binary_contains(sequence: Sequence[C], key: C) -> bool:
    low: int = 0
    high: int = len(sequence) - 1
    while low <= high:  # while there is still a search space
        mid: int = (low + high) // 2
        if sequence[mid] < key:
            low = mid + 1
        elif sequence[mid] > key:
            high = mid - 1
        else:
            return True
    return False

if __name__ == "__main__":
    print(linear_contains([1, 5, 15, 15, 15, 15, 20], 5))  # True
    print(binary_contains(["a", "d", "e", "f", "z"], "f"))  # True
    print(binary_contains(["john", "mark", "ronald", "sarah"], "sheila"))  # False

現在可以嘗試搜索其他類型的數據了。這些函數幾乎可以復用于任何Python集合類型。這正是編寫通用代碼的威力。上述例子中唯一的遺憾之處就是為了滿足Python類型提示的要求，必須以Comparable類的形式實現。Comparable是一種實現比較操作符（<、> =等）的類型。在后續的Python版本中，應該有一種更簡潔的方式來為實現這些常見操作符的類型創建類型提示。

2.2　求解迷宮問題

尋找穿過迷宮的路徑類似于計算機科學中的很多常見搜索問題，那么不妨直觀地用查找迷宮路徑來演示廣度優先搜索、深度優先搜索和A*算法吧。

此處的迷宮將是由Cell組成的二維網格。Cell是一個包含str值的枚舉，其中" "表示空白單元格，"X"表示路障單元格。還有其他一些在打印輸出迷宮時供演示用的單元格。具體代碼如代碼清單2-10所示。

代碼清單2-10　maze.py

from enum import Enum
from typing import List, NamedTuple, Callable, Optional
import random
from math import sqrt
from generic_search import dfs, bfs, node_to_path, astar, Node

class Cell(str, Enum):
    EMPTY = " "
    BLOCKED = "X"
    START = "S"
    GOAL = "G"
    PATH = "*"

這里再次用到了很多導入操作。注意，最后一個導入（from generic_search）有幾個還未定義的標識符，此處是為了方便才包含進來的，但在用到之前可以先把它們注釋掉。

還需要有一種表示迷宮中各個位置的方法，只要用NamedTuple即可實現，其屬性表示當前位置的行和列。具體代碼如代碼清單2-11所示。

代碼清單2-11　maze.py（續）

class MazeLocation(NamedTuple):
    row: int
    column: int

2.2.1　生成一個隨機迷宮

Maze類將在內部記錄一個表示其狀態的網格（列表的列表）。還有表示行數、列數、起始位置和目標位置的實例變量，該網格將被隨機填入一些路障單元格。

這里生成的迷宮應該相當地稀疏，以便從給定的起始位置到給定的目標位置的路徑幾乎總是存在（畢竟這里只是為了測試算法）。實際的稀疏度將由迷宮的調用者決定，但這里將給出默認的稀疏度為20%的路障。如果某個隨機數超過了當前sparseness參數給出的閾值，就會簡單地用路障單元格替換空單元格。如果對迷宮中的每個位置都執行上述操作，那么從統計學上說，整個迷宮的稀疏度將近似于給定的sparseness參數。具體代碼如代碼清單2-12所示。

代碼清單2-12　maze.py（續）

class Maze:
    def __init__(self, rows: int = 10, columns: int = 10, sparseness: float = 0.2, start:
     MazeLocation = MazeLocation(0, 0), goal: MazeLocation = MazeLocation(9, 9)) -> None:
       # initialize basic instance variables
       self._rows: int = rows
       self._columns: int = columns
       self.start: MazeLocation = start
       self.goal: MazeLocation = goal
       # fill the grid with empty cells
       self._grid: List[List[Cell]] = [[Cell.EMPTY for c in range(columns)] 
    for r in range(rows)]
        # populate the grid with blocked cells
        self._randomly_fill(rows, columns, sparseness)
        # fill the start and goal locations in
        self._grid[start.row][start.column] = Cell.START
        self._grid[goal.row][goal.column] = Cell.GOAL

    def _randomly_fill(self, rows: int, columns: int, sparseness: float):
        for row in range(rows):
            for column in range(columns):
                if random.uniform(0, 1.0) < sparseness:
                    self._grid[row][column] = Cell.BLOCKED

現在我們有了迷宮，還需要一種把它簡潔地打印到控制臺的方法。輸出的字符應該靠得很近，以便使該迷宮看起來像一個真實的迷宮。具體代碼如代碼清單2-13所示。

代碼清單2-13　maze.py（續）

# return a nicely formatted version of the maze for printing
def __str__(self) -> str:
    output: str = ""
    for row in self._grid:
        output += "".join([c.value for c in row]) + "n"
    return output

然后測試一下上述這些迷宮函數。

maze: Maze = Maze()
print(maze)

2.2.2　迷宮的其他函數

若有一個函數可在搜索過程中檢查我們是否已抵達目標，將會便利很多。換句話說，我們需要檢查搜索已到達的某個MazeLocation是否就是目標位置。于是可以為Maze添加一個方法。具體代碼如代碼清單2-14所示。

代碼清單2-14　maze.py（續）

def goal_test(self, ml: MazeLocation) -> bool:
    return ml == self.goal

怎樣才能在迷宮內移動呢？假設我們每次可以從迷宮的給定單元格開始水平和垂直移動一格。根據此規則，successors()函數可以從給定的MazeLocation找到可能到達的下一個位置。但是，每個Maze的successors()函數都會有所差別，因為每個Maze都有不同的尺寸和路障集。因此，代碼清單2-15中把successors()函數定義為Maze的方法。

代碼清單2-15　maze.py（續）

def successors(self, ml: MazeLocation) -> List[MazeLocation]:
    locations: List[MazeLocation] = []
    if ml.row + 1 < self._rows and self._grid[ml.row + 1][ml.column] != Cell.BLOCKED:
        locations.append(MazeLocation(ml.row + 1, ml.column))
    if ml.row - 1 >= 0 and self._grid[ml.row - 1][ml.column] != Cell.BLOCKED:
        locations.append(MazeLocation(ml.row - 1, ml.column))
    if ml.column + 1 < self._columns and self._grid[ml.row][ml.column + 1] != Cell.BLOCKED:
        locations.append(MazeLocation(ml.row, ml.column + 1))
    if ml.column - 1 >= 0 and self._grid[ml.row][ml.column - 1] != Cell.BLOCKED:
        locations.append(MazeLocation(ml.row, ml.column - 1))
    return locations

successors()只是簡單地檢查Maze中MazeLocation的上方、下方、右側和左側，查看是否能找到從該位置過去的空白單元格。它還會避開檢查Maze邊緣之外的位置。每個找到的可達MazeLocation都會被放入一個列表，該列表將被最終返回給調用者。

2.2.3　深度優先搜索

深度優先搜索（depth-first search，DFS）正如其名，搜索會盡可能地深入，如果碰到障礙就會回溯到最后一次的決策位置。下面將實現一個通用的深度優先搜索算法，它可以求解上述迷宮問題，還可以給其他問題復用。圖2-4演示了迷宮中正在進行的深度優先搜索。

 

圖2-4　在深度優先搜索中，搜索沿著不斷深入的路徑前進，直至遇到障礙并必須回溯到最后的決策位置

1．棧

深度優先搜索算法依賴棧這種數據結構。（如果你已讀過了第1章中有關棧的內容，完全可以跳過本小節的內容。）棧是一種按照后進先出（LIFO）原則操作的數據結構。不妨想象一疊紙，頂部的最后一張紙是從棧中取出的第一張紙。通常，棧可以基于更簡單的數據結構（如列表）來實現。這里的棧將基于Python的list類型來實現。

棧一般至少應包含兩種操作：

• push()——在棧頂部放入一個數據項；
• pop()——移除棧頂部的數據項并將其返回。

下面將實現這兩個操作，以及用于檢查棧中是否還存在數據項的empty屬性，具體代碼如代碼清單2-16所示。這些關于棧的代碼將會被添加到本章之前用過的generic_search.py文件中?，F在我們已經完成了所有必要的導入。

代碼清單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

星號代表深度優先搜索函數找到的路徑，從起點至目標點。請記住，因為每一個迷宮都是隨機生成的，所以并非每個迷宮都有解。

2.2.4　廣度優先搜索

或許大家會注意到，用深度優先遍歷找到的迷宮路徑似乎有點兒不盡如人意，通常它們不是最短路徑。廣度優先搜索（breadth-first search，BFS）則總是會查找最短路徑，它從起始狀態開始由近到遠，在搜索時的每次迭代中依次查找每一層節點。針對某些問題，深度優先搜索可能會比廣度優先搜索更快找到解，反之亦然。因此，要在兩者之間進行選擇，有時就是在可能快速求解與確定找到最短路徑（如果存在）之間做出權衡。圖2-5演示了迷宮中正在進行的廣度優先搜索。

 

圖2-5　在廣度優先搜索過程中，離起點位置最近的元素最先被搜索

深度優先搜索有時會比廣度優先搜索更快地返回結果，要想理解其中的原因，不妨想象一下在洋蔥的一層皮上尋找標記。采用深度優先策略的搜索者可以把小刀插入洋蔥的中心并隨意檢查切出的塊。如果標記所在的層剛好鄰近切出的塊，那么就有可能比采用廣度優先策略的搜索者更快地找到它，廣度優先策略的搜索者會費勁地每次“剝一層洋蔥皮”。

為了更好地理解為什么廣度優先搜索始終都會找出最短路徑（如果存在的話），可以考慮一下要找到波士頓和紐約之間停靠車站數最少的火車路徑。如果不斷朝同一個方向前進并在遇到死路時進行回溯（如同深度優先搜索），就有可能在回到紐約之前先找到一條通往西雅圖的路線。但在廣度優先搜索時，首先會檢查距離波士頓1站路的所有車站，然后檢查距離波士頓2站路的所有車站，再檢查距離波士頓3站路的所有車站，一直持續至找到紐約為止。因此在找到紐約時，就能知道已找到了車站數最少的路線，因為離波士頓較近的所有車站都已經查看過了，且其中沒有紐約。

1．隊列

實現BFS需要用到名為隊列（queue）的數據結構。棧是LIFO，而隊列是FIFO（先進先出）。隊列就像是排隊使用洗手間的一隊人。第一個進入隊列的人可以先進入洗手間。隊列至少具有與棧類似的push()方法和pop()方法。實際上，Queue的實現（底層由Python的deque支持）幾乎與Stack的實現完全相同，只有一點兒變化，即從_container的左端而不是右端移除元素，并用deque替換了list。這里用“左”來代表底層存儲結構的起始位置。左端的元素是在deque中停留時間最長的元素（依到達時間而定），所以它們是首先彈出的元素。具體代碼如代碼清單2-22所示。

代碼清單2-22　generic_search.py（續）

class Queue(Generic[T]):
    def __init__(self) -> None:
         self._container: Deque[T] = Deque()

    @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.popleft()  # FIFO

    def __repr__(self) -> str:
        return repr(self._container)

提示　為什么Queue的實現要用deque作為其底層存儲結構，而Stack的實現則使用list作為其底層存儲結構呢？這與彈出數據的位置有關。在棧中，是右側壓入右側彈出。在隊列中，也是右側壓入，但是從左側彈出。Python的list數據結構從右側彈出的效率較高，但從左側彈出則不然。deque則從兩側都能夠高效地彈出數據。因此，在deque上有一個名為popleft()的內置方法，但在list上則沒有與其等效的方法。當然可以找到其他方法來用list作為隊列的底層存儲結構，但效率會比較低。在deque上從左側彈出數據的操作復雜度為O(1)，而在list上則為O(n)。在用list的時候，從左側彈出數據后，每個后續元素都必須向左移動一個位置，效率也就降低了。

2．BFS算法

廣度優先搜索的算法與深度優先搜索的算法驚人地一致，只是frontier由棧變成了隊列。把frontier由棧改為隊列會改變對狀態進行搜索的順序，并確保離起點狀態最近的狀態最先被搜索到。具體代碼如代碼清單2-23所示。

代碼清單2-23　generic_search.py（續）

def bfs(initial: T, goal_test: Callable[[T], bool], successors: Callable[[T], List[T]]) 
 -> Optional[Node[T]]:
    # frontier is where we've yet to go
    frontier: Queue[Node[T]] = Queue()
    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

運行一下bfs()，就會看到它總會找到當前迷宮的最短路徑。在if __name__ == "__main__"部分中，在之前的測試代碼后面加入代碼清單2-24所示的語句，以便能對同一個迷宮對比兩種算法的結果。

代碼清單2-24　maze.py（續）

# Test BFS
solution2: Optional[Node[MazeLocation]] = bfs(m.start, m.goal_test, m.successors)
if solution2 is None:
    print("No solution found using breadth-first search!")
else:
    path2: List[MazeLocation] = node_to_path(solution2)
    m.mark(path2)
    print(m)
    m.clear(path2)

令人驚訝的是，算法可以保持不變，只需修改其訪問的數據結構即可得到完全不同的結果。以下是在之前名為dfs()的同一個迷宮上調用bfs()的結果。請注意，用星號標記出來的從起點到目標點的路徑比上一個示例中的路徑更為直接。

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

2.2.5　A*搜索

給洋蔥層層剝皮可能會非常耗時，廣度優先搜索正是如此。和BFS一樣，A*搜索旨在找到從起點狀態到目標狀態的最短路徑。與以上BFS的實現不同，A*搜索將結合運用代價函數和啟發函數，把搜索集中到最有可能快速抵達目標的路徑上。

代價函數g(n) 會檢查抵達指定狀態的成本。在求解迷宮的場景中，成本是指之前已經走過多少步才到達當前狀態。啟發式信息計算函數h(n) 則給出了從當前狀態到目標狀態的成本估算?？梢宰C明，如果h(n)是一個可接受的啟發式信息（admissible heuristic），那么找到的最終路徑將是最優解?？山邮艿膯l式信息永遠不會高估抵達目標的成本。在二維平面上，直線距離啟發式信息就是一個例子，因為直線總是最短的路徑[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()將獲?。╟apture）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

本文摘自《算法精粹：經典計算機科學問題的Python實現》