_
_
_
_

Ascensores y algoritmos

Los problemas de optimización relativos al uso de ascensores dan lugar a curiosas paradojas e ingeniosos algoritmos

Un grupo de trabajadores saliendo de ascensores durante la hora punta.
Un grupo de trabajadores saliendo de ascensores durante la hora punta.Getty Images
Carlo Frabetti

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)”.

Algoritmo ascensores

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.

Tu suscripción se está usando en otro dispositivo

¿Quieres añadir otro usuario a tu suscripción?

Si continúas leyendo en este dispositivo, no se podrá leer en el otro.

¿Por qué estás viendo esto?

Flecha

Tu suscripción se está usando en otro dispositivo y solo puedes acceder a EL PAÍS desde un dispositivo a la vez.

Si quieres compartir tu cuenta, cambia tu suscripción a la modalidad Premium, así podrás añadir otro usuario. Cada uno accederá con su propia cuenta de email, lo que os permitirá personalizar vuestra experiencia en EL PAÍS.

En el caso de no saber quién está usando tu cuenta, te recomendamos cambiar tu contraseña aquí.

Si decides continuar compartiendo tu cuenta, este mensaje se mostrará en tu dispositivo y en el de la otra persona que está usando tu cuenta de forma indefinida, afectando a tu experiencia de lectura. Puedes consultar aquí los términos y condiciones de la suscripción digital.

Sobre la firma

Carlo Frabetti
Es escritor y matemático, miembro de la Academia de Ciencias de Nueva York. Ha publicado más de 50 obras de divulgación científica para adultos, niños y jóvenes, entre ellos ‘Maldita física’, ‘Malditas matemáticas’ o ‘El gran juego’. Fue guionista de ‘La bola de cristal’.

Más información

Archivado En

Recomendaciones EL PAÍS
Recomendaciones EL PAÍS
Recomendaciones EL PAÍS
_
_