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

2.1　DNA搜索

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

 

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

2.1.1　DNA的存儲方案

核苷酸可以表示為包含4種狀態(tài)的簡單類型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“免費”提供了比較運(yùn)算符（<、>=等）。為了使要實現(xiàn)的搜索算法能完成這些操作，需要數(shù)據(jù)類型支持這些運(yùn)算符。從typing包中導(dǎo)入Tuple和List，是為了獲得類型提示提供的支持。

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

代碼清單2-2　dna_search.py（續(xù)）

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

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

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

代碼清單2-3　dna_search.py（續(xù)）

gene_str: str = "ACGTGGCTCTCTAACGTACGTACGTACGGGGTTTATATATACCCTAGGACTCCCTTT"

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

代碼清單2-4　dna_search.py（續(xù)）

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個字符轉(zhuǎn)換為Codon，并將其追加到新建的Gene的末尾。如果該函數(shù)發(fā)現(xiàn)從正在讀取的s的當(dāng)前位置開始不夠放下兩個Nucleotide的位置（參見循環(huán)中的if語句），就說明已經(jīng)到達(dá)不完整基因的末尾了，于是最后一個或兩個核苷酸就會被跳過。

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

代碼清單2-5　dna_search.py（續(xù)）

my_gene: Gene = string_to_gene(gene_str)

2.1.2　線性搜索

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

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

 

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

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

代碼清單2-6　dna_search.py（續(xù)）

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

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

2.1.3　二分搜索

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

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

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

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

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

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

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

 

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

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

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

代碼清單2-7　dna_search.py（續(xù)）

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

下面就逐行過一遍這個函數(shù)。

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

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

while low <= high:

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

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

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

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

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

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

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

else:
    return True

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

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

代碼清單2-8　dna_search.py（續(xù)）

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

提示　可以用Python標(biāo)準(zhǔn)庫中的bisect模塊構(gòu)建高性能的二分搜索方案。

2.1.4　通用示例

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

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

注意　在往下繼續(xù)之前，需要用pip install typing_extensions或pip3 install typing_extensions安裝typing_extensions模塊，具體命令取決于Python解釋器的配置方式。這里需要通過該模塊獲得Protocol類型，Python后續(xù)版本的標(biāo)準(zhǔn)庫中將會包含這個類型（PEP 544已有明確說明）。因此在Python的后續(xù)版本中，應(yīng)該不需要再導(dǎo)入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

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

2.2　求解迷宮問題

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

此處的迷宮將是由Cell組成的二維網(wǎng)格。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 = "*"

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

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

代碼清單2-11　maze.py（續(xù)）

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

2.2.1　生成一個隨機(jī)迷宮

Maze類將在內(nèi)部記錄一個表示其狀態(tài)的網(wǎng)格（列表的列表）。還有表示行數(shù)、列數(shù)、起始位置和目標(biāo)位置的實例變量，該網(wǎng)格將被隨機(jī)填入一些路障單元格。

這里生成的迷宮應(yīng)該相當(dāng)?shù)叵∈瑁员銖慕o定的起始位置到給定的目標(biāo)位置的路徑幾乎總是存在（畢竟這里只是為了測試算法）。實際的稀疏度將由迷宮的調(diào)用者決定，但這里將給出默認(rèn)的稀疏度為20%的路障。如果某個隨機(jī)數(shù)超過了當(dāng)前sparseness參數(shù)給出的閾值，就會簡單地用路障單元格替換空單元格。如果對迷宮中的每個位置都執(zhí)行上述操作，那么從統(tǒng)計學(xué)上說，整個迷宮的稀疏度將近似于給定的sparseness參數(shù)。具體代碼如代碼清單2-12所示。

代碼清單2-12　maze.py（續(xù)）

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

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

代碼清單2-13　maze.py（續(xù)）

# 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

然后測試一下上述這些迷宮函數(shù)。

maze: Maze = Maze()
print(maze)

