谁知道Sedgewick-Vitter算法？

Question

我必须在不使用Fibonacci堆的情况下实现Dijkstra和Sedgewick-Vitter算法。关于Dijkstra的信息全在互联网上，但我找不到伪代码或Sedgewick-Vitter算法的示例。我只发现在McHugh，算法图论书中有一些信息，但我找不到免费的pdf。所以，也许任何人都知道这个算法，可以分享信息，伪代码，链接？

干杯!

Answer 1

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

如你所知，Dijkstra的算法以不递减距离(s，x)的顺序访问顶点x。

A*算法以非递减距离(s，x) + h(x)的顺序访问顶点x。函数h必须是可接受的启发式，在此设置中意味着h(x)≤距离(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通过对a> 1使用h(x) =a ||x - t||将其提高到11。这种启发式是不允许的，因此我们可能找不到最短路径，但通过惩罚早期的弯路，它有望在不太大降低解质量的情况下修剪搜索空间。