1

我有一个 A-* 的实现，用于最初使用Eric Lippert 的使用 SortedDictionary 的 PriorityQueue 实现的棋盘游戏，但是对于我的棋盘大小来说，性能并不令人满意。

使用 PriorityQueue 的 MinHeap 实现给了我在长对角路径上的 *2 加速（5-6 秒降低到 2-3 秒）；但后来我意识到它提供了一种不稳定的排序。对于这个应用程序，我需要一个稳定的排序。

是否有任何众所周知的 PriorityQueue 实现结合了 MinHeap 的效率，但以 SortedDictionary 的方式提供了稳定的排序？

更新：来自以下评论的其他详细信息：

  • 需要优先队列操作：Enqueue()、Dequeue() & Count；
  • 在 A-* 的每次迭代中： IsEMpty 和 Dequeue() 每次调用一次，Enqueue() 调用 6 次；

解析度：

虽然 和 的复杂性SortedDictionary<uint,Queue<TValue>>相同MinListHeap<KeyValuePair<TPriority,TValue>>，但维护插入顺序的额外代码复杂性似乎是一个恒定的时间损失。这可能不是确定的，但我正在寻找在这个细化阶段容易实现的目标。

此外，当我更多地考虑这个问题时，我意识到稳定性只需要短路径，而不是长路径；因此可以根据从起点到目标的距离的初始启发式估计，在进入 FindPath() 时选择所需的 PriorityQueue 实现。

4

1 回答 1

1

这应该是一个评论，但它太长了。所以这里是：

在您建议的链接之后，我找不到优先级队列的实现作为排序字典，但是谷歌搜索表明这个优先级队列是使用二叉搜索树实现的。如果是这种情况，那么这些似乎不是自平衡搜索树，因为我不明白通过用堆替换 BST 会产生 2 倍的改进。自平衡 BST 在insert()和上为您提供有保证的 log(n) 性能find()。deque()(= )也是如此removeMin()：它也应该是一个有保证的log(n)：你只是向左走，直到没有更多的左孩子。

好的，所以对于二叉搜索树 (BST) 的每个操作，我们都有 log(n)。堆呢？好吧，对于您正在查看的操作，它是相同的：removeMin()(= dequeue()) 返回具有最高/最低键的节点（这是 O(1)），但随后将最后一个节点放在初始位置并将其下沉通过递归地比较它和它的孩子。这需要在每个级别进行 2 次比较，并且通常涉及 log(n) 级别。removeMin()O(log(n) ) 操作也是如此 。怎么样insert()（=enqueue())? 在这里，在通常的实现中，我们将新项目放在最后，然后通过与其父项进行比较，将其浮动。在通常情况下，这需要 0.5*log(n) 次操作，即 O(log(n) )。这意味着 BST 和堆在 enqueue() 和 dequeue() 上都应该具有 log(n) 性能。并且两种数据结构都应该在isEmpty().

这个推理，如果正确的话，表明以下之一：

  • BST 实现中的常数因子使 minHeap 优先级队列中的常数因子相形见绌
  • 使用的 BST 不是自平衡的。

有人可能还认为0.5*log(n)heap oninsert()可能比 BST 更好insert()，但是 BST 插入实际上也通常0.5*log(n)在现实中，所以我认为这不可能。常数因素是合理的：如果minHeap 被实现为自动调整大小的数组（或者更好的是非调整大小的数组），那么 minHeap 可能不需要在 上分配额外的存储空间enqueue，而 BST 实现必须这样做。

BST 也有可能不是自平衡的。在这种情况下，在最坏的情况下，thedequeue()或 theenqueue()将花费 O(n) 时间，具体取决于添加项目的顺序。所以这将是一些值得关注的事情。

编辑1：可以使常规BST实现稳定的方式是采用一种约定，即如果我们插入具有相同键的节点，则新节点将成为（例如）具有相同键的节点的右子节点。这样，具有相同键的第一个节点将被出列。对于自平衡 BST，这可能需要更多的工作，因为旋转可能会违反这个期望的不变量。在这种情况下，我想我会做什么（考虑红黑树，而不是AVL 树）是在旋转两个节点时 A 和 BI 会检查它们的键是否实际上相同，如果是，则切换节点数据同时保持节点结构。但是对于这个问题可能有更好的解决方案。

EDIT 2 According to this acticle, SortedDictionary is in fact based on red-black tree. This in turn suggests either a bug in the implementation (doubtful but not unheard of) or constant factors as a culprit.

于 2013-03-19T05:50:03.633 回答