2.2.2　迷宮的其他函數(shù)

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

代碼清單2-14　maze.py（續(xù)）

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

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

代碼清單2-15　maze.py（續(xù)）

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的上方、下方、右側(cè)和左側(cè)，查看是否能找到從該位置過去的空白單元格。它還會避開檢查Maze邊緣之外的位置。每個找到的可達(dá)MazeLocation都會被放入一個列表，該列表將被最終返回給調(diào)用者。

2.2.3　深度優(yōu)先搜索

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

 

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

1．棧

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

棧一般至少應(yīng)包含兩種操作：

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

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

代碼清單2-16　generic_search.py（續(xù)）

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實現(xiàn)棧十分地簡單，只需一直在其右端添加數(shù)據(jù)項，并且始終從其最右端移除數(shù)據(jù)項。如果List中不再包含任何數(shù)據(jù)項，則list的pop()方法將會調(diào)用失敗。因此如果Stack為空，則Stack的pop()方法同樣也會失敗。

2．DFS算法

在開始實現(xiàn)DFS算法之前，還需要來點兒花絮。這里需要一個Node類，用于在搜索時記錄從一種狀態(tài)到另一種狀態(tài)（或從一個位置到另一個位置）的過程。不妨把Node視為對狀態(tài)的封裝。在求解迷宮問題時，這些狀態(tài)就是MazeLocation類型。Node將被稱作來自其parent的狀態(tài)。Node類還會包含cost和heuristic屬性，并實現(xiàn)了__lt__()方法，因此稍后在A*算法中能夠得以復(fù)用。具體代碼如代碼清單2-17所示。

代碼清單2-17　generic_search.py（續(xù)）

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類型表示，參數(shù)化類型的值可以被變量引用，或變量可以引用None。

提示　在文件頂部，from __future__ import annotations允許Node在其方法的類型提示中引用自身。若沒有這句話，就需要把類型提示放入引號作為字符串來使用（如'Node'）。在以后的Python的版本中，將不必導(dǎo)入annotations了。要獲得更多信息，請參閱PEP 563“注釋的延遲評估”（Postponed Evaluation of Annotations）。

深度優(yōu)先搜索過程中需要記錄兩種數(shù)據(jù)結(jié)構(gòu)：當(dāng)前要搜索的狀態(tài)棧（或“位置”），這里名為frontier；已搜索的狀態(tài)集，這里名為explored。只要在frontier內(nèi)還有狀態(tài)需要訪問，DFS就將持續(xù)檢查該狀態(tài)是否達(dá)到目標(biāo)（如果某個狀態(tài)已達(dá)到目標(biāo)，則DFS將停止運(yùn)行并將其返回）并把將要訪問的狀態(tài)添加到frontier中。它還會把已搜索的每個狀態(tài)都打上標(biāo)記explored，使得搜索不會陷入原地循環(huán)，不會再回到先前已訪問的狀態(tài)。如果frontier為空，則意味著沒有要搜索的地方了。具體代碼如代碼清單2-18所示。

代碼清單2-18　generic_search.py（續(xù)）

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()執(zhí)行成功，則返回封裝了目標(biāo)狀態(tài)的Node。從該Node開始，利用parent屬性向前遍歷，即可重現(xiàn)由起點到目標(biāo)點的路徑。具體代碼如代碼清單2-19所示。

代碼清單2-19　generic_search.py（續(xù)）

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

為了便于顯示，如果在迷宮上標(biāo)上搜索成功的路徑、起點狀態(tài)和目標(biāo)狀態(tài)，就很有意義了。若能移除一條路徑以便對同一個迷宮嘗試不同的搜索算法，也是很有意義的事情。因此應(yīng)該在maze.py的Maze類中添加代碼清單2-20所示的兩個方法。

代碼清單2-20　maze.py（續(xù)）

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

本節(jié)內(nèi)容有點多了，現(xiàn)在終于可以求解迷宮了。具體代碼如代碼清單2-21所示。

