¿Qué algoritmo utilizan los ascensores para encontrar el camino más corto para recorrer los pedidos de piso?
On febrero 15, 2021 by adminEstoy tratando de simular un ascensor, como siempre, comencé de manera muy simple tomando solo un pedido a la vez, luego agregué memoria al ascensor en la forma de las colas para que los pisos se recorran en el orden en que se presionaron, lo que obviamente no es el mejor enfoque.
Por lo tanto, en este momento «estoy usando un método muy simple y» miope » lógica que es, para el piso actual encontrar el piso más cercano a mí y establecerlo como mi próximo destino y recorrer hasta que no haya más pisos en la lista.
Pero esto no siempre funciona, por ejemplo, el El ascensor estaba en el 3er piso de un edificio de 5 pisos y recibió pedidos 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 has 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?
Comentarios
- Algo relacionado: programmers.stackexchange.com/q/96278/149904
- Me ‘ me gustaría invitarte a mi oficina y averiguar el algoritmo que usan los ascensores allí. Porque no puedo ‘ t.
- @ 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?
- No del todo. 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 una eternidad, hasta que lo adelanta otro que pasa por su piso y luego baja. En el camino hacia el suelo, se detiene al menos tres veces sin que entre nadie.
- Juego / desafío de programación relevante: play.elevatorsaga.com
Respuesta
La «eficiencia» no es la característica más importante, lo más importante es asegurarse de que Se sigue el orden, que no hay hambre. Si alguien presiona 100 y la gente sigue presionando 1 y 2, puede ser eficiente continuar entre esos pisos, pero sería bueno que se visitara 100 en algún momento.
Yo creo que (de la observación personal cuando estaba interesado en averiguar) que la mayoría de ellos:
- Empiece a ir en la dirección del primer botón presionado, mantenga un registro de en qué dirección estamos yendo
- Cuando se llega a un piso y se presiona ese botón, deténgase y abra las puertas, marque los botones para este piso como ya no presionados.
-
- Si todavía hay más pisos que debemos visitar que están en la misma dirección, siga en esa dirección .
- Si no es así y todavía hay pisos que debemos visitar, muévase en esa dirección.
- De lo contrario, habremos terminado y comenzaremos en 1 cuando se presione un botón nuevamente.
Nota que muchos ascensores tienen botones «Quiero subir» y «Quiero bajar» junto a las puertas en lugar de un solo botón. El 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 para y abre las puertas si vamos en esa dirección. Posiblemente mantenga el botón presionado si las puertas se abren debido a un botón presionado dentro del ascensor y va en la dirección incorrecta.
Nunca tiene que averiguar una ruta completa, sólo en qué dirección ir a continuación.
Comentarios
- esto se me pasó por alto por completo, estaba tan concentrado en la eficiencia y olvidé que otras cosas también son importantes . ‘ s todavía no es eficiente para ir, por ejemplo, de 2- > 100 y volver a 1 simplemente porque estaba en la misma dirección pero en al menos asegura que no se muera de hambre. y, completamente fuera del tema, tal vez por eso ‘ es común encontrar dos ascensores con esta lógica. lo que me hace preguntarme si es ‘ más común encontrar los ascensores yendo en la dirección opuesta en un momento dado. de todos modos, ‘ todavía tengo curiosidad sobre cómo encontrar el camino completo más corto, pero esto responde mi pregunta muy claramente, gracias
- Tenga en cuenta que una vez que llegue a un edificio con 100 pisos, normalmente tendrá ascensores que sirven solo a un rango específico de pisos (por ejemplo, 0-19, 20-39, …), así como ascensores rápidos 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 deba cambiar de ascensor para llegar a su destino. También puede tener varios ascensores por hueco que, obviamente, no pueden pasar 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 Experiencia del usuario que resultó en una lectura muy fascinante.
- gracias, yo ‘ no lo sabía. subdividir parece una buena estrategia si una parte rompe todo el sistema no ‘ t y también distribuir la carga que es importante para el desgaste mecánico. Me pregunto si estos ascensores exprés se deben a las deficiencias lógicas del algoritmo de ascensores ‘ s de Knuth.
- solo otra cosa i ‘ Un añadido es que a menudo tienen un ‘ piso ‘ al que volverán cuando no estén en uso, esto puede ser diferente para diferentes ascensores, y posiblemente incluso cambiar según la hora del día y los patrones de uso esperados
- Tengo una tendencia a presionar el botón arriba / abajo de forma semi aleatoria independientemente de la dirección I ‘ en realidad estoy viajando. En mi caso, solo tengo un destino, por lo que el ascensor me lleva a ese lugar independientemente de si elegí subir o bajar. Sospecho que si presiono el botón hacia abajo, elijo un piso por encima de mí y luego elijo un piso debajo de mí antes de que el ascensor 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.
Responder
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 hay personas en el ascensor que están en el vestíbulo y van a 2, 5 y 10, el ascensor va a 10, luego a 5, luego a 2, dejando a las personas en orden de alquiler. Pero, por supuesto, cuando la gente del 10 abandona su apartamento, es más frecuente que tenga que esperar más para llegar al vestíbulo.
Si está buscando una solución eficaz luego, cree una métrica para el costo e implemente un montón de algoritmos diferentes y ejecute simulaciones. Recuerde medir no solo el costo promedio, sino también métricas como el tiempo más largo que una solicitud tarda en ser atendida. La optimización para promedios bajos a veces puede desoptimizar el peor de los casos, lo cual es malo.
Comentarios
- Parece ser raro (otros alogirthms)
Responder
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.
Comentarios
- Cuando habla con tanta certeza, ¿tiene experiencia profesional en la implementación del código para ascensores? ¿Especialmente los sistemas de ascensores más nuevos? Tengo curiosidad por saber si después del 11 de septiembre en Nueva York ha habido una mayor prioridad en enviar pasajeros que en subirlos.
- Sacar pasajeros, no bajar. A menudo uso el ascensor en un estacionamiento, donde el tercer piso de los pisos 1 a 6 es el nivel del suelo, por lo que para escapar, el piso 3 sería el mejor.
Respuesta
Esta respuesta trata sobre un sistema de control de destino más avanzado. En un edificio con varios ascensores donde las personas indican a qué piso quieren ir y el sistema les asigna un ascensor.
La idea es bastante simple, teóricamente sabes a dónde van todos y cada ascensor. Entonces, para cada ascensor, puede calcular cuándo es su hora de llegada prevista y cuánto ralentizará a los demás. Elija con cordialidad el ascensor más rápido.
Esto tiene limitaciones, como que los grupos presionen el botón solo una vez y las personas presionen el botón varias veces.
Deja una respuesta