多路口交通灯问题
1.问题背景
如下图，有A,B,C,D,E五个路口，其中A,D路口为单行道，方向均指向道中。现考虑修交通灯，其功能如下：
-
交通灯上有若干颜色不同的灯
-
同一时刻有且只有一种颜色的灯亮
-
每个路口都会安装一个交通灯，用于指示交通。在相同的路口，不同灯亮代表不同的通行情况。
现需要设计交通灯，使得在正常指示交通的前提下，交通灯上颜色数量尽量少。
注意：
- 按实际交通状况，一条道路上右侧为正行，左侧为逆行。
- 路口右转不会与其他通行情况产生较大冲突（正常情况），因此右转不必设灯。
2.问题分析
交通问题，先从十字路口考虑。
十字路口，每个路口的交通灯上都有3种颜色的交通灯，其中黄灯只做提醒或观察作用，因此真正决定交通状态的是红灯与绿灯。绿灯亮则通行，红灯亮则停止。但相同的道路，其灯展示情况也可不同，例如：
设A,B路口直通，C,D路口直通，其形成了一个十字路口。则道路通行情况可以为
-
A\(\rightarrow\)B，B\(\rightarrow\)A为初始通行情况，随后A,B各自停止直行，共同左转。再停止左转，转为C\(\rightarrow\)D，D\(\rightarrow\)C，然后类似继续下去。
-
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.总结
该问题带来了一个不同的问题思考方式，即生活中常见的是十字路口、丁字路口等，但五个通道的路口也是可能存在的。这样如何最优化设计交通灯实际上是一个问题。在建模后，这个问题就与图论中的一个基本问题重合了。然后通过经典算法，就可以初步得出结论。但是正如上文所说，还应切换度数相同的节点再次实验，在所有备选中选出最符合道路实情的一种交通通行设计方式。
总而言之，将实际生活与算法相结合，借助计算机的强大算力，可以更方便的处理一些事情。代码当然很经典也很简单了，算是刚回归的一个小练手吧。