不管你是在北上廣還是在港澳臺(tái)，甚至三四線城市，凡是有規(guī)模的地區(qū)，高樓比比皆是,不管是寫(xiě)字樓，還是大型商城，讓你最頭痛的就是乘電梯，尤其是在趕時(shí)間的時(shí)候。

1.問(wèn)題定義

　 電梯大家對(duì)于大家已經(jīng)是很熟悉了，現(xiàn)在存在這樣的問(wèn)題，那就是在繁忙的上下班時(shí)間，在每層樓電梯都要停。這顯然讓很多辦公室在高層的同志有點(diǎn)受不了?，F(xiàn)在要求是這樣：由于這個(gè)電梯樓層并不高，所以電梯只在一個(gè)樓層停，這樣做電梯的每個(gè)人都在這個(gè)樓層走到自己想去的樓層。那么怎么知道電梯每次在哪個(gè)樓層停下來(lái)呢？在一樓的時(shí)候每個(gè)乘客選擇自己的目的層，電梯可以快速的自動(dòng)計(jì)算出應(yīng)停的樓層。這個(gè)應(yīng)停的樓層應(yīng)該保證這次乘坐電梯的所有乘客的爬樓梯層數(shù)之和最少（包括上下樓）。

2.問(wèn)題分析

　 該問(wèn)題本質(zhì)上是一個(gè)優(yōu)化問(wèn)題。首先為這個(gè)問(wèn)題找到一個(gè)合適的抽象模型。從問(wèn)題中可以看出，有兩個(gè)因素會(huì)影響到最后的結(jié)果：乘客的數(shù)量及需要停的樓層。因此，我們可以從統(tǒng)計(jì)到達(dá)各層的乘客數(shù)目開(kāi)始分析。

　　假設(shè)樓層總共有N層，電梯停在第x層，要去第 i 層的乘客數(shù)目總數(shù)為total[i],這樣，所爬樓梯的總數(shù)就是∑{total[i]*| i - x|}(i = 1 , 2 , …… , N)。因此我們的任務(wù)就是找到一個(gè)整數(shù)x使得∑{total[i]*| i - x|}(i = 1 , 2 , …… , N)的值最小。

2.問(wèn)題解法

2.1解法一

　　按照面試的思路是，先考慮最簡(jiǎn)單的解決方案，然后優(yōu)化，那我們也這樣。先來(lái)看一個(gè)簡(jiǎn)單的解法，可以第一層開(kāi)始枚舉x一直第N層，然后計(jì)算如果電梯在第x層停的話所有乘客總共要爬多少層樓。這是最為直接的一個(gè)解法。

　　很容易想到吧，程序代碼就是兩重循環(huán)，找到最大值。對(duì)于一個(gè)問(wèn)題的解法是枚舉那么，肯定這個(gè)解法基本是最容易想，但同時(shí)也是效率不太高的解法。這個(gè)算法的時(shí)間復(fù)雜度O(N^2)。

2.2解法二

　　現(xiàn)在我們來(lái)更仔細(xì)的分析一下這個(gè)問(wèn)題，看看怎么樣優(yōu)化一下。假設(shè)電梯停在第 i 層樓，我們計(jì)算出所有乘客總共爬樓梯的層數(shù)是Y。如果有N1個(gè)乘客想去的樓層在第 i 層之下，有N2個(gè)乘客正好想去的樓層是第 i 層，有N3個(gè)乘客想去的樓層在第 i 層之上。這個(gè)時(shí)候，重點(diǎn)來(lái)了：如果電梯改停在i-1層，所有目的地在第i - 1層以下的乘客可以少爬1層，總共少爬N1層，所有在i層及以上的乘客要多爬一層，總共多爬N2+N3層，這時(shí)總共需要爬Y-N1+N2+N3。

　　反之，如果電梯在i+1層停所有目的地在第 i 層以上的乘客可以少爬1層，總共少爬N3層，所有在 i 層及以下的乘客要多爬一層，總共多爬N1+N2層，這時(shí)總共需要爬Y+N1+N2-N3層。

　　可見(jiàn)，當(dāng)N1 > N2+N3 時(shí)，電梯在第i-1層樓停更好；當(dāng)N1+N2 <  N3 時(shí)，電梯在i+1層停更好。其他情況在第i層更好。

　　如此一來(lái)，問(wèn)題的解法就出來(lái)了，從第一層開(kāi)始考察，計(jì)算各位乘客走的樓層的數(shù)目，然后根據(jù)N1，N2，N3之間的關(guān)系進(jìn)行調(diào)整，知道找到最佳樓層，這樣算法時(shí)間復(fù)雜度優(yōu)化到了O（N）

