【求愛演算法】要先跟多少人約會,才能決定最佳終生伴侶?

 

【為什麼我們挑選這本書】數學絕對是令許多人頭痛的一門科目,但生活中卻處處是數學,你不懂數學,數學也會來找你。數學最大的用處,就是幫助我們在複雜的世界中找出模型,讓我們更容易理解現實的問題、做出最好的決定。

本文選自《攸關貧富與生死的數學》,作者葉茲 2011 年取得牛津大學數學博士學位,現任巴斯大學(University of Bath)數學生物學高級講師、數學生物學中心副主任。他擅長分析現實世界的現象,研究範圍廣及胚胎疾病、蛋殼上的圖樣、蝗災的集體毀滅性等,並從中梳理出背後的數學模式。(責任編輯:鄒鎮鴻)

有效分類排序的背後,其實是演算法在運作

尼克.宏比(Nick Hornby)在 1990 年代寫下《失戀排行榜》(High Fidelity)這部經典小說,主角佛萊明(Rob Fleming)熱愛音樂,開了一家二手唱片行「冠軍黑膠片」。佛萊明會定期把自己的大量唱片依照不同的系統重新排列:可能是按字母順序、時間順序、甚至是按自己的生命自傳來排列(依自己買這些唱片的時間,講出自己的人生故事)。

像這樣重新整理的舉動,除了對音樂愛好者來說有種情緒宣洩的效果,也可以用來迅速查詢及記資料,展現其中不同的特色。就像是整理電子郵件的時候,只要點一下就能選擇排列方式是依日期、寄件人、或是郵件主旨,這正是電子郵件的客戶端執行了一套有效率的演算法來做分類排序。

而在 eBay 上,你可以選擇要用「精準度」、「價錢由低到高」或「即將結束」來排序,這也是因為 eBay 用了有效率的分類排序演算法。

至於谷歌,在它判斷了各個網頁與你搜尋的關鍵字匹配程度後,也需要迅速加以排序,用正確的順序顯示。人們夢寐以求的,就是能實現目標的高效演算法。

如果排序方法一個一個試…

要排序一定數量的項目時,一種做法是盡可能窮盡所有排法,再一一檢查是否正確。假設我們就只蒐集了五張唱片,齊柏林飛船(Led Zeppelin)、皇后合唱團(Queen)、酷玩樂團(Coldplay)、綠洲合唱團(Oasis)和阿巴合唱團(Abba)各一張。

光是五張專輯,就已經有一百二十種不同排法。六張會有七百二十種排法,到了十張,就有超過三百萬種排法。隨著唱片數量增加,排法的數量會急速成長,不管多痴狂的樂迷都不可能窮盡所有的排法:這單純就是件不可行的事。

用氣泡排序法,做簡單的排序

但幸好,你應該已經從自己過去的經驗發現,整理自己收藏的唱片、書籍或 DVD 其實是個 P 問題,也就是確實有某種可行的解決方案。在此,最簡單的演算法稱為「氣泡排序法」(bubble sort),原理如下。

讓我們先把那五張唱片依樂團原文名稱的縮寫 L、Q、C、O 和 A 來排序。氣泡排序法會從左到右檢查過去,只要相鄰的兩張順序不對,就互換位置。這個過程不斷重複,直到任何相鄰的兩張順序都正確,也就代表整個列表都排序完成。

第一次排序的時候,L 在 Q 之前沒錯,所以位置不變,但比到 Q 和 C 的時候,就會發現順序有誤,於是兩者互換位置。氣泡排序法就這樣繼續,於是 Q 再與 O 互換、接著與 A 互換,到此時完成了第一次排序,結果是 L、C、O、A、Q;Q 已經排到了列表最後面的這個正確位置。

第二次排序,L 與 C 互換、O 與 A 互換,於是 O 也來到了正確的位置:C、L、A、O、Q。接著只要再兩次排序,A 就會到達列表最前面,整個列表也成功依字母排序。 

我們把算式簡化一點好了。如果要排序五張唱片,就得將未經分類的唱片做四次排序,每次做四次比較。如果有十張唱片,就得排序九次,每次做九次比較。這意味著,我們每次排序過程中的工作量,幾乎就是需要排序的項目數量平方。

倘若你收藏了一堆唱片,這件事做起來當然還是相當費功夫,三十張唱片就得做幾百次的比較;然而,相較於暴力破解法需要列出天文數字的所有可能排法,採用氣泡排序法仍然省力不少。

氣泡排序法無法用於大量資料的排序

雖然這已經是一大進步,但電腦科學家一般認為氣泡排序法的效率還是太低。在實際應用上,不論像是臉書的動態消息、或是 Instagram 的最新動態,隨時都有幾十億則發文必須依據這些科技龍頭的最新優先順序來排序顯示,於是簡陋的氣泡排序法也就被更新、更有效率的類似方法取代。例如「合併排序法」(merge sort),做法就是先將所有發文分成幾小批,經過迅速分類排序,再組合成正確的順序。

