启发式搜索-Heuristically-Search-贪婪最佳优先搜索和A搜索
启发式搜索 (Heuristically Search)-【贪婪最佳优先搜索】和【A*搜索】
搜索是人工智能里面研究的一个核心问题，像强化学习其本质我也是理解为一种搜索算法，不过其用了一些值函数近似的方法，并做了进一步改良，使其功能更加强大。近些年来也有非常多学术研究者慢慢开始将两者融汇贯通发顶会了。比如像
Goog
的
planet
，
Muzero
以及将熵用于蒙特卡洛树搜索中平衡探索和利用的关系等等。
启发式搜索
启发式搜索( Heuristically Search )又称为有信息搜索( Informed Search )，它是 利用问题拥有的启发信息来引导搜索 ，达到减少搜索范围、降低问题复杂度的目的，这种利用启发信息的搜索过程称为启发式搜索。其代表算法为：贪婪最佳优先搜索( Greedy best-first search )和
A ∗ A^{*}
A
∗ 搜索。
人工智能中大量的问题都可以被描述为：在 给定海量信息源 以及 一些约束条件 和 额外信息 ，我们需要找到 问题所对应的答案 。
问题的答案就在海量的信息源里面，关键就在于如何快速从信息源中学得模式，找到问题与答案的对应关系。这也是当今人工智能算法所研究的核心，越好的算法能够越快地找到对应的模式，找到更精准的模式关系，使其具备更强大的泛化能力。
问题描述
我们以寻找最优路径这个问题为例，如下图所示：
我们需要寻找到
Arad
到
Bucharest
这两个城市之间的一条最短路径。这里所谓的最短路径是一个泛称，依据具体问题本身而做相应地调整。比如时间最短、油耗最少、或者自定义函数做用户体验最佳等等。在本问题中指实际的距离。
模型建立
为了这个通俗的问题能够转化为算法可求解的问题，我们需要对这个问题建立一个基本的数学模型。大致定义如下五个变量：
- 状态 ：
在上述问题中，我们将每一个城市称之为一个状态。从起始城市转移到目标城市的过程就是从初始状态转移到终止状态的过程。
- 动作 ：
我们将从当前时刻转移到下一时刻所处的状态的操作称之为动作。在搜索算法中动作一般都是离散的。
- 状态转移 ：
从当前状态转移到下一时刻的状态我们称之为状态转移。有些城市之间不存在直接的连线，所以他们之间不存在状态转移。
- 路径 ：
路径是一系列状态的集合，对于这个问题而言就是从
Arad
到
Bucharest
所形成的一系列状态转移后得到的状态集合。
- 测试目标 ：
测试目标用于评估当前状态是否为所求解的目标状态。
Greedy Best-First Search
贪婪最佳优先搜索需要在搜索过程中利用所求解问题相关的辅助信息，这里给出的
辅助信息
为：任意一个城市与
Bucharest
之间的直线距离。辅助信息必须是所求解问题以外的信息，不能是这个最短路径是啥。
除此之外在启发式搜索中我们还需要定义两个函数：
- 评价函数( evaluation function )
评价函数
f ( n ) f(n)
f
(
n
) 描述的是从当前节点
n n
n 出发，根据评价函数来选择后续节点。这个评价函数就是怎么选择动作。
- 启发函数( heuristic function )
启发函数
h ( n ) h(n)
h
(
n
) 描述的是从计算节点
n n
n 到目标节点之间所形成路径的最小代价值。这里将两点之间的直线距离作为启发函数。
**在贪婪最佳优先搜索算法里面，评价函数
f ( n ) f(n)
f
(
n
) 等于启发函数
h ( n ) h(n)
h
(
n
)** 。
- 举例 ：
从
Arad
开始，与其相邻的有三个城市，将其扩展得到(b)，依据评价函数，也就是启发函数选择
Sibiu
，再将
Sibiu
展开依次进行下去即可。
- 贪婪最佳优先搜索的不足 ：
贪婪最佳优先搜索不是最优的 。经过
Sibiu到Fagaras到Bucharest的路径(99+211 = 310)比经过Rimnicu Vilces到Pitesti到Bucharest的路径(80+97+101 = 278 )要长32公里。启发函数代价最小化这一目标会对错误的起点比较敏感 。考虑从
Iasi到Fagaras的问题，由启发式建议须先扩展Neamt，就是因为其离Fagaras最近，导致其启发函数会较小，但是这是一条存在死循环路径。贪婪最佳优先搜索也是不完备的 。所谓不完备指的是它可能沿着一条无限的路径走下去而不回来做其他的选择尝试，因此无法找到最佳路径。
在最坏的情况下，贪婪最佳优先搜索的时间复杂度和空间复杂度都是
O ( b m ) O(b^{m})
O
(
b
m
) (这个就理解成计算机要循环迭代多少次吧)，其中
b b
b 是节点的分支因子数目、
m m
m 是搜索空间的最大深度。
A ∗ A^{*} A ∗ 算法
我们来回顾一下上述问题用贪婪最佳优先搜索存在问题的根本原因是什么：就是因为它的启发函数设计地不好，它启发函数取的是城市之间的直线距离，和实际的道路会有偏差，导致直线上这个方向是没有路的。由此我们需要提出一个更好的启发函数。
A ∗ A^{*}
A
∗ 算法就这么被提出来了。
A ∗ A^{*} A ∗ 算法-启发函数
在
A ∗ A^{*}
A
∗ 算法里面，其评价函数由两部分组成，定义如下：
f ( n )
g ( n ) + h ( n ) f(n)=g(n)+h(n)
f
(
n
)
=
g
(
n
)
h
(
n
)
g ( n ) g(n)
g
(
n
) 表示的是从 起始节点到当前的节点
n n
n 的开销的代价值；
h ( n ) h(n)
h
(
n
) 表示 **从当前节点
n n
n 到目标节点** 路径中所估算的最小开销代价值。
由此我们可以知道，评估函数
f ( n ) f(n)
f
(
n
) 是由当前最小开销代价
g ( n ) g(n)
g
(
n
) ，与后续最小开销代价
h ( n ) h(n)
h
(
n
) 的和。因此
f ( n ) f(n)
f
(
n
) 可视为经过节点
n n
n ，具有最小开销代价值的路径。
那在新的评价函数中
A ∗ A^{*}
A
∗ 算法是如何工作的呢？
为了保证
A ∗ A^{*}
A
∗ 算法是最优( optimal )的(最优指的是不存在另外一个解法能得到比
A ∗ A^{*}
A
∗ 算法所求得解法具有 更小开销代价 。)，也即搜索出来的路径是最短路径，需要在启发函数
h ( n ) h(n)
h
(
n
) 上面下点功夫，需要启发函数
h ( n ) h(n)
h
(
n
) 满足两点：1. 可容的 ( admissible heuristic )和2. 一致的 ( consistency ,或者称为单调性)。
- 可容 ：
可容是专门针对启发函数而言的，即启发函数不会过高估计( over-estimate )从节点
n n
n 到目标结点之间 的实际开销代价（即小于等于实际开销）。比如：可将两点之间的直线距离作为启发函数，从而保证其不会过高估计，保证其可容性。
- 一致性 ：
假设节点
n n
n 的后续节点是
n ′ n^{'}
n
′ ，则从
n n
n 到目标节点之间的开销代价一定小于从
n n
n 到
n ′ n^{'}
n
′ 的开销再加上从
n ′ n^{'}
n
′ 到目标节点之间的开销。如果用数学公式表达的话如下所示：
h ( n ) ≤ c ( n , a , n ′ ) + h ( n ′ ) h(n) \leq c(n,a,n^{’}) + h(n^{’})
h
(
n
)
≤
c
(
n
,
a
,
n
′
)
h
(
n
′
)
其中的
c ( n , a , n ′ ) c(n,a,n^{’})
c
(
n
,
a
,
n
′
) 指的是经过行动
a a
a 所抵达后续节点
n ′ n^{'}
n
′ 与之前节点
n n
n 之间的开销代价。
举例
仍然从
Arad
到
Bucharest
为例，我们用
A ∗ A^{*}
A
∗ 来寻找出这段距离。这里的评估函数
f ( n ) f(n)
f
(
n
) 由当前最小开销代价
g ( n ) g(n)
g
(
n
) 与后续最小开销代价
h ( n ) h(n)
h
(
n
)
两部分组成。
Arad
与三个城市相邻，运用评估函数，选中
Sibiu
，之后再依次展开即可得到上图。
到这里的话，其实就已经知道了整个
A ∗ A^{*}
A
∗ 算法的工作流程，如果需要进一步了解相关知识以下知识点仅作参考：
Tree-search
的
A ∗ A^{*}
A
∗ 算法中，如果启发函数
h ( n ) h(n)
h
(
n
) 是可容的，则
A ∗ A^{*}
A
∗
算法是最优的和完备的；在
Graph-search
的
A ∗ A^{*}
A
∗ 算法中，如果启发函数
h ( n ) h(n)
h
(
n
) 是一致的，
A ∗ A^{*}
A
∗ 算法是最优的。
如果函数满足一致性条件，则一定满足可容条件；反之不然。
直线最短距离函数既是可容的，也是一致的。
如果
h ( n ) h(n)
h
(
n
) 是一致的(单调的)，那么
f ( n ) f(n)
f
(
n
) 一定是非递减的( non-decreasing )。
f ( n ′ )
g ( n ′ ) + h ( n ′ )
g ( n ) + c ( n , a , n ′ ) + h ( n ′ ) ≥ g ( n ) + h ( n )
f ( n ) f(n^{’})=g(n^{’})+h(n^{’})=g(n)+c(n,a,n^{’})+h(n^{’}) \geq g(n) + h(n) = f(n)
f
(
n
′
)
=
g
(
n
′
)
h
(
n
′
)
=
g
(
n
)
c
(
n
,
a
,
n
′
)
h
(
n
′
)
≥
g
(
n
)
h
(
n
)
=
f
(
n
)
参考资料
如果对这方面感兴趣的同学，进阶可参考如下：
我的 微信公众号名称 ：小小何先生
公众号介绍 ：主要研究分享深度学习、机器博弈、强化学习等相关内容！期待您的关注，欢迎一起学习交流进步！