参加软挑的一些感悟

写在前边的话

我本科一直在做嵌入式相关的项目,这是第一次参加软件类的竞赛,不得不说过程确实很刺激,最后止步杭厦赛区50强也很是遗憾,明明很接近,最后输在了代码效率上,本地成绩很好的 python代码 ,上传测评运行时间超限（官测环境比本地性能好，普遍情况是用时远超本地，其中华为云主机集体宕机半小时，很多人测过的最优代码，最后再上传就超时了https://bbs.huaweicloud.com/forum/thread-16237-1-1.html）。超限原因主要两点，一是自己在实现调度器时的代码臃肿，二是正式赛数据量大增。但进入32强的不少组并没有实现调度器，完全 随机时间发车+单车路径最优规划 , 感觉很(￣_,￣ )。这比赛不实现调度器，意义少了一半，再用上这种偷鸡方法，没觉出来还有啥意义。唉，菜鸡就是菜鸡。总之，这次经历对我还是有不少积极的影响的，下面就总结一下吧。

题目解读

本次比赛主要做的是 动态路网下多车辆调度问题, 参赛者合理安排数万车辆在合理时间从出发点到达各自的目的地，程序上传至官方服务器，运行后得出 所有车辆出发时间和规划的路径 ，将在官方调度器中进行调度，完成车辆调度用时即为最终成绩。具体是比赛任务书中花了很大篇幅讲了官方调度器的规则，并且论坛前期几乎天天在更新规则补充，最终完全准确实现的队伍只见过一个，其他很对队伍是很接近，但总有差别。我们自己实现的调度器，调度时间完全对的上，但是所有车辆调度总时间总是差了一些。分析原因有以下两点:

我们实现的调度规则还有与官方一些差异；（但是我们实现的和部分队伍对比的结果完全一致，但和官网就有差异，猜测可能有些规则官方描述的有些差异，或者某细节被我们忽略了）
python 即使版本相同，但是在不同机器上结果确实有差异，这个也被官方证实了https://bbs.huaweicloud.com/forum/thread-15889-1-1.html。

总体上参考任务书，下面只简单梳理一下思路（这里默认已经熟悉了任务书）：

下面先附上官方伪代码

