如何設計電梯演算法

1. 電梯演算法是怎樣的

電梯演算法是通過操作系統學術名為SCAN演算法。磁臂僅移動到請求的最外道就回轉。反方向查找服務。

如果請求調度的磁軌為98, 183, 37, 122, 14, 124, 65, 67，磁頭從53號磁軌開始移動，磁頭就會按照65, 67, 98, 122, 124, 183, 37,14 的順序依次查找，並將數據輸入內存。

電梯（升降盒）上下來回地運動，電梯內部有一些按鈕，每一個按鈕代表一層樓，當按下按鈕時，按鈕的燈亮。

電梯沿某一方向運動，在將要到達某一層樓時，實時監控器 判斷電梯內是否有乘客要在此層樓下電梯，若有，則發送信號給電梯升降架。

電梯是指服務於建築物內若干特定的樓層，其轎廂運行在至少兩列垂直於水平面或與鉛垂線傾斜角小於15°的剛性軌道運動的永久運輸設備。

也有台階式，踏步板裝在履帶上連續運行，俗稱自動扶梯或自動人行道。服務於規定樓層的固定式升降設備。垂直升降電梯具有一個轎廂，運行在至少兩列垂直的或傾斜角小於15°的剛性導軌之間。

轎廂尺寸與結構形式便於乘客出入或裝卸貨物。習慣上不論其驅動方式如何，將電梯作為建築物內垂直交通運輸工具的總稱。

2. java模擬實現兩部電梯同時工作的高效演算法

1. 各電梯控制：
a. 實現一個方法，返回本電梯到請求樓層上、下的時間（或者簡單點的，層數）；
b. 任務接受：接受用戶樓層上、下請求任務

2. 主控部分：
a. 當用戶按下上、下請求時，通過調用兩個電梯的上面所說的服務，進行比較決斷最優時間電梯；
b. 給最最優電梯發送任務；
3. 主控與各電梯控制之間的通訊可以通過多種方式實現；

3. 請問誰有C語言的電梯模擬演算法

#include <stdio.h>
#include <stdlib.h>
#include <winsock.h>
#include <winbase.h>
#include <string.h>
#include "egg.h"
#include "elevator.h"

#define START 0//定義初始狀態
#define UP 1//上行初始
#define DOWN 2//下行初始
#define PAUSE 3
#define N 100//記錄數組的容量

void getInput(void);//
void getInput0(void);//

void Status_trans(void);//顯示當前的狀態
void control(void);//控制主要的電梯過程
void control0(void);//在暫停後的控制
void time_count(void);
void Uper(void); //上行
void Downer(void); //下行

int Call[N]={0};
int Callup[10]={0}; //存放向上呼叫的整型數組
int Callin[10]={0}; //存放內部呼叫的整型數組
int Calldown[10]={0};//存放向下呼叫的整型數組
int time=0,state=0,prestate=0,flag=1,x=0;
int aimLayer=0,currentLayer=1;
float cl1=0.0,cl2=0.0;

main()
{
int service;
elevator();

system("color 3f");

printf("EVA 電梯竭誠為您服務，祝乘坐愉快\n");
printf("請選擇服務策略(1為先來先服務,2為順便服務):\n");
scanf("%d",&service);
if(service==1) {
DWORD ThreadID1 = 1;
HANDLE hRead1 = CreateThread(NULL,0,(LPTHREAD_START_ROUTINE)getInput0,NULL,0,&ThreadID1);
}
else {
DWORD ThreadID2 = 1;
HANDLE hRead2 = CreateThread(NULL,0,(LPTHREAD_START_ROUTINE)getInput,NULL,0,&ThreadID2);
}
while (1){
if(service==1)
control0();
else
control();
Status_trans(); /*確定電梯此刻的狀態，包括運行方向、所在樓層等*/

}

system("pause");
return 0;
}

