如何搜索每对符合标准的最大子集？

Question

我希望这不是一个统计问题......

假设我有一个界面:

public interface PairValidatable<T>
{
    public boolean isValidWith(T);
}

现在,如果我有一个大型的PairValidatables数组,如何找到每个对通过isValidWith测试的那个数组的最大子集？

为了澄清,如果子集中有三个条目,则元素0和1应传递isValidWith,元素1和2应传递isValidWith,元素0和2应传递isValidWith.

例,

public class Point implements PairValidatable<Point>
{
    int x;
    int y;

    public Point(int xIn, int yIn)
    {
        x = xIn;
        y = yIn;
    }

    public boolean isValidWith(Point other)
    {
        //whichever has the greater x must have the lesser (or equal) y
        return x > other.x != y > other.y;
    }
}

直观的想法是保持一个点向量,添加数组元素0,并将每个剩余的数组元素与向量进行比较,如果它通过向量中的每个元素进行验证,如果是这样就将它添加到向量...但是问题元素0可能是非常严格的.例如,

Point[] arr = new Point[5];
arr[0] = new Point(1000, 1000);
arr[1] = new Point(10, 10);
arr[2] = new Point(15, 7);
arr[3] = new Point(3, 6);
arr[4] = new Point(18, 6);

如上所述迭代将为我们提供仅包含元素0的子集,但是元素1,2和4的子集是更大的子集,其中每对通过验证.然后算法应该返回存储在元素1,2和4中的点.虽然元素3和4彼此有效并且元素1和4彼此有效,但元素2和3不是,元素1和3也不是.包含1,2和4的子集是比3和4更大的子集.

我猜想一些树或图算法最适合解决这个问题,但我不知道如何设置它.

该解决方案不必是特定于Java的,并且最好可以用任何语言实现,而不是依赖于Java内置函数.出于熟悉的原因,我刚才使用了类似Java的伪代码.

Answer 1

大概isValidWith是可交换的 - 也就是说,如果x.isValidWith(y)那么y.isValidWith(x).如果您只知道这一点,那么您就拥有了一个最大团队问题的实例,这个问题已知为NP-complete:

Skiena,SS"Clique and Independent Set"和"Clique".算法设计手册中的§6.2.3和8.5.1.纽约:Springer-Verlag,第144和312-314页,1997年.

因此,如果你想要一个有效的算法,你将不得不希望你的特定isValidWith函数具有更多的结构而不仅仅是交换性,你将不得不利用这种结构.

对于您的具体问题,您应该能够执行以下操作:

1. 按x坐标的递增顺序对点进行排序.
2. 找到排序列表中y坐标的最长递减子序列.

每个操作都可以在O(n*log(n))时间内执行,因此您的特定问题可以有效解决.