Hvilken algoritme bruges af elevatorer til at finde den korteste vej til at rejse gulvordrer?
On februar 15, 2021 by adminJeg prøver at simulere en elevator, som altid startede jeg meget simpelt ved kun at tage en enkelt ordre ad gangen og tilføjede hukommelse til elevatoren i formen af køer, så gulvene bevæges i den rækkefølge, de blev presset i, hvilket tydeligvis ikke er den bedste tilgang.
Så i øjeblikket bruger jeg en meget enkel og “kortsynt” logik, som er, for den aktuelle etage, find gulvet tættest på mig og indstil det som min næste destination og sløjfe, indtil der ikke er flere etager på listen.
Men det fungerer ikke altid, for eksempel elevator var i 3. sal i en bygning på 5 etager og fik ordrer 4,5,2, den korteste vej ville være 2-> 4-> 5, hvilket koster 4 etager, men ved hjælp af denne logik 4-> 5-> 2, der koster 5 har den samme chance for at blive valgt afhængigt af koden.
Hvordan finder jeg den korteste vej og gør elevatoren mere effektiv?
Kommentarer
- Noget relateret: programmers.stackexchange.com/q/96278/149904
- Jeg ‘ vil gerne invitere dig til mit kontor og finde ud af algoritmen, som elevatorerne bruger der. Fordi jeg absolut ikke kan ‘ t.
- @ gnasher729 Åh, jeg kan det, selvom jeg ikke ‘ ikke kender dig , fordi det ‘ helt sikkert er det samme som på mit kontor: stop aldrig ved gulvet, jeg ‘ er inde, undtagen når det allerede er fyldt med mennesker. Har jeg ret?
- Ikke helt. Der er fire elevatorer. Du trykker på knappen, intet bevæger sig i meget lang tid. Hvis man bevæger sig, stopper det lige før dit gulv og venter i evigheder, indtil det bliver overhalet af en anden, der går forbi dit gulv og derefter kommer ned. På vej ned til jorden stopper det mindst tre gange uden at nogen kommer ind.
- Relevant programmeringsspil / udfordring: play.elevatorsaga.com
Svar
“Effektivitet” er ikke den vigtigste funktion, det vigtigste er at sikre, at ordren følges, at der ikke er nogen sult. Hvis nogen trykker 100, og folk fortsætter med at trykke på 1 og 2, kan det være effektivt at fortsætte mellem disse etager, men det ville være rart for 100 at blive besøgt på et eller andet tidspunkt.
Jeg tænker (fra personlig observation, da jeg var interesseret i at finde ud af), at de fleste af dem gør:
- Start med at gå i retning af den første knap, der trykkes ned, hold styr på, hvilken retning vi er gå
- Når et gulv nås, og der trykkes på den knap, skal du stoppe og åbne dørene, markere knapperne til denne etage som ikke længere trykket.
-
- Hvis der er stadig flere etager, som vi har brug for at besøge, og som er i samme retning, fortsæt i den retning .
- Hvis ikke, og der er stadig etager, skal vi besøge, flyt i den retning.
- Hvis ikke, er vi færdige og starter kl. 1, når der trykkes på en knap igen.
Bemærk at mange elevatorer har knapper “Jeg vil gå op” og “Jeg vil ned” ved siden af dørene i stedet for en enkelt knap. algoritme behøver kun en lille ændring: i 2, hvis den eneste knap, der trykkes på for denne etage, er en af knapperne ved siden af døren, skal du kun stoppe og åbne dørene, hvis vi går i den retning. Hold muligvis knappen nede, hvis dørene åbnes på grund af en knap, der trykkes inde i elevatoren, og den går i den forkerte retning.
Du behøver aldrig finde ud af en hel sti , lige i hvilken retning jeg skal gå videre.
Kommentarer
- dette sprang mig helt over, jeg var så fokuseret på effektivitet og glemte andre ting er også vigtige . det ‘ er stadig ikke effektivt at sige fra 2- > 100 og tilbage til 1 simpelthen fordi det var i samme retning men kl. mindst det sikrer ingen sult. og helt uden for emnet, måske er det derfor, at det ‘ er almindeligt at finde to elevatorer med denne logik? hvilket får mig til at spekulere på, om det ‘ er mere almindeligt at finde elevatorer gå i den modsatte retning på et givet tidspunkt. alligevel, jeg ‘ er stadig nysgerrig efter, hvordan man finder den korteste hele sti, men det besvarer mit spørgsmål meget pænt, tak
- Bemærk, at når du først kommer til en bygning med 100 etager, vil du typisk have elevatorer, der kun betjener et specifikt udvalg af etager (f.eks. 0-19, 20-39,…) samt ekspres elevatorer, der kun går lange afstande (f.eks. 0 til 50, 0 til 100 , 50 til 100, men ingen etager imellem), så du bliver muligvis nødt til at skifte elevator for at komme til din destination. Du kan også have flere elevatorer pr. Skaft, der naturligvis ikke kan passere hinanden.Helt uden for emnet: IIRC, der var et spørgsmål om effektiviteten af disse pil op og pil ned på Brugeroplevelse -sitet, der skabte meget fascinerende læsning.
- tak, det vidste jeg ikke ‘. underopdeling virker som en god strategi, hvis en del nedbryder hele systemet ikke ‘ t og også for at fordele den belastning, der er vigtig for mekanisk slitage. Jeg spekulerer på, om disse ekspres elevatorer skyldtes de logiske mangler ved Knuth ‘ s Elevator algoritme.
- kun anden ting i ‘ tilføjelse er, at de ofte har et ‘ hjem ‘ etage, som de vender tilbage til, når de ikke er i brug, dette kan være forskelligt for forskellige elevatorer og muligvis endda ændre sig afhængigt af tidspunktet på dagen og forventede brugsmønstre
- Jeg har en tendens til at skubbe op / ned-knappen semi tilfældigt uanset hvilken retning jeg ‘ Jeg rejser faktisk ind. I mit tilfælde har jeg kun nogensinde en destination, så elevatoren fører mig til det sted, uanset om jeg valgte op eller ned. Jeg formoder, at hvis jeg skulle trykke på ned-knappen, vælge et gulv over mig og derefter vælge et gulv under mig, før elevatoren begynder at bevæge sig, ville det tage mig til gulvet under mig i stedet for det gulv, som jeg skubbede først. Jeg kunne tage fejl, jeg ‘ Jeg er sikker på at teste det næste gang jeg befinder mig i en elevator.
Svar
Det andet svar giver korrekt elevatoralgoritmen, som grundlæggende er “fortsæt i samme retning så længe som muligt og lav ethvert nødvendigt stop undervejs.” p>
Der er andre elevatoralgoritmer. Overvej f.eks. En lejlighedskompleks, hvor lejlighederne bliver dyrere, når du går op. Ejerne af bygningen vælger muligvis at ændre elevatoralgoritmen til at “gå i samme retning så længe som muligt, men kun stoppe på vej ned”. På den måde, hvis du har folk i elevatoren, der er i lobbyen og går til 2, 5 og 10, går elevatoren til 10, derefter 5, derefter 2, hvor de afleverer folk i rækkefølge efter, hvor meget husleje de betaler. Men selvfølgelig, når folk på 10 forlader deres lejlighed, bliver de oftere nødt til at vente længere på at komme til lobbyen.
Hvis du leder efter en effektiv løsning kom derefter med en metric for omkostninger og implementer en masse forskellige algoritmer, og kør simuleringer. Husk at måle ikke kun de gennemsnitlige omkostninger, men også målinger som den længste, som en anmodning tager for at blive serviceret. Optimering til lave gennemsnit kan undertiden deoptimere det værste tilfælde, hvilket er dårligt.
Kommentarer
- Det ser ud til at være sjældent (andre alogirths)
Svar
Bemærk, at elevatorer bruger de samme planlægningsalgoritmer som nogle harddiskcontrollere. Standard SCAN-algoritmen er endda kendt som elevatoralgoritmen . Jeg tror i praksis, at LOOK -algoritmen er mere almindelig, da den er lidt mere effektiv end SCAN.
Kommentarer
- Har du professionel erfaring med at implementere koden til elevatorer, når du taler så sikkert? Især nyere elevatorsystemer? Jeg er nysgerrig, om der efter 9/11 i NYC har været højere prioritet at sende passagerer ned vs. bringe dem op.
- Få passagerer ud, ikke ned. Jeg bruger ofte elevatoren på en parkeringsplads, hvor tredje sal i etage 1 til 6 er jordoverfladen, så for at undslippe ville etage 3 være det bedste.
Svar
Dette svar handler om et mere avanceret destinationsstyringssystem . I en bygning med flere elevatorer, hvor folk angiver, hvilken etage de vil gå til, og systemet tildeler en elevator til dem.
Ideen er ret enkel, teoretisk ved du, hvor alle og hver elevator skal hen. Så du kan for hver elevator beregne, hvornår din forventede ankomsttid er, og hvor meget den vil bremse de andre. Vælg grådigt den hurtigste elevator.
Der er begrænsninger for dette, såsom grupper, der kun trykker på knappen én gang, og folk, der trykker flere gange på knappen.
Skriv et svar