【BUAA-OO】ElevatorDispatcher3.0
发表于：2023-04-14 | 分类： BUAA面向对象
字数统计: 2.9k | 阅读时长: 10分钟 | 阅读量：

北航面向对象与程序设计第二单元课程作业，电梯调度器ElevatorDispatcher 3.0。
为2.0的迭代，新增需求：

  1. 限制同楼层服务电梯。
  2. 电梯可达楼层属性限制。

hw7_log

新增需求

  • 调度上有一点变化，限制了楼层停靠电梯的数量
  • 电梯可达性分析，一部电梯不一定能在所有的楼层停靠，所以需要考虑换乘的问题。（这一点的跨度很大，所以得好好分析需求

需求分析

  • 限制同楼层服务中电梯的个数与只接人电梯的个数
    • 这其实是对openAndClose做出的限制，而且满了的话也只好阻塞一下，等别的电梯退出服务状态再运行，没有什么好的优化办法（总不能说不下客了叭）。
    • 这个请求我想到的是交给总表来解决，因为电梯可以访问到总表，所以每一次开门和关门的时候都让总表的标志位+1-1就行了
      • 说到这，我觉得requestTable其实承担了太多的责任，这样其实是不好的，不符合单一责任的原则。
      • 我给我的RequestTable类改名为KanbanBoard，这样感觉更加贴切。
    • 后来我知道了一个信号量的做法，挺好用的，但是来不及实现了。
  • 对于电梯的可达性，这是电梯的一个final性质。
    • 我觉得可以在dispatcher里动态维护一个电梯可达图，在addEle与maintain的时候对它做出改变。（但是我最终没有实现。
    • 我选择在每一次需要获取从某层到某层的距离的时候，直接使用电梯的canAccess方法。
  • 给乘客加上乘坐路径的属性，然后原来的直接去的楼层属性改为destination。

具体实现

  • 第三次作业结束了，uml类图如下，由于一个比较好的架构，三次作业我只增加了一个类，就是关于路径规划的类：

uml

同楼层服务电梯的数量限制

  • 这个比较好实现，按照我上面需求分析的做法做就好了在每次开关门的时候都请示一下KanbanBoard。
  • 但是我在这个地方出了一个很傻的bug！！！
    • 因为我在maintain之后电梯的开关门是自行实现的，而不是调用的openAndClose方法，所以我在maintain的时候没有请示。
    • 这导致强测WA了两个点，呜呜呜呜呜。

可达性分析（路径规划

  • 在做这个可达性分析的时候，我非常的纠结，有过想大改的冲动，但是在一点一点的摸索中也探寻到了一个较好的方法。（从下面这幅图就能够看出来我有多纠结了。。。
    纠结ing

  • 所以确实现实不太允许我去这么做了，所以我的策略还是对于每一个需要dispatch出去的乘客，我先对他进行可达性分析，决定他下一步要去往哪一层，然后就照常分派，到不了那一层的电梯，我就直接不考虑就行。

    • 所以这样我就抽象出来了两条，路线规划与电梯选择，电梯选择我早就用Evaluation接口做好了。路线规划我也采取一种综合评价的方法，也采用策略模式，接口命名为PathPlanning，首先是一定要可达，可达的其次是可选择的电梯数量，这条路径上人多不多，电梯的属性。。。
    • 这些属性将在哪体现，这就涉及到我们探究可达路径的方法，其实无论是dfs还是floyd还是dijstra，只需要注意加权路径的权重怎么给，就可以灵活的解决我们这个规划最短路径的问题了。
  • 另外需要给乘客加上乘坐路径的属性
    • 这个属性是dispatcher给他规划的，所以对于电梯而言，只需要看路程属性即可。不需要关注目的地。
  • 所以电梯又多出来一个生产的途径，要多多考虑一下结束条件了。

路径规划及权重考虑

  • 路径规划的实现：（自定义边权重）dijstra算法
  • 关于dijstra算法的具体实现我这里就具体，网上的板子挺多的，可以选取一个单源dijstra算法实现抄一抄。我这里也给出大致的实现（仅仅表意，请根据自己的需要改编）。
  • 但注意由于我不是一种纯静态的实现，所以我把路径整个都记录了下来（很简单，用一个数组记录前驱节点即可）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
