用數學思維優化排隊公平性兼維持效率
在奧數或增潤數學課堂,教師可用下例教導學生用數學思維和知識(枚舉法、概率),優化排隊公平性兼維持效率。
例如有8人排隊進入一場所,需要過安檢,每人過安檢的時間均不同(假設最長不超過最短安檢時間的2倍,以簡化題目的複雜性)。現在有4個安檢員,傳統上便有兩種排隊方式,一是只有1條隊,二是分4條隊。前者的好處是絕對公平,誰先來誰先過安檢,但效率較低,排最前者要同時觀察4個安檢員,看誰會突然完成,對排得越後的人,因前面的人的觀察成本導致越多累積延遲。後者的好處是整體效率高,但大機會導致排後面的人不公平。首4人是公平的,每人不用排隊便可即時有一安檢員為他們進行安檢。然而,第5個來的人要在4條隊選1條,第6人理應在餘下3條選1條,如此類推,最終第5至第8人便每人等一條隊。稱第5人為E、第6人為F、第7人為G、第8人為H。若難以分辨哪個安檢會先放行,以下24個可能進行安檢的次序便可大致相同的機會發生:
EFGH, EFHG, EGFH, EGHF, EHFG, EHGF, FEGH, FEHG, FGEH, FGHE, FHEG, FHGE,
GEFH, GEHF, GFEH, GFHE, GHEF, GHFE, HEFG, HEGF, HFEG, HFGE, HGEF, HGFE
而只有EFGH是公平的,即公平的概率大概只有1/24。
為了優化排隊公平性兼維持效率,我們可用分叉的排隊形式,如左圖表示(假設前4人分別是A、B、C、D):
A B C D E F G H | A B C D E F G H I J K L M N O P |
根據左圖,E選擇同時等待A和B,F便選擇同時等待C和D,G便在E和F後面等待,誰先進便往哪方排,可能性只有EFGH, FEGH, EFHG, FEHG,而最後先G後H的機會較大,公平的概率上升至大於1/4,而E、F、G分別只需觀察其前方的左或右,看哪個先通行(而非同時觀察多個入口),效率便與分4條隊接近。
當入口數和人數均不同時(如右圖便是有8個安檢員和16人需過安檢,這16人分別是由A至P),也是用類似方式處理。