聽到“算法”（algorithm）一詞漂羊，第一反應(yīng)可能跟計算機有關(guān)，但其含義遠(yuǎn)不限于計算機卸留，存在的歷史也遠(yuǎn)遠(yuǎn)長于計算機走越。”算法“一詞得名于波斯數(shù)學(xué)家花剌子密耻瑟。公元9世紀(jì)旨指，這位數(shù)學(xué)家寫過一本書，討論用紙筆解決數(shù)學(xué)問題的技巧喳整。［書名為“al-Jabr wa’l-Muqabala”谆构，其中的“al-jabr”就是后來“algebra”（代數(shù)）這個詞的前身。］
尤瓦爾·赫拉利在《未來簡史》中寫道：“算法指的是進行計算算柳、解決問題低淡、做出決定的一套有條理的步驟。 人類有99%的決定瞬项，包括關(guān)于配偶蔗蹋、事業(yè)和住處的重要抉擇，都是由各種進化而成的算法來處理囱淋，我們把這些算法稱為感覺猪杭、情感和欲望"。
《算法之美》講的正是在我們?nèi)粘５纳詈凸ぷ髦型滓拢瑢ξ覀冇兄笇?dǎo)意義的算法皂吮。
一戒傻、
最優(yōu)停止理論：如何選擇停止觀望的時機？
最優(yōu)停止問題的權(quán)威教科書開宗明義地指出：“最優(yōu)停止理論關(guān)注的是如何選擇時機以執(zhí)行特定行動的問題蜂筹⌒枘桑”
是沖動早早停止觀望，還是多慮繼續(xù)觀望艺挪？這需要達(dá)成某種平衡不翩，平衡概念正是解決這類問題的關(guān)鍵，但是大多數(shù)人根本無法確定這個平衡點在哪里麻裳？
算法告訴我們”37%法則“正是我們要的答案口蝠。
“37%法則”源于所謂的“秘書問題”—最優(yōu)停止問題中最著名的一類難題。秘書招聘效果最佳的做法是接受所謂的“摸清情況再行動準(zhǔn)則”（look-then-leap rule）：事先設(shè)定一個“觀察”期津坑，在這段時間里妙蔗，無論人選多么優(yōu)秀，都不要接受他（也就是說疆瑰，你的任務(wù)就是考察目標(biāo)眉反，收集數(shù)據(jù)）∧四。“觀察”期結(jié)束之后禁漓，就進入了“行動”期跟衅。此時孵睬，一旦出現(xiàn)令之前最優(yōu)秀申請人相形見絀的人選，就立即出手伶跷，再也不要猶豫了掰读。隨著秘書職位申請人數(shù)不斷增加，觀察與行動之間的分界線正好處在全部申請人37%的位置叭莫，從而得出了37%法則：在考察前37%的申請人時蹈集，不要接受任何人的申請；然后雇初，只要任何一名申請人比前面所有人選都優(yōu)秀拢肆，就要毫不猶豫地選擇他。
經(jīng)典秘書問題的前提條件是靖诗，即時表態(tài)一定會被接受郭怪，而遲滯表態(tài)肯定會遭到拒絕，這樣看來刊橘，秘書問題最基本同時也最令人難以置信的前提條件—嚴(yán)格的連續(xù)性鄙才，即有進無退的單向行進，正好是時間自身屬性的一個體現(xiàn)促绵。就此而言攒庵，最優(yōu)停止問題的這個顯性前提正好就是使其充滿活力的隱性前提嘴纺。這個前提迫使我們基于還沒親眼看到的可能結(jié)果做出決定，迫使我們在采取最優(yōu)策略之后仍然愿意接受非常高的失敗率浓冒。我們永遠(yuǎn)沒有二次選擇的機會栽渴。我們有可能得到類似的選擇機會，但是絕不會得到完全相同的選擇機會稳懒。猶豫不決（不作為）與行為一樣不可改變熔萧。困在單行線上的駕車者與空間的相互關(guān)系就是我們與第四維度的關(guān)系：我們的生命真的只有一次。
我們只能知道孰優(yōu)孰劣僚祷，但是無法了解彼此之間的確切差距佛致。正因為如此，“觀望”階段是不可避免的辙谜。在前期階段俺榆，我們冒著與優(yōu)秀人選失之交臂的危險，不斷調(diào)整我們的期望值與權(quán)衡標(biāo)準(zhǔn)装哆。數(shù)學(xué)家把這種最優(yōu)停止問題稱作“無信息博弈”罐脊。全信息的意義在于我們無須觀望就可以直接出手。此時蜕琴，我們可以運用閾值準(zhǔn)則萍桌，一旦發(fā)現(xiàn)某位申請者的分?jǐn)?shù)高于某個值，就立刻接受她凌简，而不需要先考察一批候選人并確定閾值上炎。
買房子、賣房子雏搂、找工作藕施、找停車位等等問題，均可以看做是一個最優(yōu)停止問題凸郑。
二裳食、
探索和利用：要最新的還是要最好的？
直覺告訴我們芙沥，生活就是在新鮮事物和傳統(tǒng)事物之間诲祸、在最新的和最棒的之間、在勇于冒險和安于現(xiàn)狀之間取得平衡而昨。
羅伯特·波西格在他于1974年出版的經(jīng)典著作《禪與摩托車維修藝術(shù)》中對“有什么新鮮事嗎救氯？”這句寒暄語進行了公開譴責(zé)。他說：“只要認(rèn)真地研究這個問題的話配紫，得到的答案肯定是一堆瑣碎的跟風(fēng)事物径密，等到了明天它們就會失去新鮮勁兒√尚ⅲ”他認(rèn)為另一個問題就要好得多：“最好的是什么享扔？”
50多年來底桂，計算機科學(xué)家一直埋頭鉆研，希望可以在要最新的還是要最好的之間找到這個平衡點惧眠，他們的研究甚至還有一個專門的名稱：探索與利用的取舍籽懦。
英語為“explore”（探索）和“exploit”（利用）這兩個詞賦予了截然相反的含義，但是在計算機科學(xué)家眼中氛魁，它們有很多具體的中性含義暮顺。簡單地說，探索的意思是收集信息秀存，而利用則指利用所擁有的信息捶码，以產(chǎn)生一個好的結(jié)果。
你到底應(yīng)該花費精力去探索新的信息或链，還是專注于從已有的信息中獲得收獲惫恼？關(guān)鍵是時間和度的問題。隨著時間的推移澳盐，即使探索有所發(fā)現(xiàn)挺邀，我們可以認(rèn)真品味這些新發(fā)現(xiàn)的機會也已經(jīng)所剩無幾祠斧，因此探索的價值隨之降低。與之相反尸变，利用的價值隨著時間的推移反而會不斷上升哗总。利用好剩余時間就是正確的應(yīng)對之策琳轿。
“基廷斯指數(shù)（Gittins Index）”為解決探索與利用的取舍的問題提供了方案户侥。
他說剔猿，當(dāng)你計劃出去吃一頓飯的時候，明天那頓應(yīng)該比今天這頓要貶值一點 —— 因為你明天可能會離開這里倾贰，吃不上那頓飯冕碟。具體貶值多少，取決于你預(yù)期還能停留多長時間匆浙。基于這一點厕妖，他提出了一個非常復(fù)雜的解決方案首尼，最后結(jié)果是給每個選項計算了一個指數(shù)，現(xiàn)在被稱為“基廷斯指數(shù)（Gittins Index）”言秸。
“時間貶值率”會極大影響基廷斯指數(shù)软能，總的說來，未來可期并可能有驚喜举畸，則鼓勵嘗試新事物查排；當(dāng)下優(yōu)秀穩(wěn)定而未來不可知，則鼓勵堅持老事物抄沮。
我們希望每一天都活在當(dāng)下跋核，可是從現(xiàn)實的數(shù)學(xué)角度岖瑰，你預(yù)期停留的時間越長，探索新事物的價值就越高砂代，基廷斯指數(shù)也越高蹋订。
一般而言，我們對理性的直覺認(rèn)識常常來源于利用刻伊，而不是探索露戒。當(dāng)我們談?wù)摏Q策過程時，我們通常只關(guān)注某個決定的即時回報——如果你把每一個決定都當(dāng)作人生的最后一個決定捶箱，那么只有利用才是有意義的智什。但在一生中，你會做出很多決定丁屎。實際上撩鹿，在做很多決定時，理性的做法是強調(diào)探索的重要性悦屏，重視新的東西而不是最好的東西节沦，重視令人為之興奮的東西，而不是一味追求安全础爬，重視隨機選擇甫贯，而不是深思熟慮的決定。在人生早期看蚜，更應(yīng)該如此叫搁。如果我們把期限設(shè)定為人的一生，這就意味著年輕人應(yīng)該多探索供炎，到了后期就要專注于收獲渴逻。
斯坦福大學(xué)心理學(xué)教授勞拉·卡斯滕森通過自己的研究，對人們在衰老這個問題上的成見提出了質(zhì)疑音诫。她特別研究了人們的社會關(guān)系隨著年齡增長而發(fā)生變化的過程與原因惨奕。這種變化有一個明晰的基本模式：人們社交網(wǎng)絡(luò)的規(guī)模（即與他們保持社交關(guān)系的人數(shù)）幾乎總是隨著時間的推移而減少。不過竭钝，卡斯滕森的研究表明梨撞，我們應(yīng)該改變對這個現(xiàn)象的看法∠愎蓿卡斯滕森認(rèn)為卧波，老年人的社會關(guān)系越來越簡單，是他們主觀選擇的結(jié)果庇茫。由此可見港粱，社交偏好的這些差異與年齡本身無關(guān)，而是與人們對決策過程中剩余時間的認(rèn)知有關(guān)旦签。
基廷斯指數(shù)以一種正式查坪、嚴(yán)謹(jǐn)?shù)男问酱绾辏C明了在有機會對探索結(jié)果加以利用時，我們應(yīng)該傾向于選擇未知的新事物咪惠。
如果你認(rèn)為基廷斯指數(shù)太復(fù)雜击吱，或者你所處的情況并沒有表現(xiàn)出幾何貼現(xiàn)的特征，那么你還有另一個選擇—關(guān)注遺憾遥昧。自黎子良覆醇、羅賓斯之后，研究人員在過去幾十年里一直致力于尋找可以確保遺憾最少化的算法炭臭。在他們提出的算法當(dāng)中永脓，最受歡迎的就是上限置信區(qū)間算法。上限置信區(qū)間算法所采用的原理有一個綽號——“面對不確定性時的樂觀主義”鞋仍。
三常摧、
排序問題
1955年，詹姆斯·霍斯肯在第一篇公開發(fā)表的關(guān)于排序的科學(xué)論文中寫道：“為了降低單位產(chǎn)出的成本威创，人們通常會增加他們的業(yè)務(wù)規(guī)模落午。”這是任何一名商科學(xué)生都很熟悉的規(guī)模經(jīng)濟肚豺。但是溃斋，在排序這個問題中，規(guī)模往往會招致災(zāi)難：如果擴大排序的規(guī)模吸申，“排序的單位成本就會不降反升”梗劫。排序往往呈現(xiàn)非常明顯的規(guī)模不經(jīng)濟現(xiàn)象，這與普通人認(rèn)為大批量處理問題有諸多好處的直覺正好相反截碴。
這是排序理論的第一個梳侨，也是最基本的深刻見解：規(guī)模越大，難度越大日丹。
據(jù)統(tǒng)計走哺，世界上計算機資源的很大一部分被用于排序，難怪排序?qū)τ谔幚韼缀跞魏晤愋偷男畔碚f都是至關(guān)重要的聚凹。排序的主要原因之一是將內(nèi)容變成方便人眼觀察的形式割坠，這意味著排序也是人類信息體驗的關(guān)鍵。
信息處理開始于19世紀(jì)的美國人口普查妒牙，是由赫爾曼·霍爾瑞斯及后來的IBM公司根據(jù)實體打孔卡排序設(shè)備開創(chuàng)形成的。
當(dāng)我們知道被排序的不僅是信息对妄，其實還有人湘今，因此學(xué)會排序有助于理解人類可以和諧相處，偶爾才會拳腳相向的原因剪菱。所謂社會摩瞎，就是我們維持的另外一種更重要拴签、規(guī)模更大的秩序。
但是旗们，要回答如何排序蚓哩、哪種排序方法效果最佳這個問題，就需要先弄明白另外一個問題：如何計分上渴？
計算機科學(xué)有一種專門用來測量算法最壞情況的速記法岸梨，即所謂的“大O”符號。大O符號有一個非常奇怪的特點——設(shè)計這個符號的目的就是用來表示不精確性稠氮。也就是說曹阔，大O符號的目的不是使用分鐘和秒鐘來表示算法的性能，而是方便我們討論問題規(guī)模和程序運行時間之間的關(guān)系隔披。由于大O符號故意剔除了細(xì)枝末節(jié)的內(nèi)容赃份，所以展示給我們的是將問題分成不同大類的概略情況。
假設(shè)你準(zhǔn)備邀請n名客人出席晚宴奢米。在客人到來之前抓韩，打掃房間的時間與來客人數(shù)沒有任何關(guān)系。這類問題最簡單鬓长，被稱為“O（1）”谒拴，也被稱為“常數(shù)時間”。接下來痢士，烤肉在所有客人面前傳遞一圈所需的時間將是“O（n）”彪薛，也被稱為“線性時間”——客人增加一倍，菜傳遞一圈所需的時間就會增加一倍怠蹂。假設(shè)客人到來之后善延，你要與每個人熱烈擁抱，情況又會怎么樣城侧？第一個到達(dá)你家的客人與你擁抱易遣，第二個客人需要擁抱兩次，第三個客人要擁抱三次嫌佑。此時豆茫，擁抱一共發(fā)生了多少次？這種情況屬于“O（n2 ）”屋摇，也稱“平方時間”揩魂。如果沒增加一位客人都會讓你的工作加倍，那么就會有“指數(shù)時間”炮温，記做“O(2的n次方)火脉。
假設(shè)你希望將雜亂無序的藏書按照字母順序進行分類排序。那么你會很自然地想到一個方法，于是你在書架前巡視倦挂，看到有兩本書顛倒了先后次序畸颅，就把它們調(diào)換過來（例如，將品欽的小說放在華萊士后面）方援。在將品欽放到華萊士前面之后没炒，你繼續(xù)巡視。走到書架最后端之后犯戏，你就會回過頭來送火，從書架最前端重新開始。如果從頭走到尾笛丙，都沒有看到有哪兩本書次序不對漾脂，就說明你完成了這項工作。 這就是冒泡排序胚鸯，它會把我們帶進平方時間骨稿。
你可能會采取另外一種方法，即把所有的書都從書架上拿下來姜钳，然后一本一本放到合適的位置坦冠。你把第一本書放在書架中間，然后拿第二本書和第一本比較哥桥，根據(jù)比較結(jié)果把它插到第一本的右邊或者左邊辙浑。在放第三本書時，你先從左到右瀏覽書架拟糕，然后把它放到合適的位置判呕。你不斷重復(fù)這個過程，漸漸地所有的書都被按次序放到書架上送滞，直到你最終完成這項工作侠草。 計算機科學(xué)家們給這種方法起了一個非常貼切的名稱——“插入排序”
插入排序比冒泡排序更直觀，但實際上它不比冒泡排序快多少犁嗅，但仍然是處于平方時間边涕。是否有打破平方時間的算法，答案是肯定的褂微，就是分治算法功蜓。
1945年，約翰·馮·諾伊曼為了展示存儲程序計算機的威力宠蚂，編寫了一個程序式撼。在這個程序的最終結(jié)論中，就包含有比較的概念求厕。為兩張牌排序很簡單端衰，把較小的那張牌放在上面就可以了叠洗。如果有兩疊牌甘改，每疊包含兩張排好序的牌旅东，我們可以很容易地將這四張牌整理成排好序的一疊牌。重復(fù)幾次十艾，就可以整理出越來越多且排好序的牌垛抵代。很快，你就可以把完整的一副牌整理得井然有序忘嫉。在最后一次合并時荤牍，你可以通過與交錯式洗牌非常相似的手法，將撲克牌整理出你需要的次序庆冕。 這種方法現(xiàn)在被稱作“合并排序”康吵，是計算機科學(xué)中的傳奇算法之一。正如1997年的一篇論文所指出的：“合并排序在排序歷史中的重要地位與排序在計算歷史中的重要地位旗鼓相當(dāng)访递』耷叮¤” 合并排序威力巨大，是因為它的復(fù)雜程度位于線性時間和平方時間之間拷姿。具體來說惭载，O（n log n）被稱為“線性對數(shù)”時間。
從某種非常重要的意義上看响巢，合并排序算法給出的O（n log n）線性對數(shù)時間肯定是我們可以得到的最佳效果描滔。已經(jīng)有人證明，如果通過一系列面對面直接比較的方法對n個事物進行完全排序踪古，比較的次數(shù)不可能少于O（n log n）含长。這是一條普世法則，是不可能違背的伏穆。 但是拘泞，嚴(yán)格說來，這條法則并不能平息排序問題上的所有爭議蜈出。有的時候我們并不需要完全排序田弥，有的時候根本不需要逐項比較也能完成排序工作。正是因為有這兩個原因铡原，實踐中的粗略排序速度也可以比線性對數(shù)時間快偷厦。桶排序算法非常漂亮地展現(xiàn)了這個特點 。在桶排序中燕刻，排序?qū)ο蟀凑张判蝾悇e分成若干組只泼，類別之間更精細(xì)的排序問題，在分組時不予考慮卵洗，留待后面解決请唱。(在計算機科學(xué)中弥咪，"桶“這個術(shù)語表示一組未排序的數(shù)據(jù)）。
排序是搜索的準(zhǔn)備工作十绑，而排序與搜索之間的取舍是最重要的取舍問題之一聚至，其基本原理是：人們投入精力為物品排序是一種先發(fā)制人的措施，目的是保證以后無須在搜索上投入精力本橙。平衡點應(yīng)該如何確定扳躬，取決于當(dāng)時情況的具體參數(shù)，但是甚亭，如果認(rèn)為排序的價值僅僅是為未來的搜索提供支持贷币，那么你會有一個令人吃驚的發(fā)現(xiàn)：混亂無序也無傷大雅！隨著計算機搜索成本的降低亏狰，排序的價值也隨之降低役纹。
排序問題在體育比賽，動物世界的啄食順序和優(yōu)勢等級暇唾，以及比如船舶海上通行權(quán)之類的問題得以應(yīng)用促脉。船舶海上通行權(quán)在理論上需要遵循一套極其復(fù)雜的慣例，但是在實踐中信不，到底哪條船應(yīng)該給另一方讓路是由“總噸位法則”這條簡單易行的原則決定的嘲叔。
四、
緩存問題
1946年抽活，亞瑟·伯克斯硫戈、赫爾曼·戈德斯坦和約翰·馮·諾依曼在普林斯頓高級研究所展開合作，為他們所謂的“電子記憶器官”起草了一個設(shè)計方案下硕。他們寫道丁逝，在一個理想的世界里，機器當(dāng)然可以有無限量的快速儲存能力梭姓，但在實踐中這是不可能的霜幼。（現(xiàn)在仍然不可能。）于是誉尖，這三個人退而求其次罪既，提出了“分級存儲器體系，每一級的存儲能力都超過以前铡恕，但是讀取速度有所減慢”琢感。
在1962年超級計算機阿特拉斯在英國曼徹斯特問世以前，計算領(lǐng)域的這種“分級存儲”概念一直停留在理論層面探熔。
阿特拉斯問世之后不久驹针，劍橋大學(xué)數(shù)學(xué)家莫里斯·威爾克斯意識到，這種體積較小诀艰、速度較快的存儲器不僅可以為我們處理數(shù)據(jù)柬甥、將處理好的數(shù)據(jù)存回主存儲器提供了一個非常方便的場所饮六，還可以用來有意地保留稍后可能需要使用的信息片段，為后期類似的需要做好準(zhǔn)備苛蒲，從而極大地加速機器的操作卤橄。如果所需要的數(shù)據(jù)仍然保留在工作存儲器中，就不必再到主存儲器中裝載這些數(shù)據(jù)了撤防。威爾克斯認(rèn)為虽风，這種體積較小的存儲器“可以自動收集并保存來自速度較慢的主內(nèi)存的數(shù)據(jù)，為后期使用做好準(zhǔn)備寄月，從而免除了再次訪問主存儲器帶來的麻煩”。20世紀(jì)60年代末无牵，威爾克斯的提議在IBM 360/85超級計算機中得以實現(xiàn)漾肮，人們稱之為“緩存”。
我們知道茎毁，IBM在20世紀(jì)60年代率先推動緩存系統(tǒng)的部署應(yīng)用克懊。不出意料，它也是早期緩存算法開創(chuàng)性研究的發(fā)源地七蜘，也許他們?nèi)〉玫娜魏我豁棾晒紱]有拉斯洛·貝萊迪的算法重要谭溉。貝萊迪于1966年發(fā)表的那篇緩存算法論文是隨后15年里被引用最多的計算機科學(xué)研究成果。這篇論文解釋道橡卤，緩存管理的目標(biāo)是盡可能減少“頁面錯誤”或“緩存缺失”扮念。所謂緩存缺失，是指無法在緩存中找到所需數(shù)據(jù)碧库，因此只能到較慢的主存中查找的現(xiàn)象柜与。貝萊迪在文中寫道，從本質(zhì)上講嵌灰，最優(yōu)緩存清理策略就是在緩存已滿時弄匕，將未來最長時間內(nèi)不會再次使用的數(shù)據(jù)從緩存中清理出去。今天沽瞭，為了表示敬意迁匠，人們把那個無所不知、有先見之明驹溃，而且可以在分析未來情況基礎(chǔ)上執(zhí)行最優(yōu)緩存策略的那個假想算法稱作貝萊迪算法城丧。
我們可以嘗試隨機清理算法，將新數(shù)據(jù)添加到緩存中吠架，并隨機覆蓋舊數(shù)據(jù)芙贫。隨機清理是早期高速緩存理論得出的一個令人吃驚的結(jié)果，雖然遠(yuǎn)非完美傍药，但是效果也還不錯磺平。這也可能是一種巧合魂仍，因為只要有一個緩存，無論你如何維護拣挪，都可以提升系統(tǒng)的效率擦酌。不管怎么說，你經(jīng)常使用的內(nèi)容通常還會很快回到緩存中菠劝。另一種簡單的策略叫作先進先出（FIFO）赊舶。這種算法總是清理或覆蓋在緩存中保存時間最久的內(nèi)容（與瑪莎·斯圖爾特問的“我已擁有它多長時間了”這個問題有異曲同工之妙）。第三種方法是最近最少使用（LRU）赶诊，即將閑置不用時間最長的內(nèi)容清理掉（與之相對應(yīng)的斯圖爾特的問題是“上次穿它或使用它是什么時候的事”）笼平。
貝萊迪在若干情形下對隨機清理、先進先出和最近最少使用的幾個變體進行了比較舔痪，結(jié)果發(fā)現(xiàn)最近最少使用法始終表現(xiàn)出最接近未卜先知的效果寓调。最近最少使用法的高效性得益于計算機科學(xué)家所謂的“時間局部性”：如果一個程序曾經(jīng)調(diào)用過某個信息，那么在不久的將來它可能會再次調(diào)用這個信息锄码。
如果你能創(chuàng)建一個網(wǎng)頁內(nèi)容緩存夺英，其實際地理位置更接近那些有需要的人，你就可以更快地為他們提供頁面服務(wù)滋捶⊥疵酰互聯(lián)網(wǎng)上的大部分流量現(xiàn)在都是由“內(nèi)容分配網(wǎng)絡(luò)”來處理的，這些網(wǎng)絡(luò)利用遍布世界各地的電腦維護流行網(wǎng)站的拷貝重窟。因此载萌，在用戶請求使用這些頁面時，他們可以從附近的一臺計算機獲取數(shù)據(jù)亲族，而不必跨越千山萬水炒考，連接到原始服務(wù)器上。
最近霎迫，亞馬遜獲得了一項創(chuàng)新的專利斋枢，使它奉行的這條原則得到了進一步發(fā)展。在媒體看來知给，這項“可預(yù)期包裹配送”專利似乎可以幫助亞馬遜在你下單之前就把商品送到你的手上瓤帚。有人下訂單時，商品就已經(jīng)在他附近的大街上了涩赢。預(yù)測個人購買行為是有挑戰(zhàn)性的戈次，但是當(dāng)預(yù)測數(shù)千人的購買行為時，大數(shù)定律就會生效筒扒。
迄今為止怯邪，我們見過的所有家居管理建議中，必不可少的一個“郴ǘ眨客”就是“物以類聚”這個存放概念悬秉。也許沒有人會像野口由紀(jì)夫那樣直言不諱地反對這條建議澄步。他說：“我必須強調(diào)，在我的方法中和泌，一個基本原則就是不能把文件根據(jù)內(nèi)容分組村缸。”一旦認(rèn)識到野口文件歸檔系統(tǒng)是最近最少使用原則的一個實例武氓，我們就知道它不僅是一種有效策略梯皿，實際上還是最優(yōu)策略。
1987年县恕，卡內(nèi)基-梅隆大學(xué)的心理學(xué)家东羹、計算機科學(xué)家約翰·安德森為了解大學(xué)圖書館的信息檢索系統(tǒng)，查閱了大量資料弱睦。他的目標(biāo)百姓，或者說他自認(rèn)為的目標(biāo)，是弄清楚信息檢索系統(tǒng)的設(shè)計是否可以從人類記憶研究那里獲取靈感况木。結(jié)果，他發(fā)現(xiàn)現(xiàn)實正好相反：信息科學(xué)有可能為人類大腦研究填補某些空白旬迹。在安德森對人類記憶的新描述中火惊，其核心思想是，需要解決的可能不是存儲問題奔垦，而是如何組織的問題屹耐。他認(rèn)為，大腦的記憶能力基本上是無限的椿猎，但我們在大腦中搜索的時間是有限的惶岭。安德森把大腦比喻成圖書館，不過這個圖書館只有一個無限長的書架犯眠，也就是說按灶，是一個美國國會圖書館級別的野口文件歸檔系統(tǒng)。你可以在那個書架上放無數(shù)本書筐咧，但是鸯旁，書的位置越靠近前面，就越容易被找到量蕊。
如果記憶面臨的基本問題真的是一個組織管理的問題铺罢，而不是存儲問題，那么我們在衰老影響心智能力這個問題上的看法就應(yīng)該改變残炮。最近韭赘，圖賓根大學(xué)的邁克爾·瑞姆斯卡率領(lǐng)一組心理學(xué)家和語言學(xué)家完成了一項研究，結(jié)果發(fā)現(xiàn)势就，所謂的“認(rèn)知能力衰退”（滯后和檢索錯誤）可能并不表明搜索過程變慢或者搜索能力退化泉瞻，而是我們所面對的信息量不斷變大所帶來的一個不可避免的后果（至少是原因之一）脉漏。不管衰老還會帶來什么樣的難題，年長的大腦必須管理數(shù)量更多的記憶存儲瓦灶，因此鸠删，它其實每天都在解決更復(fù)雜的計算問題。面對反應(yīng)速度更快的年輕人贼陶，老年人可以不屑一顧地說：“這是因為你什么都不知道刃泡！”
五、
時間調(diào)度理論：要事先行
“科學(xué)管理理論”提出者弗雷德里奇?泰勒碉怔，利用他的同事亨利?甘特的創(chuàng)意（甘特圖）烘贴，將調(diào)度編程一種研究對象，他們富裕它視覺和概念的形式撮胧。但是桨踪，甘特圖沒有解決一個基本問題，到底怎樣安排日程是最好的芹啥？直到幾十年之后的1954年锻离，蘭德公司的數(shù)學(xué)家塞爾默·約翰遜在他發(fā)表的一篇論文里才第一個暗示這一問題可以被解決。約翰遜的研究揭示了更深層次的兩點內(nèi)容：第一墓怀，時序安排可以通過算法表達(dá)汽纠；第二，存在最優(yōu)時序安排方案傀履。這引發(fā)了一項龐大的研究虱朵，為大量假定工廠中不同數(shù)量和種類的機器運行提供策略。
約翰遜的理論是基于最小化雙機共同工作時間來降低總時間钓账，在單機調(diào)度的情況下碴犬，如果我們要完成所有工作，那么所有的安排都應(yīng)該用同樣長的時間完成梆暮，與先后順序無關(guān)服协。因此，單機調(diào)度的第一堂課是：明確你的目標(biāo)惕蹄。我們只有知道如何保持得分才能宣布哪種安排最好蚯涮。由此產(chǎn)生以下幾種研究理論：
1）如果你要降低最大延遲時間，那么最佳策略就是你先從截止日期最近的任務(wù)開始卖陵，再以此類推逐漸執(zhí)行遭顶。這一策略被直觀地稱為最早到期日原則。
2）將完成時間總和最小化可以引申出一個非常簡單的優(yōu)化算法——最短加工時間：總是先做能最快完成的任務(wù)泪蔫。事實上棒旗，在面對不確定性時，最短加工時間的加權(quán)版本是一種最通用的調(diào)度策略。它提供了一個簡單的時間管理方法：每接到一件新工作時铣揉，通過其將耗費的時間來對其進行重要性的劃分饶深。如果該重要性高于當(dāng)前正在執(zhí)行的任務(wù)，就切換到新任務(wù)逛拱，不然就堅持當(dāng)前任務(wù)敌厘。?
計算機科學(xué)能給我們提供用單機調(diào)度的運用不同度量標(biāo)準(zhǔn)的最優(yōu)算法，但選擇哪種度量標(biāo)準(zhǔn)就取決于自己朽合。這為我們提供了一種激進的方法來重新思考“拖延”這一時間管理的經(jīng)典問題俱两。我們通常認(rèn)為拖延是一種錯誤的算法，但如果它正好相反呢曹步？如果它是一個錯誤問題的最佳解決方案呢宪彩？
重點不只是要把事情做好，更重要的是把權(quán)值更高的事情做好-在每一時刻做好最重要的工作讲婚，這聽起來像是治愈拖延癥的一個行之有效的方法尿孔，但僅僅這樣還不夠。
優(yōu)先反轉(zhuǎn)和優(yōu)先繼承理論表明筹麸，想把事情做好的熱情不足以避免調(diào)度上的陷阱活合，光有把重要事情做好的熱情也不夠，要承諾堅持做你所能做的最重要的事情物赶。
有時候芜辕，最重要的事情要等不重要的事情完成之后才能進行。當(dāng)某個任務(wù)在另一個任務(wù)完成之前無法啟動時块差，調(diào)度理論家稱之為“優(yōu)先約束”。
六倔丈、
貝葉斯法則憨闰，預(yù)測未來
谷歌的研究部主任彼得·諾維德曾進行過一次題為“數(shù)據(jù)的不合理有效性”的著名演講，該演講深究了“數(shù)十億瑣碎的數(shù)據(jù)點最終如何能被理解”瘟忱。媒體不斷告訴我們勾习，我們生活在一個“大數(shù)據(jù)時代”摹闽，計算機可以篩選這數(shù)十億的數(shù)據(jù)點并發(fā)現(xiàn)一些肉眼看不到的細(xì)節(jié)。但跟日常生活聯(lián)系最密切的問題往往是另一種極端泽示。我們的生活充滿“小數(shù)據(jù)”，我們就像看到柏林墻的戈特一樣蜜氨，也就是通過一個單一的觀察械筛，做一個推論。
以中彩票或賭博為例飒炎。
貝葉斯的關(guān)鍵見解是埋哟，試圖使用我們看到的中獎和未中獎彩票來分析彩票來源于整體彩票池的方法，本質(zhì)上是在倒推郎汪。他說赤赊，要做到這一點闯狱，我們需要先用假設(shè)向前推理。換句話說抛计，我們首先需要確定哄孤，如果各種可能場景都成真的情況下，我們中獎的可能性有多少吹截。這個被現(xiàn)代統(tǒng)計學(xué)家稱為“可能性”的概率給了我們解決問題所需要的信息瘦陈。
他表示，如果我們提前真的不知道彩票的情況饭弓，然后當(dāng)我們第一次買的三張彩票中的一張彩票中獎了双饥，我們可以推測獎池里彩票的總中獎比例為2/3。如果我們買三張彩票弟断，都中獎了咏花，那我們可以推測總中獎比例正好是4/5。事實上阀趴，如果買n張彩票共w張中獎昏翰，那么中獎率就是中獎數(shù)加1，除以所購買的數(shù)目加2刘急，即棚菊。 這種令人難以置信的簡單的方法估計概率的簡單方法被稱為拉普拉斯定律，它很容易就能適用于任何你需要通過歷史事件來評估概率的情況叔汁。拉普拉斯定律的精髓就在于無論我們有一個單獨的數(shù)據(jù)點或數(shù)以百萬計的數(shù)據(jù)统求，它都同樣適用。
描述這種關(guān)系的數(shù)學(xué)公式据块，將我們先前持有的觀念和我們眼前的證據(jù)結(jié)合起來码邻，就形成了后來的貝葉斯法則。有點兒諷刺的是另假，真正重要的工作卻是由拉普拉斯完成的像屋。它提供了一個非常簡單的解決方案來如何處理現(xiàn)有的信念與觀察到的證據(jù)：將它們的概率相乘。每個假設(shè)的概率都是真實可能的边篮，這就是所謂的先驗概率己莺，或者簡稱為“先驗”。貝葉斯法則總是需要一些先驗戈轿，即使它只是一個猜測凌受。
理查德?戈特三世在1969年針對柏林墻倒塌的預(yù)測時設(shè)想，他到達(dá)柏林墻時的那一刻并不特殊凶杖，如果有任何一個時刻都有同樣的可能性胁艰，那么平均來講，他的到來應(yīng)該是在一個精確的中間點。如果我們假設(shè)我們到達(dá)的中間點有精確的時間腾么，那么對于它在未來還可以持續(xù)多久的最佳猜測就變得很明顯：確切地說就是它已經(jīng)存在的時間奈梳。這個簡單的推理，被戈特稱為“哥白尼原則”解虱，因為哥白尼400年前曾經(jīng)問道：我們在哪攘须？
哥白尼原則是應(yīng)用貝葉斯法則無信息先驗的結(jié)果，應(yīng)用貝葉斯法則殴泰，我們首先需要給每個現(xiàn)象的持續(xù)時間分配一個先驗概率于宙。在認(rèn)識到哥白尼原則是無信息先驗基礎(chǔ)上的貝葉斯法則之后，就可以回答很多關(guān)于其有效性的問題悍汛。哥白尼原則在我們什么都不知道的情況下似乎是合理的捞魁、準(zhǔn)確的，如在1969年看到的柏林墻离咐，我們不確定什么時間范疇是合適的谱俭。同時，在我們對某一對象的確有所了解時宵蛀，就會感覺這是完全錯誤的昆著。預(yù)測一個90歲的人能活到180歲是不合理的，這恰恰是因為我們關(guān)于人類壽命已經(jīng)了解了很多——在這種情況下术陶，我們就可以預(yù)測得更好凑懂。我們給貝葉斯法則帶來的先驗信息越豐富，我們便能從中得到越有用的預(yù)測梧宫。
真實世界的先驗接谨。從廣義上將，世界上有兩種類型的事物：傾向于（或圍繞）某種“自然”價值的事物塘匣，以及與之相反的事物疤坝。
比如人的壽命，屬于前一類馆铁，遵循所謂的“正態(tài)分布”，或稱為“高斯分布”锅睛，以及被稱為“鐘形曲線”埠巨。城市人口的分布可能就符合“冪律分布”，或稱為“無標(biāo)度分布”现拒。貝葉斯法則告訴我們辣垒，在基于有限證據(jù)進行預(yù)測時，很少有事情是和好的先驗一樣重要的印蔬，也就是說良好的預(yù)測要有良好的直覺勋桶，要知道何時再處理一個正態(tài)分布，何時在處理一個冪律分布。事實證明例驹，貝葉斯法則為我們處理這些情況各提供了一個簡單但顯著不同的預(yù)測經(jīng)驗法則捐韩。
對于任何冪律分布，貝葉斯法則表明鹃锈，一個合適的預(yù)測策略就是相乘法則：將迄今觀察到的數(shù)量乘以一些常數(shù)荤胁。對于無信息先驗，這個常數(shù)一般是2屎债。而將正態(tài)分布作為貝葉斯法則的先驗時仅政，我們將運用平均法則：使用分布的“自然”平均數(shù)作為指導(dǎo)。
正態(tài)分布的東西似乎太長了盆驹，最后必然會很快結(jié)束圆丹。但冪律分布的東西存在的時間越長，你可以預(yù)測它繼續(xù)下去的時間就越長躯喇。 在這兩個極端之間辫封，生活中實際上還有第三種事物：那些不具有更大或更小可能性結(jié)束的事物，只因為他們已經(jīng)持續(xù)存在了一段時間玖瘸。有時候事情是簡單的秸讹、不變的。丹麥數(shù)學(xué)家瓦格納·厄蘭研究了這種現(xiàn)象雅倒，他將獨立事件之間的間隔形式化并推導(dǎo)出帶有他名字的函數(shù)：厄蘭分布璃诀。厄蘭分布給出了第三種預(yù)測法則——相加法則：總是預(yù)測事物只會再持續(xù)一個常量。
結(jié)論：這三個非常不同的最佳預(yù)測模式——相乘法則蔑匣、平均法則和相加法則都是通過將貝葉斯法則應(yīng)用到冪律劣欢、正態(tài)和厄蘭分布上得出結(jié)果的。
七裁良、
過度擬合凿将，不要想太多
從根本上說，過度擬合就是對數(shù)據(jù)的一種偶像崇拜价脾，產(chǎn)生的原因是將重心放在我們能夠測量的數(shù)據(jù)而不是真正重要的問題上牧抵。
舉例來講，過度擬合解釋了我們具有諷刺意味的味覺侨把。如果按照進化論來說犀变，味蕾的整個功能都是為了防止我們吃壞掉的東西，那么為什么我們最喜歡吃的食物都被認(rèn)為是對我們的健康有害的呢秋柄？答案是获枝，味覺是我們身體的健康指標(biāo)。脂肪骇笔、糖和鹽是重要的營養(yǎng)物質(zhì)省店，在長達(dá)幾十萬年的時間里嚣崭，食用含有這些物質(zhì)的食物是持續(xù)性飲食的一個合理方法。 但當(dāng)我們能夠改善所食用的食物時懦傍，這種關(guān)系就被打破了雹舀。我們現(xiàn)在可以把脂肪和糖添加到食物中去，但這些食物的量已經(jīng)超出我們身體可承受的健康范圍谎脯，但是我們還是只喜歡吃那些食物葱跋，而不是吃蔬菜、谷物和肉類這些構(gòu)成人類正常飲食習(xí)慣的食物源梭。換句話說娱俺，我們可以過度擬合食物的味道。過度擬合的問題也出現(xiàn)在運動健身和培訓(xùn)當(dāng)中废麻，再比如在應(yīng)試教育中荠卷，學(xué)生技能偏向考試技巧，說明開始對考試本身這個機制出現(xiàn)過度擬合烛愧。
機器學(xué)習(xí)的研究已經(jīng)得出了一些具體的策略以檢測過度擬合油宜，而最重要的問題之一就是所謂的交叉驗證。
從統(tǒng)計的觀點來看怜姿，過度擬合是我們對看到的實際數(shù)據(jù)太過敏感的體現(xiàn)慎冤。那么，解決方案也是直截了當(dāng)?shù)模何覀儽仨毱胶馕覀兊脑竿茁业轿覀儜?yīng)該使用的對抗復(fù)雜性的模型進行分析蚁堤。 在幾個相互競爭的模型中選擇一種方法就是奧卡姆的剃刀原理，它表明但狭，所有的事情都是平等的披诗，最簡單的假設(shè)可能就是最正確的那個。
在20世紀(jì)60年代立磁，蘇聯(lián)數(shù)學(xué)家安德烈·季霍諾夫給出了一種答案：引入一個額外項來計算懲罰更復(fù)雜的解決方案呈队。如果我們引入復(fù)雜性懲罰，那么更復(fù)雜的模型需要做的不僅是做得更好唱歧，更重要的是解釋數(shù)據(jù)以證明其更大復(fù)雜性的合理性宪摧。計算機科學(xué)家將這個原則——使用約束來懲罰模型的復(fù)雜性，稱為正則化颅崩。
那么這些復(fù)雜性懲罰是什么呢绍刮？1996年，生物統(tǒng)計學(xué)家羅伯特·蒂什拉尼開發(fā)“套索算法”挨摸，通過對模型中各因素總和的懲罰，將這種下行壓力放到因素的總權(quán)重上岁歉，套索算法將驅(qū)使它們降為零得运，只有對結(jié)果又很大影響的因素才保留膝蜈。同一類原則復(fù)雜度懲罰原則也同樣出現(xiàn)在自然界中。例如熔掺，新陳代謝的負(fù)擔(dān)對生物體的復(fù)雜度起到剎車作用饱搏，對過度精細(xì)的機體運行引入熱量懲罰機制，以免進化成更復(fù)雜的大腦置逻，因為從進化論的角度推沸，一個更復(fù)雜的大腦無法提供足夠的報酬。
如果我們觀察生物（包括人類）的進化方式券坞，我們會注意到一些有趣的現(xiàn)象：變化發(fā)生得很緩慢鬓催。這意味著，現(xiàn)代生物的屬性不僅受制于它們目前所處的環(huán)境恨锚，也由它們過去的歷史共同塑造而成宇驾。過度擬合的概念給我們提供了一個能在進化的壓力下看到其長處的機會。雖然交叉神經(jīng)纖維和改變用途的頜骨似乎已經(jīng)是最理想的安排猴伶，但至少我們應(yīng)該認(rèn)識到课舍，我們并不一定要讓進化去完全優(yōu)化生物，以適應(yīng)生態(tài)環(huán)境的每一點改變他挎，這樣做會使其對環(huán)境的變化極其敏感筝尾。另一方面，必須利用現(xiàn)有的材料办桨，施加一種有用的約束筹淫。這使得它很難引起生物體結(jié)構(gòu)的急劇變化，更難擬合崔挖。作為一個物種贸街，受制于過去，就使我們不能完全地調(diào)整以適應(yīng)目前所知的情況狸相，但這有助于我們在未知的未來保持身體強健薛匪。
在機器學(xué)習(xí)中，緩慢移動的有點最明顯出現(xiàn)在一種稱為早期停止的正則化技術(shù)中脓鹃。在各種機器學(xué)習(xí)任務(wù)中逸尖，正則化的有效性表明，我們可以通過有意識地思考和少做一些事情來做出更好的決定瘸右。如果我們最先想到的因素可能是最重要的因素娇跟，那么如果思考的量超過某一個度的話，就不僅是浪費時間和努力太颤，它將會讓我們找到更糟糕的解決方案苞俘。早期停止為理性的論證而不是一味地推理提供了基礎(chǔ)。
如果你有很高的不確定性和有限的數(shù)據(jù)龄章，那么務(wù)必提前停止吃谣。如果你不清楚你的工作將如何被評估乞封，以及由誰來評估，那么你就不值得花額外的時間來對你自己（或者其他人）的特質(zhì)做出所謂完美的判斷岗憋。不確定性越大肃晚，你所能衡量的東西和真正重要的東西之間的差距就越大，你就越應(yīng)該注意過度擬合的風(fēng)險仔戈，也就是說关串，你越喜歡簡單，就應(yīng)該越早停下來监徘。
八晋修、
松弛，順其自然
正如計算機科學(xué)家在過去幾十年里所發(fā)現(xiàn)的那樣耐量，無論我們的計算機處理速度有多快飞蚓，我們?nèi)绾吻擅畹貙λ鼈冞M行編程，一個問題的完美解決方案都是不存在的廊蜒。事實上趴拧，沒有人能像計算機科學(xué)家那樣理解，在面對看似無法控制的挑戰(zhàn)時山叮，你既不應(yīng)該永遠(yuǎn)辛苦工作著榴，也不應(yīng)該放棄，但我們將會看到第三種嘗試屁倔。
"約束優(yōu)化“問題：如何找到一組變量的最佳排列脑又，并給出特定的規(guī)則和積分法。這就是”旅行推銷員問題“锐借，到目前為止還沒有得到解決的問題问麸。如果，如何最好地解決那些最佳答案似乎遙不可及的問題钞翔，如何學(xué)會放松严卖。
在計算機科學(xué)中最簡單的放松形式之一就是約束松弛。在這項技術(shù)中布轿，研究人員消除了一些問題的約束哮笆，并著手解決他們希望得到解決的問題。然后汰扭，在他們?nèi)〉靡欢ǖ倪M展之后稠肘，他們試圖再將約束添加進去。也就是說萝毛，在把問題帶回現(xiàn)實之前项阴，他們會讓問題暫時更容易處理。
旅行推銷員問題笆包，就像尋找最佳座位安排的問題一樣环揽，是一種特殊的最優(yōu)化問題拷沸，稱為“離散優(yōu)化”，即在解決方案中沒有平滑的連續(xù)統(tǒng)一體薯演。推銷員要么到這個鎮(zhèn)子，要么到那個鎮(zhèn)秧了，你要么在5號桌跨扮，要么在6號桌。兩者之間沒有灰色地帶验毡。
有很多方法可以對一個問題進行松弛衡创，我們已經(jīng)看到了三個最重要的問題。首先晶通，約束松弛璃氢，簡單地消除一些約束，在回到現(xiàn)實之前狮辽，先在更寬松的問題上取得進展一也。第二，持續(xù)松弛喉脖，將離散的或二進制的選擇變成連續(xù)體：當(dāng)決定是選冰紅茶還是檸檬水時椰苟，先想象一個50：50的“阿諾德·帕爾默”混合，然后再向上或向下延展树叽。第三舆蝴，拉格朗日松弛，把不可能的變成僅僅是懲罰题诵，要學(xué)會扭曲規(guī)則的藝術(shù)（或打破規(guī)則洁仗，并接受后果）。例如性锭，搖滾樂隊在決定將哪些歌曲放入一個有限的專輯中時赠潦，就要面對計算機科學(xué)家稱之為的“背包問題”——將一組不同大小和重要性的項目裝進一個有限的集合中的難題。在嚴(yán)格的公式中篷店，背包問題是眾所周知的棘手問題祭椰，但這并不妨礙我們松弛的搖滾明星們做決定。正如幾個著名的例子所證明的那樣疲陕，有時候稍微超過城市的宵禁方淤，并付出相應(yīng)的懲罰，好過把節(jié)目限制在適當(dāng)?shù)臅r間內(nèi)蹄殃。事實上携茂，即使你沒有違規(guī)，你也可以想象它具有啟發(fā)性诅岩。
九讳苦、隨機性? ? ?十带膜、網(wǎng)絡(luò)連接? ??十一、博弈論 （略）
