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

28

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

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

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

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

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

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

jkff
источник
1
Что такое «мультимножество» решетки?
Суреш Венкат
1
Это решетка, элементами которой являются отображения X -> N, meet - поэлементно min, а join - поэлементно max. Его можно обобщить на любую решетку вместо N в качестве кодомена.
JKFF

Ответы:

15

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

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

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

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


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

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

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

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

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

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

Сашо Николов
источник
Вау, такая простая идея! Спасибо - я подумаю над тем, кажется ли это оптимальным или нет :)
jkff
На самом деле это даже меньше, чем w log n, так как сумма длин цепей равна n. Я предполагаю, что максимум составляет около W log (н / ж).
JKFF
Хорошо, для линейных порядков это дает бинарный поиск, для решетки подмножеств это дает C (n, n / 2) log (2 ^ n / C (n, n / 2)) ~ exp (n) * n. Не слишком быстро, но и не выглядит слишком неоптимальным, поскольку на самом деле может быть так много ответов. Однако , чтобы найти одно максимальное подмножество, то нужно бинарный поиск в течение только любой одной цепи - это здорово , и теперь я называю себя глупо не думать об этом. Еще раз спасибо!
JKFF
2
Я думаю, что непересекающиеся цепочки дают нижнюю границу, по крайней мере, w + log n (для детерминированных алгоритмов). Подумайте о противнике, который «скрывает» единственное решение в последней запрошенной цепочке. Рандомизированная нижняя оценка Ω ( w ) должна следовать из минимаксного принципа Яо. Поиск одного элемента со сложностью w + log n может быть интересным. ww+lognΩ(w)w+logn
Сашо Николов
1
@YanKingYin Решетка не может быть объединением (более чем одной) непересекающихся цепей, потому что каждые два элемента должны иметь супремум. Poset - это объединение непересекающихся цепей, если его можно разбить так, чтобы элементы из разных частей были несопоставимыми, а элементы в одной и той же части допускали полный порядок.
Сашо Николов
8

nwO(wn)

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

Суреш Венкат
источник
Хех, звучит не слишком вдохновляюще по сравнению с log (n) :), но все равно спасибо!
JKFF
Но в этом все дело. Без структур данных вы не сможете получить log n даже для полностью упорядоченного набора, потому что все, что вы можете сделать, - это сканировать. Это действительно хороший вопрос, чтобы попытаться найти эквивалент BST.
Суреш Венкат
Ну, я говорю о сложности с точки зрения количества оценок предиката P, а не предиката сравнения.
JKFF
1
В некотором смысле да, но это далеко не полный ответ - например, он не дает раздвоения для 1-го или 2-го случая :) что вы предлагаете делать с корнями?
JKFF
1
Пока не уверен. мысли вслух. Но это отличный вопрос.
Суреш Венкат
4

x<y

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

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

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

nd

domotorp
источник
Боюсь, я не понимаю первый абзац. По вашему сокращению, у вас есть все n-битные строки в наборе S, и они даны как часть ввода? Если это так, мы можем пройти все строки за полиномиальное время.
Ёсио Окамото
1
@YoshioOkamoto: Я думаю, что в этом параграфе предполагается, что сравнение в S дано как логическая схема. (Но это не имеет ничего общего с поиском в поцете и поэтому мне не интересно.)
Tsuyoshi Ito
@ Цуйоши: Спасибо. Это имеет большой смысл.
Ёсио Окамото