1.1 先來(lái)先服務(wù)算法（FCFS）

先來(lái)先服務(wù)（FCFS-First Come First Serve）算法，是一種隨即服務(wù)算法，它不僅僅沒(méi)有對(duì)尋找樓層進(jìn)行優(yōu)化，也沒(méi)有實(shí)時(shí)性的特征，它是一種最簡(jiǎn)單的電梯調(diào)度算法。

它根據(jù)乘客請(qǐng)求乘坐電梯的先后次序進(jìn)行調(diào)度。此算法的優(yōu)點(diǎn)是公平、簡(jiǎn)單，且每個(gè)乘客的請(qǐng)求都能依次地得到處理，不會(huì)出現(xiàn)某一乘客的請(qǐng)求長(zhǎng)期得不到滿(mǎn)足的情況。

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

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

任何調(diào)度算法在請(qǐng)求隊(duì)列長(zhǎng)度為1時(shí)，請(qǐng)求速率極低或相鄰請(qǐng)求的間隔為無(wú)窮大時(shí)使用先來(lái)先服務(wù)算法既對(duì)調(diào)度效率不會(huì)產(chǎn)生影響，而且實(shí)現(xiàn)這種算法極其簡(jiǎn)單。

先來(lái)先服務(wù)算法可以作為衡量其他算法的標(biāo)準(zhǔn)。

1.2 最短尋找樓層時(shí)間優(yōu)先算法（SSTF）

最短尋找樓層時(shí)間優(yōu)先（SSTF-Shortest Seek Time First）算法，它注重電梯尋找樓層的優(yōu)化。

最短尋找樓層時(shí)間優(yōu)先算法選擇下一個(gè)服務(wù)對(duì)象的原則是最短尋找樓層的時(shí)間。

這樣請(qǐng)求隊(duì)列中距當(dāng)前能夠最先到達(dá)的樓層的請(qǐng)求信號(hào)就是下一個(gè)服務(wù)對(duì)象。

在重載荷的情況下，最短尋找樓層時(shí)間優(yōu)先算法的平均響應(yīng)時(shí)間較短，但響應(yīng)時(shí)間的方差較大，原因是隊(duì)列中的某些請(qǐng)求可能長(zhǎng)時(shí)間得不到響應(yīng)，出現(xiàn)所謂的“餓死”現(xiàn)象。

1.3 掃描算法（SCAN）

掃描算法（SCAN） 是一種按照樓層順序依次服務(wù)請(qǐng)求，它讓電梯在最底層和最頂層之間連續(xù)往返運(yùn)行，在運(yùn)行過(guò)程中響應(yīng)處在于電梯運(yùn)行方向相同的各樓層上的請(qǐng)求。

它進(jìn)行尋找樓層的優(yōu)化，效率比較高，但它是一個(gè)非實(shí)時(shí)算法。掃描算法較好地解決了電梯移動(dòng)的問(wèn)題，在這個(gè)算法中，每個(gè)電梯響應(yīng)乘客請(qǐng)求使乘客獲得服務(wù)的次序是由其發(fā)出請(qǐng)求的乘客的位置與當(dāng)前電梯位置之間的距離來(lái)決定的。

所有的與電梯運(yùn)行方向相同的乘客的請(qǐng)求在一次電向上運(yùn)行或向下運(yùn)行的過(guò)程中完成，免去了電梯頻繁的來(lái)回移動(dòng)。

掃描算法的平均響應(yīng)時(shí)間比最短尋找樓層時(shí)間優(yōu)先算法長(zhǎng)，但是響應(yīng)時(shí)間方差比最短尋找樓層時(shí)間優(yōu)先算法小，從統(tǒng)計(jì)學(xué)角度來(lái)講，掃描算法要比最短尋找樓層時(shí)間優(yōu)先算法穩(wěn)定。

1.4 LOOK 算法

LOOK 算法是掃描算法（SCAN）的一種改進(jìn)。對(duì)LOOK算法而言，電梯同樣在最底層和最頂層之間運(yùn)行。

但當(dāng) LOOK 算法發(fā)現(xiàn)電梯所移動(dòng)的方向上不再有請(qǐng)求時(shí)立即改變運(yùn)行方向，而掃描算法則需要移動(dòng)到最底層或者最頂層時(shí)才改變運(yùn)行方向。

1.5 SATF 算法

