Найти приблизительное значение argmax, используя только приблизительные максимальные запросы

10

Рассмотрим следующую проблему.

Есть неизвестных значений v 1 , , v пR . Задача состоит в том, чтобы найти самый большой индекс, используя только запросы следующей формы. Запрос задается множеством S { 1 , , n }, и соответствующий ответ max i S v i . Цель состоит в том, чтобы использовать как можно меньше запросов.nv1,,vnRS{1,,n}maxiSvi

Эта проблема проста: мы можем использовать бинарный поиск, чтобы найти argmax с запросами. т.е. построить полное двоичное дерево с n листьями, соответствующими индексам. Начните с корня и спуститесь к листу следующим образом. В каждом узле запросите максимальное значение в правом и левом поддеревьях, а затем перейдите к дочернему элементу на стороне с более крупным ответом. По достижении листа выведите его индекс.O(logn)n

Следующая шумная версия этой проблемы появилась в моем исследовании.

Есть неизвестных значений v 1 , , v n . К ним можно обращаться с помощью запросов, в которых задан набор S { 1 , , n } и возвращена выборка из N ( max i S v i , 1 ) . Цель состоит в том, чтобы идентифицировать i { 1 , , n } так , чтобы E [ v i ]nv1,,vnS{1,,n}N(maxiSvi,1)i{1,,n} используя как можно меньше запросов. (Ожидание превышает выбор i , который зависит как от монет алгоритма, так и от шумных запросов.)E[vi]maxivi1i

E[vi]maxiviO(logn)1O(log2n)O(log3n)

O(log2n)Ω(log2n)O~(logn)Ω(1)0O(logn)

Томас
источник
11/nc20
@daniello Это работает, когда есть разрыв между самыми большими и вторыми по величине значениями. Общий случай кажется более сложным, хотя.
Томас
Примечание для себя: прочитайте весь вопрос, прежде чем комментировать
Даниелло

Ответы:

1

B=Θ(logn){v1,,vn}={1nB,,n1nB,B}

Bn1nB

B1

logn(logn)2

Bn

Извините, это наполовину, но надеюсь, что это может быть полезно!

усул
источник
Ω(logn)Ω(log2n)
Ω(log2n)