Jeu de galets parallèle sur une ligne

13

Dans le jeu de galets sur une ligne, il y a N + 1 nœuds étiquetés de 0 à N. Le jeu commence par un caillou sur le nœud 0. S'il y a un caillou sur le nœud i, vous pouvez ajouter ou supprimer un caillou du nœud i + 1. Le but est de placer un caillou sur le nœud N, sans placer plusieurs cailloux sur la carte en même temps et sans faire trop de pas.

La solution naïve consiste à placer un caillou sur 1, puis 2, puis 3, etc. Ceci est optimal en termes de nombre d'étapes. Ce n'est pas optimal dans le nombre maximum de galets sur la planche en même temps: lors de la dernière étape il y a N galets sur la planche (sans compter celui sur 0).

Une stratégie qui place moins de cailloux sur le plateau en même temps est dans cet article . Ils atteignent le nœud N sans dépasser Θ(lgN) cailloux à la fois, mais au prix d'augmenter le nombre de pas à Θ(nlg23) . Ils basculent s'il y a un caillou en position N sans laisser d'autres cailloux autour en basculant récursivement N/2 , en utilisant cela comme point de départ pour basculer N avec une autre étape récursive, puis basculer N/2 avec une troisième étape récursive de demi-taille pour efface ça.

Je suis intéressé par le compromis entre le nombre maximum de cailloux et le nombre d'étapes, en supposant que les ajouts et les suppressions de cailloux peuvent être effectués en parallèle. Par "parallèle", je veux dire que chaque étape peut ajouter ou supprimer autant de cailloux que vous le souhaitez, tant que chaque ajout / retrait individuel est autorisé et n'interagit pas avec les autres mouvements effectués. Plus précisément, si A est l'ensemble des nœuds dont nous voulons ajouter ou supprimer des cailloux, et P est l'ensemble des nœuds qui avaient un caillou au début de l'étape, alors nous pouvons faire tous ces ajouts et suppressions en une seule étape comme tant que {a1|aA}PA .

Par exemple, considérons la stratégie qui place un caillou en i à l'étape i , mais marque les cailloux qui sont des multiples de N tant que «points de contrôle» et supprime le caillou d'index le plus élevé derrière un point de contrôle caillouteux dans la mesure du possible. Cette stratégie atteint toujours le nœud N aprèsNétapes, comme la stratégie naïve, mais réduit le nombre maximal de galets deNà2N .

Existe-t-il des stratégies de galets parallèles qui se terminent par N étapes avec une complexité max-galets asymptotique encore plus faible? Et si nous sommes prêts à autoriser les étapes O(NlgN) ? Quels sont les points "intéressants", où le compromis entre max-galet et temps est particulièrement bon?

Craig Gidney
la source
À chaque étape, combien de galets pouvez-vous ajouter ou supprimer? Si seulement un, dans votre quatrième paragraphe, voulez-vous dire O(N) pas totaux, plutôt que N ? Lors du comptage des galets utilisés, est-ce le nombre maximum sur la planche à tout moment de la séquence?
Neal Young
@NealYoung Dans le cas parallèle, vous pouvez ajouter et supprimer autant de cailloux par étape que vous le souhaitez. Mais si vous affectez la position il doit y avoir un caillou à la position k - 1 présent au début de l'étape. Je voulais dire exactement N étapes, mais O ( N ) est également intéressant et bien sûr inclus dans O ( N lg N ) . Oui, c'est le nombre maximum de galets qui compte. kk1O(N)O(NlgN)
Craig Gidney
Qu'en est-il de la stratégie d'origine mais avec une "parallélisation"? Lorsque nous atteignons commençons à effacer la première moitié en parallèle; lorsque vous atteignez 3 N / 4, commencez à effacer la plage [ N / 2 - 3 N / 4 ] ET continuez à effacer la première moitié en parallèle (au moment où nous plaçons un caillou sur 3 N / 4, il ne reste que N / 4 cailloux sur la première moitié); et ainsi de suite pour ( 2 k - 1 ) N / kN/23N/4[N/23N/4]3N/4N/4(2k1)N/2k jusqu'à . La complexité des galets doit être la même: Θ ( lg N ) , mais avec N étapes. NΘ(lgN)N
Marzio De Biasi
@MarzioDeBiasi Pourquoi la complexité des galets serait-elle la même? Pour autant que je sache, la relation de récurrence passerait de à 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)
Craig Gidney
@CraigGidney: vous avez raison ...
Marzio De Biasi

