Supongamos que tenemos un cuadro negro que podemos consultar y restablecer. Cuando reiniciamos , el estado de se establece en un elemento elegido de manera uniforme al azar a partir del conjunto
Al hacer conjeturas uniformemente al azar con cada consulta, uno esperaría tener que hacer conjeturas antes de obtener , con una varianza (indicada sin prueba).
¿Se puede diseñar un algoritmo para que funcione mejor (es decir, hacer menos conjeturas, posiblemente con menos variación en el número de conjeturas)? ¿Cuánto podría mejorar (es decir, qué es un algoritmo óptimo y cuál es su rendimiento)?
Una solución eficiente a este problema podría tener importantes implicaciones de ahorro de costos para disparar a un conejo (confinado a saltar en una pista circular) en una habitación oscura.
Respuestas:
En primer lugar, supondré que por
en realidad quieres decir
De lo contrario, no está del todo claro que siempre se cumple y cómo se exactamente .fS∈{0,...,n−1} fS±k
Usando esto, el problema básicamente se reduce a "faltar tanto como sea posible". Observe que cuanto más cerca disparamos al conejo, más grandes saltos hace; en el caso extremo tenemos . Esto da como resultado un salto uniforme entre y , que básicamente aleatoriza completamente la posición del conejo nuevamente. Por otro lado, si tanto como sea posible, por un desplazamiento de , el conejo en realidad no se mueve en absoluto (!) Y el cuadro negro realmente nos actualiza en este hecho Por lo tanto, podemos dar la vuelta y disparar al conejo.fS−x=±1modn −(⌊n/2⌋±1) (⌊n/2⌋±1) fS−xmodn=⌊n/2⌋
Nos queda encontrar un procedimiento para fallar cada vez más en cada disparo. Propongo una simple "búsqueda binaria". (Omitiré convenientemente el redondeo). Se realiza aproximadamente de la siguiente manera:
Cada paso necesita tiempo esperado para tener éxito y reduce a la mitad el espacio de búsqueda, produciendo un total de número esperado de pasos.2=O(1) O(logn)
fuente