我有一组(无序)对象.我还有一个oracle,它接受一个有序的对象列表,如果该列表中至少有一个有序冲突,则返回true,否则返回false.有序冲突是一对有序对象(A,B),因此oracle为任何输入列表[...,A,...,B,...]返回true.(A,B)是有序冲突并不一定意味着(B,A)是有序冲突.
我想找出所有无序集内的冲突:即找出所有对{X,Y},使得无论是(X,Y)或(Y,X)如上述所定义的有序冲突.oracle很慢(每次调用几十到几百毫秒)所以最小化oracle调用的数量是必不可少的; 显而易见的天真算法(将每个可能的有序集合元素集合提供给oracle; O(n²)调用)是不可接受的.有数百个集合元素,预计总体上不到10个冲突.
这是我已经得到的:如果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}.我可以维护一个备忘录矩阵,当且仅当(A,B)已经被测试时,M [a] [b]才为真,但我不知道如何使该递放很好.
由于上下文导致的其他复杂情况:如果任何对象在列表中出现多次,则忽略第二个和后续实例.此外,一些对象具有依赖关系:如果(P,Q)是依赖关系,那么在P首次出现之前出现Q的任何oracle输入(如果有的话)将虚假地报告冲突.在此算法启动之前,已经识别出所有依赖项.如果P与A冲突,则无法知道Q是否也与A冲突,但这是可接受的限制.
(上下文:这是用于识别不能包含在同一源文件中的C系统头的对."oracle"是编译器.)
一些建议:
假设您知道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必须冲突.
找到问题后,您可以删除其中一个违规项目,然后测试剩余的项目.如果仍然存在冲突,则可以使用二分法识别另一个冲突.
重复,直到找不到更多冲突.
您现在应该拥有大量不冲突的项目,以及一些已删除的项目,这些项目可能存在其他冲突.
要查找剩余的冲突,您可能需要尝试获取其中一个已删除的项目,然后重新插入所有项目(我们已经知道的项目除外).这应该确定另一个冲突,或证明已找到与该项目的所有冲突.
您可以对每个已删除的项重复此过程以查找所有剩余的冲突.