最短路径算法和维特比算法、HMM假设

本文主要是介绍最短路径算法和维特比算法、HMM假设，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

最短路径计算分静态最短路计算和动态最短路计算。
静态路径最短路径算法是外界环境不变，计算最短路径。主要有Dijkstra算法，A*（A Star）算法。 动态路径最短路是外界环境不断发生变化，即不能计算预测的情况下计算最短路。如在游戏中敌人或障碍物不断移动的情况下，典型的有D*算法。

Dijkstra算法

Dijkstra算法是典型最短路算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。

基本思想

引进两个集合S和U。S的作用是记录已求出最短路径的顶点(以及相应的最短路径长度)，而U则是记录还未求出最短路径的顶点(以及该顶点到起点s的距离)。

1. 初始时，S只包含起点s；U包含除s外的其他顶点，且U中顶点的距离为"起点s到该顶点的距离"[例如，U中顶点v的距离为(s,v)的长度，然后s和v不相邻，则v的距离为∞]。
2. 从U中选出"距离最短的顶点k"，并将顶点k加入到S中；同时，从U中移除顶点k。
3. 更新U中各个顶点到起点s的距离。之所以更新U中顶点的距离，是由于上一步中确定了k是求出最短路径的顶点，从而可以利用k来更新其它顶点的距离；例如，(s,v)的距离可能大于(s,k)+(k,v)的距离。
4. 重复步骤(2)和(3)，直到遍历完所有顶点。

大概过程：

创建两个表，OPEN, CLOSE。
OPEN表保存所有已生成而未考察的节点，CLOSED表中记录已访问过的节点。
1． 访问路网中里起始点最近且没有被检查过的点，把这个点放入OPEN组中等待检查。
2． 从OPEN表中找出距起始点最近的点，把这个点放到CLOSE表中。
3． 遍历考察2中这个点的子节点。求出这些子节点距起始点的距离值，放子节点到OPEN表中。
4． 重复2，3，步。直到OPEN表为空，或找到目标点。

黑色圆圈表示经过遍历计算过的点由图中可以看到Dijkstra算法从起始点开始向周围层层计算扩展，在计算大量节点后，到达目标点，所以速度慢效率低。
提高Dijkstra搜索速度的方法很多，常用的有用Dijkstra从起始点和终点同时搜索的方法。

Dijkstra算法求的是起点到其他所有点的最短路径，时间复杂度O(n2),空间复杂度O(n)。
dijkstra算法