Réponses:

4

MODIFICATIONS : ajout des lemmes 2 et 3.

Voici une réponse partielle: vous pouvez atteindre la position N

  • en se déplace en utilisant l'espace N O ( ϵ ( N ) ) , où ϵ ( N ) = 1 / NNO(ϵ(N)) . (Lemme 1)ϵ(N)=1/logN
  • dans se déplace en utilisant l'espace O ( log N ) (pour toute constante δ > 0 ) (Lemme 2).N1+δO(logN)δ>0

En outre, nous esquissons une borne inférieure (lemme 3): pour une certaine classe de solutions dites bien comportées , le lemme 1 est serré (jusqu'à des facteurs constants dans l'exposant), et aucune solution de ce type utilisant un espace poly-log ne peut atteindre position dans le temps O ( NN .O(NpolylogN)

Lemme 1. Pour tout , il est possible d'atteindre la position n en n mouvements en utilisant l'espace exp ( O ( nnn

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

Preuve. Le schéma est récursif, comme le montre la figure ci-dessous. Nous utilisons la notation suivante:

  • est le nombre de niveaux dans la récursiviték
  • est la solution formée (avec k niveaux de récursivité).P(k)k
  • est la position maximale atteinte par P ( k ) (à l'instant N ( k ) ).N(k)P(k)N(k)
  • est l'espace utilisé par P ( k ) .S(k)P(k)
  • est le nombre decouchesutilisées par P ( kL(k) , comme illustré ci-dessous:P(k)

                  solution structure for lemma 1

Dans l'image, le temps passe de haut en bas. La solution ne s'arrête pas au temps N ( k ) , au lieu de cela (pour une utilisation dans la récursivité) elle continue jusqu'au temps 2P(k)N(k) , inversant exactement ses mouvements, de manière à revenir à un seul galet au temps 22N(k) .2N(k)

Les lignes verticales pleines séparent les couches de P ( k ) . Dans l'image, L ( k ) est cinq, donc P ( k ) se compose de 5 couches. Chacune des couches L ( k ) de P ( k ) (sauf la plus à droite) a deux sous-problèmes, un en haut de la couche et un en bas, reliés par une ligne verticale continue (représentant un caillou qui existe pour cette durée). Dans l'image, il y a cinq couches, donc il y a neuf sous-problèmes. Généralement, P (L(k)P(k)L(k)P(k)L(k)P(k) est composé deP(k) sous-problèmes. Chaque sous-problème de P ( k ) a la solution P ( k - 1 ) .2L(k)1P(k)P(k1)

L'observation cruciale pour délimiter l'espace est qu'à tout moment, seules deux couches ont des sous-problèmes "actifs". Les autres ne contribuent qu’à un seul galet, nous avons donc

  • , etS(k)L(k)+2S(k1)
  • N(k)=L(k)N(k1)

Maintenant, nous choisissons pour déterminer complètement P ( k ) . Je ne sais pas si ce choix est optimal, mais il semble proche: prenez L ( k ) = 2 k . Ensuite, les récidives ci-dessus donnentL(k)P(k)L(k)=2k

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

Donc, en résolvant pour , nous avons k n=N(k) etS(k)k2lognS(k)2logn22logn=exp(O(logn)).

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


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).

Choosing 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
la source
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