算法:在一组对象中识别成对冲突,仅给出“在此列表中存在冲突”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中就没有无序的冲突。所以一个不完全不同于以下的分治算法应该是可行的:

  1. Put all the set elements in a list L (choose any convenient order).
  2. Invoke the oracle on L.
  3. If the oracle returns false,invoke the oracle on rev(L).
  4. If the oracle again returns false,there are no unordered conflicts within L.
  5.  
  6. # At this point the oracle has returned true for either L or rev(L).
  7. If L is a two-element list,the elements of L constitute an unordered conflict.
  8.  
  9. 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)操作通过在终点上先平分来查找单个冲突的位置,然后在开始点进行二等分。

例如,这可能是:

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

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

寻找更多的冲突

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

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

寻找剩余的冲突

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

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

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

猜你在找的Oracle相关文章