又是一篇拖了好长时间的文章…

CodeCraft是华为2015年起开始举办的编程挑战赛, 强调享受用coding解决问题的乐趣. 其实那段时间(两个月前)有好几个华为组织的比赛什么销售, 云计算等等. 我因为之前都没参加过, 加之感觉coding会好玩一些所以报名了CodeCraft. 虽然最后完成了程序但没及时上传（；´д｀）ゞ, 嗯, 从结果来说好像连炮灰也没当成?

题目在这里, 简单来说就是车辆调度的问题, 官方给出car.txt, road.txt和cross.txt三个文件即车, 路和路口信息, 根据简化后的交通规则, 你的程序需要输出每辆车的上路时间以及行驶路线. 拿到题目首先就必须研究下这个设定的交通规则, 其中涉及到不少细节问题, 大体规则可以参考官方文档, 以下是一些当时有疑问的细节和官方解答.

规则细节

关于车辆在路上行驶的规则

车辆如果行驶过程中, 发现前方有车辆阻挡, 且阻挡的车辆为终止车辆, 则该辆车也被标记为终止车辆. （与前方阻挡的车辆的距离记为s）则该车辆最大行驶速度为v = min(最高车速, 道路限速, s/t) 其中t=1, 该车辆最大可行驶距离为s.

这里官方文档第二句话少了”否”字, 应为

否则该车辆最大行驶速度为v = min(最高车速, 道路限速, s/t) 其中t=1, 该车辆最大可行驶距离为s.

也就是说当有前车开得比较慢时, 该车也要降低速度. 而第一句是说如果前车停了, 则该车立即停止. 因此, 每辆车的速度每次轮到时都要根据前车情况重新计算. 另外如果前车是等待调度状态, 那么该车也是等待状态.

下面是官方给出的例子:

假定道路有如下车辆, 车AB车速为3, CD均为车速为1
A空空B空空CD （路口）

按步骤一后ABCD均为等待状态.

在处理待状态车辆D后, 假定D前进到其他道路后, 此刻道路状态变化为

A空空B空空C空 （路口）

接下来因D车辆的前进后, 需要对该条道路该车道的所有车辆进行一次调度

因此:

C的车速为1, 则C车前进1个距离, 且为终止状态. A空空B空空空C （路口）

B的车速为3, 则B车前进3个距离, 且为终止状态. A空空空空空BC （路口）

A的车速为3, 则A车前进3个距离, 且为终止状态. 空空空A空空BC （路口）

调度后道路车辆分布为: 空空空A空空BC （路口）, 且ABC均为终止状态

关于车辆在路口调度的规则

例子如下图:

在本路口调度道路的顺序为

5000、5001、5010、5018、5000、5001、5010、5018、5000、5001、5010、5018…5000、5001、5010、5018

整个系统调度按路口ID升序进行调度各个路口, 路口内各道路按道路ID升序进行调度.

也就是说, 路口调度顺序与各道路的调度顺序是固定的.

首先调度5000道路, 只有D100可以走, 因为D101左转与5010道路的D200冲突, 所以必须等待5010车道上没有直行冲突.

这里的D101官方又写错了, 应该是L101, 该车是当前5000道路优先级最高的车, 但与5010最高优先级直行的车D200冲突(都要到5018道路), 直行的优先级更高, 故对5000道路的调度先搁下了(当道路最高优先级的车停下, 其他车也不能动).

因此, 当对路口的一条道路调度时, 首先看这条道路优先级最高的车, 若不与其他道路最高优先级的车冲突, 则立即行驶, 然后看该道路第二优先级的车. 如果有冲突, 则调度下一条道路.

其次再调度5001道路, 因5001道路的L300与道路5018的D400冲突, 所以L300必须等待道路5018的D400先行后再调度行驶.

再次调度道路5010, D200、D201、D202不与其他道路的车辆冲突, 可以直接行驶. L203左转, 且道路5001无左转车辆与其冲突, 因此L203可以左转. L204也可以左转. L205为右转, 与左侧道路5000的车辆L101不冲突（只与道路5000的直行会发生冲突）, 且与道路5018的D400不发生冲突（只与道路5018的左转车辆发生冲突）, 因此车辆L205可以右转, 依次道路5010上的剩余车辆全部可以通过.

在道路通畅的条件下(驶入道路没有限制), 路口调度应该是这样的:

  • 当调度一辆车是直行的时候一定可以立即直行
  • 当调度一辆车左转时, 只需要看右边道路最高优先级的车是否直行
  • 当调度一辆车右转时, 需要看左边道路优先级最高的车是否直行以及对面车道优先级最高的车是否左转

在实际情况时还要考虑车驶入车道的情况, 比如驶入车道是拥堵的, 此时该车的调度也只能先搁下.

接着调度5018道路上的车辆…..

再调度道路5000….

再调度道路5001…

再调度道路5000….

是否发生冲突, 只与相关道路的第一优先级车辆的行驶方向进行比较, 看是否发生冲突.

每次调度到一条道路, 直到该道路无车辆可调度, 或该条道路上车辆处于冲突状态. 也就是说尽可能多地让该道路行驶, 直到没有车辆或者车辆与其他车辆发生冲突不可行驶.

关于车辆从路口进入道路

这里要注意的是发车顺序, 先是100->200->300, 然后101->201->301. 这里200比101更靠近路口, 尽管101在1号道, 200在2号道, 依然是200先行. 这一点在上面的路口冲突判断的图里也有体现, 当D101走后是判断L101, 而不是L103

关于死锁

基于10, 参赛选手需要注意, 一次调度能使所有车辆均到达各车辆的行驶速度行驶, 就得保证不能出现各车辆循环等待的情况, 否则该次调度就会锁死. 循环等待是指比如车辆A等待车辆B, 车辆B等待车辆C, 车辆C等待车辆D, 车辆D等待车辆E, 车辆E等待车辆F, 车辆F等待车辆A的情况.

Q&A

问: 如果一个路口的所有道路的车都冲突不动了, 怎么办? 是直接结束该路口的调度? 这样的话如果下一路口调度了导致上一路口可以再进行调度, 还需要对上一路口进行调度吗? 如果不进行调度那么路口的调度顺序对结果影响很大?

答: 是的, 会对上一路口再次进行调度(会进行下一次路口的调度循环), 只要有一个路口还需要调度, 就会再进行一次调度所有路口的循环

问: 每辆车都有出发时间的限定, 但是规则中出现实际出发时间的说法, 那么是程序可以调节车的实际出发时间吗? 还是只能是因为道路堵塞推迟出发时间?

答: 车辆的实际出发时间由参赛选手自行决定, 但是不得早于车辆的计划出发时间

问: 起步车辆放置于车道的位置确定问题?

答: 进入道路依然按车道小的优先策略进行

问: 那么起步车辆与路口调度时的车辆比, 优先级如何?

答: 系统调度先调度在路上行驶的车辆进行行驶, 当道路上所有车辆全部不可再行驶后再调度等待上路行驶的车辆

问: 多辆车同地点同时发车?

答: 交通规则有说明, 同一时刻多辆车上路行驶, 按车辆编号升序进行优先上路

其他:

整个系统限制参赛选手程序编译时间最大为60s, 程序运行生成answer.txt时间为300s.

车辆的长度为1(占一格), 行驶速度的含义是一个时间单位内前进的格数

思路

整个系统要调度的只有车, 更确切点说是车的两个值: 实际出发时间和车在每个路口选择的行驶方向, 除此之外都由规则定死了. 也就说只要确定了每辆车的这两个值, 那么最后的结果就是确定的, 不存在任何的随机性.

总的来说, 解决这个问题的想法大概有两个吧.

其一直接最优化, 系统根据输入和规则直接给出最优的调度方案. 因为本质上说这是一个最优化问题. 但我还是怀疑有没有这种解法, 题目设定的规则还是过于复杂, 于是没有做这方面的尝试, 而偏向于使用模拟或尝试性的解决办法.