public Passenger planPath() {
    //初始化三个数组
    /*
     * result: 存起点到每个点的当前的最短路径
      * visited: 记录下这个点的最短路径是否已经找到
      * prevs: 记录下找到这个点的前驱节点
      */
    int[] result = new int[11];
    boolean[] visited = new boolean[11];
    int[] prevs = new int[11];
    //初始化，没有找到前驱节点的点数组值为-2，初始点前驱节点为-1
    for (int i = 0; i < 11; i++) {
        result[i] = Integer.MAX_VALUE;
        prevs[i] = -2;
        visited[i] = false;
    }
    prevs[fromFloor] = -1;
    int curFloor = fromFloor;
    result[curFloor] = 0;
    //循环寻路
    while (true) {
        //此楼层的最短路径已找到，如果这个楼层是目的地，则退出
        visited[curFloor] = true;
        if (curFloor == destination) {
            break;
        }
        //循环遍历这个点到每个未访问点的距离
        for (int i = 0; i < 11; i++) {
            if (!visited[i]) {
                int distance = getVirtualDistance(curFloor, i);
                if (distance != Integer.MAX_VALUE) {
                     //如果路径较短，更新result，将此节点记为前驱节点。
                     if (result[i] > result[curFloor] + distance) {
                         result[i] = result[curFloor] + distance;
                         prevs[i] = curFloor;
                    }
                 }
             }
        }
        //找所有已有的result中的最短距离,更新所在楼层
        int minLen = Integer.MAX_VALUE;
        for (int i = 0; i < 11; i++) {
            if (!visited[i] && result[i] <= minLen) {
                curFloor = i;
                minLen = result[i];
            }
        }
    }
    //到destination距离最大，不可达，数据的问题，报错
    if (result[destination] == Integer.MAX_VALUE) {
        throw new IllegalStateException("passenger " + passenger.getId() + " can't reach destination");
    }
    //现在给前驱数组压栈，找到前驱为-1，则当前点就是要去的楼层，这里是我的实现（用栈的结构来表示乘客下一个要去的地方。
    while (prevs[prevs[curFloor]] >= 0) {
        passenger.pushToFloor(curFloor + 1);
        curFloor = prevs[curFloor];
        cnt++;
    }
    passenger.pushToFloor(curFloor + 1);
    return passenger;
}
  • 写了这么一大堆dijstra，其实最重要最关键最灵活的是路径权重的选取，也就是int distance = getVirtualDistance(curFloor, i)这一句。
    • 路径权重可以考虑的有距离，换乘次数，最合适的电梯的评分（可能这条路上没有合适的电梯）。。。
    • 这是最为灵活的，如果你想尽量少换乘，就可以每一次getDistance的时候就加上一个巨大的权重，让它能够忽略其他的值。
    • 如果你想要让适当的换乘来分担直达电梯的压力（可能有只留了一部直达电梯，其他都要换乘的情况），可以选择权衡一下换乘次数与电梯状况的影响路径权重的配比。

动态还是静态？有一点折中

  • 关于动态的给乘客规划路径（即乘客每走过一程就重新规划一下），还是静态规划（即一开始就给乘客规定好，后面就按照这条路径走，有maintain的时候另说）。我觉得都有其优缺点。
    • 我这里采取的不是动态规划的方式，是因为我的加权路径计算比较的复杂，会遇上一个乘客在相邻两楼之间来回穿梭的bug。
    • 但是我采用的也不是静态的规划，因为很难假定乘客走完这一程之后电梯是否发生了天翻地覆的变化。
  • 还记得我说过我的“不强扭瓜”的分派方式嘛，我这里可以与这种分派方式做一个适配。
    • 即：一开始给乘客规划好所有的路径，然后每次乘客回到总表中重新分派的时候，如果有合适的电梯能够满足他的下一个需求的话，就使用这部电梯。如果没有！那就给这个乘客重新规划路径。这是一种半动态的方式。

DistanceEva！改改还能用

  • distance只需要改动两点，就能够在这一次的迭代中，达到可观的效果。
  • 一点是考虑到电梯的可达性，我再假定从1楼到11楼不合理了，应该是从可达的最低楼层到最高楼层
  • 另外的一点新的考虑是，其实对于电梯里的人与请求的人的考虑，我认为，不应该是线性的了！！！！！
    • 电梯剩余可载人数有三人和有五人有什么区别嘛？至少对于一个人是否能上这部电梯是没有区别的！！！
    • 所以我对于人数上的分数有一定的调整。
  • 经过参数调优之后，结果如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
return (int) ((33 - distance - elevator.passengerStatus() - speed * 17 - accessNum) / (speed * speed * accessNum));
//其中，电梯类的passengerStatus方法实现如下(可以看到是个阶梯状)：
public int passengerStatus() {
    double busyIndex = fullPasNum * 1.3 - passengerNum * 1.1 - passengerQueue.getPassengerNum();
    if (busyIndex > 3) {
        return 0;
    } else if (busyIndex > 0) {
        return 3;
    } else if (busyIndex > -3) {
        return 7 + (int) (0.5 * passengerQueue.getPassengerNum());
    } else {
        return 10 + passengerQueue.getPassengerNum();
    }
    }

结束条件

  • 结束条件也需要改动了，因为只要有电梯在动，就有可能有新需求，所以dispatcher不应该这么早结束。
    • 结束条件再加一条，所有电梯都是wait或者maintain的状态，分派才结束！

代码分析

  • 我用jetbrains自己家的codeMR插件（雪牲又可以白嫖，快冲）分析了一份结果出来。还挺好看的，但是我有些东西看不太懂，而且它以本地html的形式展现，我懒得弄上net了，就不放上来了，效果如下图：
    codeMR分析

  • 其实可以看出，虽然我从一到三次迭代从未重构，还算考虑周全，但是确实最后Elevator类，KanbanBoard类的复杂度还是太高了一点，代码行数也比较的恐怖，其实也本应该多做一点细分的。
    代码行数
    复杂度分析

  • 然后可以看到，圈复杂度比较高的都是些评价的算法，这个是因为我的评价体系确实考虑的太多了（

小感想

  • 这是我第一次写这么大规模的多线程的程序，教会了我很多分析线程安全问题解决问题的方法，我觉得这不仅是面向对象的程序设计所独有的一些经验。包括多进程的程序设计，并发并行程序设计等等都与这章所学到的知识息息相关。感觉在其中受益匪浅吧。
  • 另外这一章远不只是多线程这么简单，还教会了我使用设计模式，运用规范的面向对象设计原则去展开我的设计。
  • 在分析需求的过程中体会拓展与实现的各种巧思，这一点直接训练在思维能力上。我认为迭代开发中的架构设计稳定，不仅取决于良好的架构与代码风格，而且还取决于对于需求的分析，对于需求实现的发散！
北航 大二 OO 面向对象 电梯 第二单元
上一篇:
BUAA-OS-lab3-进程与调度
下一篇:
【BUAA-OS】lab2-内存管理

    • Copyright © 2019 - 2020 yuang01 | Powered by Hexo | Theme Bamboo

    本站总访问量： 次 |