多路口交通灯问题

1.问题背景

如下图,有A,B,C,D,E五个路口,其中A,D路口为单行道,方向均指向道中。现考虑修交通灯,其功能如下:

  • 交通灯上有若干颜色不同的灯

  • 同一时刻有且只有一种颜色的灯亮

  • 每个路口都会安装一个交通灯,用于指示交通。在相同的路口,不同灯亮代表不同的通行情况。

现需要设计交通灯,使得在正常指示交通的前提下,交通灯上颜色数量尽量少。

注意:

  • 按实际交通状况,一条道路上右侧为正行,左侧为逆行。
  • 路口右转不会与其他通行情况产生较大冲突(正常情况),因此右转不必设灯。

2.问题分析

交通问题,先从十字路口考虑。

十字路口,每个路口的交通灯上都有3种颜色的交通灯,其中黄灯只做提醒或观察作用,因此真正决定交通状态的是红灯与绿灯。绿灯亮则通行,红灯亮则停止。但相同的道路,其灯展示情况也可不同,例如:

设A,B路口直通,C,D路口直通,其形成了一个十字路口。则道路通行情况可以为

  1. A\(\rightarrow\)B,B\(\rightarrow\)A为初始通行情况,随后A,B各自停止直行,共同左转。再停止左转,转为C\(\rightarrow\)D,D\(\rightarrow\)C,然后类似继续下去。

  2. A\(\rightarrow\)B,B\(\rightarrow\)A为初始通行情况,随后B道路停止通行,A左转、直行共同进行。再A停止直行,B启动左转,其余与1类似。

可以发现,以上情况所需最少灯颜色数为2,即只需红灯与绿灯即可实现上述交通情况,但是情况不唯一。

可以预料到的一点是,随着路口数的增加,情况必然更加多样与复杂,即使想设计从任意道路进,再存在顺序时刻(即特定亮灯时刻)使得可以从任意非单行道(这里指进入道路中心的单行道,即从其他道路无法进入)出,则更加不容易。当然,随着交通指示灯数量的增加,必然更容易实现上述,但是也会造成更多的时间冗杂,极有可能导致交通拥挤,这也不是我们需要的。

实际上多于4条交通道路的复杂交通,更适合设计成环岛。本题是跳出常见交通情况,探索一般交通状况。

回归本题,右转由于不会与其余交通情况冲突,因此不作考虑,故需要考虑的则为道路冲突情况。下图给出了两种冲突情况

并且,该交通上可能存在许多冲突情况,关于具体的冲突情况,可以采用枚举的方式,固定一条道路,枚举其余道路,再判断是否冲突。就本题而言较为容易,但一旦道路情况复杂,则需要根据实际要求(例如进单行,出单行)进行合适的约束。

假设我们已经得到了交通道路冲突情况,接下来就可以进行建模了。本质上,这是一道图论的基本问题。

3.建立数学模型

最初的想法是把道路尽头视作点,这样中心路口的转向即可看作边。但是交通灯处理的问题本质上是使道路正常通行,不会发生冲突。正如上述所说,应该以从某路口转向某路口视作基本操作对象,即点。而点与点相连可以视作道路冲突,那么就是说当一方某色灯亮起时,另一方的某色灯一定不能亮。无妨设这两种灯颜色一样(实际上不一样也不影响本质区别,只是某路口交通灯内部顺序交换。当然不同颜色交通灯通向哪个路口应在交通告示牌上有所体现),则这就变成了图论中最基本的问题——图最小染色问题。

图最小染色问题是指,一个图中同一边的两点颜色不同,问最少需要多少种颜色数可以将所有点染色。这个基本问题对应了一个经典算法:Welsh–Powell 算法。该算法是说,有一种贪心的方式可以尽量优的求出较小颜色数,根据OI Wiki上的说法,是在不限制最大颜色数的前提下,该算法成立。可以证明的是,该贪心算法是正确的,并且时间复杂度为\(O(n^2)\)