A*(A Star）算法：启发式（heuristic）算法

A*算法是一种静态路网中求解最短路最有效的方法，公式表示为f(n)=g(n)+h(n)。

f(n) 是经过节点n时从初始点到目标点的估价函数，
g(n) 是在状态空间中从初始节点到n节点的实际代价，即起始节点到当前节点的实际代价.
h(n)是从n到目标节点最佳路径的估计代价。即当前节点到目标节点的估计代价.

当h(n) = 0, g(n) = d, 则f(n) = g(n)就变为了宽度优先搜索，也就是如果不需要启发，那就是宽度优先搜索的算法了。保证找到最短路径（最优解的）条件，关键在于估价函数h(n)的选取：

• 估价值h(n)<= n到目标节点的距离实际值，这种情况下，搜索的点数多，搜索范围大，效率低。但能得到最优解。
• 如果 估价值>实际值, 搜索的点数少，搜索范围小，效率高，但不能保证得到最优解。
• 估价值与实际值越接近，估价函数取得就越好。

对于几何路网来说，可以取两节点间欧几理德距离（直线距离）做为估价值，即f=g(n)+sqrt((dx-nx)(dx-nx)+(dy-ny)(dy-ny))；这样估价函数f在g值一定的情况下，会或多或少的受估价值h的制约，节点距目标点近，h值小，f值相对就小，能保证最短路的搜索向终点的方向进行。明显优于Dijstra算法的毫无无方向的向四周搜索。

搜索过程

A算法在运算过程中，每次从优先队列中选取f(n)值最小（优先级最高）的节点作为下一个待遍历的节点。
另外，A算法使用两个集合来表示待遍历的节点，与已经遍历过的节点，这通常称之为open_set和close_set。

* 初始化open_set和close_set；
* 将起点加入open_set中，并设置优先级为0（优先级最高）；
* 如果open_set不为空，则从open_set中选取优先级最高的节点n：* 如果节点n为终点，则：* 从终点开始逐步追踪parent节点，一直达到起点；* 返回找到的结果路径，算法结束；* 如果节点n不是终点，则：* 将节点n从open_set中删除，并加入close_set中；* 遍历节点n所有的邻近节点：* 如果邻近节点m在close_set中，则：* 跳过，选取下一个邻近节点* 如果邻近节点m也不在open_set中，则：* 设置节点m的parent为节点n* 计算节点m的优先级* 将节点m加入open_set中

和上面Dijkstra算法使用同一个路网，相同的起点终点，用A*算法的情况，计算的点数从起始点逐渐向目标点方向扩展，计算的节点数量明显比Dijkstra少得多，效率很高，且能得到最优解。
路径规划之 A* 算法

Dijkstra和A*算法的比较

1.Dijkstra算法计算源点到其他所有点的最短路径长度，A关注点到点的最短路径(包括具体路径)。
2.Dijkstra算法是一种发散式的搜索，所以空间复杂度和时间复杂度都比较高。对路径上的当前点，A算法不但记录其到源点的代价，还计算当前点到目标点的期望代价，是一种启发式算法。
3.A算法和Dijistra算法的区别在于有无估价值，Dijistra算法相当于A算法中估价值为0的情况。

Floyd（弗洛伊德）算法( from JarryWell)

Floyd算法是一个经典的动态规划算法。是解决任意两点间的最短路径(称为多源最短路径问题)的一种算法，可以正确处理有向图或负权的最短路径问题。两次遍历，时间复杂度较高。三轮循环时间所以复杂度是O(n3), 需要保留任意两点间的距离所以空间复杂度是O(n2)

算法思想
从任意节点i到任意节点j的最短路径不外乎2种可能：1)直接从节点i到节点j，2)从节点i经过若干个节点k到节点j。所以，我们假设arcs(i,j)为节点i到节点j的最短路径的距离，对于每一个节点k，我们检查arcs(i,k) + arcs(k,j) < arcs(i,j)是否成立，如果成立，证明从节点i到节点k再到节点j的路径比节点i直接到节点j的路径短，我们便设置arcs(i,j) = arcs(i,k) + arcs(k,j)，这样一来，当我们遍历完所有节点k，arcs(i,j)中记录的便是节点i到节点j的最短路径的距离。（由于动态规划算法在执行过程中，需要保存大量的临时状态（即小问题的解），因此它天生适用于用矩阵来作为其数据结构，因此在本算法中，我们将不使用Guava-Graph结构，而采用邻接矩阵来作为本例的数据结构）

for (int k = 1; k <= vexCount; k++) { //并入中转节点1,2,...vexCountfor (int i = 1; i <= vexCount; i++) {for (int j = 1; j < vexCount; j++) {if (arcs[i][k] + arcs[k][j] < arcs[i][j]) {arcs[i][j] = arcs[i][k] + arcs[k][j];path[i][j] = path[i][k]; //这里保存当前是中转的是哪个节点的信息}}}
}

维特比算法

维特比算法是一种动态规划算法，通常用于HMM最优状态序列的解码。
维特比算法的基础可以概括成下面三点：

1. 如果概率最大的路径p(或者说最短路径)经过某个点，比如途中的X22，那么这条路径上的起始点S到X22的这段子路径Q，一定是S到X22之间的最短路径。否则，用S到X22的最短路径R替代Q，便构成一条比P更短的路径，这显然是矛盾的。证明了满足最优性原理。
2. 从S到E的路径必定经过第i个时刻的某个状态，假定第i个时刻有k个状态，那么如果记录了从S到第i个状态的所有k个节点的最短路径，最终的最短路径必经过其中一条，这样，在任意时刻，只要考虑非常有限的最短路即可。
3. 结合以上两点，假定当我们从状态i进入状态i+1时，从S到状态i上各个节的最短路径已经找到，并且记录在这些节点上，那么在计算从起点S到第i+1状态的某个节点Xi+1的最短路径时，只要考虑从S到前一个状态i所有的k个节点的最短路径，以及从这个节点到Xi+1，j的距离即可。

维特比算法

HMM假设

1）齐次马尔科夫假设

齐次马尔科夫假设，通俗地说就是 HMM 的任一时刻 t 的某一状态只依赖于其前一时刻的状态，与其它时刻的状态及观测无关，也与时刻 t 无关。

2）观测独立假设

观测独立性假设，是任一时刻的观测只依赖于该时刻的马尔科夫链的状态，与其他观测及状态无关。

这篇关于最短路径算法和维特比算法、HMM假设的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---