在一个有多条分支的多叉路口,有些方向是双向通行,有些方向是单向通行,每个方向的通行时间根据不同时间段自动调节,请设计一个交通信号控制系统。(C和E是单行道)。该控制系统可以根据不同路口情况,配置合适的交通信号灯颜色及控制通行时间。
实现功能
在一个有多条分支的多叉路口,A、B、D是双向通行,C、E是单向通行,每个方向的通行时间根据不同时间段自动调节。请设计一个交通信号控制系统。该控制系统可以根据不同路口情况,配置合适的交通信号灯颜色及控制通行时间。
思路分解
道路遵循右行规则
找到可以行驶的路线(考虑C、E的单向因素)
AB、AC、AD
BA、BC、BD
DA、DB、DC
EA、EB、EC、ED
思路分解
基于以上判断出的可以行驶的路线,根据车辆必须右行和同一通行时间段内路线之间不能交叉的原则判断哪些路线不能同时行驶。结果包括以下:
(AB BC) (AB BD)
(AB DA) (AB EA)
(AC DA) (AC BD)
(AC DB) (AC EA) (AC EB)
(AD EA) (AD EB) (AD EC)
(BC EB) (BC DB)
(BD DA) (BD EB) (BD EC)
(DA EB) (DA EC)
(DB EC)
思路分解
把可以同时行驶且不发生碰撞的路线用同一种颜色的交通灯指示
该控制系统需要用多少种颜色的交通灯分配给这些行驶路线?
交通灯颜色越少表示该控制系统的管理效率越高
解决方案
借助于“图”。图中一个顶点表示一条行驶路线,行驶路线相互矛盾用顶点之间的连线(即“边”)来表示。
交通灯控制问题就变等价为:对图的顶点的染色问题,要求对图上的每个顶点染上一种颜色,且有边相连的两个顶点不能染相同的颜色,且总的颜色种类尽可能的少。
或者,如果把图上的一个顶点理解为一个国家,顶点之间的连线表示两个国家有共同的边界,相邻的国家不能涂相同的颜色,则以上交通灯控制问题又能转化为著名的地图着色问题。
解决方案
考虑使用贪心算法
算法主要思想
1. 用一种颜色给尽可能多的顶点着色
(1) 选择某未着色的顶点并用该新颜色上色
(2) 扫描未着色的其他所有顶点,逐个考察它们是否有边与已用该颜色着色的顶点相连,若没有边相连就用该颜色上色。
2. 换一种颜色重复步骤1,直到所有顶点全部着色为止
其中一种可能染色结果,圆圈中的数字标识该路径所选用的交通灯颜色,即:蓝色为1,红色为2,绿色为3,黄色为4。该算法还可能得到其他的次优解。
实现要求
选用适当的数据结构存储上面的图的信息
程序运行后的输出内容,请参考以下格式(以上图为例):
颜色1的信号灯亮时,以下方向通行:
AàB BàA AàC AàD DàC EàD
颜色2的信号灯亮时,以下方向通行:
BàC BàD EàA
颜色3的信号灯亮时,以下方向通行:
DàA DàB
颜色4的信号灯亮时,以下方向通行:
EàB EàC
实验步骤
- 建立数据的结构;
- 设计子函数;
- 利用main函数调用各子函数;
- 准备测试数据;
- 调试程序,分析运行结果。
1