Algorithme pour chasser une cible en mouvement

Supposons que nous ayons une boîte noire que nous pouvons interroger et réinitialiser. Lorsque nous réinitialisons , l'état de est défini sur un élément choisi uniformément au hasard dans l'ensemble où est fixe et connu pour donné . Pour interroger , un élément (la supposition) de est fourni, et la valeur renvoyée est . De plus, l'état f_S de f est réglé sur une valeur f_S '= f_S \ pm k , où k est sélectionné uniformément au hasard parmi$f$$f$$f_S$$f$

En faisant des suppositions uniformément aléatoires avec chaque requête, on s'attendrait à devoir faire $n$ suppositions avant d'obtenir $f_S = x$ , avec la variance $n^2 - n$ (indiqué sans preuve).

Un algorithme peut-il être conçu pour faire mieux (c.-à-d. Faire moins de suppositions, éventuellement avec moins de variance dans le nombre de suppositions)? Que pourrait-il faire de mieux (c.-à-d. Qu'est-ce qu'un algorithme optimal et quelles sont ses performances)?

Une solution efficace à ce problème pourrait avoir d'importantes implications en termes de réduction des coûts pour tirer sur un lapin (confiné au saut sur une piste circulaire) dans une pièce sombre.

Tout d'abord, je suppose que par

De plus, l'état $f_S$ de $f$ est défini sur une valeur $f_S' = f_S \pm k$ , où $k$ est sélectionné uniformément au hasard parmi

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

tu veux dire

De plus, l'état de est défini sur une valeur , où est sélectionné uniformément au hasard dans$f_S$$f$$f_S' = f_S + k \mod n$$k$

$$\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\}$$

Sinon, il n'est pas tout à fait clair que est toujours valable et comment exactement se comporte.$f_S \in \{ 0, ..., n-1\}$$f_S \pm k$

En utilisant cela, le problème se résume à "manquer autant que possible". Observez que plus nous tirons sur le lapin de près, plus le houblon qu'il fait est gros; dans le cas extrême, nous avons . Il en résulte un saut uniforme entre et , ce qui, fondamentalement, randomise à nouveau complètement la position du lapin. D'un autre côté, si nous manquons le plus mal possible - par un décalage de , le lapin ne bouge pas du tout (!) Et la boîte noire nous met à jour sur ce fait. Par conséquent, nous pouvons simplement nous retourner et tirer sur le lapin.$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$

Il nous reste à trouver une procédure pour manquer de plus en plus à chaque coup. Je propose une simple "recherche binaire". (Je vais commodément omettre l'arrondi.) Il se déroule approximativement comme suit:

1. Réinitialisez et tirez à une position arbitraire jusqu'à ce que vous obteniez de la la réponseCela prend une quantité constante d'étapes dans l'attente.$(f_S - x \mod n) \in \{ \frac{1}{4}n, ..., \frac{3}{4}n\}.$
2. Maintenant, nous savons que la position passée du lapin , et qu'il n'a pas bougé de plus de pas dans les deux sens. Cela divise par deux notre espace de recherche dans la prochaine itération, car le lapin doit être à une position$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 \}$
3. Recurse: tirer à la position . Avec la probabilité , la position le lapin a sauté aux étapes 1 et 2 se situe dans la plage . Dans ce cas, nous avons réduit de moitié l'espace de recherche. Avec la probabilité , le lapin n'a pas sauté dans cette plage, mais puisque nous savons que , nous avons les mêmes hypothèses qu'à l'étape (2) et donc ne rien perdre.$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 \}$

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