Welcher Algorithmus wird von Aufzügen verwendet, um den kürzesten Weg zu Fahrbestellungen zu finden?

27

Ich versuche, einen Aufzug zu simulieren. Wie immer habe ich sehr einfach damit begonnen, immer nur eine Bestellung aufzunehmen und dann dem Aufzug Speicher in Form von Warteschlangen hinzuzufügen, damit die Stockwerke in der Reihenfolge zurückgelegt werden, in der sie gedrückt wurden. Das ist natürlich nicht der beste Ansatz.

Im Moment verwende ich eine sehr einfache und "kurzsichtige" Logik, bei der für die aktuelle Etage die nächstgelegene Etage ermittelt und als nächstes Ziel festgelegt wird und die Schleife ausgeführt wird, bis keine Etagen mehr in der Liste enthalten sind.

Dies funktioniert jedoch nicht immer. Zum Beispiel befand sich der Aufzug 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, hat die gleiche Chance, abhängig vom Code ausgewählt zu werden.

Wie finde ich den kürzesten Weg und mache den Aufzug effizienter?

Raed Tabani
quelle
6
Ich möchte Sie in mein Büro einladen und herausfinden, welchen Algorithmus die Aufzüge dort verwenden. Weil ich absolut nicht kann.
gnasher729
1
@ gnasher729 Oh, ich kann, auch wenn ich dich nicht kenne, denn es ist sicherlich dasselbe wie in meinem Büro: Halt niemals auf dem Boden an, in dem ich mich befinde, außer wenn bereits viele Leute da sind. Habe ich recht?
Andres F.
2
Nicht ganz. Es gibt vier Aufzüge. Sie drücken die Taste, es bewegt sich sehr lange nichts. Wenn man sich bewegt, stoppt es direkt vor dem Boden und wartet ewig, bis es von einem anderen überholt wird, der am Boden vorbeigeht und dann herunterkommt. Auf dem Weg zum Boden stoppt es mindestens dreimal, ohne dass jemand eintritt.
gnasher729
2
Relevantes Programmierspiel / Herausforderung: play.elevatorsaga.com
dwikle

Antworten:

30

"Effizienz" ist nicht das wichtigste Merkmal, das Wichtigste ist, sicherzustellen, dass jeder Bestellung gefolgt wird, dass es keinen Hunger gibt. Wenn jemand 100 drückt und die Leute weiterhin 1 und 2 drücken, ist es möglicherweise effizient, zwischen diesen Etagen zu wechseln, aber es wäre schön, wenn 100 irgendwann besucht würden.

Ich denke (nach persönlicher Beobachtung, als ich herausfinden wollte), dass die meisten von ihnen Folgendes tun:

  1. Beginnen Sie, in die Richtung des ersten gedrückten Knopfes zu gehen, und verfolgen Sie, in welche Richtung wir gehen
  2. 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 diese Etage als nicht mehr gedrückt.
    • Wenn es noch mehr Etagen gibt, die wir besuchen müssen und die in dieselbe Richtung weisen , fahren Sie in diese Richtung fort .
    • Wenn nicht und es noch Böden gibt, 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.

Beachten Sie, dass in vielen Aufzügen neben den Türen anstelle einer einzigen Taste die Tasten "Ich möchte hochgehen" und "Ich möchte runtergehen" angezeigt werden. Der Algorithmus benötigt nur eine kleine Änderung: In 2, wenn der einzige Knopf, der für dieses Stockwerk gedrückt wird, einer der Knöpfe neben der Tür ist, stoppen und öffnen Sie die Türen nur, wenn wir in diese Richtung gehen. Halten Sie den Knopf möglicherweise gedrückt, wenn die Türen geöffnet sind, weil ein Knopf im Aufzug gedrückt wurde und er in die falsche Richtung zeigt.

Sie müssen nie einen ganzen Weg herausfinden , nur in welche Richtung Sie als nächstes gehen müssen.

