aijam
2022-12-01 00:33:28 +08:00
感觉这是一个比较有趣的问题,类似于 CPU scheduling ,都是对于有限的共享资源分配的问题。Scheduling 在操作系统设计是已经比较成熟的问题,会用 CPU utilization, throughput, waiting time 等来衡量 scheduling algorithm 的优劣。
那对于电梯逆行问题,我们是不是也可以有类似的指标呢?我觉得比较好的其中一个指标是等待时间,即从开始等电梯到坐上电梯的时间。我们要最小化总的等待时间,同时为了公平,也要让等待时间的方差最小。
为了方便思考,考虑一个简化场景。假设所有人都要从顶楼下到一楼,电梯每次只能容纳一个人,电梯一直从顶楼到 1 楼来回跑(高峰期通常就是这样)。
可以得出一个比较有趣的结论:无论一共有多少个人要坐电梯,总的等待时间基本是不会变的。因为一趟就只能运一个人,有多少人要坐电梯就需要运多少趟。那么按照先到先得的规则乘坐电梯,并没有太大不可,因为不管逆行与否,这一趟都要选一个人乘坐,不是你坐就是我坐,那先看到电梯的先坐没什么问题。
也考虑一个极端情况,假设顶楼有 10 个人,大家都在下一班空电梯刚好到达顶楼的之前开始等待,那所有人的等待时间都是 0 。但如果在刚开始,次顶楼就有一个人要下楼,如果不逆行,他就必须等顶楼所有人都下去了才能下去,显然对他是不公平的。恰恰如果逆行,顶楼的人都只要每个人多等一趟电梯,反而更公平。
反过来也是成立的,如果次顶楼有 10 个人都是上面顶楼的情况,逆行的话,顶楼的一个人就要等次顶楼的楼全下楼了才能下。不逆行才能最优解。
实际情况比这个复杂的多。前面也有人说了,高峰期不逆行的话,高楼下楼始终都有优势,也会有一定程度的不公平。又比如如果不是全下楼,同时会有上下的人,逆行的话就要让上行的一个人和下行的一个人都等着,才能运送一个逆行的人下楼。可以认为让两个人等不如让一个人等?然而通常逆行距离不会太长,如果其中刚好遇到有人要上行,那这个人为什么不走楼梯呢?
假想有一个全知全能的管理者,监视每个人的等待时间,有一个优先队列,按照最长等待时间先乘坐的原则安排每一趟谁应该乘坐可能是最好的选择。可惜坐电梯的时候的都是自己管自己。弄一个人脸识别系统,高峰期监视所有人的等待时间然后指定谁可以上电梯可能是一个解决方向?