《数据结构与算法：Python语言描述》一1.2　问题求解：交叉路口的红绿灯安排...

本节书摘来自华章出版社《数据结构与算法：Python语言描述》一书中的第1章，第1.2节，作者 裘宗燕，更多章节内容可以访问云栖社区“华章计算机”公众号查看

1.2　问题求解：交叉路口的红绿灯安排

本节展示一个具体问题的计算机求解过程，以此说明在这种过程中可能出现的一些情况，需要考虑的一些问题，以及一些可能的处理方法。
交叉路口是现代城市路网中最重要的组成部分，繁忙的交叉路口需要用红绿灯指挥车辆通行与等待，正确的红绿灯调度安排对于保证交通安全、道路运行秩序和效率都非常重要。交叉路口的情况多种多样，常见形式有三岔路口、十字路口，也有较为少见的更复杂形式的路口。进一步说，有些道路是单行线，在中国的交叉路口还有人车分流和专门的人行/自行车红绿灯等许多情况，这些都进一步增加了路口交通控制的复杂性。要开发一个程序生成交通路口的红绿灯安排和切换，需要考虑许多复杂情况。
现在计划考虑的问题很简单，只考虑红绿灯（实际上是相应允许行驶路线）如何安排，可以保证相应的允许行驶路线互不交错，从而保证路口的交通安全。
为把问题看得更清楚，先考虑一个具体实例，希望从中发现解决问题的线索。作为实例的交叉路口如图1.2所示：这是一个五条路的交叉口，其中两条路是单行线（图中用箭头标出），其余是正常的双向行驶道路。实际上，这个图形本身已经是原问题实例的一个抽象，与行驶方向无关的因素都已被抽象去除，例如道路的方位、不同道路交叉的角度、各条道路的实际宽度和通常的车流量等。
根据图形中表示的情况不难看到，从路口各驶入方向来的车辆，都可能向多个方向驶出，各种行驶方向的轨迹相互交错，形成很复杂的局面。按不同方向行驶的车辆可能相互冲突，存在着很实际的安全问题，因此，红绿灯的设计必须慎重！

现在的基本想法是对行驶方向分组，使得：
同属一组的各个方向行驶的车辆，均可以同时行驶，不出现相互交错的行驶路线，因此保证了安全和路线畅通。
所做的分组应该尽可能大些，以提高路口的效率（经济问题）。
第一条是基本的安全问题，丝毫不能妥协。而第二条只是经济问题，这个要求具有相对性。不难看出，允许同时行驶的方向越少，就越能保证安全。例如，每次只放行一个行驶方向，肯定能保证安全，但道路通行效率太低，因此完全不可取。另外还可以看到，这不是一个一目了然的问题，需要深入分析，才能找到较好的统一解决方法。

1.2.1问题分析和严格化

图形的表达方式一目了然，特别有助于人们把握问题的全局。但是，如图1.2这样的图形并不适合表达问题细节和分析结果。如果把所有允许行驶方向画在图中，看到的将是来来去去、相互交错的许多有向线段，不容易看清其相互关系。
为了理清情况，应该先罗列出路口的所有可能行驶方向，例如从道路A驶向道路B，从道路A驶向道路C。为简便易读，用AB、AC表示这两个行驶方向，其他方向都采用类似的表示方式。不难列出路口总共有13个可行方向：AB, AC, AD, BA, BC, BD, DA, DB, DC, EA, EB, EC, ED。
采用这种抽象表示，问题的实质看得更清楚了。有了（给定了）一集不同的行驶方向，需要从中确定一些可以同时开绿灯的方向组。也就是说，需要为所有可能方向做出一种安全分组，保证位于每组里的行驶方向相互不冲突，可以同时放行。
这里的“冲突”又是一个需要进一步明确的概念。显然，两个行驶路线交叉是最明显的冲突情况。如果对这样两个方向同时开绿灯，按绿灯行驶的车辆就有在路口撞车的危险，这是不能允许的。因此，这样的两个方向不能放入同一个分组。
为了弄清安全分组，需要设想一种表示冲突的方式，更清晰地描述冲突的情况。如果把所有行驶方向画在一张纸上，在相互冲突的方向之间画一条连线，就做出了一个冲突图。图1.3就是上面实例的冲突图，其中的13个小矩形表示所有的可能行驶方向，两个矩形之间有连线表示它们代表的行驶路线相互冲突。注意，在这个图形中，各个矩形的位置、大小等都不代表任何信息，只有矩形中的符号和矩形之间的连线有意义。这样的图形构成了一种数据结构，也称为图，图中元素称为顶点，连线称为边或者弧。相互之间有边的顶点称为邻接顶点。第7章将会详细讨论这种结构。
有了冲突图，寻找安全分组的问题就可以换一种说法：为冲突图中的顶点确定一种分组，保证属于同一组的所有顶点互不邻接。显然，可能的分组方法很多。如前所述，将每个顶点作为一个组一定满足要求。但从原问题看，这里期待一种比较少的分组或者最少的分组。回到原问题，就是希望在一个周期中的红绿灯转换最少。