代碼清單2-21　maze.py（續(xù)）

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

星號代表深度優(yōu)先搜索函數(shù)找到的路徑，從起點至目標(biāo)點。請記住，因為每一個迷宮都是隨機(jī)生成的，所以并非每個迷宮都有解。

2.2.4　廣度優(yōu)先搜索

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

 

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

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

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

1．隊列

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

代碼清單2-22　generic_search.py（續(xù)）

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的實現(xiàn)要用deque作為其底層存儲結(jié)構(gòu)，而Stack的實現(xiàn)則使用list作為其底層存儲結(jié)構(gòu)呢？這與彈出數(shù)據(jù)的位置有關(guān)。在棧中，是右側(cè)壓入右側(cè)彈出。在隊列中，也是右側(cè)壓入，但是從左側(cè)彈出。Python的list數(shù)據(jù)結(jié)構(gòu)從右側(cè)彈出的效率較高，但從左側(cè)彈出則不然。deque則從兩側(cè)都能夠高效地彈出數(shù)據(jù)。因此，在deque上有一個名為popleft()的內(nèi)置方法，但在list上則沒有與其等效的方法。當(dāng)然可以找到其他方法來用list作為隊列的底層存儲結(jié)構(gòu)，但效率會比較低。在deque上從左側(cè)彈出數(shù)據(jù)的操作復(fù)雜度為O(1)，而在list上則為O(n)。在用list的時候，從左側(cè)彈出數(shù)據(jù)后，每個后續(xù)元素都必須向左移動一個位置，效率也就降低了。

2．BFS算法

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

代碼清單2-23　generic_search.py（續(xù)）

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

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

代碼清單2-24　maze.py（續(xù)）

# 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)

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

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

2.2.5　A*搜索

給洋蔥層層剝皮可能會非常耗時，廣度優(yōu)先搜索正是如此。和BFS一樣，A*搜索旨在找到從起點狀態(tài)到目標(biāo)狀態(tài)的最短路徑。與以上BFS的實現(xiàn)不同，A*搜索將結(jié)合運(yùn)用代價函數(shù)和啟發(fā)函數(shù)，把搜索集中到最有可能快速抵達(dá)目標(biāo)的路徑上。

代價函數(shù)g(n) 會檢查抵達(dá)指定狀態(tài)的成本。在求解迷宮的場景中，成本是指之前已經(jīng)走過多少步才到達(dá)當(dāng)前狀態(tài)。啟發(fā)式信息計算函數(shù)h(n) 則給出了從當(dāng)前狀態(tài)到目標(biāo)狀態(tài)的成本估算。可以證明，如果h(n)是一個可接受的啟發(fā)式信息（admissible heuristic），那么找到的最終路徑將是最優(yōu)解。可接受的啟發(fā)式信息永遠(yuǎn)不會高估抵達(dá)目標(biāo)的成本。在二維平面上，直線距離啟發(fā)式信息就是一個例子，因為直線總是最短的路徑[1]。

到達(dá)任一狀態(tài)所需的總成本為f(n)，它只是合并了g(n)和h(n)而已。實際上，f(n) = g(n) + h(n)。當(dāng)從frontier選取要探索的下一個狀態(tài)時，A*搜索將選擇f(n)最低的狀態(tài)，這正是它與BFS和DFS的區(qū)別。

1．優(yōu)先隊列

為了在frontier上選出f(n)最低的狀態(tài)，A*搜索用優(yōu)先隊列（priority queue）作為存儲frontier的數(shù)據(jù)結(jié)構(gòu)。優(yōu)先隊列能使其數(shù)據(jù)元素維持某種內(nèi)部順序，以便使首先彈出的元素始終是優(yōu)先級最高的元素。在本例中，優(yōu)先級最高的數(shù)據(jù)項是f(n)最低的那個。通常這意味著內(nèi)部將會采用二叉堆，使得壓入和彈出操作的復(fù)雜度均為O(lg n)。