退而求其次可以逐步最优, 系统首先对输入进行模拟, 在每个时间片上(只考虑当前时刻)进行最优调度, 但每个时间片上的最优策略就结果来说并不能保证是最优的. 不过即使简化到这样可能对我来说实现还是比较困难. 不怕, 大不了在逐步最优的基础上, 再进行简化嘛, 比如变成在每个时间片上对每辆车单独进行最优调度. 还不够, 因为这个系统中的车的行驶过程不是独立的, 可能会相互影响, 因此即使单独考虑每一辆车的最优可能也是困难的, 所以只能是尽可能地靠近最优调度.

综上, 目前考虑的方法是建立在模拟运行的基础上, 每一个时间片对每辆车单独地做出尽可能接近最优的调度. 这个方法可能比较好的一点是策略是动态的, 可以根据模拟运行时的情况对调度进行调整, 而这个调整(如何尽可能接近最优)也可以有发挥的余地.

以上讨论的都是车在路口的行驶方向的选择问题, 还有一部分是车实际出发时间的确定问题, 时间比较紧就没怎么考虑过. 总之现阶段考虑车能出发则出发, 不能出发则等到能出发为止. 当然一个理想的系统可能会故意延长车的实际出发时间(能出发不出发), 以达到系统更优.

要解决这个问题路径规划(Pathfinding)算法是必不可少的, 用于实际在每个路口确定行驶方向. 这方面优先考虑的是启发式路径搜索的A*, 在Amit’s A* Pages有比较详细的介绍和生动的例子, 同时也参考了部分将启发性路径搜索算法应用于实际导航路径规划的文献. 正当要动手开始写的时候发现了一个致命的问题—比赛给的地图不保证是物理可实现的. 启发式路径搜索不同于传统路径搜索的地方在于在计算路径cost的时候多了一个启发函数项(heuristic function), 因此路径搜索受启发函数影响优先往函数值小的方向搜索. 这类方法的主要问题在于如何选择这个启发函数, 选择的好坏最终将影响路径搜索的效率, 这也是为什么这个名字这么玄乎的原因. 通常采用欧式距离(平面坐标)和曼哈顿距离(网格坐标)作为启发函数, 这通常来说是合理的, 但都要求知道每个节点确切的坐标信息, 而赛题中只是知道节点与边的关系, 需要自己去构建一个位置关系, 由于是非实际可实现的道路, 先不说能不能构建或容不容易构建, 即使构建出来, 要设计一个符合的启发函数也不容易. というわけで, 最后还是采用了Dijkstra算法(摊手), 顺带稍稍优化了权重计算.

程序大体框架

  • car.hpp实现了Car与CarList两个类, 用于封装车辆信息
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
class Car
{
public:
	Car() {} // 为什么没有默认构造函数会报错
	Car(long id, long from, long to, int speed, long planTime):
		id(id), from_id(from), to_id(to), max_speed(speed), 
		plan_time(planTime), next_cross(from), isSetoff(false), isStoped(false) {}
	Car(long* carinfo)
	{
		if (carinfo)
		{
			id = carinfo[0];
			from_id = next_cross = carinfo[1];
			to_id = carinfo[2];
			max_speed = static_cast<int>(carinfo[3]);
			plan_time = carinfo[4];
			isSetoff = isStoped = false;
		}
	}

	void showRoute();

	friend ostream & operator<<(ostream &out, Car &car);

	long id; // 车的id
	long from_id; // 起始路口id
	long to_id; // 终点路口id
	
	int max_speed; // 最大车速
	int curr_speed; // 当前车速  这个变量到目前为止好像没起什么作用 可能到考虑实时路况时才能起参考

	// 车在一条路上的坐标 如一条长为4的路坐标为 1 2 3 4
	// 这个值在车进入道路时初始化 行进过程中更新
	int pos;

	bool isSetoff; // 是否已出发
	long plan_time; // 原计划出发时间
	long real_time; // 实际出发时间
	long dally_time; // 已延迟的时间

	list<long> route_plan; // 计划路线经过的路口id 不包括已经走过的路口 虽然答案里要求是行驶道路的id
	list<long> route_real; // 实际行驶经过路口id
	int next_turn; // 下一个路口转弯方向 0-上 1-右 2-下 3-
	long next_road; // 下一条行驶的道路id 行驶到路口更新
	long next_cross; // 下一个路口id
	int lane_num; // 所行驶的车道号 车在上路时更新

