《剑指offer》:[56]五岔路口交通管理红绿灯设计

抽象建模能力
       计算机只是1种工具，是为我们服务所驱使的工具，我们不能1头扎入这个编程的海洋出不来乃至迷失了方向。它的作用是帮助我们解决实际生活中的问题。程序员的工作就是把各种现实的问题抽象成数学模型并用计算机的编程语言表达出来，所以我们应当培养自己从平常生活中抽取提炼出问题并建立相应的数学模型，找到问题的规律并解决问题的能力。
建模的第1步：从具体问题中抽象选择适合的数据结构来表述问题；
建模的第2步：分析模型的内在规律，设计1个解此数学模型的算法；
建模的第3步：编出程序，也就是用编程语言表达这类规律，进行结果的分析及调试直至成功。
       比如田鸡跳台阶问题实质就是斐波拉切问题；还有5岔路路口的交通管理其实就是图的问题，可以用着色来解决。还有图书馆里的图书的查找管理也是1种线性的数据结构，计算不规则物体的体积和面积就是微积分问题，等等，我们1定要培养这类从事物中抽象出问题核心的东西。

      下面主要介绍1个多岔道口交通灯的管理问题，由于该节的知识点在[37]中已讲过了，所以在这里插入1点书外知识。

     在1般的道路上，我们通常看见的就是红绿两种色彩的交通灯，这样就能够保持正常的交通秩序，又能到达车流量的最大量。之前当我站在人来人往的天桥上，车如马龙的街道上的时候，看见这个红绿灯，看着它默默的每天都是循环往复，帮助这个城市有秩序的运转，就不明觉厉。能感觉到红绿两色对城市交通的重要性和意义！虽然看起来简单，但是要想到达让全部城市的交通畅通无阻而且每天能发挥出公路的最大效力，也就是大道车流量的最大值，背后却不是这么简单的，需要公道的算法设置灯的色彩和更好实现全局协作。交通情况以下图所示：

                          图1                                                                       图2

    下面就简单的来讲说交通灯的问题吧！--摘自严蔚敏老师的《数据结构》(C语言版)1书，觉得挺成心思就写了下来：

    题目： 要求设计1种交通灯方案，使过往的车辆能有秩序的行驶不产生冲突，并且充分最大发挥公路的效力，尽最大可能减缓城市的交通压力。

    例如在中上图1中，就是1个城市的5岔道口，ABCDE分别表示这5个路口，E和C分别是单向车道。这里每天都有大量的车流量。通常这类交通、道路问题的数学模型是1种称为“图”的数据结构。图2中的每一个顶点表示1条通路，如AB代表车从A开向B。而如果存在矛盾的通路我们用连线来表示，例如AB和EA之间有1条连线，表示有车从A向B行驶的时候就不能有车从E到A行驶。

     由此，我们知道在图2中，每一个圆圈表示图a5岔道口上的1条通路，两个圆圈之间的连线表示这两个圆圈不能同时通行。经过这样的设计抽象和转化后，看似复杂的问题这这里设置交通灯的问题就能够等价为：对图着色的问题，
     问题转换为：要求对图上的每一个顶点然1种色彩，并且要求有线相连的两个顶点不能具有相同的色彩，而使用的总的色彩种类尽可能的少。
    上图2中就是1种着色方案。例如将红色、黄色、蓝色和绿色分别编号为1，2,3,4号灯，那末当4号灯为绿色时，那末只有DA和DB两条路可以通行，其他的都要显示为红色，制止通行。只有这样才能保证在 这个5岔道口车辆能有序的行驶，且效力最高，而且最重要的是把产生意外的可能降到了最低。