Algorithme pour chasser une cible en mouvement

20

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 parmifffSf

{0,1,...,n1}
nffx
{0,1,...,n1}
(fSx)modnfSffS=fS±kk
{0,1,2,...,n/2((fSx)modn)}

En faisant des suppositions uniformément aléatoires avec chaque requête, on s'attendrait à devoir faire n suppositions avant d'obtenir fS=x , avec la variance n2n (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.

Patrick87
la source
Je ne sais pas si tirer sur des lapins est de l'informatique.
Dave Clarke
6
@DaveClarke Mais si vous pouvez tirer sur des lapins, vous avez résolu le problème de l'arrêt des lapins.
Patrick87
@DaveClarke Ni ne tire des satellites dans l'espace, mais le calcul de la position du satellite l'est. Cette question n'est pas totalement différente de la cryptanalyse.
Gilles 'SO- arrête d'être méchant'

Réponses:

13

Tout d'abord, je suppose que par

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

{0,1,2,...,n/2((fSx)modn)}

tu veux dire

De plus, l'état de est défini sur une valeur , où est sélectionné uniformément au hasard dansfSffS=fS+kmodnk

{|n2((fSx)modn)|,,1,0,1,2,,|n2((fSx)modn)|}

Sinon, il n'est pas tout à fait clair que est toujours valable et comment exactement se comporte.fS{0,...,n1}fS±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.fSx=±1modn(n/2±1)(n/2±1)fSxmodn=n/2

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.(fSxmodn){14n,...,34n}.
  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 positionfS14nfS{(fS14n)modn,...,fS,...,(fS+14n)modn}
  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.fSn/2modn1/2fS{fS18n,...,fS,...,fS+18n}1/2fSxmodn=fSfS+n/2modn{12n14n,...,12n+14n}

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=O(1)O(logn)

HdM
la source