电梯的一点浅优化

1、调度方案的选择

第六次作业要做一个可捎带的电梯，如何呢？指导书给了ALS，我觉得ALS也有固有弊端，比如可能会在有乘客时掉头。从用户体验上，这是极差的，而且一般情况下（~~除非是这一层刚走了狼半秒钟又来了虎，比如某组变态的数据~~）这种掉头会增加时间开销。所以，我采取了贴近生活的look算法，就是咱们楼道里那个电梯的调度算法。

查了一下，电梯的几种调度算法，包括：scan算法，look算法，ALS，还有FAFS，最近距离等。

scan算法是上下循环调度，类似于摆渡车、轮渡，缺点是没有乘客的楼层也要停。

look是scan的改进，没有乘客和请求的楼层不停，直接掉头。

ALS和FAFS太熟悉了，不用说。

还有一种是最近距离，也就是当电梯内有乘客时，乘客优先。无乘客时，距离当前楼层最近的请求优先。但这会出现某些请求“饿死”的情况。

综合以上几种，还是look比较好。

基本思想就是，请求要分为电梯外请求和电梯内乘客两部分。电梯外请求按照出发楼层分类，电梯内请求按照目标楼层分类。每当电梯到达某一层时，检查是否需要上客或下客，有则开门，无则甩过直接走。每当准备移动到下一层时，检查是否需要掉头（检查是否掉头是一个扫描过程，如果电梯内有乘客则不能掉头，否则扫描电梯外请求，如果当前方向上没有请求则掉头，如果两边都没有请求，则停下来等待）。

一个最简单的优化，就是停在某一层的时候，以关门时间为粒度，检查要上的乘客。比如我现在是开门状态，就等待200毫秒，如果这200毫秒内有需要上的乘客则让他上，并继续等待200ms，如此循环，直到某个200ms内没有乘客可以上为止。这种方法虽然增加了停靠时间，但往往减少了捎带乘客的遗漏，在大量乘客请求中表现良好。

另外，如果还想骗一点分，还可以变通一下，在某一层开门，一股脑都上，不管方向如何，运行到目标楼层再放出去。这就减少了开关门总次数。但是在多电梯中不适用，因为多个电梯是并行的，不顾一切地把乘客吸走，不仅影响调度器，而且会有超载等问题。

2、大量数据下时间性能的提高--平摊分析

第七次作业不仅增加了两部电梯，而且增加了乘客数量限制、停靠层限制。所以，这决定我们需要一个调度盘来把乘客请求分配到合适的电梯上去。并且，考虑换乘问题。

架构就是三个电梯、一个调度盘，请求队列分三块，一块是原始请求，也就是刚输入的时候，没有经过调度器分配，可以理解为站在大厅门外。一块是分配后请求，可以理解为站在某个电梯门口。最后是电梯内乘客。

换乘不难解决，为了一劳永逸的防止出错，我们把未完成的请求扔回原始请求中，也就是回滚。这样保证各个电梯互相独立。电梯只负责运送乘客，不管任何调度问题。

但是调度问题比较棘手。最简单又保证正确的就是按照A，B，C的顺序来搜索合适的电梯，搜索到第一个合适的电梯即为所求。但是，这样就有一个弊端，因为每个电梯都有人数限制，一部电梯门口排太多人会导致有些人等待时间太长从而影响效率。而且，与其让B、C空着，不如让它们动起来，减小A的压力。

所以，我们要尽可能地把这些人分配到不同的电梯中。这时，搜索可分配电梯的顺序就至关重要。

什么叫尽可能？做到任何情况下最优是一个NP完全问题。真正关心的是大量乘客下平均时间性能。所以，摊还分析又大显身手了。

我们把A、B、C的六种搜索顺序（ABC ACB BAC BCA CAB CBA）排成一列，然后每次随机取一种顺序进行搜索，搜索到的第一个可行电梯作为分配目标。这样多个请求就会分配到多个电梯中。有了三个电梯的并行，效率会大大提高。

// Dispatcher.java（调度器）部分源码
private final Random random = new Random();
private final int[][] arr = {
        {0, 1, 2}, {0, 2, 1},
        {1, 0, 2}, {1, 2, 0},
        {2, 0, 1}, {2, 1, 0}
}; // 六种顺序

// 注：fixFloor()方法是寻找合适的换乘点，如果返回值等于出发楼层，说明这个电梯不能上。如果返回值等于目标楼层，说明不需要换乘。
private void dispatch(PersonRequest request, int fromFloor)
        throws InterruptedException { // 分配函数
    int i;
    int toFloor = Elevator.realFloor(request.getToFloor());
    int[] tmp = arr[random.nextInt(6)]; // tmp就是选取的搜索顺序
    for (i = 0; i <= 2; i++) {
        if (selfRequests[tmp[i]].containsKey(fromFloor)
                && fixedFloor(tmp[i], fromFloor, toFloor) != fromFloor) {
            selfRequests[tmp[i]].get(fromFloor).put(request); // 找到第一个可行电梯
            return; // 这个return是一定能执行到的，因为每一层至少有一个电梯可以上
        }
    }
}

看强测结果已经是出乎意料的好了，最终得分92.7，得到一半的性能分，甚至有的点达到96。自己测试的话，20个随机请求，大约是3~50秒之间发出，最初的贪心算法是91秒跑完，换随机之后降低到74秒。效果还是非常好的。

所以说，一个良好的随机算法有时能轻松碾压某些确定性算法的。毕竟按照请求做最短路搜索这种工作量又大，又不能保证优化效果，因为电梯不是无限载客的。尤其是电梯这种注重平均性能的东西，平摊分析更是制胜法宝。

以上就是我对电梯优化的一个办法。dalao们如果有实时调度的算法，欢迎交流。