Quale algoritmo viene utilizzato dagli ascensori per trovare il percorso più breve per gli ordini di piano di viaggio?
Su Febbraio 15, 2021 da adminSto cercando di simulare un ascensore, come sempre ho iniziato in modo molto semplice prendendo solo un singolo ordine alla volta, quindi ho aggiunto la memoria allascensore in la forma delle code in modo che i piani vengano percorsi nellordine in cui sono stati premuti, il che ovviamente non è lapproccio migliore.
Quindi al momento sto usando un sistema molto semplice e “miope” la logica è che, per il piano corrente, trova il piano più vicino a me e impostalo come destinazione successiva e continua finché non ci sono più piani nellelenco.
Ma questo non funziona sempre, ad esempio il lascensore era al 3 ° piano di un edificio di 5 piani e ha ricevuto ordini 4,5,2 il percorso più breve sarebbe 2-> 4-> 5 che costa 4 piani ma usando questa logica 4-> 5-> 2 che costa 5 ha la stessa possibilità di essere scelto, a seconda del codice.
Come faccio a trovare il percorso più breve e a rendere più efficiente lascensore?
Commenti
- Un po correlati: programmers.stackexchange.com/q/96278/149904
- Vorrei ‘ invitarti nel mio ufficio e capire lalgoritmo che usano gli ascensori. Perché posso assolutamente ‘ t.
- @ gnasher729 Oh, posso anche se ‘ non ti conosco , perché ‘ è sicuramente lo stesso del mio ufficio: non fermarti mai al piano in cui ‘ mi trovo, tranne quando sono già pieno di persone. Ho ragione?
- Non esattamente. Ci sono quattro ascensori. Premi il pulsante, niente si muove per molto tempo. Se uno si muove, si ferma proprio prima del tuo piano e aspetta per secoli, finché non viene superato da un altro che oltrepassa il tuo piano e poi scende. Durante la discesa a terra si ferma almeno tre volte senza che nessuno entri.
- Gioco / sfida di programmazione pertinente: play.elevatorsaga.com
Risposta
“Efficienza” non è la caratteristica più importante, la più importante è assicurarsi che ogni lordine è seguito, che non cè fame. Se qualcuno preme 100 e le persone continuano a premere 1 e 2, potrebbe essere efficiente continuare a spostarsi tra quei piani, ma “sarebbe bello che a un certo punto si visitasse 100.
Io penso (dallosservazione personale quando ero interessato a capire) che la maggior parte di loro fa:
- Inizia ad andare nella direzione del primo pulsante premuto, tieni traccia di quale direzione stiamo ” in corso
- Quando viene raggiunto un piano e quel pulsante è stato premuto, fermati e apri le porte, contrassegna i pulsanti di questo piano come non più premuti.
-
- Se ci sono ancora più piani che dobbiamo visitare che sono nella stessa direzione, continua in quella direzione .
- In caso contrario e ci sono ancora piani che dobbiamo visitare, spostati in quella direzione.
- In caso contrario, abbiamo finito e inizieremo da 1 quando un pulsante verrà premuto di nuovo.
Nota che molti ascensori hanno pulsanti “Voglio salire” e “Voglio scendere” accanto alle porte invece di un solo pulsante. lalgoritmo necessita solo di una piccola modifica: in 2, se lunico pulsante premuto per quel piano è uno dei pulsanti accanto alla porta, fermati e apri le porte solo se stiamo andando in quella direzione. Forse tieni premuto il pulsante se le porte si aprono a causa di un pulsante premuto allinterno dellascensore e sta andando nella direzione sbagliata.
Non devi mai calcolare un intero percorso , in quale direzione andare dopo.
Commenti
- questo mi ha completamente ignorato, ero così concentrato sullefficienza e ho dimenticato che anche altre cose sono importanti . ‘ non è ancora efficiente passare da 2 a > 100 e tornare a 1 semplicemente perché era nella stessa direzione ma in almeno non garantisce la fame. e, completamente fuori tema, forse è per questo che ‘ è comune trovare due ascensori con questa logica? il che mi fa chiedere se ‘ sia più comune trovare gli ascensori che vanno nella direzione opposta in un dato momento. in ogni caso, ‘ sono ancora curioso di sapere come trovare lintero percorso più breve, ma questo risponde molto chiaramente alla mia domanda, grazie
- Nota che una volta arrivato a un edificio con 100 piani, di solito avrai ascensori che servono solo una gamma specifica di piani (es. 0-19, 20-39, …), così come ascensori rapidi che percorrono solo lunghe distanze (es. da 0 a 50, da 0 a 100 , Da 50 a 100, ma nessun piano intermedio), quindi potresti dover cambiare ascensore per raggiungere la tua destinazione. Potresti anche avere più ascensori per vano che ovviamente non possono passare luno con laltro.Totalmente fuori tema: IIRC, cera una domanda sullefficienza dei pulsanti freccia su e giù sul sito Esperienza utente che ha reso una lettura molto affascinante.
- grazie, ‘ non lo sapevo. la suddivisione sembra una buona strategia se una parte rompe lintero sistema ‘ e anche per distribuire il carico che è importante per lusura meccanica. Mi chiedevo se questi ascensori rapidi fossero dovuti alle carenze logiche dellalgoritmo dellascensore di Knuth ‘.
- solo unaltra cosa i ‘ d aggiungere è che spesso hanno un piano ‘ home ‘ a cui torneranno quando non vengono utilizzati, questo può essere diverso per ascensori diversi e forse anche cambiare a seconda dellora del giorno e dei modelli di utilizzo previsti
- Ho la tendenza a premere il pulsante su / giù in modo semi casuale indipendentemente dalla direzione ‘ Sto effettivamente viaggiando. Nel mio caso, ho sempre e solo una destinazione, quindi lascensore mi porta in quella posizione indipendentemente dal fatto che abbia scelto su o giù. Sospetto che se dovessi premere il pulsante di discesa, scegliere un piano sopra di me e poi scegliere un piano sotto di me prima che lascensore inizi a muoversi, mi porterebbe al piano sotto di me piuttosto che al piano che ho premuto per primo. Potrei sbagliarmi, ‘ mi assicurerò di provarlo la prossima volta che mi troverò in un ascensore.
Risposta
Laltra risposta fornisce correttamente lalgoritmo standard dellascensore, che fondamentalmente è “continuare ad andare nella stessa direzione il più a lungo possibile e fare ogni sosta necessaria lungo il percorso”.
Esistono altri algoritmi per ascensori. Ad esempio, considera un condominio in cui gli appartamenti diventano più costosi man mano che sali. I proprietari delledificio potrebbero scegliere di modificare lalgoritmo dellascensore per “andare nella stessa direzione il più a lungo possibile ma fermarsi solo durante la discesa”. In questo modo, se nellascensore ci sono persone che si trovano nella hall e vanno al 2, 5 e 10, lascensore va al 10, poi al 5, poi al 2, lasciando le persone in ordine di affitto che pagano. Ovviamente, quando le persone in 10 lasciano il loro appartamento, dovranno aspettare più a lungo per raggiungere la hall.
Se stai cercando una soluzione efficiente quindi elaborare una metrica per il costo e implementare una serie di algoritmi diversi ed eseguire simulazioni. Ricorda di misurare non solo il costo medio, ma anche metriche come il tempo massimo richiesto da una richiesta per essere soddisfatta. Lottimizzazione per medie basse a volte può deottimizzare il caso peggiore, il che è negativo.
Commenti
- Sembra essere raro (altri alogirthms)
Risposta
Nota che gli ascensori utilizzano gli stessi algoritmi di pianificazione di alcuni controller del disco rigido. Lalgoritmo SCAN standard è anche noto come algoritmo dellascensore . Penso che in pratica lalgoritmo LOOK sia più comune, poiché è leggermente più efficiente di SCAN.
Commenti
- Quando parli in modo così sicuro, hai esperienza professionale nellimplementazione del codice per gli ascensori? Soprattutto i sistemi di ascensori più recenti? Sono curioso di sapere se dopo l11 settembre a New York ci sia stata una priorità più alta nellinvio di passeggeri piuttosto che nel portarli su.
- Fai scendere i passeggeri, non giù. Uso spesso lascensore in un parcheggio, dove il terzo piano dei piani da 1 a 6 è il piano terra, quindi per scappare, il piano 3 sarebbe il migliore.
Risposta
Questa risposta riguarda un sistema di controllo della destinazione più avanzato. In un edificio con più ascensori in cui le persone indicano a quale piano vogliono andare e il sistema assegna loro un ascensore.
Lidea è abbastanza semplice, in teoria sai dove stanno andando tutti e ogni ascensore. Quindi puoi per ogni ascensore, calcolare quando è lorario di arrivo previsto e quanto rallenterà gli altri. Scegli avidamente lascensore più veloce.
Ci sono limitazioni a questo, come i gruppi che premono il pulsante solo una volta e le persone che premono il pulsante più volte.
Lascia un commento