	bool isStoped; // 是否停车
	bool isScheduled; // 是否在当前时间片段经过调度


private:

};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class CarList
{
public:
	CarList() {}
	CarList(string carfile) { initCarList(carfile); }

	void initCarList(string carfile);
	Car& operator[](long i) { return carlist[i]; }
	void add(Car& car) { carlist[car.id] = car; } // unordered_map这里[]实现深复制
	void remove(long id) { carlist.erase(id); }
	const unordered_map<long, Car>& getList() { return carlist; }
	bool empty() { return carlist.empty(); }
	long size() { return carlist.size(); }

	unordered_map<long, Car>::iterator begin() { return carlist.begin(); }
	unordered_map<long, Car>::iterator end() { return carlist.end(); }

private:

	unordered_map<long, Car> carlist;
};
  • road.hpp实现了Road与RoadList两个类, 用于封装道路信息
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
class Road
{
public:
	Road() {}
	Road(long* roadinfo)
	{
		if (roadinfo)
		{
			id = roadinfo[0];
			length = static_cast<int>(roadinfo[1]);
			max_speed = static_cast<int>(roadinfo[2]);
			channel = static_cast<int>(roadinfo[3]);
			from_id = roadinfo[4];
			to_id = roadinfo[5];
			isDuplex = roadinfo[6] > 0 ? true : false;
			road_from_to.resize(channel);
			if (isDuplex)
				road_to_from.resize(channel);
		}
	}

	friend ostream & operator<<(ostream &out, Road &road);

	long id;
	int length; // 路长
	int max_speed; // 最大车速
	int channel; // 车道数
	long from_id; // 起始路口id
	long to_id; // 终点路口id
	bool isDuplex; // 是否双向
	
	bool isBlock; // 是否堵路

	vector<Lane>& getRoadCars(long to); // 返回一个方向的所有车道
	int getCarsNum(long crossid);
	bool isTo(long crossid) { return crossid == to_id || (crossid == from_id && isDuplex); }

private:
	vector<Lane> road_from_to; // 记录从from节点到to节点 各个channel行驶车的队列 存车的id
	vector<Lane> road_to_from; // 如果是单行线的话这个vector是空的
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class RoadList
{
public:
	RoadList() {}
	RoadList(string roadfile) { initRoadList(roadfile); }

	void initRoadList(string roadfile);
	Road & operator[](long i) { return roadlist[i]; }
	void add(Road& road) { roadlist[road.id] = road; }
	void remove(long id) { roadlist.erase(id); }
	const map<long, Road>& getList() { return roadlist; }

	map<long, Road>::iterator begin() { return roadlist.begin(); }
	map<long, Road>::iterator end() { return roadlist.end(); }

private:

	map<long, Road> roadlist;
};
  • cross.hpp实现了Cross与CrossList两个类, 用于封装路口信息
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
class Cross
{
public:
	Cross() {}
	//Cross(long id, long road0, long road1, long road2, long road3) : id(id)
	//{
	//	road_id[road0] = 0; road_id[road1] = 1;
	//	road_id[road2] = 2; road_id[road3] = 3;
	//}
	Cross(long* crossinfo)
	{
		if (crossinfo)
		{
			id = crossinfo[0];
			// 注意这里没路的 -1 也会放进去 把序号作为键 路id为值
			road_id[0] = crossinfo[1]; road_id[1] = crossinfo[2];
			road_id[2] = crossinfo[3]; road_id[3] = crossinfo[4];
		}
	}

	friend ostream & operator<<(ostream &out, Cross &cross);

	// 由路序号得到路id
	long getRoadIdx(int roadid)
	{
		for (auto& i : road_id)
			if (i.second == roadid)
				return i.first;
		return -1;
	}

	long id; // 路口id
	map<long, int> road_id; // 四个连接道路的id 没路的为-1 用map可以实现路id升序

