[閱讀筆記] The Math of Life and Death - ㊅ 永不停歇的改善：從演化到電子商務，展現演算法的無限潛力 (Relentless Optimization: From Evolution to E-commerce, Life is an Algorithm)

 

1. 演算法其實是一連串的指示，用來明確完成某一項任務，從整理手邊蒐集的唱片到做出一到菜等。然而，史上最早的演算法，本質上是很單純的數學。

古早時代的演算法 🤔💭📊🧮📝

古埃及時代有一套簡單的演算法，用來將兩個數字相乘； 巴比倫也有一套演算法來計算平方根； 西元前三世紀，古希臘數學家 Eratosthenes 發明質數篩選法 (sieve)，可以找出一定範圍內的質數； 阿基米德發明窮舉法 (method of exhaustion) 來計算圓周率。

2. 現在電腦執行的演算法日益複雜，當我們想要有效率的處理日常事務時，演算法變成不可或缺的一環。以往的解答已經無法滿足我們的需求

	Before	Now
搜尋引擎	找到資料	找出最相關的資料 ℹ️
氣象預報	告訴你明天天氣	告訴你明天下午五點會下雨 ☔
GPS	算出一條路線	提供能最快抵達的路線 🚗

3. P/NP 問題的核心：針對問題的答案做驗證，通常比找出問題的答案還容易。這個數學未解之謎真正要問的是：如果某個解答能用電腦快速驗證，是否也能用電腦快速求解？

P 問題 (Practical Problem)

如果有一組問題，能在多項式時間 (polynomial time) 內快速求解，就是 P 問題 🧩 假設我打造一套會拼拼圖的演算法，求解時間取決於片數、片數的平方 / 立方 / 更高的次方。舉例來說，如果這套系統取決於片數的平方，解開兩片拼圖需要 22 = 4 秒、10 片拼圖要 102 = 100 秒、100 片拼圖要 1002 = 10,000 秒，雖然看起來很久，但仍舊是幾個小時內可以解決的事。

NP 問題 (Not Practical Problem)

另一種問題，可以快速驗證，但不一定能快速求解，就是 NP 問題，NP 指的是非多項式時間 (nondeterministic polynomial time) 。NP 問題會因問題規模的增加，很快得變得不可行。 一旦能快速求解，當然就可快速驗證答案，所以 P 問題是 NP 問題的子集合。 假設這套會拼拼圖的演算法，需要的是非多項式時間 (NP)，解開兩片拼圖一樣需要 22 = 4 秒、10 片拼圖要 210 = 1,024 秒、100 片拼圖要 2100  秒，這已經超過從宇宙爆炸迄今的時間。

P 與 NP 問題間的關係

4. Bubble Sort、Insertion Sort、Merge Sort 《Algorithms to Live By》

Bubble Sort

