¿Qué algoritmo usan los ascensores para encontrar el camino más corto para los pedidos de piso de viaje?

27

Estoy tratando de simular un elevador, como siempre comencé de manera muy simple tomando solo un pedido a la vez, luego agregué memoria al elevador en forma de colas para que los pisos se desplacen en el orden en que fueron presionados, que obviamente no es el mejor enfoque.

Así que en este momento estoy usando una lógica muy simple y "miope" que es, para el piso actual, encuentre el piso más cercano a mí y configúrelo como mi próximo destino y repita hasta que no haya más pisos en la lista.

Pero esto no siempre funciona, por ejemplo, el elevador estaba en el 3er piso de un edificio de 5 pisos y recibió órdenes 4,5,2, el camino más corto sería 2-> 4-> 5 que cuesta 4 pisos pero usando esta lógica 4-> 5-> 2 que cuesta 5 tiene la misma posibilidad de ser elegido, dependiendo del código.

¿Cómo encuentro el camino más corto y hago que el ascensor sea más eficiente?

Raed Tabani
fuente
66
Me gustaría invitarte a mi oficina y descubrir el algoritmo que usan los ascensores allí. Porque absolutamente no puedo.
gnasher729
1
@ gnasher729 Oh, puedo aunque no te conozco, porque seguramente es lo mismo que en mi oficina: nunca te detengas en el piso en el que estoy, excepto cuando ya esté lleno de gente. Estoy en lo cierto?
Andres F.
2
No exactamente. Hay cuatro ascensores. Presionas el botón, nada se mueve durante mucho tiempo. Si uno se mueve, se detiene justo antes de su piso y espera por siglos, hasta que otro lo supera y luego baja. En el camino hacia el suelo, se detiene al menos tres veces sin que nadie entre.
gnasher729
2
Juego / desafío de programación relevante: play.elevatorsaga.com
dwikle

Respuestas:

30

"Eficiencia" no es la característica más importante, lo más importante es asegurarse de que se siga cada orden, que no haya hambre. Si alguien presiona 100 y la gente sigue presionando 1 y 2, puede ser eficiente continuar entre esos pisos, pero sería bueno visitar 100 en algún momento.

Yo creo (por observación personal cuando yo estaba interesado en averiguar) que la mayoría de ellos lo hacen:

  1. Comience a ir en la dirección del primer botón presionado, haga un seguimiento de en qué dirección vamos
  2. Cuando se alcanza un piso y se presiona ese botón, deténgase y abra las puertas, marque los botones para este piso como no presionados más.
    • Si todavía hay más pisos que necesitamos visitar que están en la misma dirección, continúe en esa dirección .
    • Si no, y todavía hay pisos que necesitamos visitar, muévase en esa dirección.
    • Si no es así, hemos terminado y comenzaremos en 1 cuando se presione nuevamente un botón.

Tenga en cuenta que muchos ascensores tienen botones "Quiero subir" y "Quiero bajar" al lado de las puertas en lugar de un solo botón. El algoritmo solo necesita un pequeño cambio: en 2, si el único botón presionado para ese piso es uno de los botones al lado de la puerta, solo deténgase y abra las puertas si vamos en esa dirección. Posiblemente mantenga presionado el botón si las puertas se abren debido a un botón presionado dentro del elevador y está yendo en la dirección incorrecta.

Nunca tiene que descubrir un camino completo , solo en qué dirección ir a continuación.