2008 年美國總統大選期間,馬侃(John McCain)成為候選人之後不久,受邀到谷歌發表演講,討論他的政策。谷歌當時的執行長施密特(Eric Schmidt)和馬侃開玩笑,說整個競選過程就像是谷歌的面試,接著就問了一個谷歌確實會問的面試問題:「如果只有 2 MB 的 RAM,你要怎麼將一百萬個 32 位元整數進行排序?」馬侃看起來一頭霧水,而施密特玩笑開夠了,立刻 問了下一個真正的問題。

六個月後,輪到歐巴馬(Barack Obama)來到谷歌接受考驗,施密特也拋出了同一個問題。歐巴馬看向觀眾,擦了一下眼睛,說道:「這個嘛,嗯……」施密特以為歐巴馬一時語塞,本來想接過話題,但歐巴馬直視著施密特的眼睛,繼續說著:「……不、不、不,我只是在想,絕不能用氣泡排序法吧」,全場的電腦科學家對此報以熱烈掌聲及歡呼。

歐巴馬的回應,反映出他出乎意料的博學多聞:他說了一個內行人才懂的笑話,笑點就在於這種排序演算法的效率有多麼低落。他的整個競選過程不斷顯露這種舉重若輕、信手捻來的魅力(唯有經過精心充分的準備才能做到),最後一路送他進白宮。

生活中也能適用的演算法 — 最佳停止策略

上面提到的某些最佳化演算法,都是以大規模施行的方式來取得商業利益,似乎會讓人覺得,只有科技龍頭才有辦法使用那些背後的數學道理。但也有一些更直接簡單的演算法(雖然隱藏的數學原理很複雜),可以為日常生活帶來一些微小但重要的改善。其中一類稱為「最佳停止策略」(optimal stopping strategy),能讓人知道在決策過程中何時該停止選擇,開始實際行動。

比方來說,假設你和另一半在陌生的地方逛街,正在想該去哪裡吃晚餐。雖然你們都很餓,但你不想隨便遇到一間餐廳就進去,寧願再走走,挑間好的來吃。你自認眼光精準,一看就能知道這家餐廳的品質如何,還可以跟其他餐廳比較。你更判斷出在另一半不耐煩之前,大概有時間逛到最多十間餐廳。而且,因為你不想留下優柔寡斷的印象,所以決定只要走過,絕不回頭。

遇到這樣的問題,最好的策略是先瞭解一下大致的狀況,也就是前幾間餐廳都只是觀察,卻不走進去。其實你也可以隨便遇到一間餐廳就走進去,但既然你完全不知道這個環境的情況,能夠挑到最佳餐廳的機率就只有 1/10。所以,最佳的做法是先看過幾間,接著在剩下的選擇當中,只要看到「比先前幾間都好」的選擇,就決定是它了。

說明這樣的餐廳挑選策略。前三間餐廳是做為品質判斷的基準,單純觀察品質如何,而不會進去用餐。當你逛到了第七間餐廳,發現它比過去幾個選擇都優秀,那麼就可以在這裡停下,進去用餐。

試試「37%」法則找出最佳的「相對選擇」

然而,選前三間做為基準,這個數字正確嗎?在這種最佳停止時機的問題裡,重點在於到底該先觀察幾間餐廳(而不進去用餐),才能瞭解這個環境大致的情況?如果看得不夠多,就無法充分瞭解環境,但如果觀察(並排除)了太多間,可能剩下來的選擇就十分有限。

這項問題背後的數學原理十分複雜,總而言之就是:你應該觀察前 37% 的餐廳(在只有十間的時候,捨去算成三間),接著只要遇到比先前都優秀的餐廳,就以此為最後決定。

說得更精確一點,就是先拒絕所有可得選項個數的 1/ e,這裡的 是歐拉數(Euler’s number)的簡寫,因為歐拉數大約是 2.718,所以 1/ 大約是 0.368,或是寫成大約 37%。

如果要從一百間餐廳當中挑選,到底該先觀察幾間餐廳,能夠讓選到最佳餐廳的可能性達到最高。我們可以料想到,如果太早做出決定,等於是盲目選擇,所以能選到最佳餐廳的機率很低;同理,如果太晚做出決定,很有可能已經錯過最佳的選擇。倘若你觀察的是前三十七個選項,就能把挑到最佳餐廳的可能性提升到最高。

只不過,如果最佳餐廳就在前 37% 裡怎麼辦?那不就錯過了嗎?在此要提醒各位,這種「37%」的規則本來就不是成功的保證,它只是一個機率法則,告訴你有 37% 的時候能夠挑出最好的餐廳。37% 已經是這種情況下的最高機率,高於有十間餐廳可選而隨便選的 10%,更遠遠高於有一百間餐廳可選而隨便選的 1%。在選項個數愈多的時候,相對成功率也會愈高。 