1.2.2图的顶点分组和算法

经过一步步抽象和严格化，要解决的问题从交叉路口的红绿灯安排变成了一类抽象的图数据结构上的顶点分组。假设有了这样一个图结构，现在需要考虑一个算法，其计算的结果给出一个满足需要的分组。对这个问题，安全性是第一位的基本要求，必须满足；而分组最少是进一步的附加要求，是一种追求。
以非相邻为条件的最佳顶点分组问题，实际上对应于有名的图最佳着色问题：把顶点看作区域，把相邻看作两个区域有边界，把不同分组看作给相邻顶点以不同颜色着色。著名的四色问题表明，对于以任一方式分割为区域的平面图，只需要用4种不同颜色着色，就能保证相邻区域都具有不同的颜色。但请注意，从交叉路口情况构造出的冲突图可能不是平面图，因此完全可能需要更多的颜色。
人们对图着色的算法做过一些研究，目前的情况是：已经找到的最佳着色算法（得到最佳分组），基本上相当于枚举出所有可能的着色方案，从中选出使用颜色最少的方案。例如，一种直截了当的方法是首先基于图中顶点枚举出所有可能分组，从中筛选出满足基本要求的分组（各组中的顶点互不相邻），再从中选出分组数最小的分组。由于计算中需要考虑各种可能组合，这种组合数显然是顶点个数的指数函数，这个算法的代价太高了。能得到最佳分组的其他算法可能更复杂，但在效率上没有本质性提高。
下面考虑一种简单算法，它被称为是一种贪婪算法，或称贪心法。贪心法也是一种典型的算法设计思路（或称算法设计模式），其中的基本想法就是根据当时掌握的信息，尽可能地向得到解的方向前进，直到不能继续再换一个方向。这样做通常不能找到最优解，但能找到“可接受的”解，即给出一种较好的分组。
算法的梗概（伪代码）如下：
输入：图G # 记录图中的顶点连接关系
集合verts保存G中所有顶点 # 建立初始状态
设置集合groups为空集 # 记录得到的分组，元素是顶点集合
while存在未着色顶点: # 每次迭代用贪心法找一个新分组
　　选一种新颜色
　　在未着色顶点中给尽量多的无互连边的点着色（构建一个分组）
　　记录新着色的顶点组
算法结束时集合groups里记录着一种分组方式
算法细节还需要进一步考虑
现在考虑用这个算法处理图1.3中的冲突图，假定操作按照前面列出的13个方向的顺序进行处理。操作中的情况如下：
1.选第1种颜色构造第1个分组：顺序选出相互不冲突的AB、AC、AD，以及与任何方向都不冲突的BA、DC和ED，做成一组；
2.选出BC、BD和与它们不冲突的EA作为第二组；
3.选出DA和DB作为第三组；
4.剩下的EA和EB作为第四组。
由于上面算法中这几个分组内互不冲突，而且每个行驶方向属于一个分组，因此是满足问题要求的一个解。得到的分组如下：
{AB, AC, AD, BA, DC, ED}, {BC, BD, EA}, {DA, DB}, {EA, EB}
上面算法还有重要的细节缺失：一种新颜色的着色处理。现在考虑这个问题。
假设图G保存需着色图中顶点的邻接信息，集合verts是图中所有尚未着色的顶点的集合。显然，算法开始时verts应该是G中所有顶点的集合。用另一个变量new_group记录正在构造的用当前新颜色着色的顶点（一个集合），在上面算法的每次迭代中重新构造，每次开始做分组时将这个集合重新设置为空集。
在上面安排的基础上，找出verts中可用新颜色着色的顶点集的算法是：

new_group = 空集
for v in verts:
if v与new_group中所有顶点之间都没有边:
从verts中去掉v
把v加入new_group
# 循环结束时new_group是可以用一种新颜色着色的顶点集合
# 用这段代替前面程序框架中主循环体里的一部分

这样就有了一个完整的算法。
检查上面算法，可以看到算法中假设了一些集合操作和一些图操作。集合操作包括判断一个集合是否为空集，构造一个空集，从一个集合里删除元素，向一个集合里加入元素，顺序获得集合里的各个元素（上面算法中for循环做这件事）。图操作包括获取图中所有顶点、判断两个顶点是否相邻。
上面讨论中实际上也介绍了两种最基本的算法设计方法：
枚举和选择（选优）：根据问题，设法枚举出所有可能的情况，首先筛选出问题的解（为此需要判断枚举生成的结果是否为问题的解），而后从得到的解中找出最优解（这一步需要能评价解的优劣）。
贪心法：根据当时已知的局部信息，完成尽可能多的工作。这样做通常可以得到正确的解，但可能并非最优。对于一个复杂的问题，全面考虑的工作代价可能太高，为得到实际可用的算法，常常需要在最优方面做出妥协。

1.2.3算法的精化和Python描述

前面给出了一个解决图着色的抽象算法，它与实际程序还有很大距离。要进一步考虑如何实现，还有很多需要处理的细节，例如：
如何表示颜色？例如，可以考虑用顺序的整数。
如何记录得到的分组？可以考虑用集合表示分组，把构造好的分组（集合）加入groups作为元素（也就是说，groups是集合的集合）。
如何表示图结构？
实际上，是否把“颜色”记入groups并不重要，可以记录或者不记录。下面的考虑是记录颜色，将“颜色”和新分组做成二元组。
现在考虑如何把上述算法映射到一个Python程序中，填充其中的许多细节。前面考虑的集合操作大都可以直接用Python的集合操作：
判断一个集合vs是空集，对应于直接判断not vs。
设置一个集合为空，对应于赋值语句vs = set()。
从集合中去掉一个元素的对应操作是vs.remove(v)。
向集合里增加一个元素的对应操作是vs.add(v)。
Python的集合数据类型不支持元素遍历，但上述算法中需要遍历集合元素，还要在遍历中修改集合。处理这个问题的方法是在每次需要遍历时从当时的verts生成一个表，而后对表做遍历（并不直接对集合遍历）。
算法中需要的图操作依赖于图的表示，需要考虑如何在Python中实现图数据结构。图是一种复杂数据结构，应该支持一些操作。图的可能实现方法很多，第7章将详细讨论这方面问题。这里假定两个与图结构有关的操作（依赖于图的表示）：
函数vertices(G)得到G中所有顶点的集合。
谓词not_adjacent_with_set(v,group,G)检查顶点v与顶点集group中各顶点在图G中是否有边连接。
假设有了图结构及其操作，程序实现就不难了。下面是一个程序（算法）：

def coloring(G):
# 做图G的着色
color = 0
　　groups = set()
　verts = vertices(G)
# 取得G的所有顶点，依赖于图的表示
　
while verts:
# 如果集合不空
new_group = set()
for v in list(verts):
if not_adjacent_with_set(v, newgroup, G):
new_group.add(v)
verts.remove(v)
groups.add((color, new_group))
color += 1
return groups

这个算法实际上已经是一个Python函数，能对任何一个图算出顶点分组。其中欠缺的细节就是图的表示，以及函数里涉及的两个图操作。

1.2.4讨论

完成了工作并不是结束。任何时候完成了一个算法或者程序，都应该回过头去仔细检查做出的结果，考虑其中有没有问题。做出了一个图着色程序，传递给它一个冲突图，它将返回一个分组的集合。现在应该回过头进一步认真考虑工作中遇到的各种情况和问题，包括一些前面没有关注的情况。
解唯一吗？
首先，可以看到，对于给定的交叉路口实例，可行的分组可能不唯一。除了前面几次提到的每个方向独立成组的平凡解之外，完全可能找到一些与前面给出的解的分组数相同的解。对前面问题实例，下面是另一种满足要求的分组：
{AB, EB, EC}, {AC, AD, BC}, {BA, BD, DB, ED}, {DA, DC, EA}
读者不难验证这一分组确实是该问题实例的解。
算法给出的解是确定的，依赖于算法中选择顶点的具体策略，以及对图中顶点的遍历顺序，即list(verts)给出的顶点序列中的顺序。
求解算法和原问题的关系
回顾前面从问题出发最终做出一个Python程序的工作过程：
1.有关工作开始于交叉路口的抽象图示，首先枚举出所有允许通行方向；
2.根据通行方向和有关不同方向冲突的定义，画出冲突图；
3.把通行方向的分组问题归结为冲突图中不相邻顶点的划分问题，用求出不相邻顶点的分组作为交叉路口中可以同时通行的方向分组。
问题是，这样得到的结果满足原交叉路口问题实例的需要吗？
仔细分析可以看到，上面算法中采用的定义不统一：算法给出的结果是行驶方向的一种划分（各分组互不相交，每个顶点只属于一个分组）；而工作开始考虑安全分组时，只要求同属一组的顶点（行驶方向）是互不冲突的。也就是说，原问题允许一个行驶方向属于不同分组的情况（现实情况也是这样，可能某个行驶方向在多种情况下都是绿灯。典型的例子如无害的右转弯）。出现分组不相交的情况，原因是在构建新分组时一旦选择了某个顶点，就将其从未分组顶点集中删除，这样就产生了划分的效果。
要回到求解之前的考虑，并不一定要推翻得到的算法，也可能在原算法上调整。例如，对于图1.2的交叉路口实例，前面算法给出：
{AB, AC, AD, BA, DC, ED}, {BC, BD, EA}, {DA, DB}, {EA, EB}
将分组尽可能扩充，加入与已有成员不冲突的方向，得到：
{AB, AC, AD, BA, DC, ED}, {BC, BD, EA, BA, DC, ED},
{DA, DB, BA, DC, ED, AD}, {EA, EB, BA, DC, ED, EA}
根据前面的定义，这样得到的各分组仍然是安全的，请读者检查。如何修改前面算法，使之能给出这样分组的问题留给读者考虑。
另一个问题前面已有所讨论，就是冲突概念的定义问题。前面采用行驶方向交叉作为不安全情况的定义，这只是一种合理选择。另外的情况是否看作冲突，可能存在不同考虑。如前面提到的直行与旁边道路的右转问题（例如，在允许BD方向的情况下，是否允许AD和ED）。对同一个路口，如果冲突的定义不同，做出的冲突图就会不同。实际定义可能需要反映交管部门对具体路口实际情况的考量，需要根据具体情况确定。
还有许多实际问题在前面算法中都没有考虑。例如，在用于控制交叉路口的红绿灯时，得到的行驶方向分组应该按怎样的顺序循环更替？这里能不能有一些调度的原则，能不能通过算法得出结果？另一些问题更实际，可能更难通过计算机处理。例如各个分组绿灯持续的时间，这里牵涉到公平性、实际需要等。可能还有其他问题。
从以上讨论中可以看到，前面工作中从问题出发逐步抽象，得到的算法处理的问题与原问题已经有了很大的距离。该算法的输入是经过人工分析和加工而得到的冲突图，做出冲突图需要确定冲突的定义，是人为的一步。考虑实际需要的红绿灯调度，该算法产生的结果也缺乏许多信息，真正运用到实际还需要人工做许多工作。
对于上面这些情况，在用计算机解决实际问题时经常可能看到。

小结

本节的假设是希望做出一个程序，给它任意一个交叉路口的有关信息，它能对该路口的可能行驶方向做出一种安全分组。经过仔细分析问题，考虑了一些情况，前面讨论已经给出了一种解决问题的方案（算法），并进一步精化，给出了另一个采用Python语言形式描述的“函数定义”。但这还不是一个可以运行的程序。
Python是一种比较高级的语言，提供了许多高级的数据类型和相关操作。针对这个算法，Python语言的集合和相关操作可以直接使用。但算法中的一些功能是Python语言没有的，主要是缺少图结构及若干相关操作。如果设法在Python语言里实现图结构及所需操作，这个“算法”就变成了一个可以运行的实际程序。
另一些编程语言没有高级的数据类型，只提供了很少的一组基本类型和几种数据组合机制。C语言就是这样，只有几个类型和数组、结构、指针等低级组合机制。要在C语言里实现上述算法，就需要自己实现集合、图及相关操作。
在解决各种问题的程序里，经常要用到诸如集合、图等复杂的数据结构，用于表达计算中获得、构造和处理的复杂信息。理解这类高级结构的各方面性质，在编程语言里有效实现它们，是本书后面章节中讨论的主要问题。对于提供了一些高级数据结构的Python语言，本书还将介绍这些结构的性质和合理使用方法。