Как найти самое большое подмножество, где каждая пара соответствует критериям?

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; 
    } 
} 

The intuitive idea является сохранение вектора точек, добавить элемент массива 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). Если вы ничего не знаете, у вас есть экземпляр maximum clique problem, который, как известно, является NP-полным:

Skiena, S. S. «Clique and Independent Set» и «Clique». §6.2.3 и 8.5.1 в Руководстве по проектированию алгоритмов. Нью-Йорк: Springer-Verlag, pp. 144 и 312-314, 1997.

Поэтому, если вам нужен эффективный алгоритм, вам нужно надеяться, что ваша конкретная функция isValidWith имеет больше структуры, чем просто коммутативность, и вы будете должны использовать эту структуру.

Для вашей конкретной проблемы, вы должны быть в состоянии сделать следующее:

1. Отсортируйте точки в порядке возрастания х координат.
2. Найти longest decreasing subsequence из координат y в отсортированном списке.

Каждая операция может выполняться в O (n * log (n)) времени, поэтому ваша конкретная проблема эффективно разрешима.