Milyen algoritmust használnak a liftek, hogy megtalálják a legrövidebb utat az emeleti megrendelésekhez?
On február 15, 2021 by adminMegpróbálok szimulálni egy felvonót, mint mindig, nagyon egyszerűen úgy kezdtem, hogy egyszerre csak egyetlen megrendelést vettem igénybe, majd memóriát adtam a liftbe. a sorok formája úgy, hogy az emeleteket a nyomás sorrendjében haladják, ami nyilvánvalóan nem a legjobb megközelítés.
Tehát jelenleg nagyon egyszerű és “rövidlátó” módszert használok logika, amely az aktuális emelethez keresse meg a hozzám legközelebb eső emeletet, és állítsa be a következő célomnak és a ciklusnak, amíg több emelet nem szerepel a listában.
De ez nem mindig működik, például lift egy 5. emeleti épület 3. emeletén volt és 4,5,2-es megrendeléseket kapott, a legrövidebb út a 2-> 4-> 5 lenne, ami 4 emeletbe kerül, de ezt a logikát használva 4-> 5-> 2, amelynek ára 5 a kódtól függően ugyanaz az esély a kiválasztásra.
Hogyan találhatom meg a legrövidebb utat és hogyan tehetem hatékonyabbá a liftet?
megjegyzések
- kissé összefüggőek: programers.stackexchange.com/q/96278/149904
- Én ‘ szeretném meghívni az irodámba, és kitalálni az algoritmust, amelyet a liftek ott használnak. Mert abszolút nem tudok ‘ t.
- @ gnasher729 Ja, még akkor is, ha nem tudom, hogy ‘ nem ismerlek , mert ‘ biztosan ugyanaz, mint az irodámban: soha ne álljon meg az emeleten I ‘ m, kivéve, ha már tele van emberek. Igazam van?
- Nem egészen. Négy lift van. Megnyomod a gombot, semmi sem mozog nagyon sokáig. Ha valaki elmozdul, az közvetlenül a padlója előtt áll meg, és életkorokat vár, amíg egy másik megelőzi, amely elhalad a padlón, majd lejön. A föld felé vezető úton legalább háromszor megáll, és senki sem lép be.
- Releváns programozási játék / kihívás: play.elevatorsaga.com
Válasz
A “hatékonyság” nem a legfontosabb jellemző, a legfontosabb az, hogy minden sorrendet követik, hogy nincs éhezés. Ha valaki megnyomja a 100-at, és az emberek folyamatosan lenyomják az 1-et és a 2-et, akkor hatékony lehet továbbmenni az emeletek között, de jó lenne, ha 100-at valamikor meglátogatnának.
Azt hiszem, (személyes megfigyelés alapján, amikor kíváncsi voltam a kitalálásra), hogy a legtöbben ezt teszik:
- Kezdje el haladni az első megnyomott gomb irányába, kövesse nyomon, melyik irányba tartunk megy
- Amikor elérte a padlót és megnyomta azt a gombot, álljon meg és nyissa ki az ajtókat, jelölje meg az emelet gombjait, hogy már nincsenek megnyomva.
-
- Ha még mindig vannak olyan emeletek, amelyeket meg kell látogatnunk, és amelyek ugyanabban az irányban vannak, haladj tovább ebben az irányban .
- Ha nem, és vannak még emeletek, amelyeket meg kell látogatnunk, mozogj ebben az irányban.
- Ha nem, akkor készen állunk, és 1-től kezdjük, amikor ismét megnyomunk egy gombot.
Megjegyzés hogy sok lift gombjai “fel akarok menni” és “le akarok menni” az ajtók mellett egyetlen gomb helyett. Az algoritmusnak csak egy apró változtatásra van szüksége: a 2-ben, ha az adott emeleten egyetlen gomb van megnyomva, az ajtó melletti gombok egyike van, akkor csak akkor álljon meg és nyissa ki az ajtókat, ha ebben az irányban haladunk. Esetleg tartsa lenyomva a gombot, ha az ajtók kinyílnak a lift belsejében lenyomott gomb miatt, és az rossz irányba halad.
Soha nem kell kitalálnia egy teljes utat , csak melyik irányba haladjak tovább.
Megjegyzések
- ez teljesen kihagyta az agyamat, annyira a hatékonyságra koncentráltam, és elfelejtettem, hogy más dolgok is fontosak . ‘ még mindig nem hatékony mondani a 2- > 100 értéket egyszerűen azért, mert ugyanabban az irányban volt, de legkevesebb, hogy nem éhezik. és, teljesen témátlanul, talán ezért ‘ szokott két liftet találni ezzel a logikával? ami elgondolkodtat bennem, hogy ‘ gyakoribb-e, ha az ellenkező irányba haladó lifteket bármikor megtaláljuk. Egyébként ‘ még mindig kíváncsi vagyok, hogyan lehet megtalálni a legrövidebb teljes utat, de ez nagyon szépen megválaszolja a kérdésemet, köszönöm
- Ne feledje, hogy ha eljut 100 emeletes épület, akkor általában csak bizonyos emelettartományt kiszolgáló liftek (pl. 0–19, 20–39,…), valamint csak nagy távolságokat megtöltő expressz liftek (pl. 0–50, 0–100) , 50 és 100 között, de nincs emelet között), ezért előfordulhat, hogy lifttel kell váltania, hogy célba érjen. Lehet, hogy tengelyenként több lift is van, amely nyilván nem haladhat el egymás mellett.Teljesen témán kívüli: IIRC, kérdés merült fel a felhasználói élmény webhelyen található fel és le nyílgombok hatékonyságával kapcsolatban, amelyek nagyon érdekes olvasást jelentettek.
- köszönöm, ezt nem tudtam ‘. a felosztás jó stratégiának tűnik, ha az egyik rész lebontja az egész rendszert, nem ‘ t, és elosztja a mechanikai kopás szempontjából fontos terhelést is. Kíváncsi vagyok, vajon ezek az expressz liftek a Knuth ‘ s Elevator algoritmus logikai hiányosságai miatt következtek-e be.
- csak más dolog i ‘ d hozzáteszi, hogy gyakran van egy ‘ home ‘ emeletük, ahová visszatérnek, ha nem használják őket, ez a különböző felvonóknál eltérő lehet, sőt a napszakától és a várható használati szokásoktól függően változhat
- hajlamos vagyok félig véletlenszerűen megnyomni a fel / le gombot, függetlenül attól, hogy melyik irányba I ‘ valójában beutazok. Esetemben csak egy célom van, ezért a lift elvisz erre a helyre, függetlenül attól, hogy felfelé vagy lefelé választottam. Gyanítom, hogy ha megnyomnám a lefelé gombot, választanék egy emeletet magam fölött, majd egy emeletet választanék alattam, mielőtt a lift elindulna, az inkább az alattam lévő emeletre visz, nem pedig arra a padlóra, amelyet először nyomtam. Tévedhetek, ‘ feltétlenül kipróbálom, ha legközelebb egy liftben találom magam.
Válasz
A másik válasz helyesen adja meg a szokásos liftalgoritmust, amely alapvetően “a lehető leghosszabb ideig haladjon ugyanabba az irányba, és minden szükséges megállást végezzen útközben”.
Vannak más felvonó algoritmusok is. Vegyünk például egy bérházat, ahol az apartmanok felfelé menet drágulnak. Az épület tulajdonosai dönthetnek úgy, hogy módosítják a lift algoritmusát, hogy “a lehető leghosszabb ideig ugyanabba az irányba haladjon, de csak a lefelé vezető úton álljon meg”. Így ha a liftben vannak olyan emberek, akik az előcsarnokban vannak, és a 2, 5 és 10 felé mennek, akkor a lift 10-re, majd 5-re, majd 2-re megy, és embereket enged le, annak sorrendjében, hogy mennyi bérleti díjat fizetnek. De természetesen amikor a 10-es emberek elhagyják a lakásukat, “gyakrabban kell tovább várniuk, hogy eljussanak az előcsarnokba.
Ha hatékony megoldást keres majd állítson elő egy költségmutatót, hajtson végre egy csomó különböző algoritmust, és futtasson szimulációkat. Ne felejtse el megmérni nemcsak az átlagos költségeket, hanem olyan mutatókat is, mint amelyek a leghosszabbak, ha bármelyik igényt kiszolgálják. Alacsony átlagokra történő optimalizálás néha deoptimalizálhatja a legrosszabb esetet, ami rossz.
Megjegyzések
- Úgy tűnik, hogy ritka (más alogirthmák)
Válasz
Vegye figyelembe, hogy a felvonók ugyanazokat az ütemezési algoritmusokat használják, mint néhány merevlemez-vezérlő. A szokásos SCAN algoritmus még lift algoritmusként is ismert . Úgy gondolom, hogy a gyakorlatban a LOOK algoritmus gyakoribb, mivel valamivel hatékonyabb, mint a SCAN.
Megjegyzések
- Ha ilyen biztosan beszél, van-e szakmai tapasztalata a liftek kódjának végrehajtásában? Különösen az újabb liftrendszerek? Kíváncsi vagyok, hogy szeptember 11-én NYC-ben nagyobb hangsúlyt fektettek-e az utasok leszállítására, mint az emelésre.
- Az utasokat szállítsa ki, ne pedig le. Gyakran használom a liftet egy parkolóban, ahol az 1–6. Emeletek harmadik emelete a földszint, így a szökéshez a 3. emelet lenne a legjobb.
Válasz
Ez a válasz egy fejlettebb célirányító rendszerről szól . Egy olyan épületben, amely több lifttel rendelkezik, ahol az emberek jelzik, hogy melyik emeletre akarnak menni, és a rendszer egy liftet rendel hozzájuk.
Az ötlet meglehetősen egyszerű, elméletileg tudod, merre jár mindenki és minden lift. Tehát minden liftnél kiszámíthatja, hogy mikor várható a várható érkezési idő, és mennyivel lassítja a többieket. Mohón válassza ki a leggyorsabb liftet.
Ennek vannak korlátai, például a csoportok csak egyszer nyomják meg a gombot, és az emberek többször is megnyomják a gombot.
Vélemény, hozzászólás?