2019华为软件精英挑战赛经验总结_华为挑战赛赛题分析

比赛情况

本人属于非计算机专业，编程新手，用的是PYTHON语言，参加比赛的原因是赛事题目和本人的研究方向很相近，且也十分感兴趣。非常荣幸的在组队阶段抱上了两个队友（一个机械系学长，一个计算机系好看女孩）的大腿，在整个项目的进行的过程中，自己的主要职责是代码手，自己对PYTHON语言的熟系程度在此次比赛中得到了很大的提升，以及在处理路径规划问题时积累了一定经验。
我们队在训练赛的时候成绩冲到了赛区十（当然有大佬在榜单后面潜着的）

正式比赛的时候由于计算量从一万辆车增加六万辆，地图模型扩大了一倍…结果程序就跑超时了，好不容易按照题目要求写出来的判断器，都已经具备动态规划条件了，结果不能用，只能使用随机限流调参大法！——成绩什么的全靠缘分了，结果跑出来的成绩连个复赛都进不了

伤心话不多说，直接上正文

一、题目介绍

具体题目要求可以上比赛官网下载：华为软件精英挑战赛官网
以下是初赛题目介绍：

1. 背景信息

l 道路交通是城市的核心要素之一。

l 随着社会经济的发展，中国城市的车辆保有量已经越来越多，大都市慢慢变成了“堵”市。如何在出行时避免拥堵，是每一个人的目标。

l 日常生活中，很多拥堵是由于车辆行驶路线规划失误，大批车辆集中选择主干道行驶导致通行效率下降。

l 如果车辆都由调度中心统一规划调度路线，拥堵问题将得到大大缓解甚至彻底解决。

l 实际上这一技术已经在工业领域如矿山车辆、无人货仓等得到广泛应用。

l 但道路上的私家车辆尚无法进行统一规划，未来，自动驾驶和物联网技术的结合，使得彻底解决这一难题出现了曙光。

l 请同学们提前出任“首席城市交通规划官”，为未来城市规划好每一辆车的行驶路线。

2. 题目定义

l 在模拟的道路图上为每一辆车规划行驶路线，系统会自动根据规划路线运行。

l 在路线合法的前提下，最终所有车辆按照规划的路线到达目的地。

3. 系统假定

l 路口完全立交：假定在每一个路口交汇的所有道路都可以完全互连，且车辆通过路口时不考虑在路口的通行时间。

l 无限神奇车库：我们认为，系统中的每个地点都有一个无限容量的“神奇车库”。车辆在未到既定出发时间前，或者到达目的后，就停放在“神奇车库”中，完全不影响其他车辆通过。但车辆一旦出发，在行驶过程中则不允许进入车库空间。

4. 约束条件

l 不允许超车变道：即车辆一旦进入某条车道，就必须在此车道内从道路起点驶向道路终点，中途不允许变道，即使前车速度缓慢，也不允许超车。

l 排队先到先行：在一条道路前排队等待的所有车辆，按照到达时间先后进入道路。若多辆车在同一时间到达，按如下规则进入下一道路：

1. 同一道路牌车道号小（车道的编号）的车辆优先于车道号大的车辆

2. 按现实交通规则，直行车辆有优先通行权，直行车辆优先于转弯车辆

3. 处于左转进入道路的车辆优先于右转进入道路的车辆

l 车道固定进入：车辆在进入一段道路时按照车道编号从小到大的优先级选择可以进入的车道驶入，与前车的行驶速度无关。

即就是：车辆优先按车道编号由小到大依次进入，除非车道号小的车道没有空位可进入。

二、项目思路

初赛阶段：
其实要想挺进复赛还是挺容易的，只要在满足赛方要求的时间限制内内内内内内内内内内内内内内（省略了上百万个"内"），你的程序能实现动态路劲规划那么就八九不离十就进复赛了。而要想实现动态规划，整个程序就需要三个功能：地图模型构建、路径选择算法、判断器

1、地图模型构建

为了方便之后的路径规划算法调用地图信息，以及道路模型创建，我们需要再原有的赛方地图数据：(道路id，道路长度，最高限速，车道数目，起始点id，终点id，是否双向)，(结点id,道路id,道路id,道路id,道路id)
上进行内容提取，生成新的地图数据库。当时参考了东南大学机械动力学院Fang JIA, Chenglong REN, Yi CHEN, Zhixiang XU关于AGV小车路径规划一篇论文

这里是引用
II. MAP MODELING
In flexible manufacturing systems, the main duty of AGV is
to travel between the various machine tools for handling
materials. In this paper, the AGV uses magnetic guidance.
Therefore, the magnetic stripe layout is the AGV motion map
shown in Figure 2.
None-oriented map consists of node set N = {n1, n2, n3, … ,
nm}, side set with weight E = {e1, e2, e3, … , eb}, cross card C =
{c1, c2, c3, … ,ca }, and side of the weight set W = {w1, w2, w3, … ,
wb}. P<ni ,nj> denotes the direction of node ni to node nj
(According to principle, north to south and west to east).

In the layout, ni represents any intersection node, station
node or right angle turn node. ci represents the deceleration node.
Its role is that when the AGV turn, the deceleration card prompt
AGV deceleration to the node ni. Turning function is achieved
by translation (The experiment discussed in this paper is verified
using omni-directional mobile robot, such that only translation
is needed to achieve turning function).
During the process of software development, the map
information is stored in the adjacency matrix. M(m×m)represents
the side weight matrix and O(m×m) represents direction matrix.

简单来讲我们就是要提取出我一个节点与我相邻节点中的方位关系，即我往北能到达哪个节点，往西能到达哪个节点。同时我还要提取出我节点与相邻节点的距离信息。
由于正式比赛的时候，赛方给的道路、节点的信息不保证顺序不间断，所以以上两个信息我们是以两个字典储存。

2、路径选择算法

路径选择算法上我们使用的是A算法
这有两篇文章很好的介绍了A算法：
堪称最好最全的A算法详解
利用A算法进行路径规划

这里是引用
和其它的图搜索算法一样，A潜在地搜索图中一个很大的区域。和Dijkstra一样，A能用于搜索最短路径。和BFS一样，A能用启发式函数（注：原文为heuristic）引导它自己。在简单的情况中，它和BFS一样快。

在凹型障碍物的例子中，A找到一条和Dijkstra算法一样好的路径：

成功的秘决在于，它把Dijkstra算法（靠近初始点的结点）和BFS算法（靠近目标点的结点）的信息块结合起来。在讨论A的标准术语中，g(n)表示从初始结点到任意结点n的代价，h(n)表示从结点n到目标点的启发式评估代价（heuristic estimated cost）。在上图中，yellow(h)表示远离目标的结点而teal(g)表示远离初始点的结点。当从初始点向目标点移动时，A权衡这两者。每次进行主循环时，它检查f(n)最小的结点n，其中f(n) = g(n) + h(n)。

三、判断器

判断器就借用官方的伪码来说明一下，我们编的判断器思路大概和其相似

附伪码(判题器)：（输入为car.txt,cross.txt,road.txt answer.txt， 输出为调度时间，总调度时间）

    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();
    }
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

附一张判断器运行图：

下边是代码连接
A*算法实现代码(包含地图)：https://download.csdn.net/download/weixin_44409075/11095020