Parallel Pebble Game on a Line

W grze żwirowej na linii znajdują się N + 1 węzłów oznaczonych od 0 do N. Gra rozpoczyna się od kamyka w węźle 0. Jeśli kamyk znajduje się w węźle i, możesz dodać lub usunąć kamyk z węzła i + 1. Celem jest umieszczenie kamyka na węźle N, bez umieszczania wielu kamyków na planszy w tym samym czasie i bez wykonywania zbyt wielu kroków.

Naiwnym rozwiązaniem jest umieszczenie kamyka na 1, potem 2, potem 3 i tak dalej. Jest to optymalne pod względem liczby kroków. Nie jest to optymalne pod względem maksymalnej liczby kamyków na planszy w tym samym czasie: podczas ostatniego kroku na planszy znajduje się N kamyków (nie licząc tej na 0).

Strategia, która stawia mniejsze kamyki na pokładzie w tym samym czasie jest w tym dokumencie . Docierają do węzła N nie przekraczając jednocześnie $\Theta(\lg N)$ kamyków, ale kosztem zwiększenia liczby kroków do $\Theta(n^{\lg_2 3})$ . Przełączają, czy w pozycji jest kamyk, $N$ bez pozostawiania innych kamyków, poprzez rekurencyjne przełączanie $N/2$ , wykorzystując to jako punkt początkowy do przełączania $N$ pomocą kolejnego kroku rekurencyjnego, a następnie przełączając $N/2$ za pomocą trzeciego rekurencyjnego kroku o pół wielkości, aby Wyczyść to.

Interesuje mnie kompromis między maksymalną liczbą kamyków a liczbą kroków, przy założeniu, że dodawanie i usuwanie kamyków można wykonywać równolegle. Przez „równoległe” rozumiem, że każdy krok może dodawać lub usuwać dowolną liczbę kamyków, o ile jest to pożądane, pod warunkiem, że każde pojedyncze dodawanie / usuwanie jest dozwolone i nie wchodzi w interakcje z innymi wykonywanymi ruchami. W szczególności, jeśli $A$ jest zbiorem węzłów, z których chcemy dodawać lub usuwać kamyki, a $P$ jest zbiorem węzłów, które miały kamyki na początku kroku, wówczas możemy wykonać te wszystkie dodania i usunięcia w jednym kroku, ponieważ tak długo, jak $\{a-1 | a \in A \} \subseteq P - A$ .

Na przykład, należy rozważyć strategię, która kładzie wir na na etapie , ale znaków kamyki, które są wielokrotnością $i$ $i$ jako „punkty kontrolne” i usuwa kamyk o najwyższym indeksie za punktami kontrolnymi, jeśli to możliwe. Ta strategia wciąż osiąga węzeł N pokrokach, jak strategia naiwna, ale zmniejsza maksymalną liczbę kamyków zdo $\sqrt{N}$ $N$ $N$ . $2 \sqrt{N}$

Czy istnieją strategie układania równoległego linii, które kończą się w krokach z jeszcze niższą asymptotyczną złożonością maks. Otoczaka ? Co zrobić, jeśli chcemy zezwolić na kroki ? Jakie są „interesujące” punkty, w których kompromis między maksymalnym kamykiem a czasem jest szczególnie dobry? $N$ $O(N \lg N)$

complexity reversible-computing

— Craig Gidney
źródło

Ile kamyków możesz dodać lub usunąć na każdym etapie? Jeśli tylko w czwartym akapicie masz na myśli całkowitą liczbę kroków

, a nie

? Czy przy liczeniu użytych kamyków jest to maksymalna liczba na planszy w dowolnym momencie sekwencji?

O (N)

$O(N)$

N

$N$

— Neal Young,

@NealYoung W przypadku równoległym możesz dodawać i usuwać dowolną liczbę kamyków na krok. Jeśli jednak wpływu na sytuację

to nie musiało być kamyk w pozycji

występuje na początku etapu. Miałem na myśli dokładnie N kroków, ale

jest również interesujące i oczywiście zawarte w

. Tak, liczy się maksymalna liczba kamyków.

k

$k$

k - 1

$k-1$

O (N)

$O(N)$

O (N \lg N)

$O(N \lg N)$

— Craig Gidney

Co z oryginalną strategią, ale z „równoległością”? Kiedy osiągniemy

zacznij oczyszczać pierwszą połowę równolegle; po osiągnięciu

rozpocznij czyszczenie zakresu

ORAZ kontynuuj czyszczenie pierwszej połowy równolegle (w momencie, gdy kamyk kładziemy na

pozostały tylko

kamyki na pierwsza połowa); i tak dalej dla

N / 2

$N/2$

3 N / 4

$3N/4$

[N / 2 - 3 N / 4]

$[N/2-3N/4]$

3 N / 4

$3N/4$

N / 4

$N/4$

. Złożoność otoczaków powinna być taka sama:

, ale zkrokami