37% 法則在生活中也能活用

最佳停止時機的規則並不只適用於挑餐廳。事實上,數學家一開始是把這套規則用在「雇用問題」上。假如你得依序面試一定數量的應徵者,並在面試每個人後立刻告知是否錄用,那就該採用 37% 的規則。先面試 37% 的應徵候選人(但都不錄用),以此做為基準。而在接下來,只要出現比先前都優秀的應徵者,就直接錄用。

我家附近的超市有十一個結帳台,我也會先走過前 37%(四個)結帳台,觀察現在的隊伍有多長,接著只要看到更短的隊伍,就排那一排。

如果我和朋友出門夜歸,打算趕上最後一班列車,但乘客似乎不少,而我們又希望能找到空位最多的車廂,好讓我們坐在一起;這時也可以運用 37% 的規則。要是遇到的列車總共有八節車廂,我們就會先走過前三節,觀察空位的狀況,接著在空位比先前都多的車廂坐下來。

事情總有例外,演算法並非全能

以上的場景雖然已經盡量舉實際的例子,但還是有一部分略為牽強,再修正一下或許會更加貼近現實。例如在觀察餐廳的時候,如果發現有一半都沒有空桌了,你該怎麼辦?在這種時候,很顯然該減少拒絕的餐廳。所以,不要再堅持觀察完前 37%,而是觀察了前 25% 之後,一出現比先前都優秀的選項時,就該做出決定。

像是在搭上末班列車的時候,如果有時間可以回頭走進剛才經過的車廂,但車廂有 50% 的機率坐滿了乘客,那又該怎麼選擇?可以回頭,代表選項變多、也有餘裕可以挑久一點,所以此時就可以先觀察並拒絕前 61% 的車廂,接著選擇下一節最空的車廂。當然,你得在列車跑掉之前上車才行。

此外,不管是想知道賣房的最佳時機,或是該離電影院多遠才最有機會找到不必走太久的車位,這些問題都有相關的最佳停止時機演算法。只不過,隨著條件愈來愈貼近現實,相關的數學也會愈來愈複雜,無法再用一個簡單的百分比來表示。

什麼時候會遇到真命天子/女,演算法算得出來嗎?

甚至,還有一套最佳停止時機演算法,算的是你應該先跟多少人約會,再決定你的最佳終生伴侶。首先,你得判斷在自己定下來之前,大概可以交幾個男女朋友。假設你大概一年交一個,那麼從十八歲到三十五歲之間,就有十七人可供選擇。這時,根據最佳停止時機法則,你應該先遊戲人間六年到七年(大約是十七年的 37%),觀察自己可以遇上怎樣的對象。接著,只要出現比過去都優秀的選擇,你就該認定這是今生的伴侶。

對於像這樣由一套預定規則來支配自己的愛情生活,很多人都會感到懷 疑。如果在那前 37% 裡,真的有很合得來的人怎麼辦?難道真的要為了執行這套求愛演算法,就狠心放下對方嗎?如果你自己遵守了一切規則,但認定是最佳選項的對方卻不認為你是最佳選項,又該怎麼辦?如果走到一半,發現自己喜歡的條件不一樣了,又要怎麼辦?

還好,講到內心、或是其他更明顯的數學最佳化問題時,我們並不一定需要找到絕無僅有的真命天子/天女、最好的解決方案。世界上可能有很多人都會跟我們處得不錯,能讓我們有幸福的一生。最佳停止時機的策略,並不會提供所有人生問題的答案

雖然演算法潛力無窮,能夠協助我們處理日常生活的許多面向,但絕不是所有的問題都能用演算法找出最佳解答。

我們雖然可以利用演算法來簡化、加速單調乏味的任務,但風險也常常伴隨而來,因為演算法包含輸入、規則和輸出這三個面向,也就代表有三個可能出錯的地方。就算使用者確信所用的規則完全符合自身需求,只要輸入不小心,或是輸出不合規範,就有可能造成災難。

(本文書摘內容出自《攸關貧富與生死的數學》,由 天下文化 授權轉載,並同意 TechOrange 編寫導讀與修訂標題;首圖來源:pexels。)

你可能會有興趣

【七維空間是否成立?】數學家集結 40 台電腦算力,半小時破解困擾 90 年的凱勒猜想難題
【是否有個奇數剛好也是完全數?】歐幾里得、笛卡爾都無解的數學難題,他提出了新思考方向
◊ 55 年前就用數學模型證明黑洞生成,89 歲牛津教授獲頒諾貝爾物理學獎


科技報橘 LinkedIn 上線!

最新科技產業動態、技術新突破、專業職能技巧提升 ....... 鎖定 TO  LinkedIn 專業品牌,提升職能與產業 Know-how,躋身產業菁英之列 https://www.linkedin.com/showcase/techorange

點關鍵字看更多相關文章: