Algoritmo para perseguir um alvo em movimento

20

Suponha que tenhamos uma caixa preta f que possamos consultar e redefinir. Quando redefinimos f , o estado de é definido como um elemento escolhido uniformemente aleatoriamente no conjunto que é fixo e conhecido pelo dado . Para consulta , um elemento x (a suposição) de { 0 , 1 , . . . , n - 1 } é fornecido e o valor retornado é . Além disso, o estado de f { 0 , 1 , . . . , n - 1 } n f ffSf

{0 0,1,...,n-1}
nffx
{0 0,1,...,n-1}
(fS-x)modnfSf é definido como um valor , em que é selecionado uniformemente aleatoriamente entrefS=fS±kk
{0,1,2,...,n/2((fSx)modn)}

Fazendo suposições uniformemente aleatórias com cada consulta, seria de esperar que antes de obter , com variação (declarada sem prova).f S = x n 2 - nnfS=xn2n

Um algoritmo pode ser projetado para fazer melhor (ou seja, fazer menos suposições, possivelmente com menos variação no número de suposições)? Quanto melhor ele poderia fazer (ou seja, qual é o algoritmo ideal e qual é o seu desempenho)?

Uma solução eficiente para esse problema pode ter implicações importantes na redução de custos para fotografar um coelho (confinado a pular em uma pista circular) em um quarto escuro.

Patrick87
fonte
Não sei se atirar coelhos é ciência da computação.
Dave Clarke
6
@DaveClarke Mas se você pode atirar em coelhos, você resolveu o problema da parada de coelhos.
precisa saber é o seguinte
@DaveClarke Nem está atirando satélites no espaço, mas o cálculo da posição do satélite é. Esta questão não é totalmente diferente da criptoanálise.
Gilles 'SO- stop be evil'

Respostas:

13

Antes de tudo, vou assumir que, ao

Além disso, o estado de f é definido como um valor f S = f S ± kfSffS=fS±k , onde é seleccionada de modo uniforme de forma aleatória a partir de { 0 , 1 , 2 , . . . , n / 2 - ( ( f S - x )k

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

você realmente quer dizer

Além disso, o estado de f é definido como um valor f S = f S + kfSf , onde k é selecionado uniformemente aleatoriamente de { - | nfS=fS+kmodnk

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

Caso contrário, não está totalmente claro que fS{0,...,n-1}fS±k

fS-x=±1modn-(n/2±1)(n/2±1)fSxmodn=n/2

Nos resta encontrar um procedimento para perder cada vez mais a cada tiro. Eu proponho uma simples "pesquisa binária". (Eu omitirei convenientemente o arredondamento.) Ele ocorre aproximadamente da seguinte maneira:

  1. (fSxmodn){14n,...,34n}.
  2. fS14nfS{(fS14n)modn,...,fS,...,(fS+14n)modn}
  3. fSn/2modn1/2fS{fS18n,...,fS,...,fS+18n}1/2fSxmodn=fSfS+n/2modn{12n14n,...,12n+14n}

2=O(1)O(logn)

HdM
fonte