©クリップ「江南スタイル」
私たちの都市の階数の増加に伴い、ますます多くの人々が毎日エレベーターを使用しています。 しかし、日中、特にピーク時に多くの人を多かれ少なかれ効率的に輸送するために、このエレベーターのすべての人口がどうやって管理するかについて考える人はほとんどいません。 エレベータの移動には、さまざまな条件から生じる多くのアルゴリズムがあります。たとえば、 エレベータの待ち時間を最小限に抑えることができます。 しかし、リフトアルゴリズムの開発方法について考えてみましょう。
タスクは明らかに単純ですが、建物で実際に使用するエレベーターアルゴリズムを作成することは非常に困難です。 さらに、そのようなものは企業秘密とみなされ、特許を取得しています。 したがって、単純化されたモデルを作成しようとします。
各階の建物には同数の人が住んでいます。 いくつかのエレベーターがあり、階段はありません。 簡単にするために、各階で同数の乗客がエレベーターを待っていると仮定します。 また、日中は数時間のラッシュアワーがあることも知っています。 建物内のすべての人の待ち時間を最小限に抑えるために、このようなアルゴリズムを考案する必要があります。
ここでは、問題の解決を困難にするいくつかの条件を区別できます。
- 任意の階数。
- エレベーターの任意の数。
- ラッシュアワーの期間があります。
- エレベータの分布は、負荷と待機時間の関数に基づいて説明する必要があります。
また、さらにいくつかの変数と定数を考慮します。
- 各フロアの人数は100人です。
- エレベーターが停止せずに1フロアを通過する時間は5秒です。
- エレベーターは20秒間床に立ちます。
もちろん、実際の生活では、エレベーターのそばを通る床の速度は、加速および減速するため、非線形になる可能性があります。 ただし、計算を簡素化するために、削除します。 これがタスクの単純化のように思える場合は、これらの条件を自分でアルゴリズムに入力できます。
これまで、リフト能力については何も言われていないことに注意してください。 ここでも、私たちは私たちの生活を根本的に簡素化します-エレベーターはあなたが好きなだけ多くの人を収容すると仮定します。 非現実的です、私は同意します。 しかし、その後、アルゴリズムの最初のバージョンがあれば、次の条件を導入するのが簡単になります。
- エレベーターが満杯の場合は、下の階に降ります。
- すべての乗客が降りると、エレベーターは前の階に戻ります。
エレベーター分配アルゴリズム
図から明らかなように、各エレベータには特定の責任範囲が割り当てられています。 これは、各階の待ち時間と各エレベータの負荷を平均化するために行われます。 各エレベーターは、「フロア1-> 2-> 3-> 0」というサイクルをたどることができます。 ループを完了するのにかかる時間を計算しましょう：
- 1フロアの通過時間にサイクル内のフロアの数を掛け、2を掛けます（エレベータが上下するため）。 このモデルでは次のことがわかります。
5 * < > * 2.
- 最初の階から最後の階までの停車地の数に停車地の継続時間が乗算されます。 私たちのモデルでは：
20 * < >.
組み合わせる：
= (5 * < > * 2) + (20 * < >)
次に、1サイクル中に輸送する平均人数を計算します。
= < > * < > * < > / < >
ここに：
- <ラッシュアワー>は、1ラッシュアワーの完了時間です。
- <提供階数>-エレベーターが停止する階数。
次に、2つの配列を作成します。
- 建物の配列 。 セルの数は、フロアの数に等しくなります。 セルの内容は、床で待っている人の数を示しています。
- エレベータの配列 。 セルの数はエレベータの数と同じです。 セルの内容は、このエレベーターが移動する「上」の階を示しています。 たとえば、配列[2、3、4]には3つのエレベータが記述されています。1つ目は2階以下、2つ目は3つ目、3つ目は4つ目です。
まず、最初の配列は空です。次に、配列にフロアを追加するたびに、エレベータを割り当てます。 以下に示すように、追加の性質は変わりますが、一般的には非常に簡単に説明されています。 負荷容量が制限になるまで、サイクルにフロアが追加されます。 小さな機能を紹介します：
+ (( / 100) * )
<サイクル時間>は、100秒（エレベータ内にとどまるのに十分な長さ）に達するまでの整数であり、<平均エレベータ負荷>が方程式で考慮されます。 私たちのタスクはかなり曖昧に記述されているため、ソリューションには多少のあいまいさがあります。 したがって、エレベータの責任範囲にフロアを追加する機能はかなりarbitrary意的ですが、負荷の管理には効果的です。 おそらくより良い解決策があります。
フロア追加機能の実装（Python）：
# ( * 5 ) + (20 * ( – )) # / , # ( * 2) + , # , [2]+=1 # e ( ) def addFloor(e): best = 99999 for i in range(1, len(e)): cirTime, avgCarry = eleLoop(e, i) if cirTime + ((cirTime / 100) * avgCarry) < best: elevatorNumber = i best = cirTime + ((cirTime / 100) * avgCarry) for i in range(elevatorNumber, len(e)): e[i] += 1 return e
注意： elevatorNumber
が現在のelevatorNumber
値を超えるelevatorNumber
を選択するたびに、エレベータ配列のサイズが増加します。
for i in range(elevatorNumber, len(e)): e[i] += 1
各サイクルで、選択したエレベーターの後に最大階を1つ増やします。 したがって、選択したエレベーターのサイクルで、別のエレベーターを追加します。 eleLoop(e, i)
関数は、サイクルで運ばれる乗客の時間と平均人数を単に決定します。
次に、フロアを通過してフロア自体を作成する機能を記述します。 注意：私たちの場合、フロアの人数は同じとみなされます。 この問題を解決する場合、フロアの異なる人数を考慮に入れることは非常に簡単です。
# . # Elevator[] . def elevatorAllocation(building, elevatorCount): elevator = [] for i in range(elevatorCount + 1): elevator.append(0) for i in range(1, floorCount): elevator = addFloor(elevator) printeleLoop(elevator)
これで十分です。 決定は比較的簡単なので、ここで多くを改善できます。
Pythonの実装
次に、アルゴリズムのさまざまな部分をまとめて、データを出力するための関数をいくつか追加し、 小さなシミュレーターを作成しましょう。
変数：
- 10階。
- 3つのエレベーター。
- 1ラッシュアワー。
- 5秒でフロアが完成します。
- 床に20秒立ったエレベーター。
- 1フロアあたり100人。
# , def fillBuilding(): building = [] for i in range(floorCount - 1): building.append(peoplePerFloor) return building # (cirTime), # , . # e — , # . i — e. def eleLoop(e, i): floorsServiced = e[i] - e[i-1] + 1 cirTime = timePerFloor * e[i] * 2 cirTime += timePerWait * floorsServiced avgCarry = cirTime * peoplePerFloor / rushHour * floorsServiced return cirTime, avgCarry # ( * 5 ) + (20 * ( – )) # / , # ( * 2) + , # , [2]+=1 # e ( ) def addFloor(e): best = 9999 for i in range(1, len(e)): cirTime, avgCarry = eleLoop(e, i) if cirTime + ((cirTime / 100) * avgCarry) < best: elevatorNumber = i best = cirTime + ((cirTime / 100) * avgCarry) for i in range(elevatorNumber, len(e)): e[i] += 1 return e # . def printApprox(building): str = '[ ' for i in range(len(building)): str += '%06.3f ' % building[i] str += ']' print str # (-) def printeleLoop(e): print '' print e print '' for i in range(1, len(e)): floorsServiced = e[i] - e[i-1] + 1 curr = timePerFloor * e[i] * 2 curr += timePerWait * floorsServiced avgCarry = curr * peoplePerFloor / rushHour * floorsServiced str = ' #%d, %d , ' % (i, curr) str += ' ' str += '%3.2f ' % avgCarry print str print '' # . # Elevator[] . def elevatorAllocation(building, elevatorCount): elevator = [] for i in range(elevatorCount + 1): elevator.append(0) for i in range(1, floorCount): elevator = addFloor(elevator) printeleLoop(elevator) return elevator # , def simulate(e, building): str = '[ ' for floor in range(len(building)): str += 'floor%2d ' % (floor + 1) str += ']' print str eCircuit = [] for i in range(len(e)): curr, avgCarry = eleLoop(e, i) eCircuit.append(float(curr)) emptyFloors = 0 iteration = 0 finalFloor = 0 while emptyFloors < len(building): emptyFloors = 0 iteration += 1 for i in range(1, len(e)): for j in range(e[i-1], e[i]): if building[j] > 0.0: persons = eCircuit[i] * peoplePerFloor / rushHour building[j] = building[j] - persons if 0 >= building[j]: building[j] = 0.0 emptyFloors += 1 finalFloor = j printApprox(building) print '' # , for i in range(len(e)): if e[i] > finalFloor: iteration = eCircuit[i] * iteration / 60 print ' : %d \n' % () # ___ MAIN ____ building = fillBuilding() elevator = elevatorAllocation(building, elevatorCount) simulate(elevator, building)
出力データ：
[0、4、7、9]
エレベーター1号、サイクルタイム-140秒、平均19.44人が輸送されています
エレベーター2、サイクル時間-150秒、平均16.67人
エレベーター3、サイクル時間-150秒、平均12.5人
合計時間：65分
エレベーターが通過する際の床の平均人数：
ご覧のとおり、アルゴリズムはうまく機能していますが、完全ではありません（条件に対して）。 自分で改善できます。
実行時間
アルゴリズムの実行時間は、次の3つの要因に依存します。
- k：最長サイクル、人数
- n：最長サイクルのサービス対象フロアの初期人数
- m：フロアの総数
実行時間： O(m * (n/k))
n/k
は、サイクル内でエレベータが実行する反復の最大数を決定します。 反復中に各フロアを通過する必要があるため、 m
使用されます。 この場合、各フロアの人数を表す「建物配列」を埋める「設定」を無視します。これは、実行の主な条件ではないためです（m *（n / k）+ m）。
アルゴリズムを実行するためのメモリ量は次の要素に依存します。
- e：エレベーターの数から
- f：階数から
メモリ容量： O(e + f)
最後の言葉
もちろん、アルゴリズムは完全ではありませんでしたが、非常に機能しています。 改善を提案してください。 エレベーターの動きは興味深いアプリケーションであり、コンピューターリソースの配分に似ています。