Optimización del número de robots a utilizar para una determinada tarea

Question

Tenemos $N$ botones numerados $1$ , $2$ .. $N$ . Nuestro objetivo es pulsar cada uno de los botones al menos una vez en el mínimo tiempo posible. Para ello elegimos $m$ robots. Estos robots pueden pulsar uno de los botones en cada segundo. Pero cuando dos o más robots intentan pulsar el mismo botón al mismo tiempo, ese botón no será pulsado (los robots sabrán que el botón no pudo ser pulsado). Con la restricción de que todos los robots estén codificados de forma idéntica (es decir, que ejecuten las mismas instrucciones), ¿qué valor de $m$ ¿elegirás y cómo los codificarás?

Por ejemplo, si elegimos $m=1$ y ordenar al robot que pulse la tecla $i$ en el botón $i$ segundo, tomará un total de $N$ segundos antes de pulsar todos los botones. Si elegimos $m=2$ y ordenar a los robots que pulsen el botón $1$ o $2$ uniformemente al azar hasta que hayan pulsado con éxito uno de ellos (si uno de ellos tiene éxito al pulsar uno, entonces el otro tiene éxito automáticamente al pulsar el otro), y luego pulsar secuencialmente cada uno de los otros botones (por ejemplo, si el robot tuvo éxito al pulsar el botón $1$ Entonces intentará (con éxito) pulsar los botones numerados $3$ , $5$ en los próximos segundos), entonces tomará un tiempo promedio de $2+\frac{N-2}{2}$ segundos antes de pulsar cada botón.

Answer 1

Para los pequeños $N$ En el caso de los algoritmos, los detalles del algoritmo óptimo parecen ser complicados; probablemente la mejor manera de determinarlos es mediante programación dinámica. Sin embargo, para grandes $N$ el siguiente algoritmo cubre todos los botones de $3$ segundos asintóticamente casi seguro .

Tome un número muy grande de robots, es decir $m\gg N$ y que pulsen cualquiera de los botones con probabilidad $p=1/m$ cada uno, y ningún botón con probabilidad $1-Np=1-N/m$ . (Esta última probabilidad es no negativa ya que $m\gg N$ .) La probabilidad de que un botón concreto se pulse exactamente una vez, y por tanto la fracción esperada de botones que se pulsan exactamente una vez, es

$$ mp(1-p)^{m-1}=m\cdot\frac1m\left(1-\frac1m\right)^{m-1}=\left(1-\frac1m\right)^{m-1}\to_{m\to\infty}\frac1{\mathrm e}\;. $$

Para los grandes $N$ la distribución tiene un pico muy pronunciado en torno a este valor esperado, por lo que es casi seguro que la fracción de botones pulsados con éxito sea mayor que $1/3$ . Ahora deja que los robots que han pulsado con éxito un botón pulsen otros botones según algún esquema predefinido. (Por ejemplo, deja que los robots planifiquen sus acciones actuando virtualmente en sucesión en el orden de los números de los botones que pulsaron en el primer segundo, y deja que cada robot pulse el botón con el número más bajo que no haya sido pulsado ni en un segundo anterior ni en un paso de planificación anterior).