Параллельная игра в гальку на линии

13

В игре с камушками на линии есть N + 1 узлы, обозначенные от 0 до N. Игра начинается с камешка на узле 0. Если на узле i есть камушек, вы можете добавить или удалить камешек из узла i + 1. Цель состоит в том, чтобы поместить гальку в узел N, не помещая одновременно много гальки на доску и не делая слишком много шагов.

Наивное решение состоит в том, чтобы поместить гальку в 1, затем в 2, затем в 3 и так далее. Это оптимально с точки зрения количества шагов. Это не оптимально для максимального количества камней на доске одновременно: на последнем шаге на доске есть N камней (не считая одного на 0).

В этой статье рассматривается стратегия, при которой на доске одновременно остается меньше камешков . Они достигают узла N, не превышая Θ(lgN) камешков за раз, но за счет увеличения количества шагов до Θ(nlg23) . Они переключают, есть ли камешек в позиции N не оставляя других камушков, рекурсивно переключая N/2 , используя это в качестве отправной точки для переключения N с другим рекурсивным шагом, затем переключая N/2 с третьим рекурсивным шагом половинного размера в очисти это.

Меня интересует компромисс между максимальным количеством камешков и количеством шагов, при условии, что добавление и удаление камешков можно выполнять параллельно. Под «параллелью» я подразумеваю, что каждый шаг может добавлять или удалять столько камешков, сколько необходимо, при условии, что каждое отдельное добавление / удаление разрешено и не взаимодействует с другими выполняемыми движениями. В частности, если A - это набор узлов, к которым мы хотим добавить или удалить камешки, а P - это набор узлов, у которых был камешек в начале шага, тогда мы можем сделать все эти добавления и удаления за один шаг, как пока {a1|aA}PA .

Например, рассмотрим стратегию, которая помещает камешек в на шаге i , но помечает камешки, кратные ii как «контрольные точки» и удаляет гальку с самым высоким индексом позади контрольной точки, когда это возможно. Эта стратегия все еще достигает узла N послеNшагов, как и наивная стратегия, но уменьшает максимальное количество камешков сNдо2NNN .2N

Существуют ли стратегии параллельного выравнивания линий, которые заканчиваются за шагов с еще более низкой асимптотической сложностью max-pebble? Что, если мы хотим разрешить O ( N lg N ) шагов? Каковы «интересные» моменты, когда компромисс между max-pebble и временем особенно хорош?NO(NlgN)

Крейг Гидни
источник
На каждом этапе, сколько камешков вы можете добавить или удалить? Если только один, в четвертом абзаце, вы имеете в виду полных шагов, а не N ? При подсчете используемой гальки, является ли это максимальное количество на доске в любой момент в последовательности? O(N)N
Нил Янг
@NealYoung В параллельном случае вы можете добавлять и удалять столько камешков за шаг, сколько захотите. Но если вы воздействуете на позицию то в позиции k - 1 должен быть камушек в начале шага. Я имел в виду ровно N шагов, но O ( N ) также интересно и, конечно, включено в O ( N lg N ) . Да, это максимальное количество камней, которые имеют значение. kk1O(N)O(NlgN)
Крейг Гидни
Как насчет оригинальной стратегии, но с «распараллеливанием»? Когда мы достигнем начнем очищать первую половину параллельно; при достижении 3 N / 4 начните очищать диапазон [ N / 2 - 3 N / 4 ] И продолжайте очищать первую половину параллельно (в то время, когда мы помещаем камушек на 3 N / 4, остается только N / 4 камешков на первая половина); и так далее для ( 2 k - 1 )N/23N/4[N/23N/4]3N/4N/4 до н(2k1)N/2kN, Сложность гальки должна быть такой же: , но с N шагами. Θ(lgN)N
Марцио Де
@MarzioDeBiasi Почему сложность гальки будет такой же? Насколько я могу судить, рекуррентное соотношение будет идти от к F ( n ) = 2 F ( n / 2 ) + 1 = O ( n ) . F(n)=F(n/2)+1=O(lg(n))F(n)=2F(n/2)+1=O(n)
Крейг Гидни
@CraigGidney: ты прав ...
Марцио Де