RemcoGerlich
quelle
Das hat mich völlig aus dem Konzept gebracht, ich war so auf Effizienz ausgerichtet und habe vergessen, dass andere Dinge auch wichtig sind. Es ist immer noch nicht effizient, von 2-> 100 und zurück auf 1 zu gehen, nur weil es in die gleiche Richtung ging, aber zumindest keine Hungersnot garantiert. und vielleicht ist es deshalb üblich, zwei Aufzüge mit dieser Logik zu finden? Was mich wundert, ob es üblicher ist, wenn die Aufzüge zu einem bestimmten Zeitpunkt in die entgegengesetzte Richtung fahren. Wie auch immer, ich bin immer noch gespannt, wie ich den kürzesten Weg finden kann, aber dies beantwortet meine Frage sehr genau, danke
Raed Tabani
7
Beachten Sie, dass Sie in einem Gebäude mit 100 Stockwerken normalerweise Aufzüge haben, die nur einen bestimmten Stockwerksbereich bedienen (z. B. 0-19, 20-39,…), sowie Schnellaufzüge, die nur lange Strecken zurücklegen (z. B. 0) bis 50, 0 bis 100, 50 bis 100, aber keine Stockwerke dazwischen), so müssen Sie möglicherweise die Aufzüge wechseln, um an Ihr Ziel zu gelangen. Sie können auch mehrere Aufzüge pro Schacht haben, die offensichtlich nicht aneinander vorbeifahren können. Völlig abseits des Themas IIRC gab es eine Frage zur Effizienz der Pfeiltasten nach oben und unten auf der User Experience- Website, die für eine sehr faszinierende Lektüre sorgte.
Jörg W Mittag
danke, das wusste ich nicht. Eine Unterteilung erscheint als eine gute Strategie, wenn ein Teil das gesamte System nicht zerstört 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's Elevator-Algorithmus zurückzuführen sind.
Raed Tabani
Das einzige, was ich hinzufügen möchte, ist, dass sie oft ein "Zuhause" haben, in das sie zurückkehren, wenn sie nicht benutzt werden. Dies kann für verschiedene Aufzüge unterschiedlich sein und sich möglicherweise sogar abhängig von der Tageszeit und den erwarteten Nutzungsmustern ändern
jk .
Ich habe die Tendenz, die Auf- / Ab-Taste halb zufällig zu drücken, unabhängig davon, in welche Richtung ich gerade fahre. 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 Aufwärts- oder Abwärtsfahrt entschieden habe Nieder. Ich vermute, wenn ich den Abwärtsknopf drücken würde, ein Stockwerk über mir und dann ein Stockwerk unter mir wählen würde, bevor der Aufzug in Bewegung gerät, würde es mich zu dem Stockwerk unter mir führen, anstatt zu dem Stockwerk, das ich zuerst gedrückt habe. Ich könnte mich irren, ich werde es sicher das nächste Mal testen, wenn ich mich in einem Aufzug befinde.
Ucenna
13

Die andere Antwort gibt den Standardalgorithmus für Aufzüge korrekt wieder. Dieser lautet im Grunde genommen "so lange wie möglich in die gleiche Richtung fahren und auf dem Weg alle erforderlichen Stopps einlegen".

Es gibt andere Aufzugsalgorithmen. Stellen Sie sich zum Beispiel ein Wohnhaus vor, in dem Wohnungen mit der Zeit teurer werden. Die Eigentümer des Gebäudes könnten sich dafür entscheiden, den Aufzugalgorithmus so zu ändern, dass "so lange wie möglich in dieselbe Richtung gefahren wird, aber nur auf dem Weg nach unten angehalten wird". Auf diese Weise werden Personen im Aufzug, die sich in der Lobby befinden und zu 2, 5 und 10 gehen, zu 10, dann zu 5, dann zu 2 befördert und die Personen in der Reihenfolge ihrer Mietzahlung abgesetzt. Aber wenn die 10- Jährigen 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, legen Sie eine Metrik für die Kosten fest, implementieren eine Reihe verschiedener Algorithmen und führen Sie Simulationen durch. Denken Sie daran, nicht nur die durchschnittlichen Kosten zu messen, sondern auch die Metriken, die für die Bearbeitung eines Auftrags am längsten dauern. Die Optimierung für niedrige Durchschnitte kann manchmal den schlechtesten Fall, der schlecht ist, deoptimieren.

Eric Lippert
quelle
1
Es scheint selten zu sein (andere alogirthms)
FindOutIslamNow
10

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 LOOK- Algorithmus üblicher, da er etwas effizienter als SCAN ist.

Gartenkopf
quelle
Haben Sie, wenn Sie so sicher sprechen, Berufserfahrung in der Implementierung des Codes für Aufzüge? Besonders neuere Aufzugssysteme? Ich bin neugierig, ob es nach dem 11. September in NYC eine höhere Priorität gab, Passagiere abzusenden als sie aufzuziehen.
John Zabroski