Jaký algoritmus používají výtahy k nalezení nejkratší cesty k objednávkám na podlaze?
On 15 února, 2021 by adminPokouším se simulovat výtah, jako vždy jsem začal velmi jednoduše tím, že jsem bral vždy jen jednu objednávku, poté jsem do výtahu přidal paměť forma front tak, že se podlahy pohybují v pořadí, v jakém byly stisknuty, což samozřejmě není nejlepší přístup.
Takže v tuto chvíli používám velmi jednoduchý a „krátkozraký“ logika, což je, pro aktuální podlaží najděte podlahu nejblíže ke mně a nastavte ji jako svůj další cíl a smyčku, dokud v seznamu nebudou další podlaží.
Ale to nefunguje vždy, například výtah byl ve 3. patře pětipodlažní budovy a dostal objednávky 4,5,2, nejkratší cesta by byla 2-> 4-> 5, která stojí 4 patra, ale pomocí této logiky 4-> 5-> 2, která stojí 5 má stejná šance na výběr, v závislosti na kódu.
Jak najdu nejkratší cestu a zefektivním výtah?
Komentáře
- Trochu související: programmers.stackexchange.com/q/96278/149904
- Rád bych vás ' pozval do mé kanceláře a vymyslel algoritmus, který tam výtahy používají. Protože absolutně nemohu ' t.
- @ gnasher729 Oh, nemohu, i když tě ' neznám , protože ' to je určitě to samé jako v mé kanceláři: nikdy se nezastavujte na podlaze, ' m, kromě případů, kdy už je plná lidé. Mám pravdu?
- Ne tak docela. K dispozici jsou čtyři výtahy. Stisknete-li tlačítko, nic se velmi dlouho nepohybuje. Pokud se někdo pohne, zastaví se těsně před vaší podlahou a čeká na věky, dokud ji nepřekoná další, která projde kolem vaší podlahy a poté sestoupí. Na cestě dolů k zemi se zastaví alespoň třikrát, aniž by do něj někdo vstoupil.
- Relevantní programovací hra / výzva: play.elevatorsaga.com
Odpověď
„Efektivita“ není nejdůležitější funkce, nejdůležitější je zajistit, aby každý je dodržován řád, že není hladovění. Pokud někdo stiskne 100 a lidé stisknou 1 a 2, může být efektivní pokračovat v přechodu mezi těmito patry, ale bylo by hezké, aby bylo v určitém okamžiku 100 navštíveno.
Myslím / em> (z osobního pozorování, když mě zajímalo zjistit), které většina z nich dělá:
- Začněte jít ve směru prvního stisknutého tlačítka, sledujte, kterým směrem jsme jede
- Když je dosaženo podlahy a bylo stisknuto toto tlačítko, zastavte a otevřete dveře, označte tlačítka této podlahy jako již nestisknutá.
-
- Pokud stále existuje více podlaží, která musíme navštívit a která jsou ve stejném směru, pokračujte tímto směrem .
- Pokud ne a stále existují podlaží, která musíme navštívit, přesuňte se v tomto směru.
- Pokud ne, pak jsme hotovi a začneme v 1 dalším stiskem tlačítka.
Poznámka že mnoho výtahů má místo dveří tlačítko „Chci jít nahoru“ a „Chci jít dolů“ vedle dveří. Algoritmus potřebuje jen malou změnu: ve 2, pokud je jediným tlačítkem stisknutým pro danou podlahu jedno z tlačítek vedle dveří, zastavte a otevřete dveře pouze tehdy, když jdeme tímto směrem. Je možné, že podržte stisknuté tlačítko, pokud jsou dveře otevřené kvůli stisknutému tlačítku uvnitř výtahu a jde špatným směrem.
Nikdy nemusíte přijít na celou cestu , jen kterým směrem se vydat dál.
Komentáře
- to mi úplně přeskočilo mysl, byl jsem tak zaměřený na efektivitu a zapomněl jsem, že jsou důležité i další věci . ' stále není efektivní jít říkat z 2- > 100 a zpět na 1 jednoduše proto, že to bylo ve stejném směru, ale na alespoň to nezajišťuje hladovění. a zcela mimo téma, možná právě proto je ' běžné najít dva výtahy s touto logikou? což mě nutí přemýšlet, jestli je ' běžnější najít výtahy v opačném směru v daném okamžiku. Každopádně jsem ' stále zvědavý, jak najít nejkratší celou cestu, ale na mou otázku to odpovídá velmi úhledně, díky
- Všimněte si, že jakmile se dostanete na budova se 100 podlažími, obvykle budete mít výtahy obsluhující pouze konkrétní rozsah podlaží (např. 0-19, 20-39, …), stejně jako expresní výtahy, které jezdí pouze na velké vzdálenosti (např. 0 až 50, 0 až 100 , 50 až 100, ale bez podlaží), takže možná budete muset změnit výtahy, abyste se dostali do cíle. Můžete mít také několik výtahů na jednu šachtu, které se očividně nemohou navzájem projít.Zcela mimo téma: IIRC, na webu User Experience byla otázka efektivity těchto tlačítek se šipkami nahoru a dolů, která umožnila velmi fascinující čtení.
- děkuji, ' to nevím. Rozdělení se jeví jako dobrá strategie, pokud jedna část rozbije celý systém a nerozdělí také zatížení, které je důležité pro mechanické opotřebení. Zajímalo by mě, jestli tyto expresní výtahy vznikly kvůli logickým nedostatkům algoritmu Knuth ' s Elevator.
- pouze další věc, kterou jsem Je třeba dodat, že často mají ' domovskou ' podlahu, do které se vrátí, když se nepoužívají, to se může u různých výtahů lišit a případně se to může měnit v závislosti na denní době a očekávaných vzorcích využití.
- Mám tendenci tlačit tlačítko nahoru / dolů částečně náhodně bez ohledu na to, jakým směrem I ' Ve skutečnosti cestuji dovnitř. V mém případě mám vždy jen jeden cíl, takže mě výtah dovede na toto místo bez ohledu na to, zda jsem zvolil nahoru nebo dolů. Mám podezření, že kdybych měl zmáčknout tlačítko dolů, vybrat si podlahu nade mnou a pak vybrat podlahu pode mnou, než se výtah začne pohybovat, dostalo by mě to na podlahu pode mnou, spíše než na podlahu, kterou jsem stiskl jako první. Mohl bych se mýlit, ' si to určitě vyzkouším, až se příště ocitnu ve výtahu.
Odpovědět
Druhá odpověď správně udává standardní algoritmus výtahu, který je v zásadě „držte se co nejdéle stejným směrem a po cestě proveďte všechny nezbytné zastávky“.
Existují i jiné algoritmy výtahu. Zvažte například bytový dům, kde jsou byty dražší, jak jdete nahoru. Majitelé budovy se mohou rozhodnout upravit algoritmus výtahu tak, aby „šli co nejdéle stejným směrem, ale zastavili se pouze cestou dolů“. Tímto způsobem, pokud máte ve výtahu lidi, kteří jsou ve vstupní hale a jdou na 2, 5 a 10, výtah jede na 10, pak na 5, pak na 2, kteří lidi vysazují v pořadí podle toho, kolik platí nájem. Ale samozřejmě, když lidé 10. dne opustí svůj byt, „budou častěji muset čekat déle, než se dostanou do haly.
Pokud hledáte efektivní řešení pak přijďte s metrikou nákladů a implementujte spoustu různých algoritmů a spusťte simulace. Nezapomeňte měřit nejen průměrné náklady, ale také metriky, jako je nejdelší doba, po kterou bude každý požadavek obsluhován. Optimalizace pro nízké průměry může někdy optimalizovat nejhorší případ, který je špatný.
Komentáře
- Zdá se to vzácné (jiné alogirthmy)
Odpověď
Upozorňujeme, že výtahy používají stejné plánovací algoritmy jako některé řadiče pevných disků. Standardní algoritmus SCAN je dokonce známý jako algoritmus výtahu . V praxi si myslím, že algoritmus LOOK je běžnější, protože je o něco efektivnější než SCAN.
Komentáře
- Když mluvíte tak jistě, máte profesionální zkušenosti s implementací kódu pro výtahy? Zvláště novější výtahové systémy? Zajímalo by mě, jestli po 11. září v NYC byla vyšší priorita při posílání cestujících dolů než při jejich zvedání.
- Dostaňte cestující ven, ne dolů. Často používám výtah na parkovišti, kde je třetí patro 1. až 6. patra přízemní, takže k útěku by bylo nejlepší 3. patro.
Odpověď
Tato odpověď se týká pokročilejšího cílového kontrolního systému . V budově s několika výtahy, kde lidé označují, do kterého patra chtějí jít, a systém jim přiřadí výtah.
Myšlenka je poměrně jednoduchá, teoreticky víte, kam každý a každý výtah jede. Takže u každého výtahu můžete vypočítat, kdy je váš očekávaný čas příjezdu a jak moc zpomalí ostatní. Chamtivě vybrat nejrychlejší výtah.
Existují omezení, například skupiny, které stisknou tlačítko pouze jednou a lidé, kteří stisknou tlačítko několikrát.
Napsat komentář