[关闭]
@zhuanxu 2018-02-05T12:49:48.000000Z 字数 942 阅读 570

algorithms-on-graphs:graph basics 笔记三

algorithms-on-graphs


本文是学习 Algorithms on Graphs 的笔记第3篇。

Minimum spanning tree (MST)

最小生成树算法

树的特点

两种最小生成树算法

Kruskal’s algorithm 实现

Prim’s algorithm 实现

最短路径加速:Bidirectional Dijkstra


思路是我们如果单向搜索,其搜索面积显然大于双向搜索。
看下面的例子:

我们能够找到一个meeting vetex,但是我们可以说这是最短路径嘛?

上面我们就发现了一条更短的路径。

那当我们找到一个交汇点后,怎么去寻找最短路径呢?看下面的定理:

上面定理说我们最短路径经过的点u,要么在forward和backward都处理过,要么只在其中一个处理过。

下面是证明不会出现在forward和backward都没处理的点中。

接着我们看如果点出现在forward中,会怎么样?


当我们在backward中继续计算Dijkstra距离的时候dist^R(u) <= I(u,w)+dist^R(w)
同时此时 I(u,w)+dist^R(w)是 dist(u,t)的最短距离,即 dist^R(u) >= I(u,w)+dist^R(w)
因为 此时是在最短路径上

下面是具体的算法描述:



A-star Algorithm (A * )

下面介绍另一种最短路径算法:A-star Algorithm。

A-star 的一个思想是:如果我们知道了一个搜索方向,能够帮助我们更快的找到最优路径,看对比图:
双向搜索:

有方向搜索:

先给出一个定义:

根据新的边的weights定义,我们有下面的定理:


上面这个定理的意义是:如果我们在原空间中找到最短路径,在新的空间(对边权重重新通过函数pi定义)中也是短路径。

下面我们具体介绍下A*算法:A* ≡ Dijkstra


Bidirectional A *




Lower Bounds


Euclidean Potential


总结

本文是对 Algorithms on Graphs 第5-6周 课程的一个记录,笔记更多的是给自己复习时快速查阅用。

你的鼓励是我继续写下去的动力,期待我们共同进步。
这个时代,每个人都是超级个体!关注我,一起成长!

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注