誰知道Sedgewick-Vitter算法？

Question

我必須在不使用斐波那契堆的情況下實現Dijkstra和Sedgewick-Vitter算法。關於Dijkstra完全互聯網的信息，但我找不到僞碼或Sedgewick-Vitter算法的例子。我只發現在McHugh算法圖論中有一些信息，但我找不到免費的pdf。所以也許有人知道這個算法，可以分享信息，僞代碼，鏈接？

乾杯！

Answer 1

我們假設一個具有歐幾里得距離的圖。來源是s，目的地是t。

如你所知，Dijkstra算法訪問頂點X在非減距離的順序（小號，X）。

A *算法訪問頂點X在非減距離（小號，X）+ H（X）的順序。功能ħ必須是受理啓發式，在這種設置意味着H（X）≤距離（X，噸）。考慮h的各種選擇。

• H（X）= 0。這使A *的行爲等的Dijkstra。

• H（X）=距離（X，噸）。這是最好的可接受啓發式。 A *將訪問只的距離（小號，X）+距離（X，噸）=距離（小號，噸），即那些頂點，從最短路徑上的那些頂點s至t。不幸的是，這種計算昂貴的選擇。

• H（X）= || x - t ||。直線距離在時間O（1）中是可計算的，並且總是距離的下限。

最後的試探效果很好，當有來自小號到噸一個合理的直杆，但作爲走彎路堆積，A *將訪問許多頂點是「出路」。（x）= a || Sedgewick-Vitter使用h變成11 x - t ||對於a> 1.這種啓發式算法是不可接受的，所以我們可能找不到最短路徑，但是通過懲罰早期彎路，它有望修整搜索空間而不會降低解算質量。