准确 蓝芯科技给您推荐路径搜索
时间：2019-11-19 阅读：914
引言
正所谓在家靠父母，出门靠高德。在那错综复杂的工厂里，我们的机器人哪怕视力惊人，也没办法一眼看到目的地。为了准确又的把货物送到目的地，小蓝(杭州蓝芯科技有限公司简称)只能祭出杀招了，那就是----搜索算法。在路径搜索问题中，搜索算法可以生成一个的解，按照搜索逻辑不同，可以分为深度优先法和广度优先法。但是，在实际工程上会使用一些近似算法去解决路径搜索问题，主要分为启发式搜索的A*、D*、Focused D*算法和准启发式搜索的退火、进化、蚁群优化算法。本文通过介绍启发式搜索的A*算法和准启发式搜索的遗传进化算法，让大家感受这两类算法的特色与魅力。
A*算法
A*算法作为经典启发式搜索算法，正广泛运用于智能机器人、无人驾驶等领域。详细来说，A*算法是一种静态路网中求解短路径有效的直接搜索方法，也是许多其他问题的常用启发式算法。从公式上的描述是：
f(n)=g(n)+h(n),
f(n) 是从初始状态经由状态n到目标状态的代价估计，
g(n) 是在状态空间中从初始状态到状态n的实际代价，
h(n) 是从状态n到目标状态的低的估计代价。
那么什么是代价呢，为了便于理解，你可以直接认为这里的代价就是距离。假设如图1中场景，小蓝要从出发点begin到目标点end，该如何选择路线呢？首先从出发点开始，可以选择去a点，也可以选择去d点。那么究竟去哪个点更合适呢？d点说了，我到目标点的直线距离是4.5，出发点到我距离是2，近预估总距离只要6.5，选我选我~。a点轻蔑的一笑道：我到目标点的直线距离是4，出发点到我的距离只要1.5，近的预估总距离只要5.5。于是小蓝立马投向了a点的怀抱。
那么机智的小蓝下一步该怎么走呢，小蓝只能从a点出发，去往的目的地b点，掐指一算，已经走过的距离是3.5，到目标点的直线距离是2，总距离还是5.5。小蓝轻轻瞟了一眼躲在角落怀揣6.5的d点，二话不说向b点奔去。
到了b点以后，抬头一看，下面只有c点。到了c点以后，已经走过的距离变成了6.5，到目标点的直线距离是4，总距离一下子变成了10.5。于是小蓝深情的看着d点已经它手中的6.5的牌牌，留下了悔恨的泪水。俗话说，浪子回头金不换，d点也接受了小蓝，让他可以重新开始。
重新选择了从d点出发的小蓝，抬头望向了e点。嗯很好，到e点实际距离也只有5，到目标点的直线距离是2，总距离也只有7。又回忆起c点的10.5的预估距离，小蓝不禁一阵后怕。
到达e点，小蓝便见到了金光闪闪的终点二字。这便结束了么？不，如今的小蓝已经可以称得上是一个江湖了，万一后是一段望山跑死马的远路，岂不是得亏亏亏死…于是再次打起了自己的小算盘，e点到终点的距离是2，那么走过的总距离是7，掰掰手指头就知道比途径c点更近。于是小蓝便方向大胆的迈向了终点，获取了一条低代价的路径。
这就是一次A*搜索的全部过程啦。为了加深大家的记忆，小蓝决定再次祭出学习A*算法之*组图，看看在棋盘格地图中，小蓝是如何进行A*路径搜索滴。
进化算法
进化算法也是在人工智能领域中用于解决优化问题的一种准启发式搜索算法。进化算法的思想参考了生物界的遗传进化理论，让达尔文爷爷的思想从豌豆领域出发，进军计算机领域。简单来说，进化算法将优化问题的解(特征值集合)表示为一个编码串，称为个体或者染色体，个体中的每一位，就叫做基因。那么很多个体就可以组成一个种群。为了避免局部，进化算法同样借鉴了生物学中的遗传/突变/自然选择以及杂交等。
那么进化算法是如何为后路径搜索服务的呢，小蓝通过遗传算法进行举例说明，假设下图中，小蓝要从0点出发到15点。
那么首先要对该图进行整理，也就是编码过程，编码表格如下所示：
然后检查两点之间是否可达，形成路径连接表，如下表所示：
这样就可以通过适应度函数进行路径评估了，不可达的路径的适应度为0。适应度函数表达如下所示：
这样，通过添加随机数，并加入首尾后，就能生成一群初始化群体了。生成初始化群体以后，小蓝就万事俱备，开始遗传啦。遗传过程如下图所示，通过选择，交叉和变异产生新的群体，然后按照适应度进行筛选，通过重采样的方式留下适应度高的个体，进行下一轮的计算。
看到想加几个就加几个的基因，故而遗传算法是可以同时对多个可行解进行搜索，且不容易陷入局部。同时还允许使用非常复杂的适应度函数，还能对变量的变化范围加以限制。但是很遗憾的是，遗传算法目前都还没有一个很的数学解释，所以遗传算法还是非常考验我们码农的技术滴。
总结
到这里又要和大家说拜拜啦，通过介绍启发式搜索中的A*算法和准启发式搜索的遗传进化算法后，想必大家对路径搜索方法已经有所了解了。其实类似的方法很多，同样方法的下变化也很多，在实际工程应用中要结合实际情况，进行灵活选择和调整。这才是我们工程师存在的意义啊~