priority-queue - 记录帕累托前沿的最佳数据结构

Question

请问是否有人已经看到或面临以下问题？

我需要处理满足以下条件的成本/利润值列表 c ₁ /p ₁、 c ₂ /p ₂、 c ₃ /p ₃ ……

这是一个例子：2/3, 4/5, 9/15,12/19

如果尝试插入 10/14上述列表，则由于现有的成本/利润对而拒绝9/12该操作：增加成本（9->10）和减少利润（14->12）是没有用的。例如，此类列表可能出现在背包问题的（状态）动态规划算法中，其中成本可以代表权重。

如果在上面的列表中插入 7/20，这应该会触发9/15and12/19的删除。

我已经使用C++ std::set （通常用红黑树实现）编写了一个解决方案，但我需要提供一个比较函数，最终变得有点过于复杂。此外，在此类集合中的插入需要对数时间，并且实际上很容易导致线性时间（就非摊销复杂性而言），例如当插入触发所有其他元素的删除时。

我想知道是否存在更好的解决方案，因为有无数的解决方案可以实现（有序）集合，例如优先级队列、堆、链表、哈希表等。

这是一个帕累托前沿 (obj1: min cost, obj2: max profit)，但我仍然找不到记录它的最佳结构。

score 0 · Accepted Answer

我没有完全理解你描述的规则，所以我会不可知地说尝试插入可能会触发拒绝，如果它被接受，则需要删除后续项目。

您将需要使用平衡的比较树，表示为一个数组。在这种情况下，找到您需要的节点将花费 O(logN) 时间，这将是搜索或拒绝插入尝试的复杂性。当您需要删除项目时，您将其删除并插入一个新项目，其复杂性为

O(logN + N + N + logN) （即搜索、删除、重新平衡和插入。如果在重新平衡时我们知道要插入新项目的位置，我们可以去掉最后一个对数）

O(logN + N + N + logN) = O(2logN + 2N) = O(logN^2 + 2N)，很大程度上是线性复杂度。

1 回答 1