void Status_trans(void)//yang
{
int i;

switch (state) {
case START:
if(aimLayer>currentLayer)
state=UP;
if(aimLayer==currentLayer)
state=PAUSE,prestate=START;
if(aimLayer==0)
state=START;
break;
case UP:
flag=1;

Uper();
currentLayer++;
drawCurrentLayer1(currentLayer);
drawCurrentLayer2(currentLayer);
printf("當前電梯樓層 %d\n", currentLayer);
if(currentLayer==aimLayer) {
state=PAUSE,x=1,prestate=UP;
printf("當前電梯樓層 %d\n", currentLayer);
}
if(currentLayer<aimLayer)
state=UP,flag=1;
if(currentLayer>aimLayer)
state=DOWN,flag=-1;
break;
case DOWN:
flag=-1;

Downer();
currentLayer--;//?
drawCurrentLayer1(currentLayer);
drawCurrentLayer2(currentLayer);
printf("當前電梯樓層 %d\n", currentLayer);
if(currentLayer==aimLayer) {
state=PAUSE,x=1,prestate=DOWN;
printf("當前電梯樓層 %d\n", currentLayer);
}
if(currentLayer<aimLayer)
state=UP,flag=1;
if(currentLayer>aimLayer)
state=DOWN,flag=-1;//flag?
break;
case PAUSE:
drawCurrentLayer1(currentLayer);
drawCurrentLayer2(currentLayer);
for(i=1;i<=4;i++)
WaitFor(100);
if(aimLayer<currentLayer)
state=DOWN;
if(aimLayer>currentLayer)
state=UP;
if(aimLayer==0)
state=PAUSE,prestate=PAUSE;
break;
}
}

void control(void)
{
int i,mark=0,m=0;

if(flag==1) {
if(state==PAUSE && prestate!=PAUSE) {//上行中確定目標樓層
Callin[currentLayer]=Callup[currentLayer]=0;
for(i=currentLayer+1;i<=9;i++)
if(Callup[i]==1 || Callin[i]==1 || Calldown[i]==1)
m=1;
if(m!=1)//無上行需求直接將下行此樓層處理
Calldown[currentLayer]=0;
}
for(i=currentLayer;i<=9;i++)
if(Callup[i]==1 || Callin[i]==1) {
mark=i;
aimLayer=i;
break;
}//有上行需求 ,目標樓層被確定
if(mark==0)//無上行需求
for(i=9;i>=1;i--)
if(Calldown[i]==1 || Callin[i]==1) {
aimLayer=i;
mark=i;
break;
}//確定下行目標樓層
if(mark==0)
for(i=1;i<=8;i++)
if(Callup[i]==1) {
aimLayer=i;
mark=i;
break;
}
if(mark==0)
aimLayer=0;
}//無目標樓層
else if(flag==-1) {
if(state==PAUSE && prestate!=PAUSE) {//電梯運行中
Calldown[currentLayer]=Callin[currentLayer]=0;//此層已處理過
for(i=currentLayer-1;i>=1;i--)
if(Callup[i]==1 || Callin[i]==1 || Calldown[i]==1)
m=1;
if(m!=1)
Callup[currentLayer]=0;//無目標樓層暫時停靠 m??
}
for(i=currentLayer-1;i>=1;i--)
if(Calldown[i]==1 || Callin[i]==1) {
mark=i;
aimLayer=i;
break;
}//確定下行目標樓層

//???為何要向上運行開始呢?

if(mark==0) //順便無要求,開始新的一樓起的上升需求掃描
for(i=1;i<=9;i++)
if(Callup[i]==1 || Callin[i]==1) {
aimLayer=i;
mark=i;
break;
}
if(mark==0)
for(i=9;i>=2;i--)
if(Calldown[i]==1) {
aimLayer=i;
mark=i;
break;
}
if(mark==0)
aimLayer=0;
}
}

void control0(void)//yang
{
int i;

for(i=0;i<=N-1;i++) {
if(Call[i]!=0) {
aimLayer=Call[i];
if(state==PAUSE && prestate!=PAUSE)
Call[i]=0;
break;
}
}
}

void getInput(void)
{
char ch;

while(1){
ch=getchar();
switch(ch) {

case'I':
Callup[1]=1;
break;
case'U':
Callup[2]=1;
break;
case'Y':
Callup[3]=1;
break;
case'T':
Callup[4]=1;
break;
case'R':
Callup[5]=1;
break;
case'E':
Callup[6]=1;
break;
case'W':
Callup[7]=1;
break;
case'Q':
Callup[8]=1;
break;

case'K':
Calldown[2]=1;
break;
case'J':
Calldown[3]=1;
break;
case'H':
Calldown[4]=1;
break;
case'G':
Calldown[5]=1;
break;
case'F':
Calldown[6]=1;
break;
case'D':
Calldown[7]=1;
break;
case'S':
Calldown[8]=1;
break;
case'A':
Calldown[9]=1;
break;

case '1':
Callin[1]=1;
break;
case '2':
Callin[2]=1;
break;
case '3':
Callin[3]=1;
break;
case '4':
Callin[4]=1;
break;
case '5':
Callin[5]=1;
break;
case '6':
Callin[6]=1;
break;
case '7':
Callin[7]=1;
break;
case '8':
Callin[8]=1;
break;
case '9':
Callin[9]=1;
break;
}
fflush(stdin);//使回車不被讀取
}
}

