算法:在一组对象中识别成对冲突,仅给出“在此列表中存在冲突”oracle

前端之家收集整理的这篇文章主要介绍了算法:在一组对象中识别成对冲突,仅给出“在此列表中存在冲突”oracle前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。
我有一个(无序)的对象集合。我还有一个oracle,它接受一个有序的对象列表,如果列表中至少存在一个有序的冲突,返回true,否则返回false。有序冲突是一对有序对象(A,B),使得对于任何输入列表[…,A,…,B,…]返回true。 (A,B)是有序冲突并不一定意味着(B,A)是有序的冲突。

我想识别集合中的所有无序冲突:也就是找到所有对{x,y},使得(x,y)或(y,x)是上面定义的有序冲突。 oracle缓慢(每次调用几十到几毫秒),所以必须尽量减少oracle的调用次数;明显的幼稚算法(将每个可能的有序对的集合元素提供给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)已经被测试,但我不知道如何使该播放很好的递归。

由于上下文导致的其他并发症:如果任何对象在列表中出现多次,则忽略第二个和后续实例。此外,某些对象具有依赖关系:if(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,5 -> Good
Test 1,7 -> Conflict
Test 1,6 -> Good (Now deduce Endpoint is 7,the last end with a conflict)
Test 3,6 -> Conflict
Test 5,6 -> Good
Test 4,6 -> Conflict (Now deduce Startpoint is 4.)

你现在知道4,7是紧的(即不能减小而不消除冲突),所以我们可以推断出4和7必须冲突。

寻找更多的冲突

找到问题后,您可以删除其中一个违规项目,并测试其余的集合。如果仍然存在冲突,您可以使用二分法来识别另一个冲突。

重复,直到找不到更多的冲突。

寻找剩余的冲突

你现在应该有一大堆不冲突的项目,还有一些被删除的项目可能会有额外的冲突。

要找到剩余的冲突,您可能需要尝试使用其中一个已删除的项目,然后重新插入所有项目(我们已经知道与之冲突的项目除外)。这应该是识别另一个冲突,或证明与该项目的所有冲突已被发现。

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

原文链接:https://www.f2er.com/oracle/206220.html

猜你在找的Oracle相关文章