(2^{k} - 1) N / 2^{k}

$(2^k-1)N/2^k$

N

$N$

Θ (\lg N)

$\Theta(\lg N)$

N

$N$

— Marzio De Biasi

@MarzioDeBiasi Dlaczego złożoność kamieni jest taka sama? O ile mi wiadomo, relacja powtarzalności będzie przebiegać od

F (n) = F (n / 2) + 1 = O (l g (n))

$F(n) = F(n/2) + 1 = O(lg(n))$

F (n) = 2 F (n / 2) + 1 = O (n)

$F(n) = 2F(n/2) + 1 = O(n)$

— Craig Gidney

@CraigGidney: masz rację ...

— Marzio De Biasi

EDYCJE : Dodano Lemmas 2 i 3.

Oto częściowa odpowiedź: Możesz osiągnąć pozycję $N$

w ruchach z użyciem spacji , gdzie $N$ $N^{O(\epsilon(N))}$ . (Lemat 1) $\epsilon(N) = 1/\sqrt{\log N}$
w porusza się za pomocą spacji (dla dowolnej stałej ) (Lemat 2). $N^{1+\delta}$ $O(\log N)$ $\delta>0$

Szkicujemy również dolną granicę (Lemat 3): dla pewnej klasy tak zwanych dobrze zachowanych rozwiązań, Lemat 1 jest ciasny (do stałych współczynników wykładnika), i żadne takie rozwiązanie wykorzystujące przestrzeń poliblogową nie może osiągnąć pozycja w czasie $N$ . $O(N\,\text{polylog}\, N)$

Lemat 1. Dla wszystkich , jest możliwe do osiągnięcia pozycji w ruchów wykorzystania przestrzeni $n$ $n$ $n$

\exp (O (\sqrt{\log n})) = n^{O (1 / \sqrt{\log n})}

$\exp(O(\sqrt{\log n}))~=~n^{O(1/\sqrt{\log n})}$

Dowód. Schemat jest rekurencyjny, jak pokazano na poniższym rysunku. Używamy następującej notacji:

to liczba poziomów w rekurencji $k$
jest utworzonym rozwiązaniem (z poziomów rekurencji). $P(k)$ $k$
to maksymalna pozycja osiągnięta przez (w czasie ). $N(k)$ $P(k)$ $N(k)$
to przestrzeń używana przez . $S(k)$ $P(k)$
to liczbawarstwużywanych przez , jak pokazano poniżej: $L(k)$ $P(k)$

Na zdjęciu czas biegnie od góry do dołu. Rozwiązanie nie zatrzymuje się w czasie , zamiast tego (do zastosowania w rekurencji) trwa do czasu $P(k)$ $N(k)$ , dokładnie odwraca swoje ruchy, aby w czasie powrócić do jednego kamyka $2\,N(k)$ . $2\,N(k)$

Ciągłe pionowe linie dzielą warstwy . Na zdjęciu wynosi pięć, więc składa się z 5 warstw. Każda z warstw (oprócz skrajnie prawej) ma dwa podproblemy, jeden na górze warstwy i jeden na dole, połączone ciągłą pionową linią (reprezentującą kamyk, który istnieje dla ten czas trwania). Na zdjęciu jest pięć warstw, więc jest dziewięć podproblemów. Ogólnie $L(k)$ $P(k)$ $L(k)$ $P(k)$ $L(k)$ $P(k)$ składa się z $P(k)$ podproblemy. Każdy podproblem ma rozwiązanie . $2\,L(k)-1$ $P(k)$ $P(k-1)$

Kluczową obserwacją związaną z ograniczeniem przestrzeni jest to, że w dowolnym momencie tylko dwie warstwy mają „aktywne” podproblemy. Reszta składa się tylko z jednego kamyka

i $S(k) \le L(k) + 2\,S(k-1)$
$N(k) = L(k) \cdot N(k-1)$

$L(k)$ $P(k)$ $L(k) = 2^k$

$S(k) \le k\cdot 2^k$
$N(k) = 2^{k(k+1)/2}$

$n=N(k)$ $k \approx \sqrt {2 \log n}$ $S(k) \approx \sqrt {2 \log n}\, 2^{\sqrt {2 \log n}} = \exp(O(\sqrt{\log n}))$

$n$ $\{N(k) : k\in\{1,2,\ldots\}\}$ $n$ $P(k)$ $k$ $N(k)\ge n$ $S(k) / S(k-1) = O(1)$

$\delta>0$ $n$ $n$ $n^{1+\delta}$ $O(\delta 2^{1/\delta}\log n).$

Dowód. Zmodyfikuj konstrukcję z dowodu na Lemat 1, aby opóźnić rozpoczęcie każdego podproblemu do momentu zakończenia poprzedniego podproblemu, jak pokazano poniżej:

$T(k)$ $P(k)$

