21

我有一组（无序的）对象。我还有一个 oracle，它接受一个有序的对象列表，如果该列表中至少存在一个有序冲突，则返回 true，否则返回false。有序冲突是一对有序的对象 (A,B)，使得 oracle 对任何输入列表 [..., A, ..., B, ...] 返回 true。(A,B) 是有序冲突并不一定意味着 (B,A) 是有序冲突。

我想识别集合中的所有无序冲突：也就是说，找到所有对 {x, y} 使得(x, y)或(y, x) 是上述定义的有序冲突。预言机很慢（每次调用几十到几百毫秒），因此必须尽量减少预言机调用的次数；显而易见的幼稚算法（将每个可能的有序集合元素对提供给 oracle；O(n²) 调用）是不可接受的。有数百个集合元素，预计总体冲突少于十个。

据我所知：如果 oracle 为一个二元素列表返回 true，那么显然列表中的元素构成冲突。如果 oracle 对任何列表返回 false ，则该列表中不存在有序冲突；如果 oracle 对列表 L 和列表 L 的反转都返回 false，则 L 中没有无序冲突。因此，与下面不完全不同的分治算法应该可以工作：

Put all the set elements in a list L (choose any convenient order).
Invoke the oracle on L.
  If the oracle returns false, invoke the oracle on rev(L).
    If the oracle again returns false, there are no unordered conflicts within L.

# At this point the oracle has returned true for either L or rev(L).
If L is a two-element list, the elements of L constitute an unordered conflict.

Otherwise, somehow divide the set in half and recurse on each

我被困在“将集合分成两半并递归”部分。有两个并发症。首先，取有序列表的上半部分和下半部分是不够的，因为冲突可能会通过拆分消除（考虑 [...A1, A2, ... An ... ][...B1，B2，...Bn ...]）。枚举所有大小为 n/2 的子集应该可以工作，但我不知道如何有效地做到这一点。其次，由于调用堆栈上的隐式状态，一个简单的递归可能会重复大量工作——假设我们已经确定 A 与 B 冲突，那么任何包含 A 和 B 的列表的 oracle 调用都被浪费了，但我们仍然需要排除 {A, x} 和 {B, x} 的其他冲突。我可以维护一个备忘录矩阵，使得 M[a][b] 当且仅当 (A, B) 已经过测试时为真，但我没有

由于上下文的其他复杂性：如果任何对象在列表中出现多次，则忽略第二个和后续实例。此外，一些对象具有依赖关系：如果 (P,Q) 是依赖关系，那么在 P （如果有的话）第一次出现之前出现 Q 的任何 oracle 输入都会虚假地报告冲突。在此算法开始之前，所有依赖项都已被识别。如果 P 与 A 冲突，则无法知道 Q 是否也与 A 冲突，但这是可以接受的限制。

（上下文：这是用于识别不能包含在同一源文件中的 C 系统头文件对。“oracle”是编译器。）

4

3 回答 3

6

几点建议：

寻找单一冲突

假设你知道有 n 项冲突，你可以使用 O(log n) 运算找到单个冲突的位置，先在终点二等分，然后在起点二等分。

例如，这可能看起来像：

Test 1,2,3,4,5,6,7,8,9,10 -> Conflict
Test 1,2,3,4,5 -> Good
Test 1,2,3,4,5,6,7 -> Conflict
Test 1,2,3,4,5,6 -> Good (Now deduce Endpoint is 7, the last end with a conflict)
Test 3,4,5,6 -> Conflict
Test 5,6 -> Good
Test 4,5,6 -> Conflict (Now deduce Startpoint is 4.)

您现在知道 4,5,6,7 是紧的（即不能在不消除冲突的情况下变得更小），因此我们可以推断 4 和 7 必须冲突。

发现更多冲突

发现问题后，您可以删除其中一个有问题的项目，并测试剩余的一组。如果这仍然冲突，您可以使用二分法来识别另一个冲突。

重复直到不再发现冲突。

查找剩余冲突

您现在应该有一大组不冲突的项目，以及一些已删除的项目，这些项目可能有额外的冲突。

要查找剩余的冲突，您可能需要尝试取出已删除的项目之一，然后重新插入所有项目（我们已经知道与之冲突的项目除外）。这应该要么确定另一个冲突，要么证明已找到与该项目的所有冲突。

您可以对每个已删除的项目重复此过程以查找所有剩余的冲突。

于 2013-07-15T20:28:01.707 回答
0

You need to find answers for n*(n-1) questions, each question being if an ordered pair has a conflict. Whenever you send a sequence of length k and the oracle says "good", you will have answers to k(k-1) such questions.

Create and initialize these n*(n-1) questions as a adjacency matrix with default values -1 (set self-edges as 0). Permute the sequence randomly and apply your recursive algorithm. Whenever you find that a sequence has no conflict mark the corresponding answer in the matrix (0). Mark as conflict (1) if a sequence of exactly two has a conflict.

Now, after on big iteration you have this matrix with -1s, 0s and 1s. Assume -1s are the edges and find the longest path. Reapply your algorithm. Keep doing this until number of unknowns is very small. At which point you send out pairs to the oracle.

于 2013-07-15T21:21:12.997 回答
0

既然你说你有数百个标题和少于 10 个冲突，我将在假设你有 n 个项目和 O(lg n) 个项目涉及冲突的情况下给出一个最坏情况的最佳解决方案。在最坏的情况下，如果您有 Th​​eta(lg n) 项目涉及冲突，那么所有这些项目都会相互冲突，并且无法使用少于 Omega((lg n)^2) 的 oracle 调用来确定这一点. 因此 O((lg n)^2) 预言机调用将是最佳的，假设 Theta(lg n) 项目涉及冲突。

无论如何here'e算法。首先，您确实喜欢另一个答案，并迭代地识别 O(lg n) 预言机调用中的冲突，并从您的集合中删除冲突中的一项，直到您得到一个没有冲突的集合。这最多需要 O((lg n)^2) 次 oracle 调用。然后对于您删除的每个项目 Z，您将 Z 放在无冲突集的开头，并执行二分查找以找到稍后会产生冲突的项目 X，或确定不存在任何冲突。（如果找到这样的 X，删除 X 并重复）。因此，您会发现所有以 Z 开头的冲突，并且每个这样的冲突都在 O(lg n) 的 oracle 调用中找到。同样，您将 Z 放在无冲突列表的末尾并执行二进制搜索以查找所有前面的元素 X 会产生冲突。然后，剩下要做的就是找出最初在算法第一步中删除的项目之间的所有冲突。但是假设只有 O(lg n) 个，所以这需要 O((lg n)^2) 个 oracle 调用。因此，oracle 调用的总数为 O((lg n)^2)。

于 2013-07-16T00:33:00.637 回答