在電影《巴頓將軍》中，將軍看到他的兩列坦克交叉行駛並陷入堵塞。在沮喪中，巴頓離開了他的吉普車，開始指揮交通。幾分鐘後，奧馬爾·布拉德利將他叫回，去處理更重要的職責。布拉德利嘲諷地稱讚巴頓作為交通警察的技能。
但事實是，他是一個糟糕的交通警察。當你不受道路限制時，有更有效的方法讓兩列隊伍互相交叉。
讓我們先讓問題變得更難一點。假設有四列車輛，每列顏色都不同。如圖 1 所示，這些列即將在一個十字路口相遇。
每列車輛都想從矩形區域的對邊駛出。因此，綠色車輛想從頂部駛出，橙色車輛想從左側駛出，依此類推。這樣做時，車輛可以並排行駛，而不是單列行駛。
支援科學新聞報道
如果您喜歡這篇文章，請考慮透過以下方式支援我們屢獲殊榮的新聞報道： 訂閱。透過購買訂閱，您正在幫助確保有關塑造我們今天世界的發現和想法的具有影響力的故事的未來。
因為我們透過允許四列車輛使問題變得更難，所以我們將簡化移動規則。 想象一下有一個網格。 每輛車都在一個網格單元位置。 在一列中，相鄰的車輛位於相鄰的單元格中。 車輛可以在一分鐘內移動到其垂直或水平相鄰的單元格。 如果兩輛車最終進入同一個單元格，它們就會相撞。 您需要避免碰撞。
如圖 1 所示，這四列車輛正在匯聚到中心的單個正方形上，因此如果它們同時向中心前進，就會發生碰撞。
問題是如何安排移動，以便所有車輛在儘可能短的時間內穿過其目標側。 具體來說，假設每種顏色有六輛車，網格尺寸為 13x13。
熱身題： 考慮一種情況，其中每列由一輛車組成，如圖 2 所示
同樣，每輛車都想從對邊駛出。 因此，B 想要穿過底邊；R 想要穿過右邊，依此類推。 我們如何安排才能讓所有車輛在四分鐘內穿過其目標邊？
熱身題答案
所有路線都在圖 3 中顯示
所有車輛都在四分鐘後駛出其對邊。 很容易看出沒有碰撞。
問題： 1. 假設您必須保持車隊的順序，並且它們都必須透過中心。 這需要多長時間？
2. 現在嘗試為圖 1 中每列六輛車、13x13 網格的問題找到一個 14 分鐘的解決方案。
3. 您能證明沒有更快的解決方案嗎？
4. 假設有八輛車——您可以選擇哪些車——可以在旅程的第八分鐘以正常速度的兩倍（即一分鐘兩個單元格）行駛。 那麼您如何才能在僅十三分鐘內解決圖 1 中每列六輛車、13x13 網格的問題？
這是一個開放性問題：如果只有四輛車可以在第八分鐘加速，您能實現 13 分鐘的解決方案嗎？ 請記住，不允許碰撞。