SATF（Shortest Access Time First）算法與 SSTF 算法的思想類(lèi)似，唯一的區(qū)別就是 SATF 算法將 SSTF 算法中的尋找樓層時(shí)間改成了訪問(wèn)時(shí)間。

這是因?yàn)殡娞菁夹g(shù)發(fā)展到今天，尋找樓層的時(shí)間已經(jīng)有了很大地改進(jìn)，但是電梯的運(yùn)行當(dāng)中等待乘客上梯時(shí)間卻不是人為可以控制。

SATF 算法考慮到了電梯運(yùn)行過(guò)程中乘客上梯時(shí)間的影響。

2.1 最早截止期優(yōu)先調(diào)度算法

最早截止期優(yōu)先（EDF-Earliest Deadline First）調(diào)度算法是最簡(jiǎn)單的實(shí)時(shí)電梯調(diào)度算法，它的缺點(diǎn)就是造成電梯任意地尋找樓層，導(dǎo)致極低的電梯吞吐率。

它與 FCFS 調(diào)度算法類(lèi)似，EDF 算法是電梯實(shí)時(shí)調(diào)度算法中最簡(jiǎn)單的調(diào)度算法。

它響應(yīng)請(qǐng)求隊(duì)列中時(shí)限最早的請(qǐng)求，是其它實(shí)時(shí)電梯調(diào)度算法性能衡量的基準(zhǔn)和特例。

2.2 SCAN-EDF 算法

SCAN-EDF 算法是 SCAN 算法和 EDF 算法相結(jié)合的產(chǎn)物。SCAN-EDF 算法先按照 EDF 算法選擇請(qǐng)求列隊(duì)中哪一個(gè)是下一個(gè)服務(wù)對(duì)象，而對(duì)于具有相同時(shí)限的請(qǐng)求，則按照 SCAN 算法服務(wù)每一個(gè)請(qǐng)求。它的效率取決于有相同 deadline  的數(shù)目，因而效率是有限的。

2.3 PI 算法

PI（Priority Inversion）算法將請(qǐng)求隊(duì)列中的請(qǐng)求分成兩個(gè)優(yōu)先級(jí)，它首先保證高優(yōu)先級(jí)隊(duì)列中的請(qǐng)求得到及時(shí)響應(yīng)，再搞優(yōu)先級(jí)隊(duì)列為空的情況下在相應(yīng)地優(yōu)先級(jí)隊(duì)列中的請(qǐng)求。

2.4 FD-SCAN 算法

FD-SCAN（Feasible Deadline SCAN）算法首先從請(qǐng)求隊(duì)列中找出時(shí)限最早、從當(dāng)前位置開(kāi)始移動(dòng)又可以買(mǎi)足其時(shí)限要求的請(qǐng)求，作為下一次 SCAN 的方向。

并在電梯所在樓層向該請(qǐng)求信號(hào)運(yùn)行的過(guò)程中響應(yīng)處在與電梯運(yùn)行方向相同且電梯可以經(jīng)過(guò)的請(qǐng)求信號(hào)。

這種算法忽略了用 SCAN 算法相應(yīng)其它請(qǐng)求的開(kāi)銷(xiāo)，因此并不能確保服務(wù)對(duì)象時(shí)限最終得到滿(mǎn)足。

以上兩結(jié)介紹了幾種簡(jiǎn)單的電梯調(diào)度算法。

但是并不是說(shuō)目前電梯調(diào)度只發(fā)展到這個(gè)層次。目前電梯的控制技術(shù)已經(jīng)進(jìn)入了電梯群控的時(shí)代。

隨著微機(jī)在電梯系統(tǒng)中的應(yīng)用和人工智能技術(shù)的發(fā)展，智能群控技術(shù)得以迅速發(fā)展起來(lái)。

由此，電梯的群控方面陸續(xù)發(fā)展出了一批新方法，包括：基于專(zhuān)家系統(tǒng)的電梯群控方法、基于模糊邏輯的電梯群控方法、基于遺產(chǎn)算法的電梯群控方法、基于勝景網(wǎng)絡(luò)的電梯群控方法和基于模糊神經(jīng)網(wǎng)絡(luò)的電梯群控方法。

4.1 電梯的初始狀態(tài)

本人設(shè)置的電梯的初始狀態(tài)，是對(duì)住宅樓的電梯的設(shè)置。

(1)建筑共有21層，其中含有地下一層（地下一層為停車(chē)場(chǎng)）。