Python的標(biāo)準(zhǔn)庫中包含了heappush()函數(shù)和heappop()函數(shù)，這些函數(shù)將讀取一個列表并將其維護(hù)為二叉堆。用這些標(biāo)準(zhǔn)庫函數(shù)構(gòu)建一個很薄的封裝器，即可實現(xiàn)一個優(yōu)先隊列。PriorityQueue類將與Stack類和Queue類很相似，只是修改了push()方法和pop()方法，以便可以利用heappush()和heappop()。具體代碼如代碼清單2-25所示。

代碼清單2-25　generic_search.py（續(xù)）

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)

為了確定某元素相對于其他同類元素的優(yōu)先級，heappush()和heappop()用“<”操作符進(jìn)行比較。這就是之前需要在Node上實現(xiàn)__lt__()的原因。通過查看相應(yīng)的f(n)即可對Node進(jìn)行相互比較，f(n)只是簡單地把cost屬性和heuristic屬性相加而已。

2．啟發(fā)式信息

啟發(fā)式信息（heuristics）是對問題解決方式的一種直覺[2]。在求解迷宮問題時，啟發(fā)式信息旨在選取下一次搜索的最佳迷宮位置，最終是為了抵達(dá)目標(biāo)。換句話說，這是一種有根據(jù)的猜測，猜測frontier上的哪些節(jié)點最接近目標(biāo)位置。如前所述，如果A*搜索采用的啟發(fā)式信息能夠生成相對準(zhǔn)確的結(jié)果且為可接受的（永遠(yuǎn)不會高估距離），那么A*將會得出最短路徑。追求更短距離的啟發(fā)式信息最終會導(dǎo)致搜索更多的狀態(tài)，而追求接近實際距離（但不會高估，以免不可接受）的啟發(fā)式信息搜索的狀態(tài)會比較少。因此，理想的啟發(fā)式信息應(yīng)該是盡可能接近真實距離，而不會過分高估。

3．歐氏距離

在幾何學(xué)中，兩點之間的最短路徑就是直線。因此在求解迷宮問題時，直線啟發(fā)式信息總是可接受的，這很有道理。由畢達(dá)哥拉斯定理推導(dǎo)出來的歐氏距離（Euclidean distance）表明：

 

。對本節(jié)的迷宮問題而言，x的差相當(dāng)于兩個迷宮位置的列的差， y的差相當(dāng)于行的差。請注意，要回到maze.py中去實現(xiàn)本函數(shù)。具體代碼如代碼清單2-26所示。

代碼清單2-26　maze.py（續(xù)）

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()函數(shù)將返回另一個函數(shù)。類似Python這種支持把函數(shù)視為“一等公民”的編程語言，能夠支持這種有趣的做法。distance()將獲取（capture）euclidean_distance()傳入的goal MazeLocation，“ 獲取”的意思是每次調(diào)用distance()時，distance()都可以引用此變量（持久性）。返回的函數(shù)用到了goal進(jìn)行計算。這種做法可以創(chuàng)建參數(shù)較少的函數(shù)。返回的distance()函數(shù)只用迷宮起始位置作為參數(shù)，并持久地“看到”goal。

圖2-6演示了網(wǎng)格環(huán)境（如同曼哈頓的街道）下的歐氏距離。

 

圖2-6　歐氏距離是從起點到目標(biāo)點的直線距離

4．曼哈頓距離

歐氏距離非常有用，但對于此處的問題（只能朝4個方向中的一個方向移動的迷宮），我們還可以處理得更好。曼哈頓距離（Manhattan distance）源自在曼哈頓的街道上行走，曼哈頓是紐約最著名的行政區(qū)，以網(wǎng)格模式分布。要從曼哈頓的任一地點到另一地點，需要走過一定數(shù)量的橫向街區(qū)和縱向街區(qū)（曼哈頓幾乎不存在對角線的街道）。所謂曼哈頓距離，其實就是獲得兩個迷宮位置之間的行數(shù)差，并將其與列數(shù)差相加而得到。圖2-7演示了曼哈頓距離。

 

