Бинарный поиск обобщений для поэтов?

Предположим, у меня есть poset "S" и монотонный предикат "P" на S. Я хочу найти один или все максимальные элементы S, удовлетворяющие P.

EDIT : Я заинтересован в минимизации количества оценок P .

Какие алгоритмы существуют для этой проблемы и какие свойства и дополнительные операции они требуют на S?

Как насчет важных особых случаев, таких как:

• S - линейный порядок - тогда работает обычный бинарный поиск, если у вас есть операция «найти середину»
• S - это решетка
• S является решеткой подмножеств
• S является многосеточной решеткой
• ...

Два последних случая кажутся особенно важными, например, для проектирования эксперимента - у вас есть набор булевых или реальных параметров, и вы хотите найти наименьшую возможную комбинацию из них, которая воспроизводит определенный шаблон (например, неудачный тест).

Я не очень обдумывал это, поэтому, пожалуйста, поправьте меня, если я ошибаюсь.

Скажем, - это ширина набора.$w$

1. Для poset, который является объединением непересекающихся цепочек, вам нужно как минимум w log n оценок P , просто применяя стандартную нижнюю границу сложности запроса бинарного поиска к каждой цепочке.$w$$w\log n$$P$

2. Поскольку вы даете сравнения бесплатно, вы можете вычислить цепную декомпозицию множества в цепей бесплатно. Выполнять двоичный поиск на каждой цепи , чтобы идентифицировать первый элемент, удовлетворяющий P . Затем перейдите к выявленным элементам и удалите все доминирующие. Количество оценок P равно O ( w log n ) . Это идентифицирует все максимальные элементы, поскольку в цепочке может быть не более одного максимального элемента.$w$$P$$P$$O(w\log n)$

ДОБАВЛЕНО: На самом деле я вижу простой рекурсивный алгоритм, который делает намного лучше ( ) для решетки подмножеств 2 [ n ] ( РЕДАКТИРОВАТЬ : domotor описал общую стратегию в своем ответе). Здесь я предполагаю, что P монотонно вниз (то есть подмножества { X : P ( X ) = 1 } образуют нижний набор), что, я думаю, вы имеете в виду. Итак, вот алгоритм поиска члена нижнего набора:$O(n)$$2^{[n]}$$P$$\{X: P(X) = 1\}$

а) Испытание . Если 0, то остановись.$P(\emptyset)$

б) Тест . $P(\{n\})$

bi) Если 0, то рекурсивно на (ОК, так как ни один набор, содержащий n, не может быть в нижнем наборе).$2^{[n-1]}$$n$

b.ii) Если 1, то существует элемент нижнего множества в подрешетке . Эта подрешетка изоморфна 2 [ n - 1 ], поэтому еще раз мы можем вернуться. Точнее, мы можем запустить алгоритм для 2 [ n - 1 ] , но когда алгоритм просит оценить P ( Y ) , мы оцениваем P ( X ), где X = Y ∪ { n } .$\{X: n \in X\}$$2^{[n-1]}$$2^{[n-1]}$$P(Y)$$P(X)$$X = Y \cup \{n\}$

Таким образом, на каждом шаге мы обращаемся к подрешетке, которая вдвое меньше оригинальной. В целом, нам нужно оценить не более 2 n раз (на самом деле вы можете реализовать алгоритм для оценки предиката n + 1 раз, как указывает Йошио, поскольку вам нужно проверять ∅ только один раз).$P$$2n$$n+1$$\emptyset$

$P$

Обобщение бинарного поиска: поиск в деревьях и лесоподобные частичные заказы

$n$$w$$O(wn)$

Также было бы интересно найти эффективные статические и динамические структуры данных, которые играют ту же роль для частичных порядков, что кучи и бинарные деревья поиска играют для полных порядков.

$x<y$

Кроме того, может быть много максимальных элементов, удовлетворяющих P, поэтому даже для вывода всех из них может потребоваться много времени, поэтому я думаю, что есть только надежда найти один максимальный.

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

Например. если S является сеткой с фиксированной размерностью, то существует быстрый алгоритм: всегда делите одну координату пополам, оставляя минимальные остальные, поэтому спросите, например, на первом шаге (n / 2,0, ..., 0).

$n^d$

$P$$2^{[n]}$$n$$P$$P$