是一種簡單的排序演算法。它重複走訪過要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。走訪數列的工作是重複地進行直到沒有再需要交換，也就是說該數列已經排序完成。這個演算法的名字由來是因為越小的元素會經由交換慢慢「浮」到數列的頂端。 是最簡單瞭解和實作的排序算法之一，但它對於包含大量的元素的數列排序是很沒有效率的。 平均時間複雜度O(n2) 最壞時間複雜度O(n2) 最佳時間複雜度O(n) (Ref.: https://reurl.cc/Dv3nRE)

Insertion Sort

此排序法優點是比氣泡排序法更直覺，評價較好，缺點是其實沒有快多少。採取此方式時，每個位置還是都要插一次，每次插入平均時間需經過一半的位置，才能找到正確的位置。儘管插入排序法速度快了一點，花費時間仍是平方時間，沒有比氣泡排序快多少。 平均時間複雜度O(n2) 最壞時間複雜度O(n2) 最佳時間複雜度O(n) (Ref.: https://reurl.cc/qmNdzy)

Merge Sort

上述兩個看似合理且直覺的排序方法，搜尋時間都是平方時間 (quadratic time, O(n2))，排序對象一多就難以負荷。合併排序 (merge sort) 就是用來解決上述難題，它的複雜性介於線性時間和平方時間之間，更精確地說是線性對數時間 (linearithmic time, O(n log n))。屬於 Divide and Conquer 演算法，把問題先拆解 (divide) 成子問題，並在逐一處理子問題後，將子問題的結果合併(conquer)，如此便解決了原先的問題。 (Ref.: https://reurl.cc/bzEEnl)

5. 排序與運動賽事的類比 《Algorithms to Live By》

排序方法	運動賽事
Bubble sort	羽球、壁球等常用的排位賽 (ladder)，是依照排名順序列出的選手名單，每名選手可以挑戰前一名選手，如果獲勝，排名就對調。這就是運動界的 bubble sort，執行時間是平方時間。
Merge sort	NCAA 的單淘汰制 (tournament bracket)，每一輪比賽都淘汰一半隊伍，從 64 強、32 強、16 強、8 強、4 強以及決賽。這就是運動界的 merge sort，一開始為排序的隊伍兩兩比賽，接著不斷對併再對併。

6. 旅行推銷員問題 (Travelling salesman problem, TSP)，是組合最佳化中的一個NP 困難問題，在作業研究和理論電腦科學中非常重要。問題內容為「給定一系列城市和每對城市之間的距離，求解訪問每一座城市一次並回到起始城市的最短迴路。」旅行推銷員問題有個「決策版本」，它只問有沒有比某長度更短的路徑，就是 NP-Complete 問題的經典範例。理論上，如果能提出一套可行的演算法，解出某個 NP-Complte 問題，就能轉換這套演算法來解決其他 NP 問題，這樣就能證明 P = NP。

P = NP 造成的災難

💻 🛒 🔐 線上交易安全性將會是災難，因為我們正是靠著難以解決的 NP 問題，來建置現行的網路加密技術。

P = NP 造成的好處

🏭 工廠可以排出最有效率的製程 🚚 快遞公司可以排出最有效率的送貨路線 🧬 找到更有效率的基因定序方法 🌀  找出更有效率的預測自然災害方法

7. P 與 NP 的對抗，其實是在確認人類的創意是否能自動化。若 P = NP，那麼任何可證明的數學定理，電腦都能在一定的程式序列內找出證明。這代表過去人類許多偉大的智力成就 (ex. 牛頓的運動定律、達爾文的自然選擇演化論、愛因斯坦的廣義相對論、懷爾斯的費馬最後定理證明)，只需一台機器即可複製並取代，許多數學家將因此失業。

8. 我們有時候不一定想要完美但緩慢的方案，反而寧願接受普通但快速的方案。例如，💼 在上班前，我不太需要研究怎麼擺才能讓公事包裡的物品占據最小空間，只要能讓所有東西塞進去即可。啟發式演算法 (heuristic algorithm，又稱經驗法則)，就是讓我們在面對許多不同問題時，得到與最佳解相去不遠的解決方案。

9. 貪婪演算法 (greedy algorithm) ，是一種短視的演算法，靠著找出當下問題的解決方法，希望最後找出整體問題的最佳解。貪婪演算法，一定能找出某種解決方案，卻無法保證最後得到的是最佳解，有時候甚至稱不上普通解。但確實有些問題，能夠用此法得到最佳解。

10. 汽車衛星導航採用 Dijkstra's algorithm (戴克斯特拉演算法)，是一種 greedy 演算法，每次都去找當前最小的那一條路，能在多項式時間 (polynomial time) 內快速找出「最短路徑」的答案。

運用 Dijkstra's algorithm 尋找 A 到 E 的最短路徑 (https://reurl.cc/735bE5)

建立表格

Visited: 有沒有走過這個點，預設為 False Cost: 從起點到這個點所需路程，預設為無限大 Path: 這個點的上一個相連點，預設 -1 (或是任何可代表非圖上點的值)

A → C → E 【Cost = 12】

A → B → D → E 【最短路徑，Cost = 8】

A → B → E 【Cost = 9】

11. 群體智慧 (Swarm Intelligence) 是自然科學研究的領域，他研究的對象主要是自然群體生物在現實環境中，各種群體行為的相關議題，例如：路徑規劃、任務分配和築巢…等。很多時候甚至可以觀察到，即使是弱小的生物個體，當群聚一起時，卻可以展現出極其複雜的集體行為。常被研究的自然群體生物有：細菌菌落、魚群、螞蟻群、蜜蜂群、蝗蟲、鳥群、靈長類部落，當然其中也包含了人類。研究這些群體是非常有趣的，例如：螞蟻群在工作時，儘管沒有領袖發號司令，卻可以在移動過程中漸漸地找出最佳移動路徑。演算法設計人員從動物間的互動得到靈感，可以派出大量彼此連結緊密的人工智慧體 (artificial agent)，讓它們去探索某個環境；這些人工智慧體能夠如動物群體般的迅速溝通互動，在搜尋環境的過程中，互相掌握其他個體的發現。它的控制是分布式的，不存在中心控制。(https://reurl.cc/73ORrN)

12. 在我們眼中，有許多物種適應良好，堪稱典範。但有可能演化還沒找到最佳方案，只是我們想像力不足，才會誤會這已是「完美」的方案；幸好有隨機的組合與突變，能讓我們擺脫局部最大值，進一步找到更好的解決方案。

13. 隨機性演算法未必能提出最佳解，但它不用像確定性演算法那麼辛苦，只要有計畫地丟幾個硬幣，就能在短短時間內提出相當接近最佳解的答案。隨機性演算法用於特定問題的效果，甚至超越最好的確定性演算法。問題的最佳解決方法有時候是交給機率決定，而不是自己試圖推出答案。運用隨機法，想辦法從局部最大值，變成整體最大值。《Algorithms to Live By》

14. 無論是抖動、隨機重新開始、或是接受解決方案偶而變糟，隨機性用於避免局部最大值的效果都很好。機率不只是處理困難最佳化問題的可行方法，在許多狀況下還是必要方法。從模擬退火法可以得知，你應盡早使用隨機性，並快速離開隨機的狀態，隨時間而降低隨機性，停留在接近結冰的時間最久。壓住火氣，不要急躁。《Algorithms to Live By》

15. 在最佳停止問題 (Optimal Stopping) 中，真正讓人困擾的不是該選擇哪個，而是可以考慮的選項有多少。面臨這類問題的不只有情侶與想租房子的人，還有駕駛人、想買屋的人、竊賊、開車度假找旅館的人等。37% Rule 源自於著名的最佳停止問題 - 秘書問題 (secretary problem)：《Algorithms to Live By》

秘書問題

假設你想跟幾個應徵者面試，並盡量提高從中找到最佳人選的機率。 以隨機順序與應徵者面談，每次一位，可以在任何時候決定錄取人選，且那個人一定會接受職位，並結束徵人過程。但是若你決定不錄取某人，之後就沒有機會錄用他。 【決策的兩難】 ① 太早做決定，其實有更好的人選。 ② 找得太久，想找更好的人，但是不存在這樣的人選。 最佳策略顯然是找出兩者間的平衡，不要太快做決定，但也不要太倉促決定、太不挑。

思而後行的策略 (秘書問題的最佳解決方案)

設定一段「思考」時間階段，也就是研究各種選擇和蒐集資料，在這段時間不論遇到多優秀的人，都不錄取；過了設定的時間階段後，就要準備好隨時出手，只要看到比思考階段的應徵者更好的人選，毫不猶豫馬上錄取。意即，一旦過了這個底線，就大膽地開始選擇，這就是最好的選擇模式。

37% Rule 日常生活例子(Ref.: https://reurl.cc/xgORzE)

👨‍💼 假設你是一名人力主管，要找一個會計，你們這家公司家大業大，共有十萬人來應徵，那歐拉告訴你，你的策略就是先面試 10,000 x 0.37 = 37,000 人，這些人全部打槍不錄取，到 37,001 人之後如果有比前面更優秀的人就直接錄取。 👧 假設女孩的追求者有 10 個人，依據 37% 法則，女孩會對前 4 個追求者全部發好人卡，等到第 5 位之後，若有條件更好的男生出現則直接接受。 🅿️ 我們在找車位的時候也是一樣，總是想要停的離目的地近一點，但是又怕錯過了這個車位之後就沒有了，37% 法則告訴你，假設目前的車位離你的目的地有十分鐘的距離，那當你開到距離目的地 6.3 分鐘以後只要有空車位，你應該馬上停車。 🍽️ 假設你與另一半在逛街、找餐廳，你大約有十間餐廳可以選且不想留下優柔寡斷的印象，最好的策略前三間餐廳只是觀察、不進去，從第四間開始，只要比前三間都好，就近去用餐。 當賣場有 11 個收銀櫃臺，你可以先觀察 4 個收銀櫃檯的排隊長度，接下來只要看到更短的隊伍，就去排那一排。

37% Rule 意涵

最算採取此最佳策略，失敗機率高達 63% (1-0.37=0.63)。絕大多數的狀況你無法找到最佳人選，但最佳停止就是最佳策略，不管有多少人選都適用。 37%法則不一定能讓你的人生找到完美伴侶或是保證找到車位，但是卻是數學家用模型告訴你如何面對一個既期待又怕錯過的未來。

16. 世上有很多人都會跟我們處得不錯，能讓我們有幸福的一生。最佳停止時機的策略，並不會提供所有人生問題的答案。我們雖然可以用演算法來簡化、加速單調乏味的任務，但風險也伴隨而來。因為演算法包含輸入、規則和輸出，也就代表有三個可能錯誤的地方。就算使用者確信所用的規則完全符合需求，只要輸入有誤或輸出不符合規範，就可能導致災難。

17. ​💠​🤖​ 現在的股市交易，已有越來越多是程式交易 (algo trading)，因為面對市場的種種變化，電腦察覺並做出回應的速度遠快於真人。根據估計，Wall Street 的交易已大約有 70% 都是由這種所謂的黑盒子機器來處理。

18. 📉 2010/5/6 美股遭到閃電崩盤 (flash crash)，電腦股票系統被不明原因觸發，連編寫程式的人也不了解電腦做的交易。道瓊工業指數在 5 分鐘內下跌近 600 點，電腦間在 15 秒內互相交易 27,000 份期貨合約，最終因期貨市場內建的保護機制，將所有交易中止 5 秒鐘，電腦的瘋狂交易就令人讓人難以置信的恢復正常。電腦的演算法是人撰寫的，電腦沒有常識，只會盲目地買進與賣出，因為這就是它的演算法要求它們做的事情。《Standard Deviations: Flawed Assumptions, Tortured Data, and Other Ways to Lie with Statistics》

📉 2010/5/6 flash crash (https://reurl.cc/DZap3e)

19. Navinder Sarao 在自家臥室就成功操控了股市，正說明用演算法發動惡意攻擊是多麼容易的事。我們太常把演算法視為一系列公正、不帶偏見、不受情緒影響的指令，而忘了所有演算法背後都隱藏著一開始研發的目的。

20. 即使演算法事前定義，在執行時也公正不阿，但即使設計者確實抱持公正的初衷，也不代表當初設計的目的完全不帶偏見。規則是人訂的，無論有心或無意，程式設計師都可能把自己的偏見帶進演算法本身，寫成程式後，令人一時看不出那就是先入為主的偏見。

21. 華盛頓郵報引述的內部文件揭露，臉書的排名演算法自 2017 年開始，將「怒」等表情符號回應的價值視為比「讚」高出 5 倍。背後理論很簡單，激起很多情緒符號的貼文往往會確保用戶提高參與，而確保用戶參與率對臉書有極大好處。報導更指出，演算法推廣的力量則破壞了內容審查員及操守團隊對抗有毒及有害內容的努力。臉書前產品經理兼「揭弊者」Frances Haugen 告訴英國議會，「憤怒與仇恨是臉書上最簡單的增長方式」。(https://reurl.cc/mvabnA)

22. 隨著演算法日益複雜，輸出結果也越來越難以預測，所以需要加強控制與人為監督。然而這些控制與人為監督，絕不只是科技龍頭企業的責任。身為這些科技龍頭企業的 end user，也須負起部分責任，判斷自己得到的 output 真實無偽，例如：❶ 📰 對於自己讀到的新聞，是否要相信此消息來源？❷ 🛰️ 對於汽車導航的建議路線，是否要照著走？

[閱讀筆記] The Math of Life and Death - ㊄ 錯的地方、錯的時間：數字系統如何演變、又如何讓我們失望 (Wrong Place, Wrong Time: When Our Number Systems Let Us Down)

 

1. 我們目前使用的是「十進位制位值系統」(decimal place value system)，所謂的「位值」(place value) 是指，不同位置的數字代表不同的數值；而「十進位」是指，同一個數字放在相鄰位置，代表的數值會比隔壁大或小十倍。不同位置間的相乘係數稱為進位基數，在十進位就是 10。

2. 🖐️🖐️人類會廣泛採用十進位，而非其他進位，理由很簡單，我們要計數時，就是用十根手指來計數。

3. 古羅馬系統的數字系統較為原始，共有七個符號如下表。古羅馬人意識到自己的數字系統效率低落，因此規定數字永遠要由左而右寫，從最大小到最小，這樣就能方便做數字加總。例如，MMXV = 1000 + 1000 + 10 + 5 = 2015；1888 年完成的波士頓公共圖書館，就刻著 MDCCCLXXXVIII ( = 1000 + 500 +100 +100 +100 + 50 + 10 +10 +10 + 5 + 1 +1 +1，足足有 13 個字元，是上個千禧世代最長的羅馬數字。

符號	I	V	X	L	C	D	M
數字	1	5	10	50	100	500	1000

4. 雖然羅馬數字的使用歷史悠久，佔有優勢，但這套符號系統過於複雜，不利於高等數學的發展，因而從未通行世界。事實上，羅馬帝國的一項著名事蹟，就是沒有傑出的數學家，對數學研究沒有什麼貢獻。

5. 六十進制是以 60 為底數的進位制，源於公元前三千年至公元前兩千年的蘇美人，後傳至巴比倫，流傳至今仍用作紀錄時間、角度和地理座標。(https://reurl.cc/bnQAby)

六十進制的應用

主要用以計算角度、座標，最常運用在時間計算上，60秒為一分，60分為一秒，但是在計算細部時仍是依照十進位計算。例如，"3:23:17"（三小時廿三分十七秒）即相當於3×602+23×601+17×600秒或3×600+23×60−1+17×60−2小時。當中的六十進制數字（即3、23和17）均以十進制數字寫出。 相類似的是角度，一個圓形被均分成 360 度，每一度有 60 角分，一角分等於 60 角秒。

六十進制的優點

由於 60 含有 2 、3 和 5 三個質因子，六十進制的數可被較多數整除，使得許多分數在該進制下是有限小數。例如，在分配貨幣時， 60 shekel 要分給 2 、 3 、 4 、 5 、 6 、 10 、 12 、 15 、 20 、 30 人，都能剛好分完，不會產生爭議。 先進的 60 進位位值系統，讓蘇美人能做高等數學運算，像是解二次方程式 (ex. 分配農地的時候會遇到) 和三角函數。

巴比倫人繼續發揚光大

📐 巴比倫人掌握一定的幾何知識，會把不規則的田地分成不同的長方形、三角形和梯形來計算面積。他們還掌握畢達哥拉斯定理，求得圓周和直徑的比率是3。在代數上，他們能解開三個未知數的方程式。 貿易的需要，巴比倫人還制定了重量、長度、面積、體積、貨幣等的計算單位。古巴比倫人是古代最有成就的數學家。巴比倫人的幾何學也同樣取得了令人驚嘆的成就。(https://reurl.cc/95eagx)

6. 我的兩個小孩讓我學到一項痛苦的教訓，分東西的時候一定要公平。我敢打包票，他們寧願兩個人都只有一個糖果，也不希望自己有 5 個、對方有 6 個。 如果你是以兒童為重點的產品製造商，以 12 個為一組的賣法就能讓客群最大化、也最不容易惹惱客戶，無論是要應付 1 、 2 、 3 、 4 、 6 、 12 個孩子的家庭都沒問題。

7. 一如蘇美人用的 60 進位，十二進位優於十進位的主因，在於有更多的分數能夠「漂亮的終結」。例如，十進位制裡，1/3 會變成麻煩的無限小數 0.33333；十二進位裡，1/3 就是 4/12，小數寫成 0.4。十二進位制的擁護者認為，這套制度能減少四捨五入的必要性，解決許多目前十進位制所引起的捨入誤差 (rounding error)。(https://reurl.cc/NZk1eQ)

捨入誤差 (rounding error) 例子

🚀 1990年2月25日，海灣戰爭期間，在沙烏地阿拉伯宰赫蘭的愛國者飛彈防禦系統因浮點數捨入錯誤而失效，該系統的計算機精度僅有24位，存在0.0001%的計時誤差，所以有效時間闕值是20個小時。當系統運行100個小時以後，已經積累了0.3422秒的誤差。這個錯誤導致飛彈系統不斷地自我循環，而不能正確地瞄準目標。結果未能攔截一枚伊拉克飛毛腿飛彈，飛毛腿飛彈在軍營中爆炸，造成28名美國陸軍死亡。

🚀 1996年6月4日，在亞利安五號運載火箭發射後37秒，偏離預定軌道而炸毀。原因是軟體系統試圖將64位浮點數轉換為16位浮點數，造成溢出錯誤。

📉 1982 年溫哥華證券交易所指數剛成立不久，雖然市場表現強勁，指數卻有近兩年的時間持續暴跌。原因在於每次交易後，指數會無條件捨棄到小數點第三位，所以指數一直減少。當時每天有 3000 筆交易，就讓溫哥華證券交易指數每個月下跌 20 點，22個月以後，指數的值是 524.881，然而事實上應該是 1009.811。

8. 千禧蟲危機 (Year 2000 Problem, Y2K) 是指由於電腦程式設計的一些問題，使得電腦在處理2000年1月1日以後的日期和時間時，可能會出現不正確的操作，從而可能導致一些敏感的工業部門 (比如電力，能源) 和銀行，政府等部門在2000年1月1日零點工作停頓甚至是發生災難性的結果。🏥 位於英國 Northern General Hospital 的唐氏症檢測中心，其 PathLAN 系統就是因為沒修復 Y2K 而導致憾事發生。

PathLAN 系統唐氏症檢測流程

因 Y2K 造成生日計算錯誤，導致偽陰性與憾事發生

9. 二進制 (binary)

二進制說明

在數學和數位電路中指以 2 為底數的記數系統，以 2 為基數代表系統是二進位制的。這一系統中，通常用兩個不同的數字 0 和 1 來表示。數字電子電路中，邏輯閘直接採用了二進制，因此現代的計算機和依賴計算機的裝置裡都用到二進制。 ptt joke: 「世界上只有 10 種人，一種懂二進位、一種不懂」意思就是「 1 乘 2 的 1 次方 ＋ 0 乘 2 的 0 次方 ＝ 2」這個 10 不是用十進位、而是用二進位去解讀的。(https://reurl.cc/yepOZl)

二進制造成的麻煩

在波灣戰爭，愛國者導彈系統所使用的時間單位是 1/10 秒，雖然 1/10 用十進位制寫起來是簡潔有力的 0.1，但是轉成二進制後，卻變成無限循環小數 0.001100110011...，在 0.0 之後不斷重複 0011。由於沒有任何系統可以儲存無限多位的數字，所以飛毛腿系統只儲存 24 位數，因而產生捨入誤差 (rounding error) ，飛毛腿飛彈在軍營中爆炸，造成28名美國陸軍死亡。 無論使用任何基數，都不能只用有限的位數就表達所有數字。如果採用不同基數，或許可以避免此次愛國者飛彈系統問題，但絕對會造成其他錯誤。雖然電腦系統常因二進位制而造成錯誤，但有鑑於耗能與可靠度上的優勢，二進位制仍是電腦最合理的選擇。然而，在現實社會使用二進位制，就會發現此優勢不存在。