Perdu dans un concert «unidirectionnel»

16

Vous et un ami vous êtes perdus sur la ligne à un concert, et vous ne savez pas lequel d'entre vous est plus avancé. Formellement, chacun a une coordonnée entière et ne peut marcher que vers une coordonnée plus élevée ou rester en place.

En supposant que vous et votre ami suivez exactement le même algorithme (et non, vous ne pouvez pas dire "si (nom ==" R B ") faites quelque chose :)), et la distance initiale entre vous deux était (ce qui n'est pas que vous connaissez).x

Quel est l'algorithme qui minimise la distance de marche attendue jusqu'à ce que vous et votre ami vous rencontriez?


Vous pouvez supposer que votre ami et vous-même évoluez à la même vitesse constante.


Un exemple d'algorithme simple serait quelque chose comme:

  1. Au stade (à partir de 0 ):n0

    • Marcher pas à droite wp 13n ou attendre3nunités de temps autrement.123n

Pour voir cet algorithme, les amis rencontrent la probabilité 1 de considérer ce qui se passe au stade . Même si l'ami qui était x en avance marchait toujours et que l'autre restait toujours en place, la distance entre les deux serait: x + 1 + 3 + 9 + + 3 log 3 x = 2 x + x - 1(log3x+1)x

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

Par conséquent, à l' itération , l'ami qui choisit de marcher couvrira une distance de 3 log 3 x + 1 = 3 x , donc avec probabilité 1log3x+13log3x+1=3x , l'ami qui est derrière rattrapera son retard et se rencontrera.14


Une optimisation simple (pour réduire la distance de marche) serait, au lieu de marcher pas, marcher c x3xcx pas, où est donné par: 2 + 1c

2+1c1=c

D'où le c optimalc pour cet algorithme est c=3+522.618

Malheureusement, alors que cet algorithme garantit que les amis rencontreront la probabilité 1, la distance de marche attendue est infinie, ce que j'aimerais éviter si possible.

Existe-t-il un algorithme plus efficace?

RB
la source
Lorsque vous dites "distance de marche prévue" - voulez-vous dire dans le pire des cas, où l'algorithme est probabiliste, ou supposez-vous également une certaine distribution sur les entrées? Aussi - avez-vous besoin que votre algorithme soit toujours correct, ou qu'il soit correct wp 1? (ou moins?) - notez que l'algorithme que vous présentez ici pourrait ne jamais s'arrêter (mais wp 0)
Shaull
Ceci est similaire au problème de recherche linéaire ( en.wikipedia.org/wiki/Linear_search_problem ).
Yuval Filmus
2
@Shaull - puisque les deux amis suivent le même algorithme, il doit être probabiliste sinon ils ne se rencontreront jamais. L'espérance est supérieure à la randomisation de l'algorithme.
RB
Dans votre algorithme, voulez-vous dire marcher unité de temps vers la droite à vitesse constante C ? Marcher 2 n pas peut ne pas parler 2 ^ n fois. 2nC2n
吖 奇 说 ARCHY SHUō
@ 0a-archy - nous supposons que les deux se déplacent à la même vitesse (que ce soit 1 à cet égard). L'idée dans l'algorithme que j'ai donné est que vous marchez2npas ou attendez un temps équivalent, donc chaque itération commence en même temps pour les deux joueurs. steptime unit2n
RB

Réponses:

4

À l'étape , tracez un nombre aléatoire q uniformément entre 1 , 2 et 3kq123 .

  • si , marcher 2 k - 1 , attendre 2q=12k1 , marcher 2 k2k+12k1
  • si , attendre 2 k - 1 , marcher 2 k - 1 , attendre 2 k - marcherq=22k12k12k , attendez 2 k - 12k12k1
  • si , attendez 2q=3 , marcher 2 k , attendre 2 k2k2k2k

À chaque étape , les deux amis marcheront 2 k étapes. Si k < log 2 ( x ) + 1 , ils ne se rencontreront pas pendant cette étape, cependant si k > = log 2 ( x ) + 1 , ils se rencontreront si et seulement s'ils ne tirent pas le même nombre. La probabilité que cela ne se produise pas n'est que de 1 /k2kk<log2(x)+1k>=log2(x)+1 à chaque étape.1/3

Par conséquent, la distance de marche attendue est (délimitée ci-dessus par):

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

Ce qui est fini, et égal, si mes mathématiques de serviette sont fiables, à .2log2(x)+3216x

Soit dit en passant, si est la variable aléatoire représentant la distance parcourue, nous avons toujours que D > 0 , P ( d > D ) > 0 , c'est-à-dire que la distance est illimitée et peut finir par être arbitrairement élevée. Heureusement, cette probabilité disparaît assez rapidement pour garantir que la somme infinie D = 0 P ( d = D ) D = E [ d ] converge. Ayant une limite supérieure finie pour ddD>0,P(d>D)>0D=0P(d=D)D=E[d]d est une propriété beaucoup plus solide et je pense qu'il n'est pas possible de trouver une solution satisfaisante.

David Durrleman
la source