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 cailloux à la fois, mais au prix d'augmenter le nombre de pas à . Ils basculent s'il y a un caillou en position sans laisser d'autres cailloux autour en basculant récursivement , en utilisant cela comme point de départ pour basculer avec une autre étape récursive, puis basculer 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 est l'ensemble des nœuds dont nous voulons ajouter ou supprimer des cailloux, et 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 .
Par exemple, considérons la stratégie qui place un caillou en à l'étape , mais marque les cailloux qui sont des multiples de 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èsétapes, comme la stratégie naïve, mais réduit le nombre maximal de galets deà .
Existe-t-il des stratégies de galets parallèles qui se terminent par étapes avec une complexité max-galets asymptotique encore plus faible? Et si nous sommes prêts à autoriser les étapes ? Quels sont les points "intéressants", où le compromis entre max-galet et temps est particulièrement bon?
la source
Réponses:
MODIFICATIONS : ajout des lemmes 2 et 3.
Voici une réponse partielle: vous pouvez atteindre la positionN
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 ( √n n n 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:
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)−1 P(k) P(k−1)
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
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
Donc, en résolvant pour , nous avons k ≈n=N(k)
etS(k)≈k≈2logn−−−−−√ S(k)≈2logn−−−−−√22logn√=exp(O(logn−−−−√)) .
This takes care of all positionsn 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(k−1)=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:
LetT(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
ChoosingL(k)=21/δ , we get
Solving forS=S(k) and T=T(k) in terms of n=N(k) , we have k=δlogn , and
This takes care of all positionsn 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(k−1)=O(1) . QED
The solutions in the proofs of Lemmas 1 and 2 are well-behaved, in that, for sufficiently largen , for each solution P(n) that reaches position n there is a position k≤n/2 such that only one pebble is ever placed at position k , and the solution decomposes into a (well-behaved) solution P(N−k) 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 ,
I conjecture that for every sufficiently largen 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 positionn in t steps has to take space at least n1+Ω(ϵ(n))/t at some step. This yields corollaries such as:
Proof sketch. We show2V(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 largen , we have f(n)≤mink<nf(n−k)+max(n,2f(k)) , that is, f(n)−f(n−k)≤max(n,(1+δ)f(k)) for k<n.
Sincef is convex, we have f(n)−f(n−k)≤kf′(n) . So it suffices if kf′(n)≤max(n,(1+δ)f(k)).
By a short calculation (usingf(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 x≤y , ecy(1+c/(2y))≤max(ey2−x2,(1+δ)ecx) . Since 1+z≤ez , and ez≤1+2z for z≤1 , it suffices to show
ecy+c/(2y)≤max(ey2−x2,e2δ+cx), that is,
Ify≤x+0.1δ/c , then cy+c/(2y)≤cx+0.2δ (for large y ) and we are done, so assume y≥x+0.1δ/c . Then y2−x2≥0.1yδ/c (for large y ), so it suffices to show
la source