圖2-7　曼哈頓距離不涉及對角線。路徑必須沿著水平線或垂直線前進(jìn)

具體代碼如代碼清單2-27所示。

代碼清單2-27　maze.py（續(xù)）

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

因為這種啟發(fā)式信息能夠更準(zhǔn)確地契合在迷宮中移動的實際情況（沿垂直和水平方向移動而不是沿對角線移動），所以它比歐氏距離更為接近從迷宮某位置到目標(biāo)位置的實際距離。因此，如果A*搜索與曼哈頓距離組合使用，其遍歷的迷宮狀態(tài)就會比A*搜索與歐氏距離的組合要遍歷的迷宮狀態(tài)要少一些。結(jié)果路徑仍會是最優(yōu)解，因為對于在其中僅允許朝4種方向移動的迷宮而言，曼哈頓距離是可接受的（永遠(yuǎn)不會高估距離）。

5．A*算法

從BFS轉(zhuǎn)為A*搜索，需要進(jìn)行一些小的改動。第1處改動是把frontier從隊列改為優(yōu)先隊列，這樣frontier就會彈出f(n)最低的節(jié)點。第2處改動是把已探索的狀態(tài)集改為字典類型。用了字典將能跟蹤記錄每一個可能被訪問節(jié)點的最低成本（g(n)）。用了啟發(fā)函數(shù)后，如果啟發(fā)計算結(jié)果不一致，則某些節(jié)點可能會被訪問兩次。如果在新的方向上找到節(jié)點的成本比按之前的路線訪問的成本要低，我們將會采用新的路線。

為簡單起見，函數(shù)astar()沒有把代價函數(shù)用作參數(shù)，而只是把在迷宮中的每一跳的成本簡單地視為1。每個新Node都被賦予了由此簡單公式算出的成本值，以及由作為參數(shù)傳給搜索函數(shù)heuristic()的新函數(shù)計算出來的啟發(fā)分值。除這些改動之外，astar()與bfs()極其相似，不妨將它們放在一起做一個比較。具體代碼如代碼清單2-28所示。

代碼清單2-28　generic_search.py（續(xù)）

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

恭喜。到這里為止，不僅迷宮問題的解法介紹完畢，還介紹了一些可供多種不同搜索應(yīng)用程序使用的通用搜索函數(shù)。DFS和BFS適用于小型的數(shù)據(jù)集和狀態(tài)空間，這種情況下的性能并沒那么重要。在某些情況下，DFS的性能會優(yōu)于BFS，但BFS的優(yōu)勢是始終能提供最佳的路徑。有趣的是，BFS和DFS的實現(xiàn)代碼是一樣的，差別僅僅是不用棧而用了隊列。稍微復(fù)雜一點的A*搜索算法會與高質(zhì)量、保證一致性、可接受的啟發(fā)式信息組合，不僅可以提供最佳路徑，而且性能也遠(yuǎn)遠(yuǎn)優(yōu)于BFS。因為這3個函數(shù)都是以通用方式實現(xiàn)的，所以只需要一句import generic_search即可讓幾乎所有搜索空間都能使用它們。

下面用maze.py測試部分中的同一個迷宮對astar()進(jìn)行測試,具體代碼如代碼清單2-29所示。

代碼清單2-29　maze.py（續(xù)）

# 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()也略有不同。因為有了啟發(fā)式信息，astar()立即由對角線走向了目標(biāo)位置。最終它搜索的狀態(tài)將比bfs()更少，從而擁有更高的性能。如果想自行證明這一點，請為每個狀態(tài)添加計數(shù)器。

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

本文摘自《算法精粹：經(jīng)典計算機(jī)科學(xué)問題的Python實現(xiàn)》