void getInput0(void)//yangnan
{
int i=0;
char ch;

while(1){
ch=getchar();
switch(ch) {
case'I':
Call[i]=1;
break;
case'U':
Call[i]=2;
break;
case'Y':
Call[i]=3;
break;
case'T':
Call[i]=4;
break;
case'R':
Call[i]=5;
break;
case'E':
Call[i]=6;
break;
case'W':
Call[i]=7;
break;
case'Q':
Call[i]=8;
break;

case'K':
Call[i]=2;
break;
case'J':
Call[i]=3;
break;
case'H':
Call[i]=4;
break;
case'G':
Call[i]=5;
break;
case'F':
Call[i]=6;
break;
case'D':
Call[i]=7;
break;
case'S':
Call[i]=8;
break;
case'A':
Call[i]=9;
break;

case '1':
Call[i]=1;
break;
case '2':
Call[i]=2;
break;
case '3':
Call[i]=3;
break;
case '4':
Call[i]=4;
break;
case '5':
Call[i]=5;
break;
case '6':
Call[i]=6;
break;
case '7':
Call[i]=7;
break;
case '8':
Call[i]=8;
break;
case '9':
Call[i]=9;
break;
}
i++;
fflush(stdin);//使回車不被讀取
}
}

void Uper(void)
{
int step;
for(step=1;step<=20;step++){
WaitFor(50);/*等待50毫秒*/
move(0.075);
}
}
void Downer(void)
{
int step;
for(step=1;step<=20;step++){
WaitFor(50);/*等待50毫秒*/
move(-0.075);
}
}

但是這個演算法可能會有點小問題，你研究一下看看，多多少少有幫助的

4. 電梯調度演算法...

不管你是在北上廣還是在港澳台，甚至三四線城市，凡是有規模的地區，高樓比比皆是。不管是寫字樓，還是大型商城，讓你最頭痛的就是乘電梯，尤其是在趕時間的時候。

每天早上，那些差5分鍾就遲到的程序員，在等電梯時，一般會做兩件事：

前者可能是寫字樓里上班族慣有的精神類疾病，但後者肯定是程序員的職業病。本文對「罵電梯」不給予任何指導性建議。

但說起電梯調度演算法，我覺得還是可以給大家科普一下，好為大家在等電梯之餘，打發時間而做出一點貢獻。

（電梯調度演算法可以參考各種硬碟換道演算法，下面內容整理自網路）

先來先服務（FCFS-First Come First Serve）演算法，是一種隨即服務演算法，它不僅僅沒有對尋找樓層進行優化，也沒有實時性的特徵，它是一種最簡單的電梯調度演算法。

它根據乘客請求乘坐電梯的先後次序進行調度。此演算法的 優點是公平、簡單，且每個乘客的請求都能依次地得到處理，不會出現某一乘客的請求長期得不到滿足的情況 。

這種方法在載荷較輕松的環境下，性能尚可接受，但是在載荷較大的情況下，這種演算法的性能就會嚴重下降，甚至惡化。

人們之所以研究這種在載荷較大的情況下幾乎不可用的演算法，有兩個原因：

最短尋找樓層時間優先（SSTF-Shortest Seek Time First）演算法，它注重電梯尋找樓層的優化。最短尋找樓層時間優先演算法選擇下一個服務對象的原則是 最短尋找樓層的時間。

這樣請求隊列中距當前能夠最先到達的樓層的請求信號就是下一個服務對象。

在重載荷的情況下，最短尋找樓層時間優先演算法的平均響應時間較短，但響應時間的方差較大 ，原因是隊列中的某些請求可能長時間得不到響應，出現所謂的「 餓死」現象 。

