Algoritma untuk mengejar target yang bergerak

Misalkan kita memiliki kotak hitam yang dapat kita query dan reset. Ketika kita mereset , keadaan dari diatur ke elemen yang dipilih secara acak dari himpunan mana diperbaiki dan dikenal untuk diberikan . Untuk permintaan , elemen (tebakan) dari disediakan, dan nilai yang dikembalikan adalah . Selain itu, keadaan dari diatur ke nilai , di mana dipilih secara seragam secara acak dari $f$ $f$ $f_S$ $f$

{0, 1, . . ., n - 1}

$\{0, 1, ..., n - 1\}$

n

$n$

f

$f$

f

$f$

x

$x$

{0, 1, . . ., n - 1}

$\{0, 1, ..., n - 1\}$

(f_{S} - x) \mod n

$(f_S - x) \mod n$

f_{S}

$f_S$

f

$f$

f_{S}^{'} = f_{S} \pm k

$f_S' = f_S \pm k$

k

$k$

{0, 1, 2, . . ., ⌊ n / 2 ⌋ - ((f_{S} - x) \mod n)}

$\{0, 1, 2, ..., \lfloor n/2 \rfloor - ((f_S - x) \mod n)\}$

Dengan membuat tebakan acak seragam dengan setiap kueri, orang akan berharap harus membuat $n$ tebakan sebelum mendapatkan $f_S = x$ , dengan varian $n^2 - n$ (dinyatakan tanpa bukti).

Dapatkah suatu algoritma dirancang untuk melakukan yang lebih baik (yaitu, membuat lebih sedikit tebakan, mungkin dengan lebih sedikit variasi dalam jumlah tebakan)? Seberapa jauh lebih baik yang bisa dilakukannya (yaitu, apa algoritma yang optimal, dan apa kinerjanya)?

Solusi yang efisien untuk masalah ini bisa memiliki implikasi penghematan biaya yang penting untuk menembak kelinci (terbatas pada melompat di trek melingkar) di ruangan gelap.

algorithms probability-theory randomized-algorithms Patrick87
sumber

Saya tidak yakin apakah menembak kelinci adalah ilmu komputer.

Dave Clarke

@DaveClarke Tetapi jika Anda bisa menembak kelinci, Anda telah memecahkan masalah penghentian untuk kelinci.

Patrick87

@DaveClarke Tidak ada yang menembak satelit ke ruang angkasa, tetapi perhitungan posisi satelit adalah. Pertanyaan ini tidak sepenuhnya berbeda dengan cryptanalysis.

Gilles 'SO- berhenti bersikap jahat'

Jawaban:

Pertama-tama, saya akan menganggap itu dengan

Selain itu, status dari diatur ke nilai , di mana dipilih seragam secara acak dari $f_S$ $f$ $f_S' = f_S \pm k$ $k$
${0, 1, 2, . . ., ⌊ n / 2 ⌋ - ((f_{S} - x) \mod n)}$ $\{0, 1, 2, ..., \lfloor n/2 \rfloor - ((f_S - x) \mod n)\}$

maksudmu sebenarnya

Selain itu, negara dari diatur ke nilai $f_S$ $f$ , di mana dipilih secara seragam secara acak dari $f_S' = f_S + k \mod n$ $k$
${- | ⌊ \frac{n}{2} ⌋ - ((f_{S} - x) \mod n) |, ..., - 1, 0, 1, 2, ..., | ⌊ \frac{n}{2} ⌋ - ((f_{S} - x) \mod n) |}$ $\left\{- \left| \left\lfloor \frac{n}{2} \right\rfloor - ((f_S - x) \mod n) \right|, \ldots, -1, 0, 1, 2, \ldots, \left| \left\lfloor \frac{n}{2} \right\rfloor - ((f_S - x) \mod n) \right|\right\}$

$f_S \in \{ 0, ..., n-1\}$ $f_S \pm k$

$f_S - x = \pm 1 \mod n$ $-(\lfloor n/2 \rfloor \pm 1)$ $(\lfloor n/2 \rfloor \pm 1)$ $f_S - x \mod n = \lfloor n/2 \rfloor$

Kami dibiarkan menemukan prosedur untuk kehilangan semakin dalam setiap tembakan. Saya mengusulkan "pencarian biner" sederhana. (Saya akan dengan mudah menghilangkan pembulatan.) Ini menghasilkan kira-kira sebagai berikut:

$(f_S - x \mod n) \in \{ \frac{1}{4}n, ..., \frac{3}{4}n\}.$
$f_S$ $\frac{1}{4}n$ $f_S' \in \{ (f_S - \frac{1}{4}n) \mod n, ..., f_S, ..., (f_S + \frac{1}{4}n) \mod n \}$
$f_S - n/2 \mod n$ $1/2$ $f_S'$ $\{ f_S - \frac{1}{8}n, ..., f_S, ..., f_S + \frac{1}{8}n \}$ $1/2$ $f_S' - x \mod n = f_S' - f_S + n/2 \mod n \in \{ \frac{1}{2}n - \frac{1}{4}n, ..., \frac{1}{2}n + \frac{1}{4}n \}$

$2 = \mathcal{O}(1)$ $\mathcal{O}(\log n)$

HdM
sumber