Ce algoritm este utilizat de ascensoare pentru a găsi cea mai scurtă cale de parcurgere a comenzilor de la etaj?
On februarie 15, 2021 by adminÎncerc să simulez un lift, ca întotdeauna, am început foarte simplu luând o singură comandă la un moment dat, apoi am adăugat memorie la lift forma cozilor, astfel încât etajele să fie parcurse în ordinea în care au fost apăsate, ceea ce evident nu este „cea mai bună abordare.
Deci, în acest moment, folosesc un instrument foarte simplu și„ miop ” logică care este, pentru etajul actual, găsiți etajul cel mai apropiat de mine și setați-l ca următoarea mea destinație și buclați până când nu mai sunt etaje în listă.
Dar acest lucru nu funcționează întotdeauna, de exemplu liftul se afla la etajul 3 al unei clădiri cu 5 etaje și a primit comenzi 4,5,2 cea mai scurtă cale ar fi 2-> 4-> 5 care costă 4 etaje, dar folosind această logică 4-> 5-> 2 care costă 5 are aceeași șansă de a fi ales, în funcție de cod.
Cum găsesc cea mai scurtă cale și cum să fac ascensorul mai eficient?
Comentarii
- Oarecum înrudit: programmers.stackexchange.com/q/96278/149904
- Îmi place ‘ să vă invit la biroul meu și să vă dau seama de algoritmul pe care îl folosesc lifturile acolo. Pentru că absolut nu pot ‘ t.
- @ gnasher729 Oh, chiar dacă nu te ‘ te cunosc , deoarece ‘ este cu siguranță la fel ca în biroul meu: nu vă opriți niciodată la podea în care ‘ m, cu excepția cazului în care sunt deja pline de oameni. Am dreptate?
- Nu chiar. Există patru lifturi. Apăsați butonul, nimic nu se mișcă pentru o perioadă foarte lungă de timp. Dacă cineva se mișcă, se oprește chiar înainte de podeaua ta și așteaptă vârste, până când este depășit de altul care trece de podeaua ta și apoi coboară. La coborâre spre sol, se oprește de cel puțin trei ori, fără să intre nimeni.
- Joc / provocare de programare relevantă: play.elevatorsaga.com
Răspuns
„Eficiența” nu este cea mai importantă caracteristică, cel mai important este să vă asigurați că fiecare se urmează ordinea, ca să nu existe foamete. Dacă cineva apasă 100 și oamenii continuă să apese 1 și 2, poate fi eficient să continui între etajele respective, dar ar fi bine ca 100 să fie vizitați la un moment dat.
Cred că (din observația personală când am fost interesat să aflu) că majoritatea fac:
- Începeți să mergeți în direcția primului buton apăsat, țineți evidența în ce direcție suntem merge
- Când se atinge un etaj și butonul respectiv a fost apăsat, opriți și deschideți ușile, marcați butoanele pentru acest etaj ca nu mai sunt apăsate.
-
- Dacă există încă mai multe etaje pe care trebuie să le vizităm care se află în aceeași direcție, continuați în acea direcție .
- Dacă nu și există încă etaje pe care trebuie să le vizităm, mutați-vă în acea direcție.
- Dacă nu, atunci am terminat și vom începe de la 1 când se apasă din nou un buton.
Notă că multe lifturi au butoane „Vreau să urc” și „Vreau să cobor” lângă uși în loc de un singur buton. algoritmul are nevoie doar de o mică modificare: în 2, dacă singurul buton apăsat pentru acel etaj este unul dintre butoanele de lângă ușă, opriți-vă și deschideți ușile doar dacă mergem în acea direcție. Țineți posibil butonul apăsat dacă ușile se deschid din cauza unui buton apăsat în interiorul liftului și merge în direcția greșită.
Nu trebuie să vă dați seama niciodată de o cale întreagă, tocmai în ce direcție să urmez.
Comentarii
- asta mi-a sărit complet în minte, am fost atât de concentrat pe eficiență și am uitat că și alte lucruri sunt importante . ‘ încă nu este eficient să spunem de la 2- > 100 și înapoi la 1 pur și simplu pentru că era în aceeași direcție, dar la cel puțin nu asigură lipsa de foame. și, complet lipsit de subiect, poate de aceea este ‘ obișnuit să găsești două ascensoare cu această logică? ceea ce mă face să mă întreb dacă este ‘ mai frecvent găsirea ascensoarelor care merg în direcția opusă la un moment dat. oricum, ‘ sunt încă curios să găsesc cea mai scurtă cale întreagă, dar acest lucru îmi răspunde foarte bine la întrebare, mulțumesc
- Rețineți că, odată ce ajungeți la o clădire cu 100 de etaje, în mod obișnuit veți avea lifturi care deservesc doar o anumită gamă de etaje (de exemplu, 0-19, 20-39, …), precum și lifturi expres care merg doar pe distanțe lungi (de exemplu, 0 la 50, 0 la 100 , Între 50 și 100, dar nu există etaje între ele), deci este posibil să trebuiască să schimbați lifturile pentru a ajunge la destinație. S-ar putea să aveți, de asemenea, mai multe lifturi pe arbore care, evident, nu se pot trece unul pe celălalt.Total sub-subiect: IIRC, a existat o întrebare cu privire la eficiența acelor butoane cu săgeți în sus și în jos de pe site-ul User Experience , ceea ce a făcut o lectură foarte fascinantă.
- mulțumesc, nu ‘ nu știam asta. subdivizarea pare a fi o strategie bună dacă o parte descompune întregul sistem nu ‘ t și, de asemenea, să distribuie sarcina care este importantă pentru uzura mecanică. Mă întreb dacă aceste ascensoare expres s-au datorat deficiențelor logice ale algoritmului Knuth ‘ s Elevator.
- numai alt lucru i ‘ adăugăm că deseori au un etaj ‘ acasă ‘ la care vor reveni când nu vor fi folosiți, acest lucru poate fi diferit pentru diferite ascensoare și poate chiar să se schimbe în funcție de ora din zi și de tiparele de utilizare așteptate
- Am tendința de a apăsa butonul sus / jos semi aleatoriu, indiferent de ce direcție I călătoresc de fapt. În cazul meu, am doar o singură destinație, astfel încât liftul mă duce în acea locație, indiferent dacă am ales în sus sau în jos. Bănuiesc că, dacă ar fi să apăs butonul în jos, să aleg un etaj deasupra mea și apoi să aleg un etaj sub mine înainte ca liftul să înceapă să se miște, m-ar duce la podeaua de sub mine, mai degrabă decât la podeaua pe care am împins-o prima. M-aș putea înșela, ‘ voi fi sigur că o voi testa data viitoare când mă voi găsi într-un lift.
Răspuns
Celălalt răspuns oferă corect algoritmul standard al elevatorului, care este practic „continuați în aceeași direcție cât mai mult posibil și faceți fiecare oprire necesară pe parcurs”.
Există și alți algoritmi de ascensor. De exemplu, luați în considerare o clădire de apartamente în care apartamentele devin mai scumpe pe măsură ce urcați. Proprietarii clădirii ar putea alege să modifice algoritmul ascensorului pentru a „merge în aceeași direcție cât mai mult posibil, dar să se oprească doar la coborâre”. În acest fel, dacă aveți oameni în lift, care se află în hol și merg la 2, 5 și 10, liftul merge la 10, apoi 5, apoi 2, lăsând oamenii în jos în funcție de cât chirie plătesc. Dar, bineînțeles, când persoanele din 10 părăsesc apartamentul lor, vor trebui să aștepte mai des pentru a ajunge în hol.
Dacă căutați o soluție eficientă apoi veniți cu o valoare pentru cost și implementați o grămadă de algoritmi diferiți și rulați simulări. Nu uitați să măsurați nu doar costul mediu, ci și valori cum ar fi cea mai lungă cerere pentru a fi deservită. Optimizarea pentru medii scăzute poate uneori dezoptimiza cel mai rău caz, ceea ce este rău.
Comentarii
- Se pare că este rar (alte alogirthmi)
Răspuns
Rețineți că elevatoarele folosesc aceiași algoritmi de planificare ca unele controlere de hard disk. Algoritmul SCAN standard este chiar cunoscut sub numele de algoritm elevator . Cred că în practică algoritmul LOOK este mai frecvent, deoarece este puțin mai eficient decât SCAN.
Comentarii
- Când vorbiți atât de sigur, aveți experiență profesională în implementarea codului pentru lifturi? Mai ales sisteme de ascensoare mai noi? Sunt curios dacă după 11 septembrie în New York a existat o prioritate mai mare în trimiterea pasagerilor în jos față de ridicarea acestora.
- Scoateți pasagerii afară, nu în jos. Folosesc adesea liftul într-o parcare, unde etajul al treilea de la etajele 1 până la 6 este la parter, așa că pentru a scăpa, etajul 3 ar fi cel mai bun.
Răspuns
Acest răspuns este despre un sistem de control al destinației mai avansat . Într-o clădire cu mai multe lifturi în care oamenii indică la ce etaj doresc să meargă și sistemul le atribuie un lift.
Ideea este destul de simplă, teoretic știi unde se îndreaptă toată lumea și fiecare lift. Astfel, puteți pentru fiecare lift, calculați când este timpul estimat de sosire și cât de mult îi va încetini pe ceilalți. Alegeți cu lăcomie cel mai rapid lift.
Există limitări, cum ar fi grupurile care apasă butonul o singură dată și persoanele care apasă butonul de mai multe ori.
Lasă un răspuns