Ответы:

4

РЕДАКТИРОВАТЬ : Добавлены леммы 2 и 3.

Вот частичный ответ: Вы можете достичь позиции N

  • в движется, используя пространство N O ( ϵ ( N ) ) , где ϵ ( N ) = 1 / NNO(ϵ(N)) . (Лемма 1)ϵ(N)=1/logN
  • в движется с использованием пространства O ( log N ) (для любой постоянной δ > 0N1+δO(logN)δ>0 ) (лемма 2).

Кроме того, мы рисуем нижнюю границу (лемма 3): для определенного класса так называемых решений с хорошим поведением лемма 1 является жесткой (с точностью до постоянных множителей в показателе степени), и никакое такое решение, использующее пространство с полулогами, не может достичь положение во времениNO(NpolylogN) .

Лемма 1. Для всех можно достичь положения n за n ходов, используя пробел exp ( O (nnn

exp(O(logn)) = nO(1/logn)

Доказательство. Схема рекурсивная, как показано на рисунке ниже. Мы используем следующие обозначения:

  • - количество уровней в рекурсииk
  • - сформированное решение (с k уровнями рекурсии).P(k)k
  • - максимальная позиция, достигнутая P ( k ) (в момент времени N ( k ) ).N(k)P(k)N(k)
  • - пространство, используемое P ( k ) .S(k)P(k)
  • - количествослоев,используемых P ( k ) , как показано ниже:L(k)P(k)

                  solution structure for lemma 1

На картинке время течет сверху вниз. Решение не останавливается в момент N ( k )P(k)N(k) , вместо этого (для использования в рекурсии) оно продолжается до времени 2N(k) , точно меняющий ходы, чтобы вернуться к одной гальке в момент времени 2N(k) .

Сплошные вертикальные линии разделяют слои группы P ( k ) . На рисунке L ( k ) равно пяти, поэтому P ( k ) состоит из 5 слоев. Каждый из L ( k ) слоев P ( k ) (кроме самого правого) имеет две подзадачи, одну в верхней части слоя и одну в нижней части, соединенные сплошной вертикальной линией (представляющей гальку, которая существует для эта продолжительность). На рисунке пять слоев, поэтому есть девять подзадач. Как правило,L(k)P(k)L(k)P(k)L(k)P(k) состоит из 2P(k) подзадача. Каждая подзадача в P ( k ) имеет решение P ( k - 1 ) .2L(k)1P(k)P(k1)

Критическое наблюдение для ограничения пространства состоит в том, что в любое время только два слоя имеют «активные» подзадачи. Остальные вносят только одну гальку, таким образом, мы имеем

  • иS(k)L(k)+2S(k1)
  • N(k)=L(k)N(k1)

Теперь мы выбираем чтобы полностью определить P ( k ) . Я не уверен, является ли этот выбор оптимальным, но он кажется близким: возьмем L ( k ) = 2 k . Тогда приведенные выше рецидивы даютL(k)P(k)L(k)=2k

  • S(k)k2k , и
  • N(k)=2k(k+1)/2

Итак, решая для , имеем k n=N(k) иS(k)k2logn. S(k)2logn22logn=exp(O(logn))

Это учитывает все позиции в множестве { N ( k ) : k { 1 , 2 , } } . Для произвольного n обрежьте дно решения P ( k ) для наименьшего k с N ( k ) n . Требуемая оценка выполняется, потому что S ( k ) / S ( k - 1 ) = O (n{N(k):k{1,2,}}nP(k)kN(k)n . QEDS(k)/S(k1)=O(1)


Lemma 2. For any δ>0, for all n, it is possible to reach position n in n1+δ moves using space O(δ21/δlogn).

Proof. Modify the construction from the proof of Lemma 1 to delay starting each subproblem until the previous subproblem has finished, as shown below:

                  solution structure for lemma 2

Let T(k) denote the time for the modified solution P(k) to finish. Now at each time step, only one layer has a subproblem that contributes more than one pebble, so

  • S(k)L(k)+S(k1),
  • N(k)=L(k)N(k1),
  • T(k)=(2L(k)1)T(k1)2L(k)T(k1)2kN(k).

L(k)=21/δ, we get

  • S(k)k21/δ,
  • N(k)=2k/δ,
  • T(k)2kN(k).

Solving for S=S(k) and T=T(k) in terms of n=N(k), we have k=δlogn, and

  • Sδ21/δlogn, and
  • Tn1+δ.

This takes care of all positions n in the set {N(k):k{1,2,}}. For arbitrary n, trim the bottom of the solution P(k) for the smallest k with N(k)n. The desired bound holds because S(k)/S(k1)=O(1). QED


The solutions in the proofs of Lemmas 1 and 2 are well-behaved, in that, for sufficiently large n, for each solution P(n) that reaches position n there is a position kn/2 such that only one pebble is ever placed at position k, and the solution decomposes into a (well-behaved) solution P(Nk) for positions k+1,k+2,,n and two (well-behaved) solutions P(k), each for positions 1,2,,k, connected by the pebble at position k. With an appropriate definition of well-behaved, let V(n) denote the minimum pebble volume (the sum over time of the number of pebbles at each time) for any well-behaved solution. The definition implies that for sufficiently large n, for δ=1>0,

V(n)mink<nV(nk)+max(n/2,(1+δ)V(k)).

I conjecture that for every sufficiently large n there is a well-behaved solution that minimizes pebble volume. Maybe somebody can prove it? (Or just that some near-optimal solution satisfies the recurrence...)

Recall that ϵ(n)=1/logn.

Lemma 3. For any constant δ>0, the above recurrence implies V(n)n1+Ω(ϵ(n)).

Before we sketch the proof of the lemma, note that it implies that any well-behaved solution that reaches position n in t steps has to take space at least n1+Ω(ϵ(n))/t at some step. This yields corollaries such as:

  • Lemma 1 is tight up to constant factors in the exponent (for well-behaved solutions).
  • No well-behaved solution can reach position n in npolylogn time steps using space polylogn. (Using here that nΩ(ϵ(n))=exp(Ω(logn))polylogn.)

Proof sketch. We show 2V(n)f(n) where f(n)=n1+cϵ(n) for some sufficiently small constant c. We assume WLOG that n is arbitrarily large, because by taking c>0 small enough, we can ensure 2V(n)f(n) for any finite set of n (using here that V(n)n, say).

The lemma will follow inductively from the recurrence as long as, for all sufficiently large n, we have f(n)mink<nf(nk)+max(n,2f(k)), that is, f(n)f(nk)max(n,(1+δ)f(k)) for k<n.

Since f is convex, we have f(n)f(nk)kf(n). So it suffices if kf(n)max(n,(1+δ)f(k)).

By a short calculation (using f(n)/n=eclogn and f(n)=(f(n)/n)(1+c/(2logn)), and using a change of variables x=logk and y=logn), this inequality is equivalent to the following: for all sufficiently large y and xy, ecy(1+c/(2y))max(ey2x2,(1+δ)ecx). Since 1+zez, and ez1+2z for z1, it suffices to show ecy+c/(2y)max(ey2x2,e2δ+cx), that is,

cy+c/(2y)max(y2x2,2δ+cx).

If yx+0.1δ/c, then cy+c/(2y)cx+0.2δ (for large y) and we are done, so assume yx+0.1δ/c. Then y2x20.1yδ/c (for large y), so it suffices to show

cy+c/(2y)0.1yδ/c.
This holds for sufficiently small c and large y. QED
Neal Young
источник
FWIW, I have a proof that there is always a near-optimal well-behaved solution, so the lower bound in Lemma 3 applies to all solutions. It's a bit too involved to type in here -- if anybody is interested contact me by email (google "neal young computer science" for contact info).
Neal Young