Welcher Algorithmus wird von Aufzügen verwendet, um den kürzesten Weg zu Bodenbestellungen zu finden?
On Februar 15, 2021 by adminIch versuche, einen Aufzug zu simulieren, da ich immer sehr einfach angefangen habe, indem ich jeweils nur eine Bestellung entgegengenommen und dann dem Aufzug Speicher hinzugefügt habe die Form von Warteschlangen, so dass Fußböden in der Reihenfolge bewegt werden, in der sie gedrückt wurden, was offensichtlich nicht der beste Ansatz ist.
Im Moment verwende ich also einen sehr einfachen und „kurzsichtigen“ Logik: Suchen Sie für die aktuelle Etage die Etage, die mir am nächsten liegt, und legen Sie sie als nächstes Ziel und Schleife fest, bis keine weiteren Etagen mehr in der Liste enthalten sind.
Dies funktioniert jedoch nicht immer, z Der Aufzug befand sich im 3. Stock eines 5-stöckigen Gebäudes und erhielt Aufträge 4,5,2. Der kürzeste Weg wäre 2-> 4-> 5, was 4 Stockwerke kostet, aber unter Verwendung dieser Logik 4-> 5-> 2, was 5 kostet Je nach Code die gleiche Chance, ausgewählt zu werden.
Wie finde ich den kürzesten Weg und mache den Aufzug effizienter?
Kommentare
- Etwas verwandt: programmers.stackexchange.com/q/96278/149904
- Ich ‚ möchte Sie in mein Büro einladen und den Algorithmus herausfinden, den die Aufzüge dort verwenden. Weil ich ‚ t absolut kann.
- @ gnasher729 Oh, ich kann, obwohl ich Sie nicht ‚ kenne , weil es ‚ sicherlich dasselbe ist wie in meinem Büro: Halten Sie niemals auf dem Boden an, auf dem ich ‚ bin, außer wenn es bereits voll ist Menschen. Habe ich recht?
- Nicht ganz. Es gibt vier Aufzüge. Wenn Sie den Knopf drücken, bewegt sich sehr lange nichts. Wenn man sich bewegt, bleibt es direkt vor dem Boden stehen und wartet ewig, bis es von einem anderen überholt wird, der an Ihrem Boden vorbeigeht und dann herunterkommt. Auf dem Weg zum Boden stoppt es mindestens dreimal, ohne dass jemand eintritt.
- Relevantes Programmierspiel / Herausforderung: play.elevatorsaga.com
Antwort
„Effizienz“ ist nicht das wichtigste Merkmal, das wichtigste ist, sicherzustellen, dass alle Befehl wird befolgt, dass es keinen Hunger gibt. Wenn jemand 100 drückt und die Leute weiterhin 1 und 2 drücken, kann es effizient sein, zwischen diesen Stockwerken zu wechseln, aber es wäre schön, wenn 100 irgendwann besucht würden.
Ich denke (aus persönlicher Beobachtung, als ich herausfinden wollte), dass die meisten von ihnen Folgendes tun:
- Gehen Sie in Richtung des ersten gedrückten Knopfes und verfolgen Sie, in welche Richtung wir uns befinden gehen
- Wenn eine Etage erreicht ist und dieser Knopf gedrückt wurde, halten Sie an und öffnen Sie die Türen. Markieren Sie die Knöpfe für diesen Boden als nicht mehr gedrückt.
-
- Wenn Es gibt noch mehr Stockwerke, die wir besuchen müssen und die in die gleiche Richtung weisen. Gehen Sie weiter in diese Richtung.
- Wenn nicht und es gibt noch Stockwerke, die wir besuchen müssen, bewegen Sie sich in diese Richtung.
- Wenn nicht, sind wir fertig und beginnen bei 1, wenn eine Taste erneut gedrückt wird.
Hinweis dass viele Aufzüge neben den Türen die Knöpfe „Ich möchte hoch“ und „Ich möchte runter“ anstelle eines einzigen Knopfes haben Der Algorithmus benötigt nur eine kleine Änderung: Wenn in 2 der einzige Knopf, der für diese Etage gedrückt wird, einer der Knöpfe neben der Tür ist, halten Sie an und öffnen Sie die Türen nur, wenn wir in diese Richtung gehen. Halten Sie den Knopf möglicherweise gedrückt, wenn sich die Türen aufgrund eines Knopfes im Aufzug öffnen und dieser in die falsche Richtung zeigt.
Sie müssen nie einen ganzen Pfad herausfinden. Nur in welche Richtung ich als nächstes gehen soll.
Kommentare
- Das hat mich völlig überrumpelt. Ich war so auf Effizienz konzentriert und habe vergessen, dass auch andere Dinge wichtig sind . es ‚ ist immer noch nicht effizient, von 2- > 100 und zurück zu 1 zu gehen, einfach weil es in die gleiche Richtung war, aber um Zumindest sorgt es für keinen Hunger. und, vielleicht außerhalb des Themas, ist es vielleicht der Grund, warum es ‚ üblich ist, zwei Aufzüge mit dieser Logik zu finden? Ich frage mich daher, ob es ‚ häufiger vorkommt, dass die Aufzüge zu einem bestimmten Zeitpunkt in die entgegengesetzte Richtung fahren. Wie auch immer, ich ‚ bin immer noch neugierig, wie man den kürzesten gesamten Pfad findet, aber dies beantwortet meine Frage sehr ordentlich, danke
- Beachten Sie, dass Sie einmal angekommen sind In einem Gebäude mit 100 Stockwerken verfügen Sie normalerweise über Aufzüge, die nur einen bestimmten Bereich von Stockwerken bedienen (z. B. 0-19, 20-39,…), sowie über Expressaufzüge, die nur lange Strecken zurücklegen (z. B. 0 bis 50, 0 bis 100) , 50 bis 100, aber keine Etagen dazwischen), sodass Sie möglicherweise die Aufzüge wechseln müssen, um an Ihr Ziel zu gelangen. Möglicherweise haben Sie auch mehrere Aufzüge pro Schacht, die sich offensichtlich nicht passieren können.Völlig unangebracht: IIRC, es gab eine Frage zur Effizienz dieser Aufwärts- und Abwärtspfeiltasten auf der User Experience -Seite, die für eine sehr faszinierende Lektüre sorgte / li>
- danke, das wusste ich ‚ nicht. Eine Unterteilung scheint eine gute Strategie zu sein, wenn ein Teil das gesamte System ausfällt und nicht ‚ t und auch die Last verteilt, die für den mechanischen Verschleiß wichtig ist. Ich frage mich, ob diese Expressaufzüge auf die logischen Mängel des Knuth ‚ -Aufzugsalgorithmus zurückzuführen sind.
- nur eine andere Sache i ‚ d hinzufügen ist, dass sie häufig eine ‚ home ‚ Etage haben, zu der sie zurückkehren, wenn sie nicht verwendet werden. Dies kann für verschiedene Aufzüge unterschiedlich sein und sich möglicherweise sogar je nach Tageszeit und erwarteten Nutzungsmustern ändern.
- Ich neige dazu, die Auf- / Ab-Taste halb zufällig zu drücken, unabhängig davon, in welche Richtung ich ‚ reist tatsächlich ein. In meinem Fall habe ich immer nur ein Ziel, daher bringt mich der Aufzug zu diesem Ort, unabhängig davon, ob ich mich für oben oder unten entschieden habe. Ich vermute, wenn ich den Abwärtsknopf drücke, eine Etage über mir und dann eine Etage unter mir wähle, bevor sich der Aufzug in Bewegung setzt, würde ich eher in die Etage unter mir als in die Etage gelangen, die ich zuerst gedrückt habe. Ich könnte mich irren, ich ‚ werde es das nächste Mal testen, wenn ich mich in einem Aufzug befinde.
Antwort
Die andere Antwort gibt den Standard-Aufzugsalgorithmus korrekt an. Dieser lautet im Grunde „so lange wie möglich in die gleiche Richtung fahren und alle erforderlichen Stopps auf dem Weg einlegen“.
Es gibt andere Aufzugsalgorithmen. Stellen Sie sich zum Beispiel ein Wohnhaus vor, in dem Wohnungen mit dem Aufstieg teurer werden. Die Eigentümer des Gebäudes könnten den Aufzugsalgorithmus so ändern, dass er „so lange wie möglich in die gleiche Richtung fährt, aber nur auf dem Weg nach unten anhält“. Wenn Sie also Personen im Aufzug haben, die sich in der Lobby befinden und zu 2, 5 und 10 gehen, geht der Aufzug zu 10, dann zu 5, dann zu 2 und bringt die Leute in der Reihenfolge ihrer Miete ab. Aber wenn die Leute mit 10 ihre Wohnung verlassen, müssen sie natürlich öfter länger warten, um in die Lobby zu gelangen.
Wenn Sie nach einer effizienten Lösung suchen Überlegen Sie sich dann eine Kostenmetrik, implementieren Sie eine Reihe verschiedener Algorithmen und führen Sie Simulationen aus. Denken Sie daran, nicht nur die durchschnittlichen Kosten zu messen, sondern auch Kennzahlen wie die längste, die eine Anfrage für die Bearbeitung benötigt. Die Optimierung für niedrige Durchschnittswerte kann manchmal den schlimmsten Fall, der schlecht ist, deoptimieren.
Kommentare
- Es scheint selten zu sein (andere Alogirthmen)
Antwort
Beachten Sie, dass Aufzüge dieselben Planungsalgorithmen verwenden wie einige Festplattencontroller. Der Standard-SCAN-Algorithmus ist sogar als Aufzugsalgorithmus bekannt. Ich denke, in der Praxis ist der Algorithmus LOOK häufiger, da er etwas effizienter als SCAN ist.
Kommentare
- Wenn Sie so sicher sprechen, haben Sie Berufserfahrung in der Implementierung des Codes für Aufzüge? Besonders neuere Aufzugssysteme? Ich bin gespannt, ob es nach dem 11. September in NYC eine höhere Priorität hat, Passagiere nach unten zu schicken als nach oben zu bringen.
- Passagiere rausholen, nicht runter. Ich benutze den Aufzug oft auf einem Parkplatz, wo sich die dritte Etage der Etagen 1 bis 6 im Erdgeschoss befindet. Um zu entkommen, ist die 3. Etage die beste.
Antwort
Bei dieser Antwort handelt es sich um ein erweitertes Zielsteuerungssystem . In einem Gebäude mit mehreren Aufzügen, in dem Personen angeben, in welche Etage sie gehen möchten, und das System ihnen einen Aufzug zuweist.
Die Idee ist ziemlich einfach. Theoretisch wissen Sie, wohin jeder und jeder Aufzug fährt. So können Sie für jeden Aufzug berechnen, wann Ihre voraussichtliche Ankunftszeit ist und wie stark sie die anderen verlangsamt. Wählen Sie gierig den schnellsten Aufzug aus.
Hier gibt es Einschränkungen, z. B. Gruppen, die nur einmal auf die Taste drücken, und Personen, die die Taste mehrmals drücken.
Schreibe einen Kommentar