Welk algoritme wordt door liften gebruikt om de kortste weg te vinden naar vloerorders?
Geplaatst op februari 15, 2021 door adminIk “ik probeer een lift te simuleren, zoals altijd begon ik heel eenvoudig door slechts één bestelling per keer op te nemen en vervolgens geheugen toe te voegen aan de lift in de vorm van wachtrijen zodat verdiepingen worden afgelegd in de volgorde waarin ze werden ingedrukt, wat duidelijk niet “niet de beste benadering is.
Dus op dit moment gebruik ik een heel eenvoudige en” kortzichtige ” logica dat wil zeggen, zoek voor de huidige verdieping de verdieping die het dichtst bij mij in de buurt is en stel deze in als mijn volgende bestemming en loop totdat er geen verdiepingen meer in de lijst staan.
Maar dit werkt niet altijd, bijvoorbeeld de lift bevond zich op de 3e verdieping van een gebouw met 5 verdiepingen en kreeg bestellingen 4,5,2 het kortste pad zou 2-> 4-> 5 zijn, wat 4 verdiepingen kost, maar met behulp van deze logica 4-> 5-> 2 die 5 kost heeft dezelfde kans om gekozen te worden, afhankelijk van de code.
Hoe vind ik het kortste pad en maak ik de lift efficiënter?
Reacties
- Enigszins gerelateerd: programmers.stackexchange.com/q/96278/149904
- Ik ‘ zou je graag willen uitnodigen op mijn kantoor en het algoritme uitzoeken dat de liften daar gebruiken. Omdat ik ‘ t.
- @ gnasher729 absoluut kan ‘ t. Oh, ik kan het, ook al ken ik je niet ‘ , omdat het ‘ zeker hetzelfde is als in mijn kantoor: stop nooit bij de vloer waar ik ‘ binnen ben, behalve als het al vol is mensen. Heb ik gelijk?
- Niet helemaal. Er zijn vier liften. Je drukt op de knop, heel lang beweegt niets. Als er een beweegt, stopt hij vlak voor je verdieping en wacht eeuwen, totdat hij wordt ingehaald door een andere die voorbij je verdieping gaat en dan weer naar beneden komt. Op weg naar de grond stopt het minstens drie keer zonder dat er iemand binnenkomt.
- Relevant programmeerspel / uitdaging: play.elevatorsaga.com
Antwoord
“Efficiëntie” is niet het belangrijkste kenmerk, het belangrijkste is om ervoor te zorgen dat elke bevel wordt gevolgd, dat er geen hongersnood is. Als iemand op 100 drukt en mensen blijven op 1 en 2 drukken, kan het efficiënt zijn om tussen die verdiepingen te blijven gaan, maar het “zou leuk zijn als er ooit 100 bezocht worden.
Ik denk (uit persoonlijke observatie toen ik geïnteresseerd was om erachter te komen) dat de meeste van hen doen:
- Begin in de richting van de eerste ingedrukte knop te gaan, houd bij in welke richting we gaan gaan
- Wanneer een verdieping wordt bereikt en die knop is ingedrukt, stop en open de deuren, markeer de knoppen voor deze verdieping als niet meer ingedrukt.
-
- Als er zijn nog meer verdiepingen die we moeten bezoeken die in dezelfde richting zijn, blijf in die richting gaan .
- Als dit niet het geval is en er zijn nog steeds verdiepingen die we moeten bezoeken, verplaats dan in die richting.
- Zo niet, dan zijn we klaar en beginnen we bij 1 wanneer er opnieuw op een knop wordt gedrukt.
Opmerking dat veel liften de knoppen Ik wil naar boven en Ik wil naar beneden naast de deuren hebben in plaats van een enkele knop. algoritme behoeft slechts een kleine wijziging: in 2, als de enige knop die voor die verdieping wordt ingedrukt een van de knoppen naast de deur is, stop en open de deuren dan alleen als we in die richting gaan. Houd eventueel de knop ingedrukt als de deuren opengaan doordat er een knop in de lift is ingedrukt en deze de verkeerde kant op gaat.
Je hoeft nooit een heel pad uit te zoeken, precies in welke richting ik verder zou gaan.
Reacties
- dit sloeg mijn gedachten volledig over, ik was zo gefocust op efficiëntie en vergat dat andere dingen ook belangrijk zijn . het ‘ is nog steeds niet efficiënt om van 2- > 100 en terug naar 1 te gaan, simpelweg omdat het in dezelfde richting was maar op het verzekert tenminste geen uithongering. en, volledig buiten het onderwerp, is dit misschien waarom het ‘ is om twee liften met deze logica te vinden? waardoor ik me afvraag of het ‘ gebruikelijker is om de liften op een bepaald moment in de tegenovergestelde richting te zien gaan. hoe dan ook, ik ‘ ben nog steeds benieuwd hoe ik het kortste hele pad kan vinden, maar dit beantwoordt mijn vraag heel netjes, bedankt
- Merk op dat als je eenmaal bij een gebouw met 100 verdiepingen, heb je doorgaans liften die alleen een specifiek bereik van verdiepingen bedienen (bijv. 0-19, 20-39, …), evenals expressliften die alleen lange afstanden afleggen (bijv. 0 tot 50, 0 tot 100 50 tot 100, maar geen verdiepingen ertussen), dus het kan zijn dat u van lift moet veranderen om op uw bestemming te komen. Mogelijk hebt u ook meerdere liften per schacht die elkaar uiteraard niet kunnen passeren.Helemaal buiten het onderwerp: IIRC, er was een vraag over de efficiëntie van die pijltjestoetsen omhoog en omlaag op de Gebruikerservaring -site die voor een zeer fascinerende lezing zorgde. / li>
- bedankt, ik wist ‘ dat niet. onderverdelen lijkt een goede strategie als een onderdeel het hele systeem kapot maakt ‘ t en ook om de belasting te verdelen die belangrijk is voor mechanische slijtage. Ik vroeg me af of deze expresliften te wijten waren aan de logische tekortkomingen van het Knuth ‘ s Elevator-algoritme.
- het enige andere is ‘ toegevoegd is dat ze vaak een ‘ huis ‘ verdieping hebben waar ze naar terugkeren wanneer ze niet in gebruik zijn, dit kan verschillend zijn voor verschillende liften, en mogelijk zelfs veranderen afhankelijk van het tijdstip van de dag en de verwachte gebruikspatronen.
- Ik heb de neiging om de op / neer-knop half willekeurig in te drukken, ongeacht in welke richting ik ‘ m eigenlijk naar binnen. In mijn geval heb ik maar één bestemming, dus de lift brengt me naar die locatie, ongeacht of ik omhoog of omlaag kies. Ik vermoed dat als ik op de knop Omlaag zou drukken, een verdieping boven mij zou kiezen en dan een verdieping onder mij zou kiezen voordat de lift in beweging komt, deze me naar de verdieping onder mij zou brengen in plaats van naar de verdieping die ik het eerst duwde. Ik zou het mis kunnen hebben, ik ‘ zal het zeker testen de volgende keer dat ik me in een lift bevind.
Antwoord
Het andere antwoord geeft correct het standaard liftalgoritme, dat in feite is “blijf zo lang mogelijk in dezelfde richting gaan en maak onderweg elke noodzakelijke stop”.
Er zijn andere liftalgoritmen. Overweeg bijvoorbeeld een appartementengebouw waar appartementen duurder worden naarmate u hoger komt. De eigenaren van het gebouw kunnen ervoor kiezen om het liftalgoritme te wijzigen om “zo lang mogelijk in dezelfde richting te gaan, maar alleen op de weg naar beneden te stoppen”. Op die manier, als je mensen in de lift hebt die in de lobby zijn en naar 2, 5 en 10 gaan, gaat de lift naar 10, dan 5 en dan 2, mensen afzetten in volgorde van hoeveel huur ze betalen. Maar als de mensen op 10 verlaten hun appartement “zullen ze natuurlijk vaker langer moeten wachten om bij de lobby te komen.
Als je op zoek bent naar een efficiënte oplossing bedenk vervolgens een metriek voor de kosten en implementeer een heleboel verschillende algoritmen en voer simulaties uit. Vergeet niet om niet alleen de gemiddelde kosten te meten, maar ook statistieken zoals de langste tijd die nodig is om aan een verzoek te voldoen. Optimaliseren voor lage gemiddelden kan soms het ergste geval deoptimaliseren, wat slecht is.
Reacties
- Het lijkt zeldzaam te zijn (andere alogirthms)
Antwoord
Merk op dat liften dezelfde planningsalgoritmen gebruiken als sommige hardeschijfcontrollers. Het standaard SCAN-algoritme staat zelfs bekend als het liftalgoritme . Ik denk dat het LOOK -algoritme in de praktijk vaker voorkomt, omdat het iets efficiënter is dan SCAN.
Opmerkingen
- Als u zo zeker spreekt, heeft u dan professionele ervaring met het implementeren van de code voor liften? Vooral nieuwere liftsystemen? Ik ben benieuwd of er na 9/11 in NYC een hogere prioriteit is geweest bij het naar beneden sturen van passagiers dan bij het naar boven brengen.
- Haal passagiers eruit, niet naar beneden. Ik gebruik vaak de lift in een parkeergarage, waar de derde verdieping van de verdiepingen 1 tot 6 het maaiveld is, dus om te ontsnappen zou verdieping 3 de beste zijn.
Antwoord
Dit antwoord gaat over een meer geavanceerd bestemmingscontrolesysteem . In een gebouw met meerdere liften waar mensen aangeven naar welke verdieping ze willen gaan en het systeem hen een lift toewijst.
Het idee is vrij eenvoudig, in theorie weet je waar iedereen en elke lift heen gaat. U kunt dus voor elke lift berekenen wanneer uw verwachte aankomsttijd is en hoeveel deze de andere zal vertragen. Kies gretig de snelste lift.
Hier zijn beperkingen aan verbonden, zoals groepen die slechts één keer op de knop drukken en mensen die meerdere keren op de knop drukken.
Geef een reactie