Welsh–Powell 算法的过程是,对点按度数从高到低排序,然后从度数最高的点开始,依次染色。一个要求是:每次循环对应染上一种颜色,且保证同色不相连。这样所染出的颜色数就是较小的着色数。先说时间复杂度,按颜色可以将点分组,每组内部需要判断是否与其他点相连,对于第k组颜色内的点集即为\(O(n^2_k)\)的时间复杂度,但是在同一个颜色中枚举点时额外产生的时间复杂度为\(O(n)\)。由于\(\sum n_k=n\),并且枚举点最多n次,所以总复杂度为 \(\sum O(n^2_k)+O(n^2)\) ,即\(O(n^2)\)级。而直接枚举考虑颜色数则是np问题,时间复杂度非多项式级。故可见Welsh-Powell算法极大的方便了对图最小染色数的计算,对解决生活中实际问题也很有帮助。但是值得注意的一点是,该算法得到的颜色数可能并非最优解,这与起始节点和图形性质皆有关系。但在图形较简单及节点度数不高的情况下,该算法性能优良。并且可以保证最大颜色数不会超过最大节点度数加一。具体证明参见 \(OI\) \(Wiki\),大体思路是按照算法思路将每种颜色所染的节点归为一类,再根据数学归纳法递推得到类的性质。

这样就解决了这个问题,下面是代码及运行结果。

4.实际运行

代码:

#include<cstdio>
#include<algorithm>
using namespace std;
struct node
{
	int num;
	int dis;
};
node t[100];
int edge[100][100],colorn=0,n;
int col[100],cnt,pre[100],rt;
bool cmp1(node p,node q) { return p.dis>q.dis; }
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		t[i].num=i;
		for(int j=1;j<=n;j++)
		{
			int v;
			scanf("%d",&v);
			if(v)
			{
				edge[i][j]=v;
				t[i].dis++;
				t[j].dis++;	
			}
		}
	}
	sort(t+1,t+n+1,cmp1);
	while(colorn<n)
	{
		rt=1;
		for(int i=1;i<=n;i++)
		{
			if(!col[t[i].num])
			{
				col[t[i].num]=++cnt;
				pre[rt]=i;
				colorn++;
				break;
			}
		}
		for(int i=1;i<=n;i++)
		{
			if(col[t[i].num]) continue;
			int flag=0;
			for(int j=1;j<=rt;j++)
			{
				if(edge[t[pre[j]].num][t[i].num]) 
				{
					flag=1;
					break;
				}
			}
			if(!flag) 
			{
				col[t[i].num]=cnt;
				colorn++;
				pre[++rt]=i;
			}
		}
	}
	printf("min-color-number:%d\n",cnt);
	for(int i=1;i<=n;i++) printf("num%d's color is %d\n",i,col[i]);
	return 0;
}

下面是运行结果:

min-color-number:3
num1's color is 2
num2's color is 1
num3's color is 1
num4's color is 3
num5's color is 2
num6's color is 1
num7's color is 3
num8's color is 3
num9's color is 2

当然,这只是理论上最小颜色数。比如B-E段实际只需两个交通灯。但以次观之,十字路口交通灯只需两色:分别管理直行和左转,但这样显然是不好的。故设计为绿灯通行红灯停止。上述也可如此,对于不同通行方向,皆用绿灯但用不同指向表示,这样在加上红灯限定停止的同时可以更方便车辆通行。以上问题实际上与此方式相同。

5.总结

该问题带来了一个不同的问题思考方式,即生活中常见的是十字路口、丁字路口等,但五个通道的路口也是可能存在的。这样如何最优化设计交通灯实际上是一个问题。在建模后,这个问题就与图论中的一个基本问题重合了。然后通过经典算法,就可以初步得出结论。但是正如上文所说,还应切换度数相同的节点再次实验,在所有备选中选出最符合道路实情的一种交通通行设计方式。

总而言之,将实际生活与算法相结合,借助计算机的强大算力,可以更方便的处理一些事情。代码当然很经典也很简单了,算是刚回归的一个小练手吧。