(2)建筑內(nèi)部設(shè)有兩部電梯，編號(hào)分別為A梯、B梯。

(3)電梯內(nèi)部有23個(gè)按鈕，其中包括開(kāi)門(mén)按鈕、關(guān)門(mén)按鈕和樓層按鈕，編號(hào)為-1，1，2，3，4……20。

(4)電梯外部含有兩個(gè)按鈕，即向上運(yùn)行按鈕和向下運(yùn)行按鈕。建筑頂層與地下一層例外，建筑頂層只設(shè)置有向下運(yùn)行按鈕，地下一層只設(shè)置有向上運(yùn)行按鈕。

(5)電梯開(kāi)關(guān)門(mén)完成時(shí)間設(shè)定為1秒。電梯到達(dá)每層后上下人的時(shí)間設(shè)定為8秒。電梯從靜止開(kāi)始運(yùn)行到下一層的時(shí)間設(shè)置為2秒，而運(yùn)行中通過(guò)一層的時(shí)間為1秒。

(6)在凌晨2：00——4：30之間，如若沒(méi)有請(qǐng)求信號(hào)，A梯自動(dòng)停在14層，B梯自動(dòng)停在6層。

(7)當(dāng)電梯下到-1層后，如果沒(méi)有請(qǐng)求信號(hào)，電梯自動(dòng)回到1層。

4.2 電梯基本功能

每一架電梯都有一個(gè)編號(hào)，以方便監(jiān)控與維修。每一架電梯都有一實(shí)時(shí)監(jiān)控器，負(fù)責(zé)監(jiān)控電梯上下，向電梯升降盒發(fā)送啟動(dòng)、制動(dòng)、加速、減速、開(kāi)關(guān)電梯門(mén)的信號(hào)。若電梯發(fā)生故障，還應(yīng)向相應(yīng)的電梯負(fù)責(zé)人發(fā)送求救信號(hào)。

4.3 電梯按鈕功能

電梯內(nèi)部的樓層按鈕：電梯內(nèi)部對(duì)應(yīng)每一個(gè)樓層的按鈕成為樓層按鈕，即本章第一結(jié)提到的編號(hào)為 -1，1，2，3，4……20的按鈕。當(dāng)乘客進(jìn)入電梯后按下樓層按鈕，此按鈕顯示灰色，代表不可以用。

這樣就表示乘客將要去往此層，電梯將開(kāi)往相應(yīng)層。當(dāng)電梯到達(dá)該層后，按鈕恢復(fù)可以使用狀態(tài)。

電梯內(nèi)部開(kāi)門(mén)按鈕：當(dāng)電梯達(dá)到乘客想要去往的某樓層后，乘客需要準(zhǔn)備離開(kāi)電梯，當(dāng)電梯停穩(wěn)后，乘客可以按下開(kāi)門(mén)按鈕，電梯門(mén)將打開(kāi)，讓用戶(hù)離開(kāi)。

如若電梯到了乘客曾經(jīng)按下的樓層，但是無(wú)乘客按開(kāi)門(mén)按鈕，電梯將自動(dòng)在停穩(wěn)后1秒后自動(dòng)開(kāi)門(mén)。

電梯內(nèi)部關(guān)門(mén)按鈕：當(dāng)所有想要乘坐電梯的乘客都進(jìn)入電梯以后，準(zhǔn)備讓電梯開(kāi)始運(yùn)行的時(shí)候，乘客需要按下關(guān)門(mén)按鈕，讓電梯門(mén)關(guān)閉，使電梯進(jìn)入運(yùn)行狀態(tài)。設(shè)置電梯的自動(dòng)關(guān)門(mén)時(shí)間為8秒。

電梯外部向上按鈕：此按鈕表示上樓請(qǐng)求，當(dāng)按下此按鈕時(shí)，如果電梯到達(dá)按下此按鈕的樓層，且電梯運(yùn)行方向是向上的，那么電梯響將停下，并在電梯停穩(wěn)之后自動(dòng)開(kāi)門(mén)，此請(qǐng)求被響應(yīng)后，取消此請(qǐng)求信號(hào)。

電梯外部向下按鈕：此按鈕表示下樓請(qǐng)求，當(dāng)按下此按鈕時(shí)，如果電梯到達(dá)按下此按鈕的樓層，且電梯運(yùn)行方向是向下的，那么電梯響將停下，并在電梯停穩(wěn)之后自動(dòng)開(kāi)門(mén)，此請(qǐng)求被響應(yīng)后，取消此請(qǐng)求信號(hào)。