Как перебирать векторы в порядке вероятности в малом пространстве

12

Рассмотрим мерный вектор v, где v i{ 0 , 1 } . Для каждого i мы знаем p i = P ( v i = 1 ) и допустим, что v i независимы. Используя эти вероятности, существует ли эффективный способ итерации по двоичным n- мерным векторам в порядке от наиболее вероятного к наименее вероятному (с произвольным выбором связей) с использованием пространства, сублинейного в выходном размере? nvvi{0,1}ipi=P(vi=1)vin

Возьмем для примера . Наиболее вероятным вектором является ( 1 , 0 , 1 ), а наименее вероятным - { 0 , 1 , 0 } . p={0.8,0.3,0.6}(1,0,1){0,1,0}

Для очень малого мы могли бы обозначить каждый из 2 n векторов с его вероятностью и просто отсортировать, но это, конечно, все равно не использовало бы сублинейное пространство.n2n

Близкий вариант этого вопроса ранее задавался по адресу /cs/24123/how-to-iterate-over-vectors-in-order-of-probability .

Lembik
источник
Есть ли какая-то причина, по которой вы тоже не задали дополнительный вопрос? Главная проблема здесь заключается в том, чтобы делать это в сублинейном пространстве?
Суреш Венкат
@SureshVenkat Да, проблема полностью в сублинейном пространстве (в размере вывода). Я спросил это здесь, так как думаю, что вопрос может быть очень сложным.
Лембик
Решение этого в пространстве и времени, кажется, требует методов, аналогичных SUBSET-SUM (быстрое знание того, какие суммы подмножеств почти отменяют различные суммы). Таким образом, вряд ли будет быстрое решение. poly(n)
Джеффри Ирвинг
@ GeoffreyIrving Как вы думаете, эту интуицию можно сделать более формальной?
Лембик

Ответы:

9

Далее приведен алгоритм, который использует приблизительно времени и 2 n / 2 пространства.2n2n/2

Во-первых, давайте рассмотрим проблему сортировки сумм всех подмножеств элементов.n

Рассмотрим эту подзадачу: у вас есть два отсортированных списка длины , и вы хотели бы создать отсортированный список попарных сумм чисел в списках. Вы хотели бы сделать это примерно за O ( м 2 ) времени (выходной размер), но сублинейное пространство. Мы можем достичь O ( м ) пространства. Мы сохраняем приоритетную очередь и извлекаем суммы из приоритетной очереди в порядке возрастания.mO(m2)O(m)

Пусть списки будут и b 1b m , отсортированные по возрастанию. Мы берем m сумм a i + b 1 , i = 1 m и помещаем их в очередь с приоритетами.a1amb1bmmai+b1i=1m

Теперь, когда мы вытаскиваем наименьшую оставшуюся сумму из очереди приоритетов, если j < m, мы помещаем сумму a i + b j + 1 в очередь приоритетов. В пространстве преобладает очередь с приоритетами, которая всегда содержит не более m сумм. И время O ( m 2 log m ) , так как мы используем O ( log m ) для каждой приоритетной операции очереди. Это показывает, что мы можем сделать подзадачу в O ( м 2ai+bjj<mai+bj+1mO(m2logm)O(logm) время и O ( m ) пространство.O(m2logm)O(m)

Теперь, чтобы отсортировать суммы всех подмножеств из чисел, мы просто используем эту подпрограмму, где список a i является набором сумм подмножеств первой половины элементов, а список b i является набором сумм подмножеств второй половины предметов. Мы можем найти эти списки рекурсивно с помощью того же алгоритма.naibi

Теперь рассмотрим исходную проблему. Пусть будет набором координат , равным 0 , а S 1 будет набором координат, равным 1 . Тогда Π я S 0 р ( v я = 0 ) Π я S 1 р ( v я = 1 )S00S11

iS0p(vi=0)iS1p(vi=1)=1inp(vi=0)iS1p(vi=1)p(vi=0)=1inp(vi=0)exp(iS1logp(vi=1)p(vi=0)).

Сортировка этих чисел такого же , как сортировка числа , так что мы свели задачу к сортировке суммы подмножеств п элементов.iS1logp(vi=1)logp(vi=0)n

Питер Шор
источник
Есть ли правдоподобное сокращение, которое сделало бы неправдоподобным решение времени / пространства?
Лембик
2nn2n
Спасибо. Я, конечно, не имел в виду поли-время, а скорее что-то линейное в выходном размере и поли-пространстве.
Лембик
4

O(n)

  1. x{0,1}nO(n)r(x)xxp(x)>p(x)x{0,1}nxp(x)>p(x)r(x)x
  2. kxr(x)=kO(n)x{0,1}nxr(x)xr(x)=k
  3. k02n1kxr(x)=k

(Мы также должны позаботиться о возможных связях, но это не сложно.)

Юрий
источник
Спасибо. Однако это довольно медленный алгоритм :)
Lembik
0

Изменить: этот ответ неверен. Смотрите комментарии для деталей. ~ gandaliter

O(2n)O(n)

  1. (i,pi)|0.5pi|

  2. vvi1pi>0.50vviv

  3. Вызовите эту рекурсивную функцию в отсортированном списке и пустом векторе.

010.5

O(2n)O(n)nO(2n)O(n)O(2n)временные шаги. Поэтому этот алгоритм является оптимальным в худшем случае.

gandaliter
источник
Θ(2n)
Благодарю. Я явно не читал это достаточно внимательно! Я отредактировал свой ответ.
гандалитер
3
v1=12n1v1=1pi=0.5
Вы правы, это не работает. Сожалею!
гандалитер