《劍指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岔道口車輛能有序的行駛，且效力最高，而且最重要的是把產生意外的可能降到了最低。