面向对象课程 HW7
本次作业新增了以下两个约束：
- 新增的电梯有可达性要求，即只能在特定的楼层停靠。
- 限制了在同一层开门的电梯数量。
本次作业主要的难点在于当停掉所有的全能电梯（即初始的六部电梯）后需要对乘客规划路径。本次作业中动态规划路径 + 加权最短路取得了非常优秀的成绩（我的大佬同学）。
本次作业中我重新考虑了以下电梯的移动逻辑、添加了搜索路径算法与电梯开门数量控制。
运行策略
hw5 与 hw6 的策略相似，但是策略不是很能适应 hw7 的需求。
本次作业中，电梯采取了类似 look 策略的掉头逻辑。当前方没有任务请求且电梯乘客队列为空时则掉头。这样设计带来的好处是电梯可以接受不同方向的乘客请求。
分配乘客策略
首先尝试直接分配乘客。接下来若乘客已被规划过路径且路径中的电梯没有维护则乘客按照既定的路径。否则给乘客规划新的路径。
存储路径的方式：使用一个二位数组 path[][2]。path[i][0] 的含义是要乘坐第 i 部电梯的 id。path[i][1] 的含义是要乘坐该部电梯所到达的楼层。
搜索路径
采取类似最小生成树的方式寻找路径。每次尝试添加一部电梯，若尝试添加的电梯的可达楼层与当前可达楼层没有交集或是当前可达楼层的子集，则不添加这个电梯；否则加入这个电梯，直到当前可达楼层包含乘客目的地时，代表我们找到了一个路径。之后就是把路径提取出来。
复杂度分析
| method | CogC | ev(G) | iv(G) | v(G) |
|---|---|---|---|---|
| AllRequest.AllRequest(ArrayList\ |
0.0 | 1.0 | 1.0 | 1.0 |
| AllRequest.getRequest() | 4.0 | 3.0 | 3.0 | 3.0 |
| AllRequest.getRequests() | 0.0 | 1.0 | 1.0 | 1.0 |
| AllRequest.isEmpty() | 0.0 | 1.0 | 1.0 | 1.0 |
| AllRequest.isEnd() | 0.0 | 1.0 | 1.0 | 1.0 |
| AllRequest.run() | 1.0 | 1.0 | 1.0 | 2.0 |
| Building.addPassenger(Passenger) | 0.0 | 1.0 | 1.0 | 1.0 |
| Building.addService(int) | 0.0 | 1.0 | 1.0 | 1.0 |
| Building.Building(AllRequest, ArrayList\ |
1.0 | 1.0 | 2.0 | 2.0 |
| Building.delService(int) | 0.0 | 1.0 | 1.0 | 1.0 |
| Building.directlyAlloc(Passenger) | 13.0 | 4.0 | 6.0 | 10.0 |
| Building.elevatorEnd() | 3.0 | 3.0 | 2.0 | 3.0 |
| Building.findPath(Passenger) | 25.0 | 7.0 | 9.0 | 13.0 |
| Building.handleFindPath(Information, Passenger, ArrayList\ |
27.0 | 1.0 | 13.0 | 15.0 |
| Building.handleRequest() | 12.0 | 7.0 | 7.0 | 7.0 |
| Building.isEnd() | 1.0 | 1.0 | 4.0 | 4.0 |
| Building.openAble(int) | 0.0 | 1.0 | 1.0 | 1.0 |
| Building.pasAlloc(Passenger) | 12.0 | 7.0 | 8.0 | 9.0 |
| Building.run() | 3.0 | 2.0 | 2.0 | 3.0 |
| Building.step() | 13.0 | 1.0 | 8.0 | 8.0 |
| Elevator.capacityAlloc() | 0.0 | 1.0 | 1.0 | 1.0 |
| Elevator.carry(Passenger) | 0.0 | 1.0 | 1.0 | 1.0 |
| Elevator.Elevator(int, int, double, int, int, int, Building) | 6.0 | 1.0 | 1.0 | 4.0 |
| Elevator.findBottom() | 4.0 | 1.0 | 4.0 | 4.0 |
| Elevator.findTop() | 4.0 | 1.0 | 4.0 | 4.0 |
| Elevator.getAccess() | 0.0 | 1.0 | 1.0 | 1.0 |
| Elevator.getId() | 0.0 | 1.0 | 1.0 | 1.0 |
| Elevator.getState() | 0.0 | 1.0 | 1.0 | 1.0 |
| Elevator.goDie() | 13.0 | 4.0 | 11.0 | 11.0 |
| Elevator.hasPassenger() | 3.0 | 3.0 | 2.0 | 3.0 |
| Elevator.ifDirectly(Passenger) | 2.0 | 3.0 | 1.0 | 3.0 |
| Elevator.ifOff() | 3.0 | 3.0 | 2.0 | 3.0 |
| Elevator.ifOff(Passenger) | 0.0 | 1.0 | 1.0 | 1.0 |
| Elevator.ifTake() | 4.0 | 4.0 | 2.0 | 4.0 |
| Elevator.ifTake(Passenger) | 1.0 | 1.0 | 2.0 | 2.0 |
| Elevator.isDie() | 0.0 | 1.0 | 1.0 | 1.0 |
| Elevator.isEmpty() | 0.0 | 1.0 | 1.0 | 1.0 |
| Elevator.isEnd() | 1.0 | 1.0 | 2.0 | 2.0 |
| Elevator.isFree() | 1.0 | 1.0 | 2.0 | 2.0 |
| Elevator.move() | 15.0 | 3.0 | 6.0 | 12.0 |
| Elevator.setDie(boolean) | 0.0 | 1.0 | 1.0 | 1.0 |
| Elevator.step() | 22.0 | 8.0 | 16.0 | 19.0 |
| Elevator.takeOff() | 7.0 | 2.0 | 4.0 | 5.0 |
| Elevator.takeOff(Passenger) | 0.0 | 1.0 | 1.0 | 1.0 |
| Elevator.takeOn() | 5.0 | 2.0 | 4.0 | 5.0 |
| Elevator.takeOn(Passenger) | 0.0 | 1.0 | 1.0 | 1.0 |
| Elevator.toString() | 0.0 | 1.0 | 1.0 | 1.0 |
| Elevator.tryClose() | 1.0 | 2.0 | 1.0 | 2.0 |
| Elevator.tryOpen() | 5.0 | 2.0 | 4.0 | 5.0 |
| Information.add(int, int, int, int) | 0.0 | 1.0 | 1.0 | 1.0 |
| Information.getAccess(int) | 0.0 | 1.0 | 1.0 | 1.0 |
| Information.getAccessById(int) | 3.0 | 3.0 | 1.0 | 3.0 |
| Information.getId(int) | 0.0 | 1.0 | 1.0 | 1.0 |
| Information.getNow(int) | 0.0 | 1.0 | 1.0 | 1.0 |
| Information.getPathLen(int) | 0.0 | 1.0 | 1.0 | 1.0 |
| Information.growPathLen(int) | 0.0 | 1.0 | 1.0 | 1.0 |
| Information.setNow(int, int) | 0.0 | 1.0 | 1.0 | 1.0 |
| Information.size() | 0.0 | 1.0 | 1.0 | 1.0 |
| MainClass.main(String[]) | 0.0 | 1.0 | 1.0 | 1.0 |
| Passenger.addPath(int[]) | 3.0 | 1.0 | 2.0 | 3.0 |
| Passenger.clearPath() | 0.0 | 1.0 | 1.0 | 1.0 |
| Passenger.getDirection() | 0.0 | 1.0 | 1.0 | 1.0 |
| Passenger.getFinish() | 0.0 | 1.0 | 1.0 | 1.0 |
| Passenger.getFistPath() | 0.0 | 1.0 | 1.0 | 1.0 |
| Passenger.getId() | 0.0 | 1.0 | 1.0 | 1.0 |
| Passenger.getPath() | 0.0 | 1.0 | 1.0 | 1.0 |
| Passenger.getStart() | 0.0 | 1.0 | 1.0 | 1.0 |
| Passenger.Passenger(int, int, int) | 0.0 | 1.0 | 1.0 | 1.0 |
| Passenger.removePathHead() | 3.0 | 1.0 | 2.0 | 3.0 |
| Passenger.setPath(int[][]) | 4.0 | 3.0 | 2.0 | 4.0 |
| Passenger.takeOff(int) | 0.0 | 1.0 | 1.0 | 1.0 |
| Passenger.toString() | 0.0 | 1.0 | 1.0 | 1.0 |
| State.getValue() | 0.0 | 1.0 | 1.0 | 1.0 |
| State.isClosing() | 0.0 | 1.0 | 1.0 | 1.0 |
| State.isDie() | 0.0 | 1.0 | 1.0 | 1.0 |
| State.isOpen() | 0.0 | 1.0 | 1.0 | 1.0 |
| State.isOpening() | 0.0 | 1.0 | 1.0 | 1.0 |
| State.isRunning() | 0.0 | 1.0 | 1.0 | 1.0 |
| State.isWait() | 0.0 | 1.0 | 1.0 | 1.0 |
| State.setClosing() | 0.0 | 1.0 | 1.0 | 1.0 |
| State.setDie() | 0.0 | 1.0 | 1.0 | 1.0 |
| State.setOpen() | 0.0 | 1.0 | 1.0 | 1.0 |
| State.setOpening() | 0.0 | 1.0 | 1.0 | 1.0 |
| State.setRunning() | 0.0 | 1.0 | 1.0 | 1.0 |
| State.setWait() | 0.0 | 1.0 | 1.0 | 1.0 |
| State.State(int) | 0.0 | 1.0 | 1.0 | 1.0 |
| Total | 225.0 | 141.0 | 193.0 | 235.0 |
| Average | 2.616279069767442 | 1.6395348837209303 | 2.244186046511628 | 2.7325581395348837 |
本次作业复杂度中搜索路径的两个方法复杂度较高。这部分我写的这部分太面向过程了。
bug分析
本次作业由于把分配乘客的间隔设置为 1s 而寄了五个点…要不本来只会寄一个点，只能说是弄巧成拙了。后来检查的时候发现是乘客分配的锅，但是我也没有找到到底是哪里有问题…于是最后在电梯步进的时候对任务队列做了一个强检查，要是不能达到乘客需求的楼层就把他弹回楼里。
协作关系
由于本单元均为状态机逻辑，故没有线程之间的协作关系
Dbug技巧
单线程的状态机 dbug 还是比较简单的，出了问题之后感觉哪里有问题在哪里添加 println 打印状态就可以了。而且所有 bug 都能够稳定复现，我在本单元基本没有为 dbug 苦恼过。
本单元收获
遗憾的是，本单元并没有怎么学习到多线程的精髓…收获最大的大概是和同学一起搭的评测机。本单元由于测试一个点的时间过长，于是评测机需要是多进程的，于是乎在这个过程中学习了一些多进程的写法，也算是学到了一些新东西。此外前两次的数据生成也是由我负责的，从自己生成的数据与课程组强测的数据对比我也学习到了一些数据生成的要领。事实上，单纯由程序随机生成的数据总是有缺陷的。最优解是通过随机跑出来一些数据之后通过手动微调数据，或者直接手搓一些特殊的测试点。第六次作业我自己生成的数据强度还是比较认可的，就是因为太强了而不满足互测标准从而没法在互测里直接用…不过那个评测机 d 出来的 bug 是真不少。
在学习的过程中也感受到了不同科目之间的交叉性。比如 OO 课内讲到的概念在 OS 上也会有提及。另外 CO 的状态机设计也助我通过了本次作业。事实上貌似只要设计的好，电梯这单元无论如何使用状态机都是有出路的。来年或许可以想一个办法 ban 掉状态机（如果当上了助教的话）。
