Perdido em um concerto "unidirecional"

16

Você e um amigo se perderam na fila para um concerto, e nenhum deles tem certeza de qual deles está mais à frente. Formalmente, cada um está em alguma coordenada inteira e só pode caminhar em direção a uma coordenada mais alta ou permanecer no local.

Supondo que você e seu amigo estejam seguindo exatamente o mesmo algoritmo (e não, você não pode dizer "if (name ==" R B ") faça algo :)), e a distância inicial entre vocês dois foi (que não é conhecido por você).x

Qual é o algoritmo que minimiza a curta distância esperada até você e seu amigo se encontrarem?


Você pode assumir que seu amigo e você estão se movendo na mesma velocidade constante.


Um exemplo de algoritmo simples seria algo como:

  1. No estágio (a partir de ):0n0

    • Ande etapas para a direita wp ou aguarde unidades de tempo.13n 3n123n

Para ver esse algoritmo faz com que os amigos se encontrem com probabilidade 1, considere o que acontece no estágio . Mesmo que o amigo que estava passo à frente sempre andasse e o outro sempre estivesse no lugar, a distância entre os dois seria: x x + 1 + 3 + 9 + + 3 log 3 x = 2 x + x - 1(log3x+1)x

x+1+3+9++3log3x=2x+x123x

Portanto, na , o amigo que escolher andar percorrerá a distância de , portanto, com probabilidade , o amigo que está por trás alcançará e eles se encontrarão.3 log 3 x + 1 = 3 x 1log3x+13log3x+1=3x14


Uma otimização simples (para reduzir a distância a pé) seria, em vez de andar etapas, andar etapas, em que é dada por: c x c 2 + 13xcxc

2+1c1=c

Portanto, o ideal para esse algoritmo éc c=3+522.618

Infelizmente, embora esse algoritmo garanta que os amigos encontrarão a probabilidade 1, a distância esperada é infinita, o que é algo que eu gostaria de evitar, se possível.

Existe um algoritmo mais eficiente?

RB
fonte
Quando você diz "distância esperada a pé" - você quer dizer, na pior das hipóteses, onde o algoritmo é probabilístico, ou também assume alguma distribuição nas entradas? Além disso - você exige que seu algoritmo esteja sempre correto ou esteja correto wp 1? (ou menos?) - note que o algoritmo que apresentamos aqui pode nunca mais parou (mas wp 0)
Shaull
Isso é semelhante ao problema de pesquisa linear ( en.wikipedia.org/wiki/Linear_search_problem ).
Yuval Filmus
2
@ Shaull - como os dois amigos estão seguindo o mesmo algoritmo, ele deve ser probabilístico ou eles nunca se encontrarão. A expectativa é superior à randomização do algoritmo.
RB
No seu algoritmo, você quer dizer andar unidade de tempo para a direita com velocidade constante C ? Andar 2 n passos pode não falar 2 ^ n tempo. 2nC2n
说 奇 说 ARCHY SHUō
@ 0a-archy - assumimos que ambos estão se movendo na mesma velocidade (seja 1 para este assunto). A idéia no algoritmo que dei é que você caminha2netapas ou espera um tempo equivalente, para que cada iteração comece ao mesmo tempo para os dois jogadores. degrauunidade de tempo2n
RB

Respostas:

4

Na etapa , desenhe um número aleatório q uniformemente entre 1 , 2 e 3 .kq123

  • se , ande 2 k - 1 , espere 2 k + 1 , ande 2 k - 1q=12k-12k+12k-1
  • se , espere 2 k - 1 , ande 2 k - 1 , espere 2 k , ande 2 k - 1 , espere 2 k - 1q=22k-12k-12k2k-12k-1
  • se , aguarde 2 k , caminhe 2 k , aguarde 2 kq=32k2k2k

A cada passo , os dois amigos andam 2 k passos. Se k < log 2 ( x ) + 1 , eles não se encontrarão durante essa etapa; no entanto, se k > = log 2 ( x ) + 1 , eles se encontrarão se e somente se não desenharem o mesmo número. A probabilidade de que isso não acontece apenas 1 / 3 em cada etapa.k2kk<registro2(x)+1k> =registro2(x)+11/3

Portanto, a distância a pé esperada é (delimitada acima por):

2(k=0 0registro2(x)2k+3registro2(x)k=registro2(x)+1(23)k)

Qual é finito e igual, se minha matemática de guardanapo é confiável, para .2registro2(x)+3-216x

dD>0 0,P(d>D)>0 0D=0 0P(d=D)D=E[d]d é uma propriedade muito mais forte e acho que não é possível encontrar uma solução que a satisfaça.

David Durrleman
fonte