No.17 一道產品面試題 - 交通燈的最優解

前幾天某家屬碰到了一道面試題，在此嘗試進行解答

題設：請設計海星馬路的交通燈規則，使得該路口的通過效率最高，假設每條路雙向車流量均相同。

1. 問題解讀

① 通過效率

顯然，車輛的等待時間越長，通過效率最低，所以盡量讓車輛處於通行狀態；

同時，不能讓車輛處於阻塞狀態，即同一時間的行車路徑不能有交叉。

② 環島設計

看到這個問題第一反應是直接設計一個環島，一定通過效率最高，因為所有的車都不會等待。當然這種操作可能不是本題考察的，有作弊嫌疑。

③ 每條路雙向車流量均相同

這是一個很重要的條件，可以等價為『如果某條路車流量是1，那麼這些車開到其他任意車道的流量均為1/4』。

為什麼這兩個條件是等價的？

我們先不考慮5個路口的情況，不妨先考慮只有3個路口A，B，C，假設每條路的車流量均為1

如果要保證每條路的車流量均相等，對於某一條路，需要同時滿足兩個條件

• 流入這條路的車流量總和為1
• 從這條路流出的車流量總和為1

流出情況：

對於A路口流出車輛，流向B的假如有1/a，流向C的就有 1-1/a ；

對於B路口流出車輛，流向C的假如有1/b，流向A的就有 1-1/b ；

對於C路口流出車輛，流向A的假如有1/c，流向B的就有 1-1/c ；

流入情況：

流向A路口的車輛，滿足 1/c + 1 - 1/b = 1，即 c = b

流向B路口的車輛，滿足 1/a + 1 - 1/c = 1，即 a = c

流向C路口的車輛，滿足 1/b + 1 - 1/a = 1，即 b = a

所以 a = b = c = 2，某一路口流向其餘任一路口的流量均為1/2

從特殊到一般，同樣的解法可以得出，如果有n條路，某條路流向任一其餘路口的車流量均為1/(n-1)

2. 演繹推理

先不考慮有5條路口的情況，沿著從特殊到一般的思路，從只有兩條路開始，對本題的場景進行演繹，嘗試找出 n 條路情況下的通用解

① 2條路的情況

這種情況下不需要交通燈，A和B兩條路它丫的就是同一條

② 3條路的情況

先找出不受交通等影響的路徑，即無論如何，也不會和別的行車路徑有交叉

從圖上可以很明顯的看出來，A -> B，B -> C，C -> A 這三個相鄰路口的右轉行車路徑可以全程亮綠燈，不會和其他行車路徑交叉。

枚舉所有的路徑：

A -> B，B -> C，C -> A；

A -> C，B -> A，C -> B；

前三個路徑已經討論過了，而對於後三種路徑，同時只能有一個存在，如圖

所以有3個路口的情況，最優解如下：

A -> B，B -> C，C -> A 始終通行；

A -> C 通行，B -> A，C -> B 等待；

B -> A 通行，A -> C，C -> B 等待；

C -> B 通行，A -> C，B -> A 等待。

我們把3條路情況的解法定義為『三路徑解法』，以方便之後敘述

③ 4條路的情況

給四條路編號，按照逆時針順序分別為A，B，C，D

顯然，按照三路徑解法的結論，A -> B；B -> C；C -> D；D -> A 四條路徑始終通行即可；

剩下的路徑總共有8條：

A -> C；A -> D；B -> D；B -> A；C -> A；C -> B；D -> B；D->C。

在四條路徑的狀況下，每相鄰的三個路徑都適用於三路徑解法，所以

A -> C，B -> A，C -> B 三選一；

B -> D，C -> B，D -> C 三選一；

C -> A，D -> C，A -> D 三選一；

D -> B，A -> D，B -> A 三選一；

四條路徑的情況不同於三條路徑，出現了非相鄰車道的路徑，定義『對角線規則』如下

A -> C，C -> A，B -> D，D -> B

若 A -> C 或 C -> A 通行，則 B -> D，D -> B 等待；

