Ascensores y algoritmos

Nuestro ascensor bala de la semana pasada no debería, por el bien de sus ocupantes, acelerar a 10 m/s² hasta la mitad de su recorrido y, por tanto, la respuesta del segundo visitante es muy razonable, porque, como señala Marina Puente:

“La deceleración no puede ser mayor que la gravedad (9,8 m/s²) porque los pasajeros perderían el contacto con el suelo del ascensor. Por tanto, la velocidad máxima debería darse antes del piso 100″.

En cuanto al ascensor de Gamow, a primera vista parece que, aunque haya más de un ascensor, la probabilidad de que el primer ascensor que se detiene en la 2ª planta sea de bajada sigue siendo 5/6, ya que esa es la probabilidad para cada ascensor individual y da lo mismo usar uno que otro. De hecho, el propio Gamow se confundió al principio. Pero Donald E. Knuth se dio cuenta de que, en contra de lo que sugiere la intuición, si hay varios ascensores la cosa cambia, y analizó a fondo la situación en su artículo de 1979 The Gamow-Stern Elevator Problem. Tanto cambia la cosa que, cuando el número de ascensores tiende a infinito, la probabilidad tiende a 1/2, tal como han deducido varios lectores (ver comentarios de la semana pasada).

Con respecto al problema del edificio de cinco plantas con un único ascensor con capacidad para dos personas, coinciden en hallar un recorrido mínimo de 18 unidades Francisco Montesinos y Salva Fuster, que dice:

“Coincido en el argumento que demuestra que un trayecto inferior a 14 unidades es imposible. Como Francisco, he conseguido también un trayecto de 18 unidades y creo que 18 es el mínimo conseguible. Para verlo, creo que conviene dividir cada desplazamiento a realizar en segmentos unitarios dirigidos (dejo el diagrama en la imagen adjunta). Cada par de segmentos entre dos pisos contiguos se puede hacer en un único desplazamiento de 1 unidad (2 unidades si contamos ambos sentidos), pero teniendo en cuenta la (im)paridad de segmentos, en parte de los trayectos únicamente podremos acercar a una única persona a su destino (en concreto ocurrirá en 8 ocasiones)”.

El algoritmo de Karp

El prestigioso científico de la computación Richard M. Karp, que en 1985 recibió el Premio Turing por sus contribuciones a la teoría de algoritmos y a la resolución de problemas de optimización combinatoria, ideó un sencillo procedimiento para resolver una generalización del problema anterior:

1. Cuando el ascensor está subiendo, si alguien (sea en el ascensor o en la planta donde acaba de detenerse) desea subir, se carga el ascensor con las personas de destino más alto, y todas las demás permanecen en esa planta, y acto seguido el ascensor sube una planta. Si nadie desea subir, el ascensor baja.
2. Cuando el ascensor está bajando, se carga con las personas de destino más bajo (tanto si están ya en el ascensor o en la planta en la que acaba de detenerse), y el ascensor baja una planta. Si nadie desea bajar, el ascensor sube.

Invito a mis sagaces lectoras y lectores a reconsiderar el problema de las cinco plantas en relación con el algoritmo de Karp, y a buscar posibles generalizaciones o variantes de este y los demás problemas de ascensores vistos recientemente.

Puedes seguir a MATERIA en Facebook, X e Instagram, o apuntarte aquí para recibir nuestra newsletter semanal.