人工智能（9）A×search

人工智能 + 编程 基础学习

欢迎关注，点赞或者转发喔。

如有问题或建议，请公众号留言;

马上到新年了，祝大家新的一年阖家欢乐，诸事顺利。拖了好久的A* search今天来一起聊一聊。下面的分享参考斯坦福大学和中国香港科技大学人工智能讲义。前面一起看过了depth-first search, breadth-first search, dynamic programming, uniform cost search 这四种搜索的方式，并且分享了一些非常简单的demo的原创代码示例。这四种不同的方式，适用情景各不同。比如有这样的一个例子：

假设要从城市1到达城市n，然后再回到城市1，条件是不重复经过任何一个城市。其中从城市i到j的cost是Cij, 这是一个非负的值。这是一个有向图，因为遍历每个城市的时候是有方向的，但每两个城市之间的cost是无向的，也即Cij = Cji. 上面的这四种方式哪种会比较适合这样一个问题。首先，很明显，DFS是一条道走到底，不考虑节点之间的cost，或者说默认节点之间的cost是0，不适合于现在要考虑的问题。BFS考虑的是所有节点之间的cost是一样的，考虑一个节点的子节点的时候要把所有子节点遍历一遍。Dynamic programming 考虑的是非循环图，uniform cost 考虑的所有的cost为非负，这两种方式可以适用于这样一个情形。

STATE

说到底，最重要的一个概念还是state，state是过去的action的集合，并且足够帮助我们寻找将来的最优的action。对于一个search 问题，几个要素一直被反复的讨论：初始状态，每个状态的可能的action，action对应的cost，每一个action之后进入的新的状态，是否是最终状态的判断。我们要做的就是找出从初始状态到达最终状态的最优的路径。

比如下面这样一个例子，

初始状态：1，

步行的动作：从S状态到S+1状态，cost是1，

坐有轨电车：从状态S到2s，cost是2.

终止状态：n。

对于上面的例子，很明显我们可以采用之前讲过的dynamic programming 和 uniform cost search 去处理.那要是反过来，已知动作的序列，求不同动作的cost，这其实是学习的目标。中国有句古话叫做，“透过现象看本质”，其实表达的意思和人工智能中“学习”的过程有异曲同工之妙。

A* search

正向和反向：

Cost(state, action)->(a1,a2,a3,,ak)

(a1,a2,a3,,ak)->cost(state, action)

比如从state 1到state 4，可以有两条不同的序列，分别是：

1 walk 2 tram 4.

1 walk 2 walk 3 walk 4.

如果最终结果的序列是第一种方案，walk和tram 的cost可以分别是3，2，如果是第二种方案，walk和tram的cost可以分别是1和3.当然这不是唯一的。总的来讲，降低真实路径的cost，增加非最优路径的cost，这样一个过程能使得最终的模型拟合我们观察到的方式选择。关于这样学习的过程，我们后面会专门结合structured perceptron 来学习。

我们都知道，在USC中，比较的是离初始状态的“距离” （past cost），在A*搜索中，我们比较的是距离终止状态的“距离” (future cost)。直白一点，跟UCS很像的，我们在选择最优路径的时候倾向于离终止状态近的那些状态。在理想情况下，我们可以选择那些past cost 和 future cost之和最小的那些来作为最优结果，现实情况是我们只能去估计future cost。这也就引入了heuristic function的概念，通常用h(s)来表示估计的s状态的future cost。需要注意的是：

A* search：[Hart/Nilsson/Raphael, 1968],用一句话来总结Asearch的话，就是基于UCS的路径cost修改过的算法。此外，我们见的比较多的一种情况是consistent heuristics，多了两个附加的条件：一是，满足三角形的不等式，也即两边之和大于等于第三边，Cost(s,a) + h(Succ(s,a))>=h(s),在讲UCS的时候，我们提到过，路径的cost要求是非负的，同理，对于Asearch也是一样的要求。

二是，h(终止状态) = 0.

我们假设只有一个终止状态，如果有多个终止状态的话，再创造一个新的状态作为这些终止状态的子状态。Heuristic function需要在0和实际的future cost之间，越接近实际的future cost越好。

性质

对于一个consistent heuristic ，我们肯定能找到一个最小cost的路径，这一点也叫做correctness of A*.

每两个状态之间的路径cost的关系是：修改过的路径的cost = 原来的路径的cost + h(Succ(s,a))-h(s)。

累加之后可以证明，对于S0到SL状态，修改过的路径cost和原来的路径cost有一个关系式：修改过的路径cost = 原来的路径cost + h(SL) – h(S0)。h(SL) =0，并且 h(S0) 是固定的值，是constant，每个点出发都是从S0开始的。也就是对于任意一个状态S，

修改过的cost = 原来的路径cost + h(S) – h(S0), S0 是初始状态。这个公式是计算比较的时候常见的。

并且相比于UCS，可以推导出来A探索的状态是那些 原来路径cost + h(s) 不大于 终止状态的cost 的那些状态。Asearch 可以说是UCS的一种特殊的情况，如果heuristic function是0的话，A* 即是UCS。当heuristic function和实际的future cost相等（unattainable。。）的时候，A* search 只会检索在最短的路径上的那些状态。

通过归纳法可以证明：h(s)

h(s)

第一个不等式，是前面讲过的“三角形不等式”。

第二个不等式是根据初始条件的归纳。

第三个等式是定义。

最后补充一点的是：consistent 的heuristic一定是admissible的，反过来不一定；admissible的heuristic适用于在搜索树算法中，如果扩展到图算法的话，则必须是consistent的heuristic。

来，大家结合一个例子和程序来看一下A的应用。在1010的矩形阵中，有初始和终止结点，坐标分别是（2，5），（8，9），矩形阵中存在“墙壁”，找出从初始点到终止点的最优路径。每一步的cost是不同的，有的设置为1，有的是5.

在现实生活中，A* search 也有很多重要的应用，比如北美一条货运铁路网的修建，应用了该算法。至此，人工智能的搜索领域我们差不多分享结束了，后面有机会再做一些补充。后面我们从Adversarial games（对抗游戏）方向跟大家一起学习和分享。