Algorithme pour chasser une cible mouvante

Question

Supposons que nous ayons une boîte noire $-f $ que nous pouvons interroger et réinitialiser. Lorsque nous remettons à zéro $ f $, l'état de F_S $ $ de $ f $ est fixé à un élément choisi uniformément au hasard dans l'ensemble $$ \ {0, 1, ..., n - 1 \} $$ où $ n $ est fixé et connu pour donné $ f $. Pour requête $ f $, un élément $ x $ (l'estimation) de $$ \ {0, 1, ..., n - 1 \} $$ est fourni, et la valeur retournée est $ (F_S - x) \ mod n $. En outre, l'état f_s de $ $ de $ F $ est réglée à une valeur f_s de $ »= f_s \ pm $ k, où est choisi $ $ k uniformément au hasard dans $$ \ {0, 1, 2, ..., \ lfloor n / 2 \ rfloor - ((f_s - x) \ mod n) \} $$

En faisant des suppositions uniformément aléatoires à chaque requête, on pourrait attendre d'avoir à faire des suppositions $ n $ avant d'obtenir $ F_S = x $, avec une variance $ n ^ 2 -. N $ (déclaré sans preuve)

peut-être un algorithme conçu pour faire mieux (à savoir, faire moins de suppositions, peut-être avec moins de variance du nombre de suppositions)? Combien pourrait-il mieux faire (à savoir, ce qui est un algorithme optimal, et quelle est sa performance)?

Une solution efficace à ce problème pourrait avoir d'importantes conséquences de réduction des coûts pour le tir à un lapin (limité à sauter sur une piste circulaire) dans une pièce sombre.

Answer 1

Tout d'abord, je suppose que par

  

En outre, l'état f_s de $ $ de $ F $ est réglée à une valeur f_s de $ »= f_s \ h k $, où est choisi $ $ k uniformément au hasard dans $$ \ {0, 1, 2,. .., \ n lfloor / 2 \ rfloor - ((f_S - x) \ n mod) \} $$

vous dire en fait

  

En outre, l'état f_s de $ $ de $ f $ est réglée à une valeur f_s de $ »= f_s + k \ mod n $, où est choisi $ $ k uniformément au hasard dans $$ \ ex \ {- \ 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) \ n mod) \ right | \ right \} $$

Dans le cas contraire, il est pas tout à fait clair que F_S $ \ in \ {0, ..., n-1 \} $ tient toujours et comment exactement $ F_S PM k $ de les se comporte.

Avec cela, le problème se résume à « manque autant que possible ». Observons que plus on tire le lapin, les plus grands bonds qu'il fait; dans le cas extrême, nous avons $ F_S - x = \ pm 1 \ mod n $. Il en résulte un saut uniforme entre $ - (\ lfloor n / 2 \ rfloor \ pm 1) $ et $ (\ lfloor n / 2 \ rfloor \ pm 1) $, ce qui randomizes essentiellement complètement la position du lapin à nouveau. D'autre part, si nous manquons aussi mal que possible - par un décalage de $ F_S - (!) X \ mod n = \ lfloor n / 2 \ rfloor $, le lapin ne fait bouge pas du tout et la boîte noire nous met à jour en fait sur ce fait. Par conséquent, nous pouvons simplement tourner autour et tirer le lapin.

Il nous reste à trouver une procédure pour manque de plus en plus chaque tir. Je propose un simple « recherche binaire ». (Je pratique omettre l'arrondissement.) Il procède à peu près comme suit:

1. Reset et tirer à une position arbitraire jusqu'à ce que vous obtenez de la Blackbox $ la réponse (F_S - x \ mod n) \ in \ {\ frac {1} {4} n, ..., \ frac {3} {4} n \}. $ Cela prend une quantité constante d'étapes dans l'attente.
2. Maintenant, nous savons que la position passée de lapin $ F_S $, et qu'il ne bougeait pas plus de $ \ frac {1} {4} n étapes $ dans les deux sens. Ce diminue de moitié notre espace de recherche dans la prochaine itération, puisque le lapin doit être à une position F_S de $ » \ in \ {(F_S - \ frac {1} {4} n) \ n mod, ..., F_S, ..., (f_S + \ frac {1} {4} n) \ n mod \} $
3. Recurse: Pousse à la position de F_S $ - n / 2 \ $ mod n. Avec une probabilité de 1 $ / 2 $, le lapin $ 'la position F_S de $ a sauté sur l'étape 1 et 2 se situe la plage $ \ {F_S - \ frac {1} {8} n, ..., F_S, ..., F_S + \ frac {1} {8} n \} $. Dans ce cas, nous réduit de moitié l'espace de recherche une fois de plus. Avec une probabilité de 1/2 $, le lapin n'a pas sauté dans cette gamme, mais puisque nous savons que F_S de $ '- x \ mod n = F_S' - F_S + n / 2 \ n mod \ dans \ {\ frac {1} {2} n - \ frac {1} {4} n, ..., \ frac {1} {2} n + \ frac {1} {4} n \} $, nous avons les mêmes hypothèses que dans l'étape (2) et donc rien perdre.

Chaque étape a besoin $ 2 = \ mathcal {O} (1) $ temps prévu pour réussir et demi l'espace de recherche, ce qui donne un ensemble de $ \ mathcal {O} (\ log n) $ nombre prévu d'étapes.