Vilken algoritm används av hissar för att hitta den kortaste vägen till resgolvbeställningar?
On februari 15, 2021 by adminJag försöker simulera en hiss, som alltid började jag väldigt enkelt genom att bara ta en enda beställning åt gången och sedan lägga till minne i hissen i i form av köer så att golv färdas i den ordning de trycktes in, vilket uppenbarligen inte är det bästa tillvägagångssättet.
Så just nu använder jag en mycket enkel och ”kortsiktig” logik som är, för den aktuella våningen, hitta golvet närmast mig och ställ in det som min nästa destination och slinga tills inga fler våningar finns i listan.
Men det fungerar inte alltid, till exempel hiss var på 3: e våningen i en 5 vånings byggnad och fick order 4,5,2 den kortaste vägen skulle vara 2-> 4-> 5 som kostar 4 våningar men med denna logik 4-> 5-> 2 som kostar 5 har samma chans att bli plockad, beroende på kod.
Hur hittar jag den kortaste vägen och effektiviserar hissen?
Kommentarer
- Något relaterat: programmers.stackexchange.com/q/96278/149904
- Jag ’ vill bjuda in dig till mitt kontor och ta reda på algoritmen som hissarna använder där. Eftersom jag absolut inte kan ’ t.
- @ gnasher729 Åh, jag kan trots att jag inte ’ inte känner dig , eftersom det ’ säkert är detsamma som på mitt kontor: stanna aldrig vid golvet jag ’ är inne, förutom när det redan är fullt av människor. Har jag rätt?
- Inte riktigt. Det finns fyra hissar. Du trycker på knappen, ingenting rör sig på mycket länge. Om en rör sig stannar den precis innan golvet och väntar i evigheter, tills den omges av en annan som går förbi golvet och sedan kommer ner. På väg ner till marken stannar det minst tre gånger utan att någon kommer in.
- Relevant programmeringsspel / utmaning: play.elevatorsaga.com
Svar
”Effektivitet” är inte den viktigaste funktionen, det viktigaste är att se till att alla ordning följs, att det inte finns någon svält. Om någon trycker på 100 och människor fortsätter att trycka på 1 och 2 kan det vara effektivt att fortsätta mellan dessa våningar, men det skulle vara trevligt att 100 besökas någon gång.
Jag tänker (från personlig observation när jag var intresserad av att ta reda på) att de flesta av dem gör:
- Börja gå i riktning mot den första knappen som du trycker på, håll reda på vilken riktning vi är går
- När ett golv når och den knappen trycks in, stanna och öppna dörrarna, markera knapparna för det här golvet som inte längre tryckta.
-
- det finns fortfarande fler våningar som vi behöver besöka som är i samma riktning, fortsätt i den riktningen .
- Om inte och det finns fortfarande våningar måste vi besöka, flytta i den riktningen.
- Om inte så är vi klara och börjar klockan 1 när en knapp trycks in igen.
Obs att många hissar har knappar ”Jag vill gå upp” och ”Jag vill gå ner” bredvid dörrarna istället för en enda knapp. algoritmen behöver bara en liten förändring: i 2, om den enda knappen som trycks ned för det golvet är en av knapparna bredvid dörren, stanna bara och öppna dörrarna om vi går i den riktningen. Håll eventuellt knappen nedtryckt om dörrarna öppnas på grund av en knapp som trycks in i hissen och den går åt fel håll.
Du behöver aldrig räkna ut en hel stig , precis i vilken riktning jag ska gå vidare.
Kommentarer
- detta hoppade helt över mig, jag var så fokuserad på effektivitet och glömde att andra saker är viktiga också . det ’ är fortfarande inte effektivt att säga från 2- > 100 och tillbaka till 1 helt enkelt för att det var i samma riktning men vid det säkerställer åtminstone ingen svält. och, helt utanför ämnet, kanske det är därför det ’ är vanligt att hitta två hissar med denna logik? vilket får mig att undra om det ’ är vanligare att hitta hissarna går i motsatt riktning vid varje given tidpunkt. Hur som helst är jag ’ fortfarande nyfiken på hur jag hittar den kortaste hela vägen, men det svarar på min fråga väldigt snyggt, tack
- Observera att när du väl kommer till en byggnad med 100 våningar, kommer du vanligtvis att ha hissar som endast betjänar ett visst golvområde (t.ex. 0-19, 20-39, …), samt expresshissar som bara går långa sträckor (t.ex. 0 till 50, 0 till 100 , 50 till 100, men inga golv däremellan), så du kan behöva byta hiss för att komma till din destination. Du kan också ha flera hissar per axel som uppenbarligen inte kan passera varandra.Helt utanför ämnet: IIRC, det fanns en fråga om effektiviteten hos dessa upp- och nedpilar på Användarupplevelse -sidan som gav mycket fascinerande läsning.
- tack, jag visste inte ’ det. delning verkar som en bra strategi om en del bryter ner hela systemet inte ’ t och också för att fördela belastningen som är viktig för mekaniskt slitage. Jag undrar om dessa expresshissar berodde på de logiska bristerna i Knuth ’ s Hissalgoritm.
- bara andra saker jag ’ tillägg är att de ofta har ett ’ hem ’ golv som de kommer att återvända till när de inte används, detta kan vara annorlunda för olika hissar, och eventuellt till och med förändras beroende på tid på dagen och förväntade användningsmönster.
- Jag har en tendens att trycka upp / ner-knappen semi slumpmässigt oavsett vilken riktning jag ”9caafe2044”>
Jag reser faktiskt. I mitt fall har jag bara någonsin en destination, så hissen tar mig till den platsen oavsett om jag väljer upp eller ner. Jag misstänker att om jag skulle trycka nedåtknappen, välja ett golv ovanför mig och sedan välja ett golv under mig innan hissen börjar röra sig, skulle det ta mig till golvet nedanför mig snarare än golvet som jag tryckte först. Jag kan ha fel, jag ’ kommer nog att testa nästa gång jag befinner mig i en hiss.
Svar
Det andra svaret ger korrekt hissalgoritmen, som i princip är ”fortsätt i samma riktning så länge som möjligt och gör alla nödvändiga stopp längs vägen”.
Det finns andra hissalgoritmer. Tänk till exempel på en hyreshus där lägenheter blir dyrare när du går upp. Ägarna till byggnaden kan välja att ändra hissalgoritmen för att ”gå i samma riktning så länge som möjligt men bara stanna på väg ner”. På det sättet om du har människor i hissen som är i lobbyn och går till 2, 5 och 10, går hissen till 10, sedan 5, sedan 2 och släpper folk i ordning efter hur mycket hyra de betalar. Men naturligtvis när människor på 10 lämnar sin lägenhet måste de oftare vänta längre för att komma till lobbyn.
Om du letar efter en effektiv lösning kom sedan med ett mått för kostnad och implementera en massa olika algoritmer och kör simuleringar. Kom ihåg att inte bara mäta genomsnittskostnaden utan även mått som den längsta som en begäran tar för att få service. Optimering för låga medel kan ibland deoptimera det värsta fallet, vilket är dåligt.
Kommentarer
- Det verkar vara sällsynt (andra alogirthms)
Svar
Observera att hissar använder samma schemaläggningsalgoritmer som vissa hårddiskstyrenheter. Standard-SCAN-algoritmen är även känd som hissalgoritmen . Jag tror att LOOK -algoritmen är vanligare, eftersom den är lite effektivare än SCAN.
Kommentarer
- Har du yrkeserfarenhet att implementera koden för hissar när du talar så säkert? Särskilt nyare hissystem? Jag är nyfiken på om det efter 9/11 i NYC har varit högre prioritet att skicka passagerare ner kontra att föra upp dem.
- Ta ut passagerare, inte ner. Jag använder ofta hissen på en parkeringsplats, där tredje våningen på våningarna 1 till 6 är marknivån, så för att fly, skulle våning 3 vara bäst.
Svar
Detta svar handlar om ett mer avancerat destinationsstyrsystem . I en byggnad med flera hissar där människor anger vilket våning de vill gå till och systemet tilldelar en hiss till dem.
Idén är ganska enkel, teoretiskt vet du vart alla och varje hiss ska åka. Så du kan för varje hiss, beräkna När din förväntade ankomsttid är och hur mycket det kommer att sakta ner de andra. Välj girigt den snabbaste hissen.
Det finns begränsningar för detta, till exempel att grupper bara trycker på knappen en gång och personer som trycker på knappen flera gånger.
Lämna ett svar