掃描演算法（SCAN） 是一種按照樓層順序依次服務請求，它讓電梯在最底層和最頂層之間連續往返運行，在運行過程中響應處在於電梯運行方向相同的各樓層上的請求。

它進行尋找樓層的優化，效率比較高，但它是一個 非實時演算法 。掃描演算法較好地解決了電梯移動的問題，在這個演算法中，每個電梯響應乘客請求使乘客獲得服務的次序是由其發出請求的乘客的位置與當前電梯位置之間的距離來決定的。

所有的與電梯運行方向相同的乘客的請求在一次電向上運行或向下運行的過程中完成， 免去了電梯頻繁的來回移動 。

掃描演算法的平均響應時間比最短尋找樓層時間優先演算法長，但是響應時間方差比最短尋找樓層時間優先演算法小， 從統計學角度來講，掃描演算法要比最短尋找樓層時間優先演算法穩定 。

LOOK 演算法是掃描演算法（SCAN）的一種改進。對LOOK演算法而言，電梯同樣在最底層和最頂層之間運行。

但 當 LOOK 演算法發現電梯所移動的方向上不再有請求時立即改變運行方向 ，而掃描演算法則需要移動到最底層或者最頂層時才改變運行方向。

SATF（Shortest Access Time First）演算法與 SSTF 演算法的思想類似，唯一的區別就是 SATF 演算法將 SSTF 演算法中的尋找樓層時間改成了訪問時間。

這是因為電梯技術發展到今天，尋找樓層的時間已經有了很大地改進， 但是電梯的運行當中等待乘客上梯時間卻不是人為可以控制 。

SATF 演算法考慮到了電梯運行過程中乘客上梯時間的影響 。

最早截止期優先（EDF-Earliest Deadline First）調度演算法是最簡單的實時電梯調度演算法，它的 缺點就是造成電梯任意地尋找樓層，導致極低的電梯吞吐率。

它與 FCFS 調度演算法類似，EDF 演算法是電梯實時調度演算法中最簡單的調度演算法。 它響應請求隊列中時限最早的請求，是其它實時電梯調度演算法性能衡量的基準和特例。

SCAN-EDF 演算法是 SCAN 演算法和 EDF 演算法相結合的產物。SCAN-EDF 演算法先按照 EDF 演算法選擇請求列隊中哪一個是下一個服務對象，而對於具有相同時限的請求，則按照 SCAN 演算法服務每一個請求。它的效率取決於有相同 deadline 的數目，因而效率是有限的。

PI（Priority Inversion）演算法將請求隊列中的請求分成兩個優先順序，它首先保證高優先順序隊列中的請求得到及時響應，再搞優先順序隊列為空的情況下在相應地優先順序隊列中的請求。

FD-SCAN（Feasible Deadline SCAN）演算法首先從請求隊列中找出時限最早、從當前位置開始移動又可以買足其時限要求的請求，作為下一次 SCAN 的方向。

並在電梯所在樓層向該請求信號運行的過程中響應處在與電梯運行方向相同且電梯可以經過的請求信號。

這種演算法忽略了用 SCAN 演算法相應其它請求的開銷，因此並不能確保服務對象時限最終得到滿足。

以上兩結介紹了幾種簡單的電梯調度演算法。

但是並不是說目前電梯調度只發展到這個層次。目前電梯的控制技術已經進入了電梯群控的時代。

隨著微機在電梯系統中的應用和人工智慧技術的發展，智能群控技術得以迅速發展起來。

由此，電梯的群控方面陸續發展出了一批新方法，包括：基於專家系統的電梯群控方法、基於模糊邏輯的電梯群控方法、基於遺產演算法的電梯群控方法、基於勝景網路的電梯群控方法和基於模糊神經網路的電梯群控方法。

本人設置的電梯的初始狀態，是對住宅樓的電梯的設置。

(1)建築共有21層，其中含有地下一層（地下一層為停車場）。
(2)建築內部設有兩部電梯，編號分別為A梯、B梯。
(3)電梯內部有23個按鈕，其中包括開門按鈕、關門按鈕和樓層按鈕，編號為-1，1，2，3，4……20。
(4)電梯外部含有兩個按鈕，即向上運行按鈕和向下運行按鈕。建築頂層與地下一層例外，建築頂層只設置有向下運行按鈕，地下一層只設置有向上運行按鈕。
(5)電梯開關門完成時間設定為1秒。電梯到達每層後上下人的時間設定為8秒。電梯從靜止開始運行到下一層的時間設置為2秒，而運行中通過一層的時間為1秒。
(6)在凌晨2：00——4：30之間，如若沒有請求信號，A梯自動停在14層，B梯自動停在6層。
(7)當電梯下到-1層後，如果沒有請求信號，電梯自動回到1層。

