algorithm - 谁知道 Sedgewick-Vitter 算法？

Question

我必须在不使用斐波那契堆的情况下实现 Dijkstra 和 Sedgewick-Vitter 算法。有关 Dijkstra 完整互联网的信息，但我找不到 Sedgewick-Vitter 算法的伪代码或示例。我只发现 McHugh, Algorithmic Graph Theory book 中有一些信息，但我找不到免费的 pdf。所以也许有人知道这个算法并且可以分享信息、伪代码、链接？

干杯!

Answer 1

让我们假设一个带有欧几里得距离的图。源是s，目标是t。

如您所知，Dijkstra 算法以非递减距离（s，x）的顺序访问顶点x 。

A* 算法以非递减距离 ( s , x ) + h( x ) 的顺序访问顶点x。函数h必须是可接受的启发式，在此设置中意味着 h( x ) ≤ distance( x , t )。考虑 h 的各种选择。

• h( x ) = 0。这使得 A* 表现得像 Dijkstra。

• h( x ) = 距离( x , t )。这是最好的可接受的启发式方法。A* 将只访问距离（s，x）+距离（x，t）=距离（s，t）的那些顶点，即从s到t的最短路径上的那些顶点。不幸的是，这个 h 的选择计算起来很昂贵。

• h( x ) = || x - t ||。直线距离可以在 O(1) 时间内计算，并且始终是距离的下界。

当从s到t有一个合理的直射时，最后一个启发式方法很有效，但是随着弯路堆积，A* 将访问许多“不碍事”的顶点。

Sedgewick–Vitter 使用 h( x ) = a ||将其变为 11 x - t || 对于a > 1。这种启发式方法是不可接受的，因此我们可能找不到最短路径，但通过惩罚早期的弯路，它有望在不过多降低解决方案质量的情况下修剪搜索空间。