Hvilken algoritme brukes av heiser for å finne den korteste veien for å reise gulvordrer?
On februar 15, 2021 by adminJeg prøver å simulere en heis, som alltid begynte jeg veldig enkelt ved å ta bare en enkelt ordre om gangen, og la deretter til minnet til heisen i formen av køer slik at gulv beveges i den rekkefølgen de ble presset i, noe som åpenbart ikke er den beste tilnærmingen.
Så for øyeblikket bruker jeg en veldig enkel og «kortsiktig» logikk som er, for den nåværende etasjen, finn gulvet nærmest meg og sett det som min neste destinasjon og sløyfe til ingen flere etasjer er i listen.
Men dette fungerer ikke alltid, for eksempel heis var i 3. etasje i en 5 etasjes bygning og fikk ordre 4,5,2 den korteste veien ville være 2-> 4-> 5 som koster 4 etasjer, men bruker denne logikken 4-> 5-> 2 som koster 5 har den samme sjansen for å bli plukket, avhengig av koden.
Hvordan finner jeg den korteste veien og effektiviserer heisen?
Kommentarer
- Noe relatert: programmers.stackexchange.com/q/96278/149904
- Jeg ‘ vil invitere deg til kontoret mitt og finne ut algoritmen som heisene bruker der. Fordi jeg absolutt ikke kan ‘ t.
- @ gnasher729 Åh, jeg kan selv om jeg ikke ‘ ikke kjenner deg , fordi det ‘ sikkert er det samme som på kontoret mitt: stopp aldri på gulvet jeg ‘ er inne, bortsett fra når det allerede er fullt av mennesker. Har jeg rett?
- Ikke helt. Det er fire heiser. Du trykker på knappen, ingenting beveger seg veldig lenge. Hvis en beveger seg, stopper den rett før gulvet ditt og venter i evigheter, til det blir forbigått av en annen som går forbi gulvet ditt og deretter kommer ned. På vei ned til bakken stopper det minst tre ganger uten at noen kommer inn.
- Relevant programmeringsspill / utfordring: play.elevatorsaga.com
Svar
«Effektivitet» er ikke den viktigste funksjonen, det viktigste er å sørge for at ordren følges, at det ikke er sult. Hvis noen trykker 100 og folk fortsetter å trykke 1 og 2, kan det være effektivt å fortsette mellom disse etasjene, men det ville være fint for 100 å få besøk på et eller annet tidspunkt.
Jeg tror (fra personlig observasjon da jeg var interessert i å finne ut) at de fleste av dem gjør:
- Begynn å gå i retning av den første knappen som trykkes ned, hold rede på hvilken retning vi går
- Når et gulv er nådd og den knappen ble trykket på, stopp og åpne dørene, merk knappene for denne etasjen som ikke lenger trykket.
-
- Hvis det er fortsatt flere etasjer som vi trenger å besøke som er i samme retning, fortsett i den retningen .
- Hvis ikke, og det er fremdeles etasjer vi trenger å besøke, flytt i den retningen.
- Hvis ikke, er vi ferdige og starter kl. 1 når en knapp trykkes på igjen.
Merk at mange heiser har knappene «Jeg vil gå opp» og «Jeg vil gå ned» ved siden av dørene i stedet for en enkelt knapp. algoritmen trenger bare en liten endring: i 2, hvis den eneste knappen som trykkes for det gulvet er en av knappene ved siden av døren, må du bare stoppe og åpne dørene hvis vi går i den retningen. Muligens holde knappen inne hvis dørene åpnes på grunn av en knapp som er trykket inne i heisen og den går i feil retning.
Du trenger aldri å finne ut en hel sti , bare i hvilken retning jeg skal gå videre.
Kommentarer
- dette hoppet helt over tankene mine, jeg var så fokusert på effektivitet og glemte at andre ting er viktig også . det ‘ er fortsatt ikke effektivt å si fra 2- > 100 og tilbake til 1 bare fordi det var i samme retning men kl. i det minste sørger det ikke for sult. og, helt utenfor emnet, er det kanskje derfor det ‘ er vanlig å finne to heiser med denne logikken? som får meg til å lure på om det ‘ er mer vanlig å finne heisene som går i motsatt retning til enhver tid. uansett, jeg ‘ er fortsatt nysgjerrig på hvordan du finner den korteste hele veien, men dette svarer veldig pent på spørsmålet mitt, takk
- Merk at når du kommer til en bygning med 100 etasjer, vil du vanligvis ha heiser som bare betjener et bestemt utvalg av etasjer (f.eks. 0-19, 20-39, …), samt ekspressheiser som bare går lange avstander (f.eks. 0 til 50, 0 til 100 , 50 til 100, men ingen gulv i mellom), så du må kanskje bytte heis for å komme til destinasjonen. Du kan også ha flere heiser per skaft som åpenbart ikke kan passere hverandre.Helt utenfor emnet: IIRC, det var et spørsmål om effektiviteten til disse pilene opp og ned på Brukeropplevelse -siden som ga veldig fascinerende lesing.
- takk, jeg visste ikke ‘ det. underinndeling virker som en god strategi hvis en del bryter ned hele systemet ikke ‘ t og også for å fordele belastningen som er viktig for mekanisk slitasje. Jeg lurer på om disse ekspressheisene skyldtes de logiske manglene ved Knuth ‘ s Heisalgoritme.
- bare andre ting i ‘ d add er at de ofte har et ‘ hjem ‘ etasje som de vil komme tilbake til når de ikke er i bruk, dette kan være forskjellig for forskjellige heiser, og muligens til og med endre seg avhengig av tid på dagen og forventede bruksmønstre
- Jeg har en tendens til å trykke opp / ned-knappen semi tilfeldig uansett hvilken retning jeg ‘ Jeg reiser faktisk inn. I mitt tilfelle har jeg bare en destinasjon, så heisen tar meg til det stedet uansett om jeg valgte opp eller ned. Jeg mistenker at hvis jeg skulle trykke ned-knappen, velge et gulv over meg, og deretter velge et gulv under meg før heisen begynner å bevege seg, vil det ta meg til gulvet under meg i stedet for gulvet som jeg presset først. Jeg kan ta feil, jeg ‘ Jeg kommer til å teste det neste gang jeg befinner meg i heis.
Svar
Det andre svaret gir korrekt heisalgoritmen, som i utgangspunktet er «fortsett i samme retning så lenge som mulig og gjør alle nødvendige stopp underveis».
Det finnes andre heisalgoritmer. Tenk for eksempel på en bygård hvor leiligheter blir dyrere når du går opp. Eierne av bygningen kan velge å endre heisalgoritmen for å «gå i samme retning så lenge som mulig, men bare stoppe på vei ned». På den måten hvis du har folk i heisen som er i lobbyen og skal til 2, 5 og 10, går heisen til 10, deretter 5, deretter 2, og slipper folk av i rekkefølge hvor mye leie de betaler. Men selvfølgelig når folket på 10 forlater leiligheten sin, må de oftere vente lenger på å komme til lobbyen.
Hvis du leter etter en effektiv løsning så kom med en beregning for kostnad og implementer en rekke forskjellige algoritmer, og kjør simuleringer. Husk å måle ikke bare gjennomsnittskostnaden, men også beregninger som den lengste en forespørsel tar for å få service. Optimalisering for lave gjennomsnitt kan noen ganger deoptimere det verste tilfellet, noe som er dårlig.
Kommentarer
- Det ser ut til å være sjelden (andre fødsler)
Svar
Merk at heiser bruker de samme planleggingsalgoritmene som noen harddiskstyrere. Standard SCAN-algoritmen er til og med kjent som heisalgoritmen . Jeg tror i praksis at LOOK algoritmen er mer vanlig, siden den er litt mer effektiv enn SCAN.
Kommentarer
- Har du profesjonell erfaring med å implementere koden for heiser når du snakker så sikkert? Spesielt nyere heisesystemer? Jeg er nysgjerrig på om det etter 9/11 i NYC har vært høyere prioritet å sende passasjerer mot å bringe dem opp.
- Få passasjerer ut, ikke ned. Jeg bruker ofte heisen på en parkeringsplass, der tredje etasje i etasje 1 til 6 er bakkenivå, så for å unnslippe, ville etasje 3 være det beste.
Svar
Dette svaret handler om et mer avansert destinasjonskontrollsystem . I en bygning med flere heiser hvor folk indikerer hvilket gulv de vil gå til og systemet tildeler en heis til dem.
Ideen er ganske enkel, teoretisk vet du hvor alle og hver heis skal. Så du kan beregne når forventet ankomsttid er for hver heis og hvor mye den vil redusere de andre. Velg grådig den raskeste heisen.
Det er begrensninger for dette, for eksempel grupper som bare trykker på knappen en gang og folk som trykker på knappen flere ganger.
Legg igjen en kommentar