每一架電梯都有一個編號，以方便監控與維修。每一架電梯都有一實時監控器，負責監控電梯上下，向電梯升降盒發送啟動、制動、加速、減速、開關電梯門的信號。若電梯發生故障，還應向相應的電梯負責人發送求救信號。

電梯內部的樓層按鈕：

這樣就表示乘客將要去往此層，電梯將開往相應層。當電梯到達該層後，按鈕恢復可以使用狀態。

電梯內部開門按鈕：

如若電梯到了乘客曾經按下的樓層，但是無乘客按開門按鈕，電梯將自動在停穩後1秒後自動開門。

電梯內部關門按鈕：

電梯外部向上按鈕：

電梯外部向下按鈕：

你肯能意識到 哪個演算法都不是一個最佳方案，只是它確實解決了一定情況的問題 。但是對一個優秀的程序員而言，研究各種演算法是無比快樂的。也許你下一次面試，就有關於調度演算法的問題。

5. 如何將各種演算法應用到實際的電梯調度中

說明 假設大廈有31層樓.電梯每經過1層(不論上下行)的時間是4秒.也就是說,電梯從1樓到31樓且中間不停則需要(31-1)*4=120秒.電梯每次需要停10秒,因此,如果電梯每層都停一次,就需要30*4+29*10=410秒.與此同時,員工步行一層樓(不論上下行)需要20秒,從1樓到31樓就需要30*20=600秒.明顯,這個主意不好.因此,很多員工依賴電梯前往他們的辦公室.現在我們需要設計一個方案，這個方案的設計目標是讓最後一個到達辦公室的員工花費最短的時間(也就是說,他並不保證每一位員工都能最快到達自己辦公室).比如,如果員工想到達4,5和10層,則電梯的運行方案是在4和10層停止.因為電梯在第12秒到達4層,停止10秒,則電梯到達10層需要3*4+10+6*4=46秒.按此計劃,住在4層的員工需要12秒,5層的員工需要12+20=32秒,10層的員工需要46秒.因此,最後到達辦公室的員工需要46秒.對於大家來說,這是個不錯的方案.

實現 下面就詳細說一說我實現的具體方式，雖然花了我近2天的時間，但是其實並不是很復雜，這里我本著拋磚引玉的原則，下面就一起來看看吧：

我們將定義一個名叫Case的class用來存儲一些要測試的數據，然後再定義一個叫CaseUtil的class用來實現我們的方案。

首先我說一下具體得思路：這里我只考慮從下到上的方案(從上到下其實是一樣的，具體自己想吧)。舉個例子，假設當前的樓層是【29 30 31】.3個。那麼我們該如何做呢？

首先，不管怎麼說，假設最後一層即31的到達時間為 （31-1）* 4 + （stopNums-1）*10 說明一下，這里為了簡單起見我們就按照案例的數據進行分析，實際上4表示電梯經過每層所需時間，而10表示電梯每層停靠的時間。上面的stopNums是什麼呢？就是電梯到達31層時所有的停靠次數，減去1是除去31層得停靠。而最後一層到達的人則很可能為最後一位到達的人，為什麼不是一定呢，按照本例，上面舉得例子就可以很簡單的看出，在28、31停2次即可，此時最後一個到達的就是地30層的人了。當然在僅僅是在本例中，實際上會由於具體數值不一樣而有不同。所以這里我用了可能，而它也和我們的最優解很接近了，而這給了我想法。雖然最後一層不一定是最後一位，但已經很接近了，而它所花費的時間，僅僅只和一個變數有關，即stopNums，即可以得出如下結論：

電梯的停靠次數越少，最後一層的時間也就越少，同樣最佳時間也就越少。

假設我們有一個方法可以根據當前的停靠次數來計算最佳的停靠方案，那麼我們該如何得到實際最佳方案呢？下面的一段代碼很好的可以達到我們的目標。