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.