	//int road_num; // 连接道路数目
	bool isBlock; // 是否堵塞
private:

};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class CrossList
{
public:
	CrossList() {}
	CrossList(string crossfile) { initCrossList(crossfile); }

	void initCrossList(string crossfile);
	Cross & operator[](long i) { return crosslist[i]; }
	void add(Cross& cross) { crosslist[cross.id] = cross; }
	void remove(long id) { crosslist.erase(id); }
	const map<long, Cross>& getList() { return crosslist; }

	map<long, Cross>::iterator begin() { return crosslist.begin(); }
	map<long, Cross>::iterator end() { return crosslist.end(); }

private:

	map<long, Cross> crosslist; // 由于之后cross要按id从小到大遍历 所以用有序map

};
  • RoadGraph.hpp实现RoadGraph类, 负责整合道路与路口构建图网络, 并且实现路径规划算法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class RoadGraph
{
public:
	RoadGraph() {}
	RoadGraph(CrossList& crosslist, RoadList& roadlist) { initGraph(crosslist, roadlist); }
	
	// 初始化路线图 neighborsOf 与 distBetween 便于之后搜索路径
	void initGraph(CrossList& crosslist, RoadList& roadlist);

	void findFastestRoute(CrossList& crosslist, RoadList& roadlist, Car& car);

	unordered_map<long, list<long> > neighborsOf; // 一个节点的相邻节点
	unordered_map<long, unordered_map<long, double> > distBetween; // 所有相邻节点的距离
	unordered_map<long, unordered_map<long, long> > roadBetween; // 所有相邻节点之间路的id

private:
	void dijkstra_search(CrossList& crosslist, RoadList& roadlist, Car& car); // dijkstra路径搜索方法

};
  • Scheduler.hpp实现了一个调度器
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
class Scheduler
{
public:
	Scheduler(string cartxt, string roadtxt, string crosstxt): time(0), isDone(false) 
	{
		initScheduler(cartxt, roadtxt, crosstxt);
	}

	long time; // 调度时间
	bool isDone; //是否调度完成
	void step(); // 走一个时间片段

	CarList carwaitgo; // 等待上路的车
	CarList carsetoff; // 在路上的车
	RoadList roadlist;
	CrossList crosslist;
	RoadGraph roadgraph;

private:
	void initScheduler(string cartxt, string roadtxt, string crosstxt);

	void scheduleCarwaitgo(); // 调度等待上路的车

	void scheduleInit(); // 每次调度前准备
	void scheduleRoad(); // 调度每一条道路
	void scheduleLane(Road& road, Lane& lane); // 调度路一个方向上的所有车道
	bool scheduleCross(); // 调度所有路口
	bool scheduleCrossRoad(Cross& cross);

	void enterRoad(Car& car, Lane& lane, int lane_num, int speed); // 车进入道路
	void leaveRoad(Car& car, Lane& lane); // 车离开道路
	long getfirstCar(Road& road, Cross& to); // 返回一个方向的车道中最先调度的车
	bool tryEnterRoad(Cross& cross, Road& road, Car& car);

	void answer(Car& car);
	void showstatus();

	bool flag1; // 记录遍历 所有cross 的一个循环中 是否发生了调度 如果调度再进行一次这个循环
	bool flag2; // 记录遍历 一个cross所有路 的循环中 是否发生了调度
	bool flag3; // 记录遍历一个cross所有路的循环中 是否发生了调度 如果调度再进行一次这个循环 直到没有调度

	long carnum = 0;
	long donenum = 0;
	long carwaitgonum = 0;
	long carsetoffnum = 0;

};
  • main
1
2
3
4
5
6
7
8
9
int main()
{
	Scheduler scheduler("car.txt", "road.txt", "cross.txt");

	while (!scheduler.isDone)
		scheduler.step();

	return 0;
}

最后

  • 由于没有成功在赛方的服务器上跑过, 所以到底效果如何有没有其他问题都尚不明确, 虽然线下测试结果勉强还行, 也没碰到死锁的情况. 当然为了鲁棒性加个死锁判定还是有必要的.
  • 由于比赛期间一直有其他事, 所以前后参赛了不到5天的时间. 后来看获奖者感言, 原来大家都一样, 都是在搬砖期间抽空做的, 白天搬砖, 晚上调程序…
  • 全程玩得还是挺开心的, 嗯, 希望下次能做一个合格的炮灰(认真脸).

.

.

.

.

.

.

終わり