算法题电梯

① 算法系列：电梯调度

在繁忙的大城市中，如芝加哥、纽约、东京、新加坡及香港，电梯作为人们离开办公大楼的主要交通工具，其调度系统对提升整体效率至关重要。然而，我们鲜少深入了解电梯是如何在人流高峰时段，如每天的上下班时间，高效地为数百万人服务的。

电梯调度领域的研究，特别是关注乘客等待时间的分配系统与电梯流量模拟的算法，已经获得了专利并在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，即可以得出如下结论：

电梯的停靠次数越少，最后一层的时间也就越少，同样最佳时间也就越少。

假设我们有一个方法可以根据当前的停靠次数来计算最佳的停靠方案，那么我们该如何得到实际最佳方案呢？下面的一段代码很好的可以达到我们的目标。