Quale algoritmo viene utilizzato dagli ascensori per trovare il percorso più breve per gli ordini del piano di viaggio?

"Efficienza" non è la caratteristica più importante, il più importante è assicurarsi che ogni ordine sia seguito, che non ci sia fame. Se qualcuno preme 100 e le persone continuano a premere 1 e 2, potrebbe essere efficace continuare a passare da un piano all'altro, ma sarebbe bello visitarlo a un certo punto.

I pensa (dall'osservazione personale quando ero interessato a capire) che la maggior parte di loro fa:

1. Iniziare nella direzione del primo pulsante premuto, tenere traccia della direzione in cui stiamo andando
2. Quando viene raggiunto un piano e viene premuto quel pulsante, fermati e apri le porte, contrassegna i pulsanti per questo piano come non più premuto.
3. • Se ci sono ancora più piani che dobbiamo visitare che si trovano nella stessa direzione, continua in quella direzione .
   • Se no e ci sono ancora piani che dobbiamo visitare, spostati in quella direzione.
   • In caso contrario, abbiamo finito e inizieremo a 1 quando un pulsante viene premuto di nuovo.

Si noti che molti ascensori hanno pulsanti "Voglio salire" e "Voglio andare giù" accanto alle porte anziché un singolo pulsante. L'algoritmo richiede solo una piccola modifica: in 2, se l'unico pulsante premuto per quel piano è uno dei pulsanti accanto alla porta, fermati e apri le porte solo se stiamo andando in quella direzione. Forse tenere premuto il pulsante se le porte si aprono a causa di un pulsante premuto all'interno dell'ascensore e sta andando nella direzione sbagliata.

Non devi mai calcolare un intero percorso , solo in quale direzione andare avanti.

L'altra risposta fornisce correttamente l'algoritmo standard dell'ascensore, che fondamentalmente "continua nella stessa direzione il più a lungo possibile e fa ogni sosta necessaria lungo il percorso".

Esistono altri algoritmi di ascensore. Ad esempio, si consideri un condominio in cui gli appartamenti diventano più costosi man mano che si sale. I proprietari dell'edificio potrebbero scegliere di modificare l'algoritmo dell'ascensore per "andare nella stessa direzione il più a lungo possibile ma fermarsi solo durante la discesa". In questo modo se ci sono persone nell'ascensore che si trovano nella hall e stanno andando a 2, 5 e 10, l'ascensore va a 10, quindi a 5, quindi a 2, lasciando andare le persone in ordine di quanto affitto pagano. Ma ovviamente quando le persone su 10 lasciano il loro appartamento, dovranno più spesso aspettare più a lungo per raggiungere l'atrio.

Se stai cercando una soluzione efficiente, crea una metrica per i costi e implementa una serie di algoritmi diversi ed esegui simulazioni. Ricorda di misurare non solo il costo medio, ma anche le metriche più lunghe richieste per la manutenzione. L'ottimizzazione per le medie basse può talvolta deottimizzare il caso peggiore, il che è negativo.

Si noti che gli elevatori utilizzano gli stessi algoritmi di scheduling di alcuni controller del disco rigido. L'algoritmo SCAN standard è anche noto come algoritmo di elevatore . Penso che in pratica l'algoritmo LOOK sia più comune, in quanto è leggermente più efficiente di SCAN.