$S(k) \le L(k) + S(k-1)$
$N(k) = L(k) \cdot N(k-1)$
$T(k) = (2\,L(k)-1)\cdot T(k-1) \le 2\,L(k)\cdot T(k-1) \le 2^k N(k)$

$L(k) = 2^{1/\delta}$

$S(k) \le k 2^{1/\delta}$
$N(k) = 2^{k/\delta}$
$T(k) \le 2^k N(k)$

$S = S(k)$ $T=T(k)$ $n=N(k)$ $k=\delta \log n$

$S \le \delta 2^{1/\delta} \log n$
$T \le n^{1+\delta}$

$n$ $\{N(k) : k\in\{1,2,\ldots\}\}$ $n$ $P(k)$ $k$ $N(k)\ge n$ $S(k) / S(k-1) = O(1)$

$n$ $P(n)$ $n$ $k\le n/2$ $k$ $P(N-k)$ $k+1,k+2,\ldots,n$ $P(k)$ $1,2,\ldots,k$ $k$ $V(n)$ $n$ $\delta=1>0$

V (n) \geq min_{k < n} V (n - k) + max (n / 2, (1 + δ) V (k)) .

$V(n) \ge \min_{k<n} V(n-k) + \max(n/2, (1+\delta) V(k)).$

$n$

$\epsilon(n) = 1/\sqrt{\log n}$

$\delta>0$ $V(n) \ge n^{1+\Omega(\epsilon(n))}$

$n$ $t$ $n^{1+\Omega(\epsilon(n))}/t$

Lemat 1 jest ściśle związany ze stałymi czynnikami wykładnika (dla dobrze wychowanych rozwiązań).
$n$ $n\,\text{polylog}\, n$ $\text{polylog}\, n$ $n^{\Omega(\epsilon(n))} = \exp(\Omega(\sqrt{\log n})) \not\subseteq \,\text{polylog}\, n$

Szkic próbny. Pokazujemy gdzie dla pewnej wystarczająco małej stałej Zakładamy, że WLOG, że jest dowolnie duży, ponieważ przyjmując wystarczająco małe, możemy zapewnić dla dowolnego skończonego zestawu (używając tutaj, że , mówić). $2 V(n) \ge f(n)$ $f(n) = n^{1+c\epsilon(n)}$ $c.$ $n$ $c>0$ $2 V(n) \ge f(n)$ $n$ $V(n)\ge n$

Lemat będzie następował indukcyjnie od nawrotu, o ile dla wszystkich wystarczająco dużych mamy , to znaczy, dla $n$ $f(n) \le \min_{k<n} f(n-k) + \max(n, 2 f(k))$ $f(n) - f(n-k) \le \max(n, (1+\delta) f(k))$ $k<n.$

Ponieważ jest wypukły, mamy . Wystarczy więc, jeśli $f$ $f(n) - f(n-k) \le k f'(n)$ $k f'(n) \le \max(n, (1+\delta) f(k)).$

Według krótkiego obliczenia (używając i i przy zmianie zmiennych i ), nierówność ta jest równoważna z następującą: dla wszystkich odpowiednio dużych i , . Ponieważ oraz dla , wystarczy pokazać czyli $f(n)/n = e^{c\sqrt{\log n}}$ $f'(n)=(f(n)/n)(1+c/(2\sqrt{\log n})),$ $x = \sqrt{\log k}$ $y=\sqrt{\log n}$ $y$ $x\le y$ $e^{cy}(1+c/(2y)) \le \max(e^{y^2 - x^2}, (1+\delta) e^{cx})$ $1+z\le e^z$ $e^z\le 1+2z$ $z\le 1$ $e^{cy + c/(2y)} \le \max(e^{y^2 - x^2}, e^{2\delta+cx}),$

c y + c / (2 y) \leq max (y^{2} - x^{2}, 2 δ + c x) .

$cy + c/(2y) \le \max(y^2 - x^2, 2\delta+cx).$

Jeśli , to (dla dużego ) i gotowe, więc załóżmy . Następnie (dla dużego ), więc wystarczy pokazać Odnosi się to do wystarczająco małych i dużych CO BYŁO DO OKAZANIA $y \le x + 0.1\delta/c$ $cy+c/(2y) \le cx + 0.2\delta$ $y$ $y\ge x + 0.1\delta/c$ $y^2-x^2 \ge 0.1y\delta/c$ $y$

c y + c / (2 y) \leq 0.1 y δ / c .

$cy + c/(2y) \le 0.1 y\delta/c.$

c

$c$

y .

$y.$

— Neal Young
źródło

FWIW, mam dowód, że zawsze istnieje prawie optymalne, dobrze wychowane rozwiązanie, więc dolna granica w Lemma 3 dotyczy wszystkich rozwiązań. Wpisywanie tutaj jest trochę zbyt skomplikowane - jeśli ktoś jest zainteresowany, skontaktuj się ze mną przez e-mail (informacje kontaktowe znajdują się w Google „Neal Young Computer Science”).

— Neal Young