首页 > 代码库 > 海康威视复赛题

海康威视复赛题

题目概述

在车库中安排若干泊车机器人,根据给定的车位地图,合理优化机器人的数量及其运动路径,尽量减少客户在停车和取车中的等待时间,并使总成本最小。

参数设定

为了简化问题,我们对泊车机器人的实际运行情况做出如下规定和说明,与“题目背景”中所述的泊车机器人真实运行情况有所不同,请注意。

地图说明:

给定一个停车地图,以下图为例:地图中红色部分表示车位(P),黑色部分表示障碍物(B),黄色部分表示入口(I),绿色部分表示出口(E),白色表示行车道路(X),每个车位都与行车道路(X)相邻,每个车位(P)只能停一辆车。

1.泊车机器人必须能到达每个车位;

2.每个车位有且只有一个入口, 即每个红色区域旁边有且只有一个白色区域;

3.出口和入口各只有一个,且不重合,分布在地图边缘,泊车机器人从入口和出口都能到达每个车位。

技术分享

 

泊车机器人说明:

1.泊车机器人(R)运行速度为每秒一个格,且只能向前、后、左、右移动,不能沿对角线移动。

2.泊车机器人不论在载车还是空车状态,都不能穿过图例中黑色区域(B);且只能由白色区域(X)进入到红色区域(P),或相反;不能在红色区域(P)之间移动。比如,上图图例中左上角, 允许3->1和1->3,但不允许1->2。

3.泊车机器人在空闲的时候,可以行驶到任何位置(除了B区域)。

4.泊车机器人不论是空车还是载车状态都不能同时出现在一个格子中(入口和出口处不受限制),即不能相遇,不能相撞,存在碰撞体积。

5.假设泊车机器人空载时耗能极少可忽略不计,载车时能耗(W)与车的质量(m)以及行驶里程(S)相关,W=k*m*S,k为能耗系数。

 

车辆说明:

1.每辆车(C)都有申请进入时间(T-in)、申请离开时间(T-out)、实际进入时间(T-in')、实际离开时间(T-out')、最长等待时间(t)、车的质量(m,m≤2000)。