若 B -> D 或 D -> B 通行，則 A -> C，C -> A 等待。

不要忘了還有車流量相同的條件

在此條件下，需要讓每條路的通行平均分配，使得一個交通燈周期內所有路徑的通行次數相等

在以上條件的約束下，只有唯一解

第一次變燈，讓所有流向 A 的路徑通行；

第二次變燈，讓所有流向 B 的路徑通行；

第三次變燈，讓所有流向 C 的路徑通行；

第四次變燈，讓所有流向 D 的路徑通行；

以1代表通行，0代表等待

• A -> B；B -> C；C -> D；D -> A 始終暢通
• 其餘路徑用交通燈控制，如下圖

④ 5條路的情況

回到題設，5條路的情況，嘗試用以上得出的結論進行求解

顯然，A -> B；B -> C；C -> D；D -> E；E -> A 可以永久通行不影響交通，此外的路徑中，每三個路口之間，『三路徑情況』的解法和規則同樣適用。

五邊形的頂點最多可以組成10個三角形，參考『三路徑解法』，有如下規則限制

相鄰頂點組成的三角形：

A -> C，C -> B，B -> A，三選一；

B -> D，D -> C，C -> B，三選一；

C -> E，E -> D，D -> C，三選一；

D -> A，A -> E，E -> D，三選一；

E -> B，B -> A，A -> E，三選一；

非相鄰頂點組成的三角形：

A -> D，D -> C，C -> A，三選一；

B -> E，E -> D，D -> B，三選一；

C -> A，A -> E，E -> C，三選一；

D -> B，B -> A，A -> D，三選一；

E -> C，C -> B，B -> E，三選一；

此外，根據以上得出的『對角線規則』，非相鄰路口如果通行，通行路徑兩邊的路口之間只能等待，無法通行

若 A -> C 或 C -> A 通行，則 B -> D，D -> B，B -> E，E -> B 等待；

若 B -> D 或 D -> B 通行，則 A -> C，C -> A，C -> E，E -> C 等待；

若 C -> E 或 E -> C 通行，則 A -> D，D -> A，B -> D，D -> B 等待；

若 A -> D 或 D -> A 通行，則 C -> E，E -> C，B -> E，E -> B 等待；

若 B -> E 或 E -> B 通行，則 A -> C，C -> A，A -> D，D -> A 等待；

同時在以上條件的約束下，另外要保證在一個交通燈周期內，每個路口流出和流入，路口和路口之間流量必須相同，平均分配車流量，只有唯一解

第一次變燈，讓所有流向 A 的路徑通行；

第二次變燈，讓所有流向 B 的路徑通行；

第三次變燈，讓所有流向 C 的路徑通行；

第四次變燈，讓所有流向 D 的路徑通行；

第五次變燈，讓所有流向 E 的路徑通行；

A -> B，B -> C，C -> D，D -> E，E -> A 始終通行

3. 通用解

• 對於n個路口的情況，給每個路口逆時針標號1，2，3 ... m，m+1... n
• 對於任意3條路組成的三角形，路徑 m -> m+2，m+2 -> m+1，m+1 -> m 三選一
• 所有三角形的三選一條件組成規則庫
• 此外有對角線規則，如果 m->m+x 或 m+x->m 路徑通行，則 {1,2...m-1} 和 {m+1,m+2...n} 兩個集合之間元素組成的路徑，均等待，不能通行
• 在每個交通燈周期內，每個路口流出和流入，路口和路口之間流量必須相同

在以上條件制約下，此類問題只有唯一解

• 交通燈一個周期內有n次變燈
• 第1次，所有要進入1號線路的車輛行使，其餘均等待
• 第2次，所有要進入2號線路的車輛行使，其餘均等待
• 第3次，所有要進入3號線路的車輛行使，其餘均等待...
• ......
• 第n次，所有要進入n號線路的車輛行使，其餘均等
• 循環以上

感興趣的同學可以研究一下每條路徑流量不相等的情況，

如有邏輯錯誤，隨時指正！