for(/* 按时间片处理 */) {foreach(roads) {/* 调整所有道路上在道路上的车辆，让道路上车辆前进，只要不出路口且可以到达终止状态的车辆* 分别标记出来等待的车辆（要出路口的车辆，或者因为要出路口的车辆阻挡而不能前进的车辆）* 和终止状态的车辆（在该车道内可以经过这一次调度可以行驶其最大可行驶距离的车辆）*/driveAllCarJustOnRoadToEndState(allChannle);/* 对所有车道进行调整 *//* driveAllCarJustOnRoadToEndState该处理内的算法与性能自行考虑 */}while(/* all car in road run into end state */){/* driveAllWaitCar() */foreach(crosses){foreach(roads){while(/* wait car on the road */){Direction dir = getDirection();Car car = getCarFromRoad(road, dir);if (conflict）{break;}channle = car.getChannel();/* 这里只指因下一道路有等待车辆阻挡而导致该车辆无法进入的情况 *//* 其他情况均返回true,比如下一车道满无法进入（全是终态），或才是下一车道限速不能进入，该车辆停留在其当前车道最前方 *//* 该车辆也是移动至其所在车道最前方，只有有车辆由等待变以终止，就对其车道后续车辆状态进行调整 */if(!car.moveToNextRoad()) {break;}/* driveAllCarJustOnRoadToEndState该处理内的算法与性能自行考虑 */driveAllCarJustOnRoadToEndState(channel);}}}}/* 车库中的车辆上路行驶 */driveCarInGarage();}

要调度的车辆分两种：路上的车和要上路的车

每个时间片先处理路上车，在处理上路车

路上的车处理步骤： step1标记状态， step2 移动车辆

车的状态：每个时间片（一个时间片指的是所有车辆一次调度完成）路上车辆有三种状态，未调度过的车是 无状态，调度过但是由于阻挡或者其他原因不能移动的车标记为 等待状态，调度过并且完成移动的车标记为 终态。

step1: 怎样标记状态？

- 这个时间片车辆最大行驶速度能超过该道路长度（超过了但不一定就能进入下一条道路），直接标记为`等待状态`
- 这个时间片车辆最大行驶速度不能超过该道路长度，但是前方有车辆挡住自己将要走的路，直接标记为`等待状态`
- 这个时间片车辆最大行驶速度不能超过该道路长度，并且前方没车辆挡住自己，**移动该车**，直接标记为`终止状态`

step2: 按什么顺序调度车辆？
- 路上的车：
  - 处理次序：
    - 按照ID升序反复遍历路口，直到所有车辆变成终态
    - 对每个路口，按照ID升序遍历朝向这个路口的道路（也反复遍历，直到所有车进入终止状态，或者被阻挡无法移动）
    - 每个道路上有多条线，按照优先级顺序处理车辆，只有第一优先级车辆完成调度，才能调度优先级低的车。
    - 不过马路而被标记等待的车，不受优先级限制，阻挡车辆离开，这种车立马跟上
- 上路的车：
  - 上路车按照ID升序处理
  - 规划的时间因为前方无空位而未上路的车，顺延到下一时刻优先上路，即不参与下一时刻车辆ID升序发车。

哪些车参与优先级的排序？

要过马路的车和车速超过当前道路剩余长度，但是根据任务书10-5条，不能进入下一道路的车都参与优先级排序。

大概就这些了，其他更细微的只能遇到才想起来了。

思路总结

这里只总结一下初赛的思路。

这个比赛就是合理安排车辆调度，以最短时间让所有车都到达终点。所以要找到合适的方法让车辆快速充满道路而不至于 锁死,锁死也是赛题的最难点。道路上流动的车越多，越容易出现锁死情况；道路上流动的车越少，最终调度时间就越长。所以优化的目标变成了保证不死锁的情况下，让更多的车在道路上流动起来。

什么是死锁？

死锁指的是，某个时间片道路上的车辆由于循环等待（形成了环形等待情况），导致无法再进一步调度任何车辆，导致调度失败，成绩为0。体现在调度器里，就是step2 反复调度路口时，等待状态的车辆数量不再减少，即锁死了。

怎么避免死锁？

唯一可以避免的方法是完全实现调度器，和官方调度器一致，就可以准确判断到锁死，并且在规划道路时动态规划新路，解开环形等待的死亡链。可惜大家完全模拟出来调度器的几乎没有（据我一直水群了解到的情况看，是这样，不排除潜水大佬真的实现了）。
所以呢，大部分人都是想尽办法的尽量减少锁死，无法完全避免，下面会举例几种方法。

有不完全正确调度器的解决方案

单车最优路径静态规划 + 遇锁死时对部分车动态规划

如果调度器不太一致时，就当某道路调度同一车辆多次，就给这个车强制规划新路径。
单车最优路径静态规划 + 遇锁死时把锁死车辆从路上删除，未来重新发车
分批次发车 + 每个批次单独规划路径 + 动态路阻 + 锁死车辆动态规划

这个是效果比较好的一种方法，练习赛后期成绩能进入前15名的方法。动态路阻指的是道路情况拥堵，这里选择了几个因素：

动态路阻 = 这个批次经过该道路车辆数量a + abs(道路限速 - 车速)b + （1 - 道路中路线数/最大线数）*c

路阻每个批次都清除一次，这样在调度器不准确的情况下很大程度上抑制了死锁的发生，当时采用这种方法之后，每个批次发车量明显可以提高很多。这里a，b，c是需要调节的参数。

没有调度器的解决方案

如果没实现调度器，也有一些不错的方法，但是不算偷鸡。这里把路网当成计算机的网络，网络的带宽就是道路的线数，我们想让网络传输最大量的数据，但是网络本身承载能力有限制，我们要找到均衡流量的方法，让网络上流动的流量尽可能的均衡，这样再找到合适的参数，即网络最适合的承载车辆数目，保证网络流量不超过这个限制，也可以减少死锁的情况。即 分批次发车 + 每个批次单独规划路径 + 动态路阻

还有一种不太有意义的方法

这种也被很多人叫做偷鸡方法，就是 单车路径最优规划 + 随机时间发车，然后就是调调调。这种方法优势是答案生成快，可以反复调无数次。而实现调度器的同学，基本半小时才能调一次参数，因为模拟调度的过程比较费时间，又加上动态路径规划，时间代价大大提高。

对单车的寻路算法

想当然的觉得地图是平面的，因为官方给的任务书全是平面图，并且每个路口对应的四个街道都是有方向的，所以对路口直接建立了坐标系，有了每个点的方位坐标信息，也就很自然的选择了A*算法。结果没想到，最后正式赛当天出现的地图是这。。。样。。。的。。。，出现了高空立交桥，这还算直行吗。开始不知道地图变了样子，结果递归建坐标系的部分爆了bug，改了半天，卒了。后来看到群里可视化后的效果是下图，吐血了，赶紧换了Dijkstra算法。这两个算法有时间再总结。

logo

我们组的结果

结果就是止步初赛了，调度器 + 动态规划 + 动态路阻 + 。。。+ python 真是很费时间，本地要15分钟勉强出结果，服务器上直接超时。放弃了调度器和动态规划，只用了动态路阻，最后所剩时间不多了，只调了几次参数就到时间了。

比赛的经验与教训

比赛运行环境一定要保证和官方一致，不然结果会出现不一致。
如果还是这种复杂规则的情况，不要再选择python，速度确实有问题，代码能力差的人体现的更明显~、~、
好好理解题目在行动。

感悟

结果有点惨淡，但是这段时间确实收获了很多，也多亏了两位队友的倾力相助，以及师兄的思路指导。郭同学为团队提供了大部分算法上的思路和代码；丁同学从开始比赛到最后一天，也一直在和我讨论着调度以及算法，纠正了我很多错误的理解，比赛的日子也是近段时间来最开心的日子，期待大家下一次的合作。画江湖之绿皮车将要回归。。。