2.申请进入时间(T-in)表示车辆到达时间,实际进入时间(T-in')为泊车机器人从入口处把车辆接走的时间点;申请离开时间(T-out)表示客户取车的时间点,实际离开时间(T-out')表示泊车机器人把车辆搬到出口的时间点;若(T-in')>(T-in)+(t),则客户放弃停车。

3.每辆车的等待时间(T1)=(T-in')-(T-in)+(T-out')-(T-out);若发生客户放弃停车的情况,需要对每辆被放弃的车辆增加罚时(p),总罚时(T2)=罚时系数(p)*放弃停车车辆数(q)。(注:放弃停车的车辆的等待时间,不计算到T1,该车不会停到车库里面,因此也不用规划路径,只需要计入T2即可)

 

题目说明

现有一批车辆需要停到车库中,请设计一个合理的停车方案,使Z最小。 Z =a*n+T+W。

n为泊车机器人个数,a为系数;T=bT1+T2, b为系数;W为总能耗。具体公式为 Z = n*a + b*∑T1 + p*q + k*∑m*s

 

输入

1.从标准输入 输入的数据以空格分隔,每行以换行符(‘\n’)结尾。

2.格式:

能耗系数k 罚时系数p 泊车机器人系数a 客户停车等待系数b

停车库宽w 停车库高h

接下来是一个w*h的二维数组, 数组中P表示车位,B表示障碍物,I表示入口,E表示出口,X表示过道

车辆数目N

1 申请入库时间点 申请出库时间点 最大等待时间 车的质量

2

3

.

.

N 申请入库时间点 申请出库时间点 最大等待时间 车的质量

说明:

a.所有输入都是不小于0的整数,且不大于100000,地图宽高都不大于100,车辆数N不大于5000

b.为了方便计算,时间点都是归一化时间,即从0开始,依次增加

c.机器人行驶里程说明,例如示例图中车辆从入口4到停车位6,它的行驶路程为4->5->6,那么它的里程数为2

 

输入示例:

1 800 400 5 //能耗系数k:1, 罚时系数p:800, 泊车机器人系数a:400,等待系数b:5

6 6 // 地图宽高都为6

X X X X X X

X B P P P P

X X B B B B

X X X X X E

X X X X X X

I B P P B B

4 // 车辆数为4

1 0 42 20 10 // 车辆编号为1,申请进入时间点为0,申请离开时间点42,最大等地时间20,质量为10,即车辆如果在0+20这个时间点还没有被接走,就表示该车放弃泊车。

2 3 45 15 15

3 10 64 10 11

4 25 60 20 12

输出

1.标准输出,输出的数据以空格分隔,每行以换行符(‘\n’)结尾。

2.输出格式:

首先判断给的用例地图是否有效(判断依据见地图说明),

如果地图无效则:NO

文件结束

如果地图有效:YES

泊车机器人个数n 所有车的等待时间T(b*T1+T2) 所有泊车机器人的总能耗W处理完当前case所用的经历时间M(指最后一辆车离开车库的时间,相当于这个时间点后,没有车入库了,程序运行结束)

接下来M +1行,

0 (机器人编号0,当前位置X, 当前位置Y, 车辆编号(空载时为0)) 。。。(机器人编号n-1,当前位置X, 当前位置Y, 车辆编号(空载时为0))

1 (机器人编号0,当前位置X, 当前位置Y, 车辆编号(空载时为0)) 。。。(机器人编号n-1,当前位置X, 当前位置Y, 车辆编号(空载时为0))

.

M (机器人编号0,当前位置X, 当前位置Y, 车辆编号(空载时为0)) 。。。(机器人编号n-1,当前位置X, 当前位置Y, 车辆编号(空载时为0))

如果机器人个数为0,那么M为0,输出结束。如下:

YES

0 3200 0 0

输出示例:

YES

2 175 714 79

0 (0,5,0,1) (1,5,0,0)

1 (0,4,0,1) (1,5,0,0)

2 (0,4,1,1) (1,5,0,0)

3 (0,4,2,1) (1,5,0,2)

4 (0,5,2,1) (1,4,0,2)

5 (0,4,2,0) (1,3,0,2)

6 (0,4,1,0) (1,2,0,2)

7 (0,4,0,0) (1,1,0,2)

8 (0,5,0,0) (1,0,0,2)

9 (0,5,0,0) (1,0,1,2)

10 (0,5,0,3) (1,0,2,2)

11 (0,4,0,3) (1,1,2,2)

12 (0,3,0,3) (1,1,2,0)

13 (0,2,0,3) (1,1,2,0)

14 (0,1,0,3) (1,1,2,0)

15 (0,0,0,3) (1,1,2,0)

16 (0,0,1,3) (1,1,2,0)

17 (0,0,2,3) (1,1,2,0)

18 (0,0,3,3) (1,0,2,0)

19 (0,1,3,3) (1,0,1,0)

20 (0,0,3,0) (1,0,0,0)

21 (0,0,2,0) (1,1,0,0)

22 (0,1,2,0) (1,2,0,0)

23 (0,1,2,0) (1,3,0,0)

24 (0,1,2,0) (1,4,0,0)

25 (0,1,2,0) (1,5,0,4)

26 (0,1,2,0) (1,4,0,4)

27 (0,1,2,0) (1,4,1,4)

28 (0,1,2,0) (1,4,2,4)

29 (0,1,2,0) (1,4,3,4)

30 (0,1,2,0) (1,5,3,4)

31 (0,1,2,0) (1,4,3,0)

32 (0,1,2,0) (1,4,2,0)

33 (0,1,2,0) (1,5,2,0)

34 (0,1,2,0) (1,5,2,0)

35 (0,1,2,0) (1,5,2,0)

36 (0,1,2,0) (1,5,2,0)

37 (0,1,2,0) (1,5,2,0)

38 (0,1,2,0) (1,5,2,0)

39 (0,1,2,0) (1,5,2,0)

40 (0,1,2,0) (1,5,2,0)

41 (0,1,2,0) (1,5,2,0)

42 (0,1,2,0) (1,5,2,1)

43 (0,1,2,0) (1,4,2,1)

44 (0,1,2,0) (1,4,3,1)

45 (0,1,2,2) (1,4,4,1)

46 (0,0,2,2) (1,4,5,1)

47 (0,0,1,2) (1,3,5,1)

48 (0,0,0,2) (1,3,4,0)

49 (0,1,0,2) (1,3,3,0)

50 (0,2,0,2) (1,3,2,0)

51 (0,2,1,2) (1,3,1,0)

52 (0,3,1,2) (1,3,0,0)

53 (0,3,2,2) (1,2,0,0)

54 (0,3,3,2) (1,1,0,0)

55 (0,3,4,2) (1,0,0,0)

56 (0,3,5,2) (1,0,1,0)

57 (0,4,5,0) (1,0,2,0)

58 (0,4,4,0) (1,0,3,0)

59 (0,4,3,0) (1,1,3,0)

60 (0,5,3,4) (1,1,3,0)

61 (0,4,3,4) (1,1,3,0)

62 (0,4,4,4) (1,1,3,0)

63 (0,4,5,4) (1,1,3,0)

64 (0,3,5,4) (1,1,3,0)

65 (0,3,5,0) (1,1,3,0)

66 (0,3,5,0) (1,1,3,0)

67 (0,3,5,0) (1,1,3,3)

68 (0,3,5,0) (1,0,3,3)

69 (0,3,5,0) (1,0,2,3)

70 (0,3,5,0) (1,0,1,3)

71 (0,3,5,0) (1,0,0,3)

72 (0,3,5,0) (1,1,0,3)

73 (0,3,5,0) (1,2,0,3)

74 (0,3,5,0) (1,2,1,3)

75 (0,3,5,0) (1,3,1,3)

76 (0,3,5,0) (1,3,2,3)

77 (0,3,5,0) (1,3,3,3)

78 (0,3,5,0) (1,3,4,3)

79 (0,3,5,0) (1,3,5,3)

补充说明

1.泊车机器人初始位置都在入口I处。

2.泊车机器人在没有收到申请出库之前不能在车位上搬运汽车。即车一旦到达车位后,只有收到离开命令后才能搬运。

3.同时申请入库(出库)的车辆顺序由机器人决定,不同时间的先申请先处理。申请入库和出库之间没有时间关系(例:A先申请入库,B后申请出库,机器人可以先执行B,再执行A)。补充:评判程序对于出库的先后顺序不做判断。

4.车位有空的情况下,泊车机器人空闲时且入口有车辆等待入库,不能拒载。补充:评判程序对于拒载不做判断,根据自己需要可以选择合适的车辆。

5.编程所使用的语言为C,C++,JAVA;不能使用第三方开源库,也不能使用操作系统的特效函数。

6.如果总共12个case,所有的case机器人数目为1,或者0的答案视为无效。只要有一个大于1就有效。case的机器人价格可能会很低

7.特别说明,注意代码规范,代码注释。进入总决赛者需要必要的文档,PPT,流程图等说明,

8.由于行驶过程中可以等待,因此用例无法保证每辆车都能入库,即有可能出现还没到车位就收到出库命令,这个时候,可以直接搬运到出口。但是到车位后,必须收到出库命令才能搬运,这点与补充说明2保持一样

9.运行环境

硬件环境:至强E5 2650 V4 8核心;

最大内存:2G;

运行时间:100S以内

GCC版本:4.8.2

JAVA版本:JDK 1.7.0_80

示例展示

技术分享

K=1, p=80,a=400,b=5

技术分享

一种策略如下:

技术分享

技术分享

对于该策略,用了一辆泊车机器人,时间T = 120+90+110 =400, 能耗W =200+120+96=416。这个策略得到的Z不一定是最小的,因此现在需要参赛者提供的程序能够针对不同的比赛用例,给出Z最小即可,即不存在标准答案,参赛者给出自认为可行的方案即可。

海康威视复赛题