我對A *的打開列表使用跳過列表感興趣。然而，錯誤的是它的概率性質。打開列表可能會有所不同，從非常小的集合到最多的節點，並且需要保持每個節點的性能。小數據集的跳過列表
據我所知跳過列表有更大的機會隨機給小數據集的壞結果。我認爲這可能會在生成大量短路徑時出現問題。
我正在考慮解決這個問題，爲什麼不監視隨機數到一定程度。保持每個級別的節點總數，並且爲了保持每個級別之間的節點的理想分佈有時干預並強制節點成爲特定級別。
我不確定這將在我的給定應用程序中工作得如何，也許我應該關注另一個我的開放列表的數據結構。
我在跳過列表上閱讀的所有文章都沒有提到這樣的優化。由於我對整個性能分析遊戲相當陌生，因此我對試圖改進記錄的數據結構猶豫不決。
是，你是正確的 - 跳躍列表具有更高的機會談到小跳躍列表時衰減。
一般而言，根據this paper，存在恆定的alpha，使得跳過列表超過alpha * n的空間的概率小於1/2Ω(sqrt(n))-因此，跳過列表變得更大，則（超過該限制）的概率變得更小和更小。
爲了避免跳過列表中最壞的情況，可以使用原始跳過列表的變體，確定性跳過列表。該主題在this thesis work
其它替代方案討論的balanced BSTs，如AVL和red-black-tree，甚至B+ trees（其通常爲者優先的文件系統）。如果你的「開放集合」確實很小 - 你的分支因子很小（接近1），或者確切的說是B^d（d =解決方案的深度; B =分支因子）也會很小。這將導致快速查找，無論跳過列表的實現，因爲預計需要少數節點。
確定性跳過列表聲音有趣的必須閱讀該論文。 – user1759679
我建議您創建一個隨機生成您希望創建A *算法的長度的跳過列表的程序。檢查這些清單，看看其中有多少不是最優的。
我不建議嘗試創建一個生產跳過列表數據結構，它具有您提出的監視。您可能會發現監控和干預代碼會導致跳過列表在一般情況下表現不佳。
我有點好奇，爲什麼它會在一般情況下表現不佳。如果我只是將我的篡改限制在新節點插入的級別上，會對性能產生不利影響嗎？ – user1759679
監控隨機數的代碼將要求您爲每個列表存儲這些數字，並在每次插入時迭代它們。這將大大增加已完成的工作量。現在，如果您主要關心的是搜索小列表，那麼我會說不要太擔心，因爲即使是小列表的線性搜索（其跳躍列表退化爲非常不優化）也將非常快。 –
好的謝謝你的答案 – user1759679
當你說「跳過列表有更高的機會給小數據集隨機給出錯誤結果」時，你到底在害怕什麼？
你不應該害怕的是，對於10個元素的列表，沒有足夠的2級或3級節點來加速遍歷。迭代一個鏈表（這是一個沒有級別2+節點的跳過列表歸結爲）2個元素或10個元素之間的區別基本上是不存在的，即使在緊密的循環中（數據所需的節點引用管理類型結構可能會有更多的影響）。
顯然，一旦你得到更多的元素，沒有足夠高級別節點的影響會增加。但幸運的是，獲得更高級別節點的機會也會增加。例如，如果添加8個元素，它們全部爲1級節點的機會爲0.5^8 = 0.39％，即極不可能。
美在於跳過列表對小列表具有不良屬性是無關緊要的，因爲即使退化爲線性查找時間，小列表仍然會很快。我不會擔心這個，直到*分析後發現它是一個問題。 –