RemcoGerlich
fuente
esto me saltó por completo la mente, estaba tan concentrado en la eficiencia y olvidé que otras cosas también son importantes. Todavía no es eficiente pasar de 2 a 100 y volver a 1 simplemente porque estaba en la misma dirección, pero al menos asegura que no haya hambre. y, completamente fuera de tema, ¿quizás es por eso que es común encontrar dos ascensores con esta lógica? lo que me hace preguntarme si es más común encontrar los ascensores que van en la dirección opuesta en un momento dado. de todos modos, todavía tengo curiosidad sobre cómo encontrar el camino más corto, pero esto responde a mi pregunta muy claramente, gracias
Raed Tabani
77
Tenga en cuenta que una vez que llegue a un edificio con 100 pisos, generalmente tendrá ascensores que sirven solo a un rango específico de pisos (por ejemplo, 0-19, 20-39, ...), así como ascensores expresos que solo recorren largas distancias (por ejemplo, 0 a 50, 0 a 100, 50 a 100, pero sin pisos intermedios), por lo que es posible que tenga que cambiar los ascensores para llegar a su destino. También puede tener múltiples ascensores por eje que obviamente no pueden cruzarse entre sí. Totalmente fuera de tema: IIRC, hubo una pregunta sobre la eficiencia de esos botones de flecha hacia arriba y hacia abajo en el sitio de Experiencia del usuario que resultó en una lectura fascinante.
Jörg W Mittag
Gracias, no lo sabía. la subdivisión parece una buena estrategia si una parte descompone todo el sistema y también distribuye la carga, lo cual es importante para el desgaste mecánico. Me pregunto si estos elevadores rápidos se debieron a las deficiencias lógicas del algoritmo de elevadores de Knuth.
Raed Tabani
única otra cosa que me gustaría añadir es que a menudo tienen una baja 'casa' que van a volver a cuando no esté en uso, esto puede ser diferente para diferentes ascensores, y posiblemente incluso cambiar dependiendo de la hora del día y los patrones de utilización esperados
jk .
Tengo la tendencia de presionar el botón arriba / abajo de forma semi aleatoria, independientemente de la dirección en la que realmente viaje. En mi caso, solo tengo un destino, por lo que el ascensor me lleva a esa ubicación independientemente de si elegí o no. abajo. Sospecho que si tuviera que presionar el botón hacia abajo, elegir un piso sobre mí y luego elegir un piso debajo de mí antes de que el elevador comience a moverse, me llevaría al piso debajo de mí en lugar del piso que presioné primero. Podría estar equivocado, me aseguraré de probarlo la próxima vez que me encuentre en un ascensor.
Ucenna
13

La otra respuesta da correctamente el algoritmo de ascensor estándar, que básicamente es "seguir en la misma dirección el mayor tiempo posible y hacer todas las paradas necesarias en el camino".

Hay otros algoritmos de ascensor. Por ejemplo, considere un edificio de apartamentos donde los apartamentos se vuelven más caros a medida que sube. Los propietarios del edificio pueden optar por modificar el algoritmo del ascensor para "ir en la misma dirección el mayor tiempo posible pero solo detenerse en el camino hacia abajo". De esa manera, si tiene personas en el elevador que están en el lobby y van a 2, 5 y 10, el elevador pasa a 10, luego a 5, luego a 2, y deja a las personas en orden de cuánto renta pagan. Pero, por supuesto, cuando las personas de 10 se van su departamento, con mayor frecuencia tendrán que esperar más para llegar al lobby.

Si está buscando una solución eficiente, elabore una métrica de costo e implemente varios algoritmos diferentes y ejecute simulaciones. Recuerde medir no solo el costo promedio, sino también las métricas, como el tiempo más largo que tarda una solicitud en ser atendida. La optimización para promedios bajos a veces puede desestimular el peor de los casos, que es malo.

Eric Lippert
fuente
1
Parece ser raro (otras alogirthms)
FindOutIslamNow
10

Tenga en cuenta que los ascensores utilizan los mismos algoritmos de programación que algunos controladores de disco duro. El algoritmo SCAN estándar incluso se conoce como algoritmo de ascensor . Creo que en la práctica el algoritmo LOOK es más común, ya que es un poco más eficiente que SCAN.

cabeza de jardín
fuente
Cuando hablas tan ciertamente, ¿tienes experiencia profesional implementando el código para ascensores? ¿Sistemas de ascensores especialmente nuevos? Tengo curiosidad por saber si después del 11 de septiembre en Nueva York ha habido una mayor prioridad en enviar pasajeros hacia abajo en lugar de subirlos.
John Zabroski