本文由 伯乐在线 - 土豆粉ss 翻译，黄利民 校稿。未经许可，禁止转载！
英文出处：theory.stanford.edu。欢迎加入翻译组。

本系列：

• 关于寻路算法的一些思考（1）：A* 算法介绍
• 关于寻路算法的一些思考（2）：Heuristics 函数
• 关于寻路算法的一些思考（3）：A* 算法的实现
• 关于寻路算法的一些思考（4）：A* 算法的变体
• 关于寻路算法的一些思考（5）：处理移动中的障碍物
• 关于寻路算法的一些思考（6）：预先计算好的路径的所用空间
• 关于寻路算法的一些思考（7）：地图表示
• 关于寻路算法的一些思考（8）：长期和短期目标
• 关于寻路算法的一些思考（9）：寻路者的移动成本
• 关于寻路算法的一些思考（10）：最短路径的用户体验
• 关于寻路算法的一些思考（11）：寻路算法的其他应用
• 关于寻路算法的一些思考（12）：AI 技术

AI技术

寻路问题常常会和人工智能（AI） 联系在一起，原因是 A算法和许多其他寻路算法是由 AI 研究者开发出来的。一些生物启发式的 AI 技术目前十分流行，我也收到一些为何不使用这类技术的咨询。神经网络是依据实例的大脑学习建模——给定一个正解的集合，它会学习出一个一般的解决问题模式。强化学习是依据经验的大脑学习建模——给定一些行为的集合和最终奖惩结果，它会学习出哪种行为是正确或错误的。遗传算法根据自然选择的进化规律建模——给定一些agent 集合，优胜劣汰。通常情况下，遗传算法不允许 agent 在他们的生存时间内进行学习。强化学习则不但允许 agent 在生存时间内学习，还可以和其他 agent 分享知识。（译注：agent：智能体，正文保留未翻）*

神经网络

神经网络是这样构建的：它受到训练，来对输入进行模式识别。他们是一种用来处理函数近似的方法:给定 y1 = f(x1),y2 = f(x2), …, yn = f(xn)，构建一个函数 f’使得 f’逼近 f。近似函数 f’一般都是光滑的：对于接近 x 点的 x’，我们希望 f’(x)也能接近f’(x’)。

函数近似方法可以满足以下两个目的：

• 规模：近似函数的表达可以明显小于真实的函数规模。
• 泛化：未知函数值的输入数据可以使用近似函数

神经网络典型做法是使用一组输入值向量，产生一组输出值向量。在算法内部，训练“神经元”(neurons)的权重。神经网络使用监督学习，即输入和输出都是已知的，学习的目标是建立一个可以近似输入输出映射的函数表达。

在寻路问题中，函数 f(start,goal)=path。我们并不知道输出路径是什么。我们可以使用一些方法，可能是 A*算法，来计算它们。但是如果我们能根据(start, goal)计算路径，那么我们就已经知道了函数 f，那么为什么还要自找麻烦的找它的近似函数呢？因为我们已经完全知道了函数 f，再归纳 f 就没有用了。用函数近似的唯一潜在的好处可能会降低 f 的表达规模。但f 表达的是个相当简洁几乎不占用空间的算法，所以我认为神经网络在这里也没有什么用。另外，神经网络输出规模是固定的，而寻路问题规模是可变的。

但另一方面，函数近似可能对构建寻路的一些组成部分有用。比如移动的成本函数是未知的。例如，没有实际移动操作和战役的情况下，穿越怪兽聚集森林的成本，我们可能并不知道。使用函数近似的方法的话，每次穿越森林时，移动成本函数f(number of orcs, size of forest)可以测量出来并装入神经网络模型中（注：这里移动成本f的自变量是怪兽数量和森林规模）。对于未来的寻路部分，根据算出的未知移动成本，我们可以找到更好的路线。

另一个可以从归功于近似计算的函数是启发式函数。A算法中的启发式函数可以计算到达目的地的最小成本，如果一个单元沿着路径 P=p1,p2,…,pn移动，当每穿过一段路径的时候，我们可以更新 n到近似函数 h 中，其中g(pi,pn)=（从i到 n 的实际移动成本）。当启发函数优化了，A算法也会运行的更快。

神经网络尽管对于寻路算法本体不太实用，但对 A*算法使用的函数可以起到作用。移动函数和启发式函数都可以测算，因此能给函数近似反馈。

遗传算法

根据适应度函数（fitness function），遗传算法允许开发参数空间来求得效果良好的解。他们是一种用来处理函数优化的方法：给定一个函数g(x)（x 是一组典型的参数值向量），求得能最大化（或最小化）g(x)的 x 值。这是一种非监督学习——问题的正确答案预先并不知道。

对于寻路问题，给定一个起始位置和一个目标位置，x 是这两点间的路径，g(x)是穿越这路径的成本。简单的优化方法，比如爬山算法会以增加g(x)为代价的方法改变 x。不幸的是，在一些问题中，会遇到“局部最大值”，x 值周围没有点 具有更大的对应g值，但是某个离x 值比较远的点表现更好。遗传算法改善了爬山算法，它保留了 x 的多样性，使用比如变异和交换的进化-启发式方法更新 x。

爬山算法和遗传算法可以用来学习出 x 的最优值。然而对于寻路问题，我们已经有了 A*算法找到最优的 x ，因此函数优化的方法就不需要了。

遗传编程是遗传算法的更深层次，它把程序当做参数。例如，你可以输入的是寻路算法而不是寻路路径，你的适应值函数会根据表现测算每个算法。对于寻路问题来说，我们已经有个很好的算法，我们无需在进化出一个新的算法。

也许在和神经网络结合的情况下，遗传算法可以应用于寻路问题的某个部分。但是，在这篇文章中我还不知道有何用处。相反，如果问题解是已知的，估计会有一个更有前途的方法作为许多可行工具之一，在寻路问题中优化 agent。

强化学习

和遗传算法一样，强化学习是一种非监督学习。然而，和遗传算法不同的是，agent 可以在他们的生存时间内学习；没必要等着观察他们的存活情况。并且，多 agents 同时参与到不同部分中分享各自学习成果是可能的。强化学习和 A*的核心部分有着一些相似的地方。

在 A中，到达结束目标后会沿着经过的路径追溯回去，标记到目前为止所有路径的选择；其他选择就被去掉了。在强化学习中，可以测算每个状态时的情况，并且当前的奖（惩）都可以追溯回导致这个状态之前的所有选择。使用一个值函数表达这个追溯的过程，这有点像 A中的启发式函数，但随着 agent 尝试新路径并对这过程进行学习的更新，这一方面两者是不同的。

相比于更简单的算法来说，强化学习和遗传算法的一个关键的优势是：在探求新解和利用目前学到的信息两者间是可以做出选择的。遗传算法，通过变异寻找（新解）；强化学习，通过明确给出选择新行为的概率寻找（新解）。

即使和遗传算法结合，我认为强化学习也不会在寻路问题本身上使用。但是相对来说，它却可以作为一个向导，指导agent 在游戏世界中如何表现。

注： 函数近似方法可以变形为函数优化问题。为了找到最逼近 f(x)的f'(x),令 g(f’)=∑(f’(x)-f(x))^2（即在所有输入 x 上(f’(x)-f(x))^2的和）。

参考

作者写这个系列的参考文章在这里。我们翻译组的工作，基本结束了此为止咯，欢迎大家保持关注伯乐在线的其他文章 :)