Zagubiony w „jednokierunkowym” koncercie

Ty i przyjaciel zgubiliście się na linii na koncercie, i żaden nie jest pewien, który z was jest dalej. Formalnie każda z nich ma jakąś całkowitą współrzędną i może podążać w kierunku wyższej współrzędnej lub pozostać na miejscu.

Zakładając, że ty i twój przyjaciel przestrzegacie dokładnie tego samego algorytmu (i nie, nie można powiedzieć „jeśli (name ==" R B ”) zrób coś :)), a początkowa odległość między wami wynosiła (co nie jest znane tobie). $x$

Jaki jest algorytm, który minimalizuje oczekiwany dystans pieszy do spotkania się ciebie i twojego przyjaciela?

Możesz założyć, że zarówno twój przyjaciel, jak i ty poruszamy się z tą samą stałą prędkością.

Przykładowy prosty algorytm mógłby wyglądać następująco:

Na etapie (od ): $n$ $0$

Przejdź kroków w prawo wp $3^n$ lub poczekajjednostek czasu inaczej. $\frac{1}{2}$ $3^n$

Aby zobaczyć ten algorytm, przyjaciele spotykają się z prawdopodobieństwem 1 zastanów się, co dzieje się na etapie . Nawet jeśli przyjaciel, który był krok do przodu zawsze chodził, a drugi zawsze pozostawał na miejscu, odległość między nimi byłaby: $(\log_3 x+1)$ $x$

x + 1 + 3 + 9 + \dots + 3^{\log_{3} x} = 2 x + \frac{x - 1}{2} \leq 3 x

$x+1+3+9+\ldots+3^{\log_3 x}=2x+\frac{x-1}{2}\leq 3x$

Dlatego przy iteracji przyjaciel, który zdecyduje się przejść, pokona odległość , stąd z prawdopodobieństwem $\log_3 x+1$ $3^{\log_3 x+1}=3x$ , przyjaciel, który jest z tyłu, dogoni i spotka się. $\frac{1}{4}$

Prostą optymalizacją (w celu zmniejszenia odległości chodzenia) byłoby, zamiast chodzenia kroków, chodzenie kroków, gdzie jest podane przez: $3^x$ $c^x$ $c$

2 + \frac{1}{c - 1} = c

$2+\frac{1}{c-1}=c$

Dlatego optymalnym dla tego algorytmu jest $c$ $c=\frac{3+\sqrt 5}{2}\approx 2.618$

Niestety, podczas gdy ten algorytm gwarantuje, że znajomi spotkają się z prawdopodobieństwem 1, oczekiwany dystans marszu jest nieskończony, czego chciałbym uniknąć, jeśli to możliwe.

Czy istnieje bardziej wydajny algorytm?

algorithms randomized-algorithms

— RB
źródło

Kiedy mówisz „oczekiwany dystans marszu” - czy masz na myśli w najgorszym przypadku, gdy algorytm jest probabilistyczny, czy też zakładasz pewien rozkład na wejściach? Ponadto - czy wymagasz, aby algorytm był zawsze poprawny, czy poprawny wp 1? (lub mniej?) - zwróć uwagę, że algorytm, który tu prezentujesz, może nigdy nie zostać zatrzymany (ale wp 0)

— Shaull

Jest to podobne do problemu wyszukiwania liniowego ( en.wikipedia.org/wiki/Linear_search_problem ).

— Yuval Filmus

@Shaull - ponieważ obaj przyjaciele stosują ten sam algorytm, musi być probabilistyczny, inaczej nigdy się nie spotkają. Oczekiwanie jest ponad randomizacją algorytmu.

— RB

Czy w twoim algorytmie masz na myśli przejście

jednostki czasu w prawo przy stałej prędkości

? Chodzenie

krokami może nie mówić 2 razy.

2^{n}

$2^n$

C

$C$

2^{n}

$2^n$

— 吖奇说 ARCHIA SHUō

@ 0a-archy - zakładamy, że oba poruszają się z tą samą prędkością (niech będzie to 1

dla tej sprawy). Pomysł w algorytmie Dałem to, że albo chodzić

kroków lub czekać równoważnego czasu, więc każdy startów iteracji jednocześnie dla obu graczy.

\frac{step}{time unit}

$\frac{\text{step}}{\text{time unit}}$

2^{n}

$2^n$

— RB

W kroku narysuj losowo liczbę równomiernie między , i . $k$ $q$ $1$ $2$ $3$

jeśli , przejdź , poczekaj , przejdź $q = 1$ $2^{k-1}$ $2^{k+1}$ $2^{k-1}$

jeśli , poczekaj , przejdź , poczekaj , przejdź , poczekaj $q = 2$ $2^{k-1}$ $2^{k-1}$ $2^{k}$ $2^{k-1}$ $2^{k-1}$

jeśli , poczekaj , przejdź , poczekaj $q = 3$ $2^k$ $2^k$ $2^k$

Na każdym kroku obaj przyjaciele przejdą kroków. Jeśli , nie spotkają się podczas tego kroku, jednak jeśli , spotkają się wtedy i tylko wtedy, gdy nie narysują tego samego numeru. Prawdopodobieństwo, że to nie zdarza się to tylko na każdym kroku. $k$ $2^k$ $k < \log_2(x) + 1$ $k >= \log_2(x) + 1$ $1/3$

Dlatego oczekiwany dystans marszu jest (ograniczony powyżej):

2 (\sum_{k = 0}^{⌈ \log_{2} (x) ⌉} 2^{k} + 3^{⌈ \log_{2} (x) ⌉} \sum_{k = ⌈ \log_{2} (x) ⌉ + 1}^{\infty} {(\frac{2}{3})}^{k})

$2\left(\sum_{k=0}^{\lceil\log_2(x)\rceil}2^k+3^{\lceil\log_2(x)\rceil}\sum_{k=\lceil\log_2(x)\rceil+1}^{\infty}\left(\frac{2}{3}\right)^k\right)$

Który jest skończony i równy, jeśli mam zaufać mojej matematyce , do . $2^{\lceil\log_2(x)\rceil+3}-2 \le 16x$

Nawiasem mówiąc, jeśli jest zmienną losową reprezentującą przebytą odległość, nadal mamy to , tj. Odległość jest nieograniczona i może być dowolnie wysoka. Na szczęście prawdopodobieństwo to zanika wystarczająco szybko, aby zapewnić, że nieskończona suma zbiega się. Posiadanie skończonej górnej granicy dla $d$ $\forall D>0, \mathrm{P}(d>D) > 0$ $\sum_{D=0}^{\infty}\mathrm{P}(d=D)\cdot D = \mathbb{E}[d]$ $d$ jest znacznie silniejszą własnością i uważam, że nie jest możliwe znalezienie rozwiązania, które by to spełniło.

— David Durrleman
źródło