我们现实中的很多问题,都可以归纳为图搜索问题,因此它在地图导航,路径规划,游戏AI中得到广泛的应用。而我们在动态规划里面提到的几个问题,其实是图搜索问题的几个特例。这也使得我们有必要单独写一篇介绍这一类问题的算法。

Graph search, also known as graph traversal, refers to the process of visiting each vertex in a graph. Graphs have nodes and edges $G = \lt V, E>$. Edges can be directed or undirected, weighted or unweighted.

本文将以此介绍一下几个算法:

深度优先搜索 Depth First Search

我们以下图为例

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

visited = set() # Set to keep track of visited nodes.

def dfs(visited, graph, node):
    if node not in visited:
        print(node)
        visited.add(node)
        for neighbour in graph[node]:
            dfs(visited, graph, neighbour)

dfs(visited, graph, 'A')

运行的结果是

A
B
D
E
F
C

广度优先搜索 Breadth First Search

同样以上图为例

visited = []   # List to keep track of visited nodes.
queue = []     # Initialize a queue

def bfs(visited, graph, node):
  visited.append(node)
  queue.append(node)

  while queue:
    s = queue.pop(0) 
    print(s) 

    for neighbour in graph[s]:
      if neighbour not in visited:
        visited.append(neighbour)
        queue.append(neighbour)

# Driver Code
bfs(visited, graph, 'A')

运行的结果是

A
B
C
D
E
F

我们很容易发现,深度优先算法找到的路径并不是最短路径,而广度优先回溯出来的的才是。后面介绍的Dijkstra’s Algorithm和A* Algorithm就是基于BFS的算法。

戴克斯特拉算法 Dijkstra’s Algorithm

BFS与其说是找的最短路径,不如说是找的最少途径点,因为graph中所有的edge权值相等。这就导致了其应用的局限性。现实中,比如城市中两地间的交通,距离路况等等,都影响我们的选择,这时候BFS就不适用了。

我们以下图为例:

要求从 $a$ 点出发,找到其他所有点到 $a$ 点的最优路径,我们设$N(x)$ 为 $x$ 的邻点。

  • 数组$D = [\infty, \infty, \infty, \infty, \infty, \infty]$已记录的 $a$ 到 $a,b,c,d,e,f$ 的最优距离;
  • 集合$V = \empty$, 代表已经访问过的节点。
  • 集合$S = \{a\}$, 代表正在访问的节点。
$$\begin{array}{l|l|l} Step & & \\ \hline\hline 1 & State & S = \{a\}, D = [0, \infty, \infty, \infty, \infty, \infty], V = \empty \\ & Update & N(a) = \{b, c\}, D(b) = 10, D(c) = 20 \\ & & V = \{a\}, S = \{b, c\} \\\hline 2 & State & S = \{b, c\}, D = [0, 10, 20, \infty, \infty, \infty], V = \{a\} \\ & Update & N(b) = \{e, d\}, D(e) = D(b) + 10 = 20, D(d)=D(b) + 50 = 60 \\ & & V = \{a, b\}, S = \{c, e, d\} \\\hline 3 & State & S = \{c, e, d\}, D=[0, 10, 20, 60, 20, \infty], V=\{a,b\} \\ & Update & N(c)=\{d, e\}, D(ace)=D(c) + 33 > D(e) \\ & & D(acd) = D(c) + 20 = 40 \lt D(d), D(d)=40 \\ & & V = \{a, b, c\}, S = \{e, d, f\} \\\hline 4 & State & S = \{e, d, f\}, D = [0, 10, 20, 40, 20, \infty], V = \{a, b, c\} \\ & Update & N(e) = \{f\}, D(f) = D(e) + 1 = 21 \\ & & V = \{a, b, c, e\}, S = \{d, f\} \\\hline 5 & State & S = \{d, f\}, D = [0, 10, 20, 40, 20, 21], V = \{a, b, c, e\} \\ & Update & N(d) = \{e, f\}, D(ade) = D(d) + 20 > D(e), D(adf) = D(d) + 2 > D(f) \\ & & S = \{f\} V = \{a, b, c, e, d\} \\\hline 6 & State & S = \{f\}, D = [0, 10, 20, 40, 20, 21], V = \{a, b, c, e, d\} \\ & Update & N(f) = \empty \\ & & V = \{a, b, c, e, d, f\}, S = \empty \\ \end{array}$$
from collections import defaultdict

graph = {
    'a': {'c': 20, 'b': 10},
    'b': {'e': 10, 'd': 50},
    'c': {'e': 33, 'd': 20},
    'd': {'e': 20, 'f': 2},
    'e': {'f': 1},
    'f': {}
}

def dijkstra(g, s):
    D = defaultdict(lambda: float('inf'))
    P = {}
    S = [s]
    V = {}
    D[s] = 0
    
    while len(S) > 0:
        node = S.pop(0)
        for v in g[node]:
            if v not in D or D[node] + g[node][v] < D[v]:
                D[v] = D[node] + g[node][v]
                P[v] = node
            if v not in V:
                S.append(v)
        V[node] = 0
    print(D)
    print(P)

dijkstra(graph, 'a')

A算法 A-Star Algorithm

很显然,随着节点数目的增多,Dijkstra算法需要考察的节点数目从起点层层往外增加。如果平均每个节点的子节点数目为$N$,节点总数为$M$的话,那么算法的平均搜索深度为$O(\log_N M)$,在最深处,需要考察的节点数目为$O(M)$。为了提高其搜索效率,有算法提出从起点和终点同时搜索,这其实相当于给搜索指定了方向。所以更聪明的算法呼之欲出,即本文的主角A*算法。

A* 算法是一种启发式搜索算法,所谓启发式,其实是在评估路径的时候用了一个启发函数$h(x)$,A*算法对节点$x$的评估函数*

$$f(x) = g(x) + h(x)$$

这里 $g(x)$是起点到节点$x$的最优距离,即上文中Dijkstra算法中的$D(x)$, $h(x)$是对节点$x$到目标节点的估算距离。A*算法会优先考察$f(x)$最小的节点。值得注意的是:

  1. 如果$g(x)$, 本算法即为最佳搜索优先算法**BFS**,速度最快,但解不是最优。
  2. 如果$h(x)$, 本算法即为Dijkstra算法,计算的节点最多。
  3. $h(x)$的选取,常用的有欧式距离(L2)和曼哈顿距离(L1)。

因为算法对$h(x)$的需要,这也使得A*更适合在有障碍物的网格类问题中得到应用。

import numpy as np
from collections import defaultdict

class AStar:
    def __init__(self):
        self.H = 30
        self.W = 30
        self.S = (15, 17)
        self.T = (15, 25)
        graph = np.chararray((self.H, self.W))
        graph[:, :] = '.'
        graph[5:25, 20] = 'H'
        graph[5, 10:20] = 'H'
        graph[25, 10:21] = 'H'
        graph[self.S] = 'S'
        graph[self.T] = 'T'
        self.g = graph

    def distance(self, x, y):
        return np.abs(x[0] - y[0]) + np.abs(x[1] - y[1])

    def neighbors(self, node):
        x, y = node
        offset = [(-1, 0), (1, 0), (0, 1), (0, -1)]
        out = []
        for dx, dy in offset:
            ix, iy = x+dx, y+dy
            if 0 <= ix < self.H and 0 <= iy < self.H:
                if self.g[ix, iy].decode('utf-8') != 'H': 
                    out.append((ix, iy))
        return out

    def tostring(self, g=None):
        if g is None:
            g = self.g
        out = ""
        for i in range(self.H):
            out += " ".join([str(x, encoding='utf-8') for x in g[i]])
            out += '\n'
        return out

    def solve(self):
        print("Astar Path Finding")
        print("H standds for wall, S stands for source, T stands for target")
        print(self.tostring())
        D = defaultdict(lambda: float('inf'))
        D[self.S] = 0
        P = {}
        S = {self.S: 0}
        V = {}

        count = 0
        while self.T not in S:
            node = min(S, key=S.get)
            if node == self.T:
                break
            for v in self.neighbors(node):
                if v not in D or D[v] > D[node] + 1:
                    D[v] = D[node] + 1
                    P[v] = node
                    if v not in V:
                        S[v] = D[v] + self.distance(v, self.T)
            V[node] = 0
            del S[node]

        print("Finding path ...")
        print()
        print()
        print('Path found, represented by *')
        gx = np.copy(self.g)
        v = self.T
        while v in P:
            v = P[v]
            gx[v] = '*'
        
        # for k in S: gx[k] = 'O'
        # for k in V: gx[k] = 'X'
        print(self.tostring(gx))
            

s = AStar()
s.solve()

运行的结果如下:

Astar Path Finding
H standds for wall, S stands for source, T stands for target
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . H H H H H H H H H H H . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . H . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . H . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . H . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . H . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . H . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . H . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . H . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . H . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . H . . . . . . . . .
. . . . . . . . . . . . . . . . . S . . H . . . . T . . . .
. . . . . . . . . . . . . . . . . . . . H . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . H . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . H . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . H . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . H . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . H . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . H . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . H . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . H . . . . . . . . .
. . . . . . . . . . H H H H H H H H H H H . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Finding path ...

Path found, represented by *
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . * * * * * * * * * * * * * . . . . . . . .
. . . . . . . . . * H H H H H H H H H H H * . . . . . . . .
. . . . . . . . . * * * * * * * * * . . H * . . . . . . . .
. . . . . . . . . . . . . . . . . * . . H * . . . . . . . .
. . . . . . . . . . . . . . . . . * . . H * . . . . . . . .
. . . . . . . . . . . . . . . . . * . . H * . . . . . . . .
. . . . . . . . . . . . . . . . . * . . H * . . . . . . . .
. . . . . . . . . . . . . . . . . * . . H * . . . . . . . .
. . . . . . . . . . . . . . . . . * . . H * . . . . . . . .
. . . . . . . . . . . . . . . . . * . . H * . . . . . . . .
. . . . . . . . . . . . . . . . . * . . H * . . . . . . . .
. . . . . . . . . . . . . . . . . * . . H * * * * T . . . .
. . . . . . . . . . . . . . . . . . . . H . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . H . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . H . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . H . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . H . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . H . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . H . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . H . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . H . . . . . . . . .
. . . . . . . . . . H H H H H H H H H H H . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .