algorithm - para - planos de un ascensor

Estructura de datos para mecanismo de ascensores

Question

Esta pregunta me la hice durante la entrevista de la empresa: ¿qué estructura de datos es eficiente para implementar el mecanismo de ascensores?

No puedo encontrar la estructura de datos eficiente para ello incluso después de una gran cantidad de Google.

Puedo pensar en la cola de prioridad para implementarla. ¿Es la cola de prioridad una estructura de datos eficiente o una estructura de datos más eficiente para implementar el mecanismo de elevador?

¡Gracias!

Answer 1

¿Qué pasa si usamos dos listas vinculadas una para las solicitudes de movimiento en dirección ascendente y otra para la solicitud de movimiento en dirección descendente?

p.ej

Primera solicitud: a). Mientras que el ascensor está en el piso 0 y las solicitudes vienen para el 3er piso.

Lista enlazada para movimiento ascendente.

3-> nulo.

Lista enlazada para movimiento descendente.

nulo.

Segunda solicitud: b). mientras que el elevador se ha movido al primer piso y una solicitud proviene del segundo piso para un movimiento ascendente.

Lista enlazada para movimiento ascendente.

2-> 3-> null

Lista enlazada para movimiento descendente.

nulo.

Tercera solicitud: c) Supongamos que 2 personas entran en el segundo piso, uno presiona el botón para el quinto piso y otro para el primero.

Lista enlazada para movimiento ascendente.

3-> 5-> nulo

Nota: Aquí se ha eliminado 2 de la lista vinculada ascendente a medida que se ha alcanzado.

Lista enlazada para movimiento descendente.

1-> nulo.

d) Supongamos que una persona entra en el 3er piso y presiona el botón para el 0 ° piso

Lista enlazada para movimiento ascendente.

5-> nulo

Lista enlazada para movimiento descendente.

1-> 0-> nulo.

Una vez que el quinto piso alcanza las solicitudes ascendentes, la lista vinculada se vacía, por lo que la lista vinculada puede considerarse para el movimiento.

Si tanto la lista enlazada están vacías, el elevador estaría en reposo.

Así que creo que la lista enlazada también puede ser una estructura de datos efectiva para el ascensor.

Answer 2

¿Qué tal tener una matriz, donde cada entrada de matriz representa un piso? Cuando el usuario desea detenerse en un piso, marcará esa entrada en el arreglo, y el elevador buscará en el arreglo y borrará la entrada si marca cuando el elevador llega a ese piso. Similar al algoritmo de planificación SCAN / CSAN. Espero sus comentarios.

Answer 3

A continuación se muestra una forma de diseñar el sistema de ascensor. Cada ascensor usa la Cola (podría ser la Cola de Bloqueo) para almacenar solicitudes de piso. También hay un ElevatorManager central que supervisa todas las colas de Elevadores y puede delegar solicitudes a un determinado elevador en función de algunas reglas comerciales. El trabajo de ElevatorManager es delegar eficientemente las solicitudes al elevador correspondiente. El siguiente pseudocódigo no optimiza el algoritmo de delegación, pero muestra cómo se podría hacer la delegación real a una lista de ascensores.

Clases necesarias para el sistema de elevador:

ElevatorManager [Singleton - Este es el programa principal de ascensores que gestionará n ascensores en el edificio]
Miembros:
Lista de Ascensor
Queue of Floor.Request // Esto mantiene la solicitud de ambas direcciones. Una mejora podría ser mantener dos colas, una para cada dirección, pero aumentaría la complejidad
MIN_FLOOR
MAX_FLOOR
Operaciones:
delgate ()
detener () // configurar el sistema completo del elevador en modo de mantenimiento o detener la operación


Ascensor [Representa ascensores individuales. Podría haber n ascensores en un edificio]
Miembros:
Queue of Floor // esto debe ordenarse para que pueda ser un PriorityQueue.
Dirección: Enum. [Enum. De dirección: arriba, abajo, esperar, inactivo, mantenimiento]
Piso actual: piso
Operaciones:
funcionar()
ascender()
mover hacia abajo()
puerta abierta()
cerrarPuerta ()
callEmergencyLine ()
getDirection ()
getCurrentFloor ()
setInMaintenanceMode ()


Piso [Representa pisos individuales]
Miembros:
eNum de pisos
Solicitud de clase {
suelo actual
destinationFloor
Dirección [arriba, abajo]
}
Operación:
goUp ()
bajar()

Algunos de los pseudocódigos principales para los componentes anteriores:

class Floor {
    goUp() {
        ElevatorManager.queue.offer(new Request(currentFloor, destinationFloor, up));
    }   

    goDown() {
        ElevatorManager.queue.offer(new Request(currentFloor, destinationFloor, down));
    }
}

ElevatorManager {
    delegate() {

        // Instead of using one object, we could use a list to track idle and elevators moving in same direction so that these list could be used for next requests in queue
        // but again to simplify pseudocode, I am using single objects instead of lists
        Elevator idleElevator; // track idle elevator
        Elevator elevatorMovingInSameDirection; // elevator moving in same direction as next request in main elevator manager queue 

        while(!halt()) { //keep delegating until powered down or whole system is halted through main controls

            if(queue.peek() != null) {

                Request req = queue.peek();
                boolean startAgain = false; // flag to start from beginning if the request is already pushed to one of the elevators queue during iterating elevators

                for(Elevator elevator : elevators) {

                    // first find if there is an elevator at current floor going in same direction as current request in queue
                    if(req.currentFloor == elevator.currentFloor && req.direction == elevator.direction) {
                        elevator.queue.offer(req.destinationFloor);
                        queue.poll(); // remove this request from Elevator Manager queue

                        startAgain = true;
                        break;
                    }

                    // check if this elevator is idle
                    if(elevator.direction == "idle")) {
                        idleElevator = elevator; // For this simple design, I am ok to overwrite idle elevator value and instead get the latest idle elevatior
                    }

                    // check if this elevator is moving in desired direction and elevator''s current floor is behind desired floor in queue
                    if(elevator.direction == req.direction) {

                        // Make sure elevators moving in same direction should also be behind the floor where request is made
                        if(req.direction == "Up" && req.currentFloor - elevator.currentFloor > 0) {

                            elevatorMovingInSameDirection = elevator; // Same as above, it''s ok to get this overwritten and instead get the latest elevator moving in same      direction
                        }

                        // Make sure elevators moving in same direction should also be behind the floor where request is made
                        if(req.direction == "Down" && req.currentFloor - elevator.currentFloor < 0) {
                            elevatorMovingInSameDirection = elevator;
                        }
                    }

                }

                // Only delegate to other floors if you could not find elevator going in same direction at same floor from where the request was made
                if(!startAgain && idleElevator != null) {
                    idleElevator.queue.offer(req.destinationFloor);
                    queue.poll();
                }

                // if we could neither find elevator at current floor nor idle elevator then send this request to elevator behind current Floor and moving in same direction as the request
                if(!startAgain && elevatorMovingInSameDirection != null) {
                    elevatorMovingInSameDirection.queue.offer(req.destinationFloor);
                    queue.poll();
                }


            }
        }
    }
}


Elevator {

    moveUp() {
        this.currentFloor += 1;
    }

    moveDown() {
        this.currentFloor -= 1;
    }

    operate() {

        while(queue.peek() != null) {

            Floor nextFloorInQueue = queue.peek();

            while(this.currentFloor != nextFloorInQueue.request.destinationFloor) {
                if(this.direction == "Up") {
                    moveUp();
                } else if(this.direction == "down") {
                    moveDown();
                }
            }

            queue.poll(); // remove the request from queue
            open(); //open door

            Direction backUpDirection = this.direction; //back up elevators direction to retrieve it later once dooor closes
            this.direction = "idle"; // set state to idle to let elevatorManager know that requests at current floor could be offered to this elevator queue

            Thread.sleep(10000); // sleep for 10 seconds so that people can leave elevator

            close(); // once people are out close door to move to next floor in queue
            this.direction = backUpDirection;
        }

        this.direction = "idle"; // once queue is empty set the direction to idle
    }
}

También está disponible aquí en mi Github: https://github.com/prabhash1785/Java/blob/master/ObjectOrientedDesign/src/com/prabhash/java/design/objectoriented/elevator/ElevatorDesignWithPseudocode.md

Answer 4

Dado que no puede implementar mecanismos en el software (aunque ciertamente puede modelarlos ), asumo que la pregunta ha sido sobre el algoritmo de Ascensor .

El algoritmo parece engañosamente simple, pero es sorprendentemente muy difícil de implementar, incluso con un buen conjunto de estructuras de datos en la mano. Una buena estructura para usar para este algoritmo es tres colas de prioridad:

1. Para la dirección actual con entradas más allá del punto actual,
2. Para la dirección opuesta, y
3. para la dirección actual antes del punto actual.

Su implementación primero decidirá la dirección y luego elegirá una cola en la que colocar el par solicitado de valores {from, to} .

Answer 5

Para simplificar, consideremos un sistema de ascensor único.

Estructura de datos utilizada: listas simples para almacenar el número de piso, enumeraciones para eventos y estados.

El sistema puede ser hecho por el estado del evento . Cada aspecto del comportamiento o el entorno de los usuarios debe tenerse cuidado al decidir qué escenarios pueden lanzarse al ascensor.

Events of the elevator : GOINGUP, GOINGDOWN, STOP 
States of the elevator : ONMOVE, WAITING (between door open and close), IDLE (serving no one), UNDERMAINTENANCE

Elevator movement is usually driven by two activites:
1. Press Up or Down key (before the entry gate of elevator) and wait for the elevator to come and serve you. (Press-And-Wait, say PAW) 
2. Enter inside the elevator and make request by pressing keys (Enter-And-Request, say EAR)

So it can said that PAW from outside and EAR from inside can decide the hops of the elevator. But what about direction?

Two possible types of PAW: PAWup (press Up button) and PAWdown (press Down button)

Now, EAR can be any of the three types depending upon the users behavior. These are the critical challenges in deciding the algorithm: 
1.) Normal - same direction as PAW (wanted to go down and enter lower floor#) 
2.) Opposite - wanted to go down BUT enter higher floor#
3.) Indecisive - Do Nothing, no key press

Now comes all the important rules:
RULE 1: If at IDLE, use FCFS to decide between the DownList front and UpList front - whoever is oldest, serve it first to ensure less waiting time. 
RULE 2: When both lists (DownList and UpList) are empty, move elevator to IDLE state. 
RULE 3: Elevator state change GOINGUP->STOP clears that floor# from UpList. Similarly, GOINGDOWN->STOP clears that floor from DownList.
RULE 4: Absolute Zero Skipping: GOINGxxx serves as many floors in xxxList as possible. 
RULE 5: Elevator doesn''t favour Opposite-EAR, and obviously can''t serve Indecisive-EAR.
RULE 6: Elevator in UNDERMAINTENANCE state is shunned from all external signals.
RULE 7: In the event of Power-cuts or Fire, the elevator goes and stops at Lobby. Flooding??

To achieve RULE#5, GOINGDOWN clears all the lower floor# in DownList in ONE GO. Similarly, GOINGUP clears all the higher floor# in UpList.    

Lets discuss one scenario to clear the above concepts:
Say, an elevator is resting at floor 7 is at IDLE state, 
    DownList : 
    UpList : 

IDLE@7 - PAWdown@12 then PAWup@9 then PAWdown@13
    DownList : 12, 13 (older requests at lower index.Push new requests at front.)
    UpList : 9 
    Using RULE#2, in the above case, 
    Event: GOINGUP to Pick@12.  

WAITING@12  - 12 cleared following RULE#3

MeanWhile, PAWup@8 then PAWup@10 then PAWdown@10, so updated lists are:
    DownList : 13, 10 
    UpList : 9, 8, 10

So here, in the current situation, if the EAR is
1.) Normal, GOINGDOWN(towards new EAR) is triggered.
2.) Opposite/Indecisive, GOINGDOWN(towards 9) is triggered and add the new EAR in UpList. 

Usando las reglas mencionadas anteriormente, el elevador continúa su trabajo habitual.