algorithm - エレベーター機構のデータ構造

Question

この質問は、会社の面接中に私に尋ねられました-エレベーターメカニズムを実装するのに効率的なデータ構造はどれですか?

グーグルを何度も試した後でも、効率的なデータ構造を見つけることができません。

それを実装するプライオリティ キューを考えることができます。プライオリティ キューは効率的なデータ構造ですか、それともエレベータ メカニズムを実装するためのより効率的なデータ構造ですか?

ありがとう！

Answer 1

ソフトウェアにメカニズムを実装することはできないので（確かにモデル化することはできますが）、質問はエレベータアルゴリズムに関するものだと思います。

アルゴリズムは一見シンプルに見えますが、優れたデータ構造のセットが手元にある場合でも、実装するのは驚くほど非常に困難です。このアルゴリズムに使用するのに適した構造は、3つの優先キューです。

1. 現在のポイントを過ぎたエントリを持つ現在の方向については、
2. 反対方向の場合、および
3. 現在のポイントの前の現在の方向。

実装は最初に方向を決定し、次に要求された{from, to}値のペアを配置するキューを選択します。

Answer 2

2 つのリンクされたリストを 1 つを上方向の移動要求用に、もう 1 つを下方向の移動要求用に使用するとどうなるでしょうか。

例えば

最初のリクエスト: a). エレベーターが 0 階にあり、リクエストが 3 階にある場合。

上向きの移動のためのリンクされたリスト。

3->ヌル。

下方向への移動のためのリンクされたリスト。

ヌル。

2 番目の要求: b)。エレベーターが 1 階に移動し、2 階から上昇の要求が来ている間。

上向きの移動のためのリンクされたリスト。

2->3->ヌル

下方向への移動のためのリンクされたリスト。

ヌル。

3 番目の要求: c) 2 人が 2 階に入るとします。1 人は 5 階のボタンを押し、もう 1 人は 1 階のボタンを押します。

上向きの移動のためのリンクされたリスト。

3->5->ヌル

注: ここで 2 は、到達したため、上位リンク リストから削除されています。

下方向への移動のためのリンクされたリスト。

1->ヌル。

d) 人が 3 階から入り、0 階のボタンを押したとします。

上向きの移動のためのリンクされたリスト。

5->ヌル

下方向への移動のためのリンクされたリスト。

1->0->ヌル。

5 階に到達すると、上方向の要求のリンク リストが空になるため、下方向のリンク リストを移動の対象と見なすことができます。

リンクされたリストが両方とも空の場合、エレベーターは停止します。

リンクリストもエレベータの効果的なデータ構造になると思います

Answer 3

簡単にするために、単一のエレベータ システムを考えてみましょう 。

使用されるデータ構造:フロア番号を格納する単純なリスト、イベントと状態の列挙。

システムをイベント状態駆動にすることができます。ユーザーの行動や環境のあらゆる側面を考慮して、エレベーターでどのようなシナリオを想定できるかを決定する必要があります。

Events of the elevator : GOINGUP, GOINGDOWN, STOP 
States of the elevator : ONMOVE, WAITING (between door open and close), IDLE (serving no one), UNDERMAINTENANCE

Elevator movement is usually driven by two activites:
1. Press Up or Down key (before the entry gate of elevator) and wait for the elevator to come and serve you. (Press-And-Wait, say PAW) 
2. Enter inside the elevator and make request by pressing keys (Enter-And-Request, say EAR)

So it can said that PAW from outside and EAR from inside can decide the hops of the elevator. But what about direction?

Two possible types of PAW: PAWup (press Up button) and PAWdown (press Down button)

Now, EAR can be any of the three types depending upon the users behavior. These are the critical challenges in deciding the algorithm: 
1.) Normal - same direction as PAW (wanted to go down and enter lower floor#) 
2.) Opposite - wanted to go down BUT enter higher floor#
3.) Indecisive - Do Nothing, no key press

Now comes all the important rules:
RULE 1: If at IDLE, use FCFS to decide between the DownList front and UpList front - whoever is oldest, serve it first to ensure less waiting time. 
RULE 2: When both lists (DownList and UpList) are empty, move elevator to IDLE state. 
RULE 3: Elevator state change GOINGUP->STOP clears that floor# from UpList. Similarly, GOINGDOWN->STOP clears that floor from DownList.
RULE 4: Absolute Zero Skipping: GOINGxxx serves as many floors in xxxList as possible. 
RULE 5: Elevator doesn't favour Opposite-EAR, and obviously can't serve Indecisive-EAR.
RULE 6: Elevator in UNDERMAINTENANCE state is shunned from all external signals.
RULE 7: In the event of Power-cuts or Fire, the elevator goes and stops at Lobby. Flooding??

To achieve RULE#5, GOINGDOWN clears all the lower floor# in DownList in ONE GO. Similarly, GOINGUP clears all the higher floor# in UpList.    

Lets discuss one scenario to clear the above concepts:
Say, an elevator is resting at floor 7 is at IDLE state, 
    DownList : 
    UpList : 

IDLE@7 - PAWdown@12 then PAWup@9 then PAWdown@13
    DownList : 12, 13 (older requests at lower index.Push new requests at front.)
    UpList : 9 
    Using RULE#2, in the above case, 
    Event: GOINGUP to Pick@12.  

WAITING@12  - 12 cleared following RULE#3

MeanWhile, PAWup@8 then PAWup@10 then PAWdown@10, so updated lists are:
    DownList : 13, 10 
    UpList : 9, 8, 10

So here, in the current situation, if the EAR is
1.) Normal, GOINGDOWN(towards new EAR) is triggered.
2.) Opposite/Indecisive, GOINGDOWN(towards 9) is triggered and add the new EAR in UpList. 

上記のルールを使用して、エレベーターは通常の作業を続けます。

Answer 4

各配列エントリがフロアを表す配列を持つことはどうですか。ユーザーがフロアに停止したい場合、彼はアレイ内のそのエントリをマークし、エレベータはアレイを調べて、エレベータがそのフロアに到達したときにマークされている場合はエントリをクリアします。SCAN/CSAN スケジューリング アルゴリズムに似ています。コメントお待ちしております