路径搜索算法

一、问题描述

我们经常使用地图软件，输入开始、目的地点，就能给我们一条距离最短，或者用时最少，或者红绿灯最少的路径。那么地图软件是怎么样找到这些不同维度下的最优路径的呢？

对于这个问题，我们可以先进性抽象建模，假设我们要寻找距离最短的路径，那么就把每个岔路口看做是一个顶点，两个岔路口之间的路看作是一条边，路的长度就作为这条边的权重，如此就可以组成一个有向有权图。

假如我们只是想要从起点到终点寻找一条可行的路，那么广度优先搜索算法、深度优先搜索算法就能满足我们的需要；但是，如果我们想要寻找一条最短的路径，那么可能就要使用贪心算法、回溯算法、动态规划了。

然而，我们是有一些在原先没有介绍到的但是非常有效和出名的算法也可以来解决这个问题，如下给出介绍。

二、Dijkstra算法

本质上算是一种动态规划算法。但是当我们不了解动态规划的时候也是可以直接拿来使用的，起码比使用回溯算法要高效得多。

• 根据图中节点的个数n，构造一个长度为n的数组vertex[]，用来存放起点到各个点之间的最短距离，初始情况下，只有第一个值为0，其它值都是Integer.MAX_VALUE；
• 构造一个优先级队列数组inqueue[]，用来记录已经计算过的节点信息；
• 从vertex中选择一个未在inqueue中存在的最小路径值节点，基于该节点计算可以达到的下一节点路径长度，假设计算出来的下一节点的路径长度比vertex中该下一节点记录的路径长度小，那么就替换，否则不动；
• 继续重复上一个步骤，直至终点进入inqueue中，或者所有节点都进入inqueue中为止；

我们基于如上的算法规则来实际看一个例子：

Dijkstra算法介绍

第一步：vertex[]={0,MAX,MAX,MAX,MAX,MAX},inqueue={}，此时vertex中路径值最小的是节点0；

第二步：vertex[]={0,10,MAX,MAX,15,MAX},inqueue={0}，此时节点0可达的节点有1和4，从0分别过去的路径长度为10和15，明显比MAX要小，所以替换vertex中该节点的路径值；

第三步：vertex[]={0,10,25,12,15,MAX},inqueue={0,1}，此时vertex中路径值最小的是节点1，可达节点是2和3，路径长度分别是25和12，明显比MAX要小，所以替换vertex中该节点的路径值；

第四步：vertex[]={0,10,13,12,15,24},inqueue={0,1,3}，此时vertex中路径值最小的是节点3，可达节点是2和5，路径长度分别是13和24，明显比数组中该节点的当前路径值要小，所以替换vertex中该节点的路径值；

第五步：vertex[]={0,10,13,12,15,18},inqueue={0,1,3,2}，此时vertex中路径值最小的是节点2，可达节点是5，路径长度是18，明显比数组中该节点的当前路径值要小，所以替换vertex中该节点的路径值；

第六步：vertex[]={0,10,13,12,15,18},inqueue={0,1,3,2,4}，此时vertex中路径值最小的是节点4，可达节点是5，路径长度是25，比数组中该节点的当前路径值要大，所以不用替换vertex中该节点的路径值；

第七步：vertex[]={0,10,13,12,15,18},inqueue={0,1,3,2,4,5}，此时终点进入Inqueue了，而且所有节点都在inqueue中了，那么算法执行结束，此时vertex中的值就是起点0到每一个顶点的最短路径值。

时间复杂度是O(V+E)，其中V为节点的个数，E为所有的边数；

如上只是寻找路径最短的路径，当我们需要寻找时间最短的路径，那么就可以把边的权重改为通过的平均时间；如果我们需要寻找红绿灯最少的路径，那么就相当于把权重全部去掉，换成一个有向无权图。

Dijkstra算法仅在小数据量时可以快速找到最短路径，当起点和终点距离过远，中间有很多岔路时，求解效率就会非常低下，此时我们不一定要求一定要找到最优解，可以想办法找到一个效率还算可以的次优解，如此也能解决我们的工程问题。

根据总结，次优路径一般都会出现在最优路径附近，它们并不会呈现发散的趋势。所以，当地图很大的时候，我们缩小比例尺，不要太在意细节路径，而是把起点和终点周围的空间都划分为一个个等大的方块，然后基于这些方块的岔路口和边权重，使用Dijkstra算法来进行求解。当我们在行驶过程中，需要细节最短路径时，再动态生成即可。

三、启发式搜索算法

本质上算是一种贪心算法。算是对Dijkstra算法的一种改进。

Dijkstra算法虽然能找到最短路径，但是在大地图上寻找最短路径时不够高效，它之所以不够高效，是因为存在跑偏的现象。比如在上面讲Dijkstra算法的第六步时，我上一步已经达到节点2和3了，马上逼近终点5了，结果又返还回去从距离终点较远的节点4开始。

启发式搜索算法就能避免如上的问题，但是需要注意的是它只能找到一个次优解，不能保证找到的是最优解。其实这点也很好理解，没有遍历所有的节点和路径，就无法保证最优。启发式搜索算法有很多，比如A*算法、蚁群算法、遗传算法等，我们下面就以A*算法的讲解为例；

• 当走到某个顶点时，和起点的距离表示为g(k)；和终点的最短距离我们是未知的，但是我们可以使用直线距离进行模拟估算，直线距离当然是使用欧几里得距离比较合适，但是在计算时涉及开根号，比较浪费性能，所以我们使用曼哈顿距离，即两点之间横纵坐标距离之和，h(k)=Math.abs(v1.x-v2.x) + Math.abs(v1.y-v2.y)；其中h(k)被称为启发函数；
• 我们此时选取下一节点的时候，不光依赖g(k)作出决定，还根据h(k)作出决定，比如我们的估价函数f(k)=g(k)+h(k)；根据f(k)来选择下一个节点，此时就能有效解决跑偏的问题。
• 当选取下一地点达到终点时，就结束了，此时就找到了一个次优解；这是和Dijkstra算法不同的地方，Dijkstra算法在达到终点后还可以继续运行，求解达到后续其它节点的最短路径。