演算法題電梯

① 演算法系列：電梯調度

在繁忙的大城市中，如芝加哥、紐約、東京、新加坡及香港，電梯作為人們離開辦公大樓的主要交通工具，其調度系統對提升整體效率至關重要。然而，我們鮮少深入了解電梯是如何在人流高峰時段，如每天的上下班時間，高效地為數百萬人服務的。

電梯調度領域的研究，特別是關注乘客等待時間的分配系統與電梯流量模擬的演算法，已經獲得了專利並在Quaro上發表。在一次面試中，面試官提出了如何優化電梯調度的問題，希望在給定的十層樓、三部電梯和均勻分布的乘客需求下，實現最高效的服務，同時確保每個樓層的等待時間最小化。

為了解決這一問題，我們可以設計一個演算法，以確保在高峰時段內，所有樓層的等待時間最短。考慮到樓層數量、電梯數量以及特定的高峰時段，演算法需根據負載量和時間函數分配電梯，同時考慮以下條件：

• 樓層數量任意


• 電梯數量任意


• 高峰時段已給定


• 每層人數相同且均等使用電梯

假設每層人數為100人，電梯通過一層的時間（不停）為5秒，每層等待時間為20秒。這些假設雖然簡化了問題，但仍能為面試提供足夠的挑戰性，同時方便後續的深入討論。

電梯分配演算法的關鍵在於將特定樓層與特定電梯關聯，即所謂的區域電梯分配策略。通過計算電梯往返時間，我們能夠實現最優調度。總的往返時間包括電梯通過每一層的時間與電梯在樓層數之間停靠的總等待時間。

為簡化問題，我們假設電梯容量無限大。一旦演算法實現並驗證其有效性，針對電梯容量的限制進行調整將相對容易。演算法採用兩個數組表示大樓與電梯，分別記錄樓層人數和電梯到達的最高樓層，以實現最優調度。

演算法的核心在於為每個樓層分配最優的電梯，以最小化整體等待時間和提高服務效率。通過計算電梯往返時間、平均載客量以及調整電梯分配策略，演算法能夠顯著降低高峰時段的等待時間，優化整體電梯調度。

實現演算法後，我們能夠通過模擬器可視化結果，展示不同電梯的往返時間、平均載客量以及整體服務效率。這些數據有助於評估演算法的有效性，並為進一步優化提供依據。

總結而言，通過設計一個合理的電梯調度演算法，我們能夠在高峰時段內顯著提升電梯服務效率，減少乘客等待時間，優化辦公樓的交通流。這一問題的解決不僅對提升城市交通效率具有重要意義，也為後續的深入研究提供了理論基礎。

② 電梯演算法是怎樣的

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

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

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

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

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

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

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

③ 電梯演算法構築貨如輪轉

在城市的摩天大樓中，人口激增與垂直空間的挑戰

隨著城市化進程的加速，人口密度的提升使得高樓林立，成為容納更多人群並追求美好生活的重要方式。在這些高聳的建築中，貨物的頻繁流動如何高效運轉，成為了決定效率的關鍵因素。

高層建築的貨物運輸難題

在高層建築中，貨物的運輸涉及三個核心環節：電梯的垂直移動、到達目標層的等待時間以及在樓層間的順序搬運。理想狀態下，貨物如同車輪般順暢流轉，通過哈密頓迴路在每層樓間循環，從電梯出來後遍歷每個房間再返回電梯。

電梯演算法：關鍵環節中的效率提升

電梯運行效率的高低，尤其是垂直方向的調度，直接影響貨物的流轉。最基礎的先進先出演算法（FIFO）按請求到達順序運行，簡單公平，但可能造成電梯頻繁切換方向，效率在請求密集時會下降。為解決這一問題，引入了優先順序排序，讓時間敏感的貨物優先使用電梯。

演算法創新：從SSTF到C-SCAN

短服務時間優先演算法（SSTF）通過優先處理近在咫尺的請求，減少了電梯的移動距離，但可能會使遠處請求等待時間過長。掃描演算法（SCAN）則通過單向移動，提高了效率，C-SCAN在此基礎上實現了上下分離，避免了單一方向的運輸沖突。

動態調度與靈活應對

面對不斷插入的新請求，電梯調度需兼顧既有請求與新請求。靜態隊列方式雖可能導致等待，但能避免磁碟飢餓；而動態演算法如SATF，通過預估裝載卸載時間，使貨物裝卸快的優先處理。

實例演示：演算法在實際中的應用

通過一個具體的例子，我們看到SSTF、SCAN和C-SCAN在128層建築中的出色表現，SATF雖然移動層數多，但確保了貨物的快速裝卸。在多電梯協作和差異化停靠策略下，整體的貨物運輸效率得到了提升。

電梯演算法：構建垂直空間的運輸網路

總的來說，電梯演算法在高層建築中起著至關重要的作用，它們不僅提升了垂直方向的運輸效率，更是城市生活中繁榮與便捷的催化劑，推動著我們更好地利用垂直空間，實現貨如輪轉的美好生活願景。

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

說明 假設大廈有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，即可以得出如下結論：

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

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