Z.H.Chen's Blog
0%

Python 中的图：A* 算法

发表于 分类于 ， Valine：
1.4k 2 分钟

1 什么是A*算法

  假设一个走迷宫游戏，我将 A 点定义成起点也就是开始状态，定义 B 为终点也就是结束状态。我们的目标就是找到从 A 走到 B 地最佳路径，如下图所示：

在这里插入图片描述

我们可以将上述的迷宫看做一张图，在简单的情况下（比如这个），生成的图由少量节点和边组成，BFS、DFS 和 Dijkstra 就足够了。然而，在现实生活中，因为我们通常要处理组合复杂性非常大的问题，我们将不得不处理大量的节点和边，而 BFS、DFS 和 Dijkstra 要不可避免地遍历整张图，搜索代价十分巨大。因此，我们必须使用某种意义上的引导算法（启发式算法）。A 算法就是一种启发式算法。与其他图遍历算法不同，A 仅根据其功能在看起来有希望且合理的情况下执行一个步骤。它朝着目标前进，不考虑任何非最佳步骤，所以 A 所搜索出来的路径一定是最优路径。这使得 A 对于人工智能系统非常有用——尤其是在机器学习和游戏开发中，因为这些系统复制了现实世界的场景。

1.1 A* 的基本概念

  A 基于使用 启发式 方法来实现最优性和完整性，是最佳优先算法的一种变体。当搜索算法具有最优性时，这意味着它可以保证找到可能的最佳解决方案。当搜索算法具有完备性时，这意味着如果给定问题的解决方案存在，则该算法保证找到它。
  每次 A 进入一个状态即图中的一个节点，它计算从当前节点移动到所有相邻节点的成本 f(n) ，然后进入具有最低 f(n) 的节点，注意 n 指的是当前节点的邻居节点。计算公式如下：

其中：

  • f(n)：从初始状态经由状态 n 到目标状态的代价估计；
  • g(n)：在状态空间中从初始状态到当前状态 n 的实际代价；
  • h(n)：从当前状态 n 到目标状态的最佳路径的估计代价。

为了能够重建任何路径，我们需要用具有最佳 f(n) 值的相对标记每个节点。这也意味着如果我们重新访问某些节点，我们也必须更新它们的最佳邻居。A* 的效率高度依赖于启发式值h(n)，并且根据问题的类型，我们可能需要使用不同的启发式函数来找到最佳解决方案。。

1.2 启发函数的可接受性和一致性

  如果一个给定的启发式函数从不高估 n 和目标节点之间的实际距离，则 h(n) 是可接受的。因此，对于每个节点 n，适用以下公式：

h*(n) 是 n 和目标节点之间的实际距离。但是，如果函数确实高估了实际距离，但从不超过 d，我们可以肯定地说，该函数产生的解的精度为 d（即它不会高估从开始到结束的最短路径超过 d)。
  如果估计总是小于或等于目标节点 n 和其任何邻居之间的估计距离，加上到达该邻居的估计成本，则给定启发式函数h(n) 是一致的：

如果 h(n) 是一致的，那么我们就知道到任何已经检查过的节点的最佳路径。这意味着这个函数是最优的。

2 Python 实现 A* 算法

  本次实现从零开始，也即先构建一个加权有向图，其次利用 A* 算法寻找图中的某一节点到达另一节点的的最佳路径，其中：

  • 图的存储结构是邻接列表，可参考：Python 中的图：图的存储结构；
  • 为了方便，本次定义的启发函数 h(n) = 1，即任何的当前节点到目标节点的最佳路径的估计代价均为1。

图的构建如下：

1
2
3
adjacency_list = {'A' : [('B', 1), ('C', 3), ('D', 7)],
                  'B' : [('D', 5)],
                  'C' : [('D', 12)]}

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
adjacency_list = {'A' : [('B', 1), ('C', 3), ('D', 7)],
                  'B' : [('D', 5)],
                  'C' : [('D', 12)]}
class Graph() :
    def __init__(self, adjacency):
        self.adjacency = adjacency

    def get_neighbors(self, v):
        return self.adjacency[v]

    def h(self, n):
        H = {'A' : 1,
             'B' : 1,
             'C' : 1,
             'D' : 1}

        return H[n]

    def A_star(self, start, target):
        # 首先说明：下面注释中邻居节点和子节点指的是同一个意思
        # open_list 存的是已访问，但该节点的邻居节点仍未被访问的节点，从 start 节点开始
        # close_list 存的是已访问，且该节点的邻居节点已被访问的节点
        open_list = set(start)
        close_list = set()

        # g 存的是
        g = {}
        g[start] = 0

        # 记录所有节点的父节点
        parents = {}
        parents[start] = start

        while len(open_list) > 0:
            # 当前节点
            n = None

            # 在当前节点的邻居节点中找到 f() 值最低的节点，更新当前节点
            for v in open_list :
                if n == None or g[v] + self.h(v) < g[n] + self.h(n) :
                    n = v

            if n == None :
                print('path does not exists!')
                return None

            # 如果当前节点是目标节点，回溯求得最佳路径。利用 parents
            if n == target :
                path = []
                while parents[n] != n :
                    path.append(n)
                    n = parents[n]

                path.append(start)
                path.reverse()
                best_path = '->'.join(path)
                print(f'the best path of the node {start} to {target} is: {best_path}')
                return path

            # 当前节点的所有邻居节点
            for (m, weight) in self.get_neighbors(n) :
                # 如果没被访问过，添加至 open_list
                if m not in open_list and m not in close_list :
                    open_list.add(m)
                    parents[m] = n
                    # 开始节点到当前节点的邻居节点的代价，为求下一个最佳节点做准备
                    g[m] = g[n] + weight
                # 否则说明 m 节点的父节点是 n 节点的子节点，也是最佳路径中的上一个节点的子节点
                else :
                    # 如果从上一个节点先访问 n 再访问 m 比直接访问 m 更快，则更新父节点和相应的代价
                    if g[m] > g[n] + weight :
                        g[m] = g[n] + weight
                        parents[m] = n
                        # 如果 m 节点位于 closed_list 中，将其移至 open_list
                        if m in close_list :
                            close_list.remove(m)
                            open_list.add(m)

            open_list.remove(n)
            close_list.add(n)

        print('path does not exists!')
        return None

graph = Graph(adjacency_list)
graph.A_star('A', 'D')

代码中有详细注释，便不再讲解。效果如下：
在这里插入图片描述