我对使用跳过列表作为 A* 的开放列表很感兴趣。然而，让我感到困扰的是它的概率性质。开放列表可以从非常小的节点集到大量节点，并且需要保持每个节点的性能。
据我了解，跳过列表对于小数据集随机给出错误结果的可能性更高。我认为这可能会在生成大量短路径时出现问题。
我正在考虑解决这个问题，为什么不在一定程度上监视随机数。保持每个级别的节点数量的运行总数，并且为了保持每个级别之间的理想节点分布，有时会干预并强制节点成为特定级别。
我不确定这在我给定的应用程序中的效果如何，如果我应该专注于我的开放列表的另一个数据结构。
我在跳过列表上阅读的所有文章都没有提到这种优化。由于我对整个性能分析游戏相当陌生，因此我不愿尝试改进已记录的数据结构。
我建议您创建一个程序，该程序随机生成您希望 A* 算法创建的长度的跳过列表。检查这些列表，看看其中有多少不是最佳的。
我不建议尝试创建具有您建议的监控的生产跳过列表数据结构。您可能会发现监控和干预代码会导致跳过列表在一般情况下表现不佳。
是的，你是对的- 在谈论小型跳过列表时，跳过列表有更高的衰减机会。
一般来说，根据这篇论文，有一个常数alpha使得跳过列表超出alpha * n空间的概率小于- 所以随着跳过列表变大，这个（超过这个限制）的概率变得越来越小。1/2Ω(sqrt(n))
为了避免跳过列表最坏的情况，可以使用原始跳过列表的一种变体，即确定性跳过列表。这个主题在本论文工作中进行了讨论
如果您的“开放集”确实如此之小 - 您的分支因子也非常小（接近 1），或者确切地说B^d（d = 解决方案深度；B = 分支因子）也将很小。这将导致快速查找，无论跳过列表实现如何，因为预计需要很少的节点。
当你说“跳过列表更有可能随机给出小数据集的坏结果”时，你到底害怕什么？
你不应该害怕的是，对于一个包含 10 个元素的列表，没有足够的 2 级或 3 级节点来加速遍历。迭代 2 个元素或 10 个元素的链表（没有 2+ 级节点的skiplist 归结为）之间的区别基本上不存在，即使在紧密循环中（数据所需的节点引用管理类型）结构可能会产生更大的影响）。
显然，一旦获得更多元素，没有足够的更高级别节点的影响就会增加。但幸运的是，获得更高级别节点的机会也增加了。例如，如果添加 8 个元素，它们都成为 1 级节点的机会是 0.5^8 = 0.39%，即极不可能。