聽(tīng)到“算法”（algorithm）一詞，第一反應(yīng)可能跟計(jì)算機(jī)有關(guān)，但其含義遠(yuǎn)不限于計(jì)算機(jī)，存在的歷史也遠(yuǎn)遠(yuǎn)長(zhǎng)于計(jì)算機(jī)?！彼惴ā耙辉~得名于波斯數(shù)學(xué)家花剌子密。公元9世紀(jì)，這位數(shù)學(xué)家寫(xiě)過(guò)一本書(shū)，討論用紙筆解決數(shù)學(xué)問(wèn)題的技巧。［書(shū)名為“al-Jabr wa’l-Muqabala”，其中的“al-jabr”就是后來(lái)“algebra”（代數(shù)）這個(gè)詞的前身。］
尤瓦爾·赫拉利在《未來(lái)簡(jiǎn)史》中寫(xiě)道：“算法指的是進(jìn)行計(jì)算、解決問(wèn)題、做出決定的一套有條理的步驟。 人類(lèi)有99%的決定，包括關(guān)于配偶、事業(yè)和住處的重要抉擇，都是由各種進(jìn)化而成的算法來(lái)處理，我們把這些算法稱(chēng)為感覺(jué)、情感和欲望"。
《算法之美》講的正是在我們?nèi)粘５纳詈凸ぷ髦?，?duì)我們有指導(dǎo)意義的算法。
一、
最優(yōu)停止理論：如何選擇停止觀望的時(shí)機(jī)？
最優(yōu)停止問(wèn)題的權(quán)威教科書(shū)開(kāi)宗明義地指出：“最優(yōu)停止理論關(guān)注的是如何選擇時(shí)機(jī)以執(zhí)行特定行動(dòng)的問(wèn)題?！?/b>
是沖動(dòng)早早停止觀望，還是多慮繼續(xù)觀望？這需要達(dá)成某種平衡，平衡概念正是解決這類(lèi)問(wèn)題的關(guān)鍵，但是大多數(shù)人根本無(wú)法確定這個(gè)平衡點(diǎn)在哪里？
算法告訴我們”37%法則“正是我們要的答案。
“37%法則”源于所謂的“秘書(shū)問(wèn)題”—最優(yōu)停止問(wèn)題中最著名的一類(lèi)難題。秘書(shū)招聘效果最佳的做法是接受所謂的“摸清情況再行動(dòng)準(zhǔn)則”（look-then-leap rule）：事先設(shè)定一個(gè)“觀察”期，在這段時(shí)間里，無(wú)論人選多么優(yōu)秀，都不要接受他（也就是說(shuō)，你的任務(wù)就是考察目標(biāo)，收集數(shù)據(jù)）?！坝^察”期結(jié)束之后，就進(jìn)入了“行動(dòng)”期。此時(shí)，一旦出現(xiàn)令之前最優(yōu)秀申請(qǐng)人相形見(jiàn)絀的人選，就立即出手，再也不要猶豫了。隨著秘書(shū)職位申請(qǐng)人數(shù)不斷增加，觀察與行動(dòng)之間的分界線正好處在全部申請(qǐng)人37%的位置，從而得出了37%法則：在考察前37%的申請(qǐng)人時(shí)，不要接受任何人的申請(qǐng)；然后，只要任何一名申請(qǐng)人比前面所有人選都優(yōu)秀，就要毫不猶豫地選擇他。
經(jīng)典秘書(shū)問(wèn)題的前提條件是，即時(shí)表態(tài)一定會(huì)被接受，而遲滯表態(tài)肯定會(huì)遭到拒絕，這樣看來(lái)，秘書(shū)問(wèn)題最基本同時(shí)也最令人難以置信的前提條件—嚴(yán)格的連續(xù)性，即有進(jìn)無(wú)退的單向行進(jìn)，正好是時(shí)間自身屬性的一個(gè)體現(xiàn)。就此而言，最優(yōu)停止問(wèn)題的這個(gè)顯性前提正好就是使其充滿活力的隱性前提。這個(gè)前提迫使我們基于還沒(méi)親眼看到的可能結(jié)果做出決定，迫使我們?cè)诓扇∽顑?yōu)策略之后仍然愿意接受非常高的失敗率。我們永遠(yuǎn)沒(méi)有二次選擇的機(jī)會(huì)。我們有可能得到類(lèi)似的選擇機(jī)會(huì)，但是絕不會(huì)得到完全相同的選擇機(jī)會(huì)。猶豫不決（不作為）與行為一樣不可改變。困在單行線上的駕車(chē)者與空間的相互關(guān)系就是我們與第四維度的關(guān)系：我們的生命真的只有一次。
我們只能知道孰優(yōu)孰劣，但是無(wú)法了解彼此之間的確切差距。正因?yàn)槿绱?，“觀望”階段是不可避免的。在前期階段，我們冒著與優(yōu)秀人選失之交臂的危險(xiǎn)，不斷調(diào)整我們的期望值與權(quán)衡標(biāo)準(zhǔn)。數(shù)學(xué)家把這種最優(yōu)停止問(wèn)題稱(chēng)作“無(wú)信息博弈”。全信息的意義在于我們無(wú)須觀望就可以直接出手。此時(shí)，我們可以運(yùn)用閾值準(zhǔn)則，一旦發(fā)現(xiàn)某位申請(qǐng)者的分?jǐn)?shù)高于某個(gè)值，就立刻接受她，而不需要先考察一批候選人并確定閾值。
買(mǎi)房子、賣(mài)房子、找工作、找停車(chē)位等等問(wèn)題，均可以看做是一個(gè)最優(yōu)停止問(wèn)題。
二、
探索和利用：要最新的還是要最好的？
直覺(jué)告訴我們，生活就是在新鮮事物和傳統(tǒng)事物之間、在最新的和最棒的之間、在勇于冒險(xiǎn)和安于現(xiàn)狀之間取得平衡。
羅伯特·波西格在他于1974年出版的經(jīng)典著作《禪與摩托車(chē)維修藝術(shù)》中對(duì)“有什么新鮮事嗎？”這句寒暄語(yǔ)進(jìn)行了公開(kāi)譴責(zé)。他說(shuō)：“只要認(rèn)真地研究這個(gè)問(wèn)題的話，得到的答案肯定是一堆瑣碎的跟風(fēng)事物，等到了明天它們就會(huì)失去新鮮勁兒?！彼J(rèn)為另一個(gè)問(wèn)題就要好得多：“最好的是什么？”
50多年來(lái)，計(jì)算機(jī)科學(xué)家一直埋頭鉆研，希望可以在要最新的還是要最好的之間找到這個(gè)平衡點(diǎn)，他們的研究甚至還有一個(gè)專(zhuān)門(mén)的名稱(chēng)：探索與利用的取舍。
英語(yǔ)為“explore”（探索）和“exploit”（利用）這兩個(gè)詞賦予了截然相反的含義，但是在計(jì)算機(jī)科學(xué)家眼中，它們有很多具體的中性含義。簡(jiǎn)單地說(shuō)，探索的意思是收集信息，而利用則指利用所擁有的信息，以產(chǎn)生一個(gè)好的結(jié)果。
你到底應(yīng)該花費(fèi)精力去探索新的信息，還是專(zhuān)注于從已有的信息中獲得收獲？關(guān)鍵是時(shí)間和度的問(wèn)題。隨著時(shí)間的推移，即使探索有所發(fā)現(xiàn)，我們可以認(rèn)真品味這些新發(fā)現(xiàn)的機(jī)會(huì)也已經(jīng)所剩無(wú)幾，因此探索的價(jià)值隨之降低。與之相反，利用的價(jià)值隨著時(shí)間的推移反而會(huì)不斷上升。利用好剩余時(shí)間就是正確的應(yīng)對(duì)之策。
“基廷斯指數(shù)（Gittins Index）”為解決探索與利用的取舍的問(wèn)題提供了方案。
他說(shuō)，當(dāng)你計(jì)劃出去吃一頓飯的時(shí)候，明天那頓應(yīng)該比今天這頓要貶值一點(diǎn) —— 因?yàn)槟忝魈炜赡軙?huì)離開(kāi)這里，吃不上那頓飯。具體貶值多少，取決于你預(yù)期還能停留多長(zhǎng)時(shí)間?；谶@一點(diǎn)，他提出了一個(gè)非常復(fù)雜的解決方案，最后結(jié)果是給每個(gè)選項(xiàng)計(jì)算了一個(gè)指數(shù)，現(xiàn)在被稱(chēng)為“基廷斯指數(shù)（Gittins Index）”。
“時(shí)間貶值率”會(huì)極大影響基廷斯指數(shù)，總的說(shuō)來(lái)，未來(lái)可期并可能有驚喜，則鼓勵(lì)嘗試新事物；當(dāng)下優(yōu)秀穩(wěn)定而未來(lái)不可知，則鼓勵(lì)堅(jiān)持老事物。
我們希望每一天都活在當(dāng)下，可是從現(xiàn)實(shí)的數(shù)學(xué)角度，你預(yù)期停留的時(shí)間越長(zhǎng)，探索新事物的價(jià)值就越高，基廷斯指數(shù)也越高。
一般而言，我們對(duì)理性的直覺(jué)認(rèn)識(shí)常常來(lái)源于利用，而不是探索。當(dāng)我們談?wù)摏Q策過(guò)程時(shí)，我們通常只關(guān)注某個(gè)決定的即時(shí)回報(bào)——如果你把每一個(gè)決定都當(dāng)作人生的最后一個(gè)決定，那么只有利用才是有意義的。但在一生中，你會(huì)做出很多決定。實(shí)際上，在做很多決定時(shí)，理性的做法是強(qiáng)調(diào)探索的重要性，重視新的東西而不是最好的東西，重視令人為之興奮的東西，而不是一味追求安全，重視隨機(jī)選擇，而不是深思熟慮的決定。在人生早期，更應(yīng)該如此。如果我們把期限設(shè)定為人的一生，這就意味著年輕人應(yīng)該多探索，到了后期就要專(zhuān)注于收獲。
斯坦福大學(xué)心理學(xué)教授勞拉·卡斯滕森通過(guò)自己的研究，對(duì)人們?cè)谒ダ线@個(gè)問(wèn)題上的成見(jiàn)提出了質(zhì)疑。她特別研究了人們的社會(huì)關(guān)系隨著年齡增長(zhǎng)而發(fā)生變化的過(guò)程與原因。這種變化有一個(gè)明晰的基本模式：人們社交網(wǎng)絡(luò)的規(guī)模（即與他們保持社交關(guān)系的人數(shù)）幾乎總是隨著時(shí)間的推移而減少。不過(guò)，卡斯滕森的研究表明，我們應(yīng)該改變對(duì)這個(gè)現(xiàn)象的看法?？ㄋ闺J(rèn)為，老年人的社會(huì)關(guān)系越來(lái)越簡(jiǎn)單，是他們主觀選擇的結(jié)果。由此可見(jiàn)，社交偏好的這些差異與年齡本身無(wú)關(guān)，而是與人們對(duì)決策過(guò)程中剩余時(shí)間的認(rèn)知有關(guān)。
基廷斯指數(shù)以一種正式、嚴(yán)謹(jǐn)?shù)男问剑C明了在有機(jī)會(huì)對(duì)探索結(jié)果加以利用時(shí)，我們應(yīng)該傾向于選擇未知的新事物。
如果你認(rèn)為基廷斯指數(shù)太復(fù)雜，或者你所處的情況并沒(méi)有表現(xiàn)出幾何貼現(xiàn)的特征，那么你還有另一個(gè)選擇—關(guān)注遺憾。自黎子良、羅賓斯之后，研究人員在過(guò)去幾十年里一直致力于尋找可以確保遺憾最少化的算法。在他們提出的算法當(dāng)中，最受歡迎的就是上限置信區(qū)間算法。上限置信區(qū)間算法所采用的原理有一個(gè)綽號(hào)——“面對(duì)不確定性時(shí)的樂(lè)觀主義”。
三、
排序問(wèn)題
1955年，詹姆斯·霍斯肯在第一篇公開(kāi)發(fā)表的關(guān)于排序的科學(xué)論文中寫(xiě)道：“為了降低單位產(chǎn)出的成本，人們通常會(huì)增加他們的業(yè)務(wù)規(guī)模?！边@是任何一名商科學(xué)生都很熟悉的規(guī)模經(jīng)濟(jì)。但是，在排序這個(gè)問(wèn)題中，規(guī)模往往會(huì)招致災(zāi)難：如果擴(kuò)大排序的規(guī)模，“排序的單位成本就會(huì)不降反升”。排序往往呈現(xiàn)非常明顯的規(guī)模不經(jīng)濟(jì)現(xiàn)象，這與普通人認(rèn)為大批量處理問(wèn)題有諸多好處的直覺(jué)正好相反。
這是排序理論的第一個(gè)，也是最基本的深刻見(jiàn)解：規(guī)模越大，難度越大。
據(jù)統(tǒng)計(jì)，世界上計(jì)算機(jī)資源的很大一部分被用于排序，難怪排序?qū)τ谔幚韼缀跞魏晤?lèi)型的信息來(lái)說(shuō)都是至關(guān)重要的。排序的主要原因之一是將內(nèi)容變成方便人眼觀察的形式，這意味著排序也是人類(lèi)信息體驗(yàn)的關(guān)鍵。
信息處理開(kāi)始于19世紀(jì)的美國(guó)人口普查，是由赫爾曼·霍爾瑞斯及后來(lái)的IBM公司根據(jù)實(shí)體打孔卡排序設(shè)備開(kāi)創(chuàng)形成的。
當(dāng)我們知道被排序的不僅是信息，其實(shí)還有人，因此學(xué)會(huì)排序有助于理解人類(lèi)可以和諧相處，偶爾才會(huì)拳腳相向的原因。所謂社會(huì)，就是我們維持的另外一種更重要、規(guī)模更大的秩序。
但是，要回答如何排序、哪種排序方法效果最佳這個(gè)問(wèn)題，就需要先弄明白另外一個(gè)問(wèn)題：如何計(jì)分？
計(jì)算機(jī)科學(xué)有一種專(zhuān)門(mén)用來(lái)測(cè)量算法最壞情況的速記法，即所謂的“大O”符號(hào)。大O符號(hào)有一個(gè)非常奇怪的特點(diǎn)——設(shè)計(jì)這個(gè)符號(hào)的目的就是用來(lái)表示不精確性。也就是說(shuō)，大O符號(hào)的目的不是使用分鐘和秒鐘來(lái)表示算法的性能，而是方便我們討論問(wèn)題規(guī)模和程序運(yùn)行時(shí)間之間的關(guān)系。由于大O符號(hào)故意剔除了細(xì)枝末節(jié)的內(nèi)容，所以展示給我們的是將問(wèn)題分成不同大類(lèi)的概略情況。
假設(shè)你準(zhǔn)備邀請(qǐng)n名客人出席晚宴。在客人到來(lái)之前，打掃房間的時(shí)間與來(lái)客人數(shù)沒(méi)有任何關(guān)系。這類(lèi)問(wèn)題最簡(jiǎn)單，被稱(chēng)為“O（1）”，也被稱(chēng)為“常數(shù)時(shí)間”。接下來(lái)，烤肉在所有客人面前傳遞一圈所需的時(shí)間將是“O（n）”，也被稱(chēng)為“線性時(shí)間”——客人增加一倍，菜傳遞一圈所需的時(shí)間就會(huì)增加一倍。假設(shè)客人到來(lái)之后，你要與每個(gè)人熱烈擁抱，情況又會(huì)怎么樣？第一個(gè)到達(dá)你家的客人與你擁抱，第二個(gè)客人需要擁抱兩次，第三個(gè)客人要擁抱三次。此時(shí)，擁抱一共發(fā)生了多少次？這種情況屬于“O（n2 ）”，也稱(chēng)“平方時(shí)間”。如果沒(méi)增加一位客人都會(huì)讓你的工作加倍，那么就會(huì)有“指數(shù)時(shí)間”，記做“O(2的n次方)。
假設(shè)你希望將雜亂無(wú)序的藏書(shū)按照字母順序進(jìn)行分類(lèi)排序。那么你會(huì)很自然地想到一個(gè)方法，于是你在書(shū)架前巡視，看到有兩本書(shū)顛倒了先后次序，就把它們調(diào)換過(guò)來(lái)（例如，將品欽的小說(shuō)放在華萊士后面）。在將品欽放到華萊士前面之后，你繼續(xù)巡視。走到書(shū)架最后端之后，你就會(huì)回過(guò)頭來(lái)，從書(shū)架最前端重新開(kāi)始。如果從頭走到尾，都沒(méi)有看到有哪兩本書(shū)次序不對(duì)，就說(shuō)明你完成了這項(xiàng)工作。 這就是冒泡排序，它會(huì)把我們帶進(jìn)平方時(shí)間。
你可能會(huì)采取另外一種方法，即把所有的書(shū)都從書(shū)架上拿下來(lái)，然后一本一本放到合適的位置。你把第一本書(shū)放在書(shū)架中間，然后拿第二本書(shū)和第一本比較，根據(jù)比較結(jié)果把它插到第一本的右邊或者左邊。在放第三本書(shū)時(shí)，你先從左到右瀏覽書(shū)架，然后把它放到合適的位置。你不斷重復(fù)這個(gè)過(guò)程，漸漸地所有的書(shū)都被按次序放到書(shū)架上，直到你最終完成這項(xiàng)工作。 計(jì)算機(jī)科學(xué)家們給這種方法起了一個(gè)非常貼切的名稱(chēng)——“插入排序”
插入排序比冒泡排序更直觀，但實(shí)際上它不比冒泡排序快多少，但仍然是處于平方時(shí)間。是否有打破平方時(shí)間的算法，答案是肯定的，就是分治算法。
1945年，約翰·馮·諾伊曼為了展示存儲(chǔ)程序計(jì)算機(jī)的威力，編寫(xiě)了一個(gè)程序。在這個(gè)程序的最終結(jié)論中，就包含有比較的概念。為兩張牌排序很簡(jiǎn)單，把較小的那張牌放在上面就可以了。如果有兩疊牌，每疊包含兩張排好序的牌，我們可以很容易地將這四張牌整理成排好序的一疊牌。重復(fù)幾次，就可以整理出越來(lái)越多且排好序的牌垛。很快，你就可以把完整的一副牌整理得井然有序。在最后一次合并時(shí)，你可以通過(guò)與交錯(cuò)式洗牌非常相似的手法，將撲克牌整理出你需要的次序。 這種方法現(xiàn)在被稱(chēng)作“合并排序”，是計(jì)算機(jī)科學(xué)中的傳奇算法之一。正如1997年的一篇論文所指出的：“合并排序在排序歷史中的重要地位與排序在計(jì)算歷史中的重要地位旗鼓相當(dāng)?！琛?合并排序威力巨大，是因?yàn)樗膹?fù)雜程度位于線性時(shí)間和平方時(shí)間之間。具體來(lái)說(shuō)，O（n log n）被稱(chēng)為“線性對(duì)數(shù)”時(shí)間。
從某種非常重要的意義上看，合并排序算法給出的O（n log n）線性對(duì)數(shù)時(shí)間肯定是我們可以得到的最佳效果。已經(jīng)有人證明，如果通過(guò)一系列面對(duì)面直接比較的方法對(duì)n個(gè)事物進(jìn)行完全排序，比較的次數(shù)不可能少于O（n log n）。這是一條普世法則，是不可能違背的。 但是，嚴(yán)格說(shuō)來(lái)，這條法則并不能平息排序問(wèn)題上的所有爭(zhēng)議。有的時(shí)候我們并不需要完全排序，有的時(shí)候根本不需要逐項(xiàng)比較也能完成排序工作。正是因?yàn)橛羞@兩個(gè)原因，實(shí)踐中的粗略排序速度也可以比線性對(duì)數(shù)時(shí)間快。桶排序算法非常漂亮地展現(xiàn)了這個(gè)特點(diǎn) 。在桶排序中，排序?qū)ο蟀凑张判蝾?lèi)別分成若干組，類(lèi)別之間更精細(xì)的排序問(wèn)題，在分組時(shí)不予考慮，留待后面解決。(在計(jì)算機(jī)科學(xué)中，"桶“這個(gè)術(shù)語(yǔ)表示一組未排序的數(shù)據(jù)）。
排序是搜索的準(zhǔn)備工作，而排序與搜索之間的取舍是最重要的取舍問(wèn)題之一，其基本原理是：人們投入精力為物品排序是一種先發(fā)制人的措施，目的是保證以后無(wú)須在搜索上投入精力。平衡點(diǎn)應(yīng)該如何確定，取決于當(dāng)時(shí)情況的具體參數(shù)，但是，如果認(rèn)為排序的價(jià)值僅僅是為未來(lái)的搜索提供支持，那么你會(huì)有一個(gè)令人吃驚的發(fā)現(xiàn)：混亂無(wú)序也無(wú)傷大雅！隨著計(jì)算機(jī)搜索成本的降低，排序的價(jià)值也隨之降低。
排序問(wèn)題在體育比賽，動(dòng)物世界的啄食順序和優(yōu)勢(shì)等級(jí)，以及比如船舶海上通行權(quán)之類(lèi)的問(wèn)題得以應(yīng)用。船舶海上通行權(quán)在理論上需要遵循一套極其復(fù)雜的慣例，但是在實(shí)踐中，到底哪條船應(yīng)該給另一方讓路是由“總噸位法則”這條簡(jiǎn)單易行的原則決定的。
四、
緩存問(wèn)題
1946年，亞瑟·伯克斯、赫爾曼·戈德斯坦和約翰·馮·諾依曼在普林斯頓高級(jí)研究所展開(kāi)合作，為他們所謂的“電子記憶器官”起草了一個(gè)設(shè)計(jì)方案。他們寫(xiě)道，在一個(gè)理想的世界里，機(jī)器當(dāng)然可以有無(wú)限量的快速儲(chǔ)存能力，但在實(shí)踐中這是不可能的。（現(xiàn)在仍然不可能。）于是，這三個(gè)人退而求其次，提出了“分級(jí)存儲(chǔ)器體系，每一級(jí)的存儲(chǔ)能力都超過(guò)以前，但是讀取速度有所減慢”。
在1962年超級(jí)計(jì)算機(jī)阿特拉斯在英國(guó)曼徹斯特問(wèn)世以前，計(jì)算領(lǐng)域的這種“分級(jí)存儲(chǔ)”概念一直停留在理論層面。
阿特拉斯問(wèn)世之后不久，劍橋大學(xué)數(shù)學(xué)家莫里斯·威爾克斯意識(shí)到，這種體積較小、速度較快的存儲(chǔ)器不僅可以為我們處理數(shù)據(jù)、將處理好的數(shù)據(jù)存回主存儲(chǔ)器提供了一個(gè)非常方便的場(chǎng)所，還可以用來(lái)有意地保留稍后可能需要使用的信息片段，為后期類(lèi)似的需要做好準(zhǔn)備，從而極大地加速機(jī)器的操作。如果所需要的數(shù)據(jù)仍然保留在工作存儲(chǔ)器中，就不必再到主存儲(chǔ)器中裝載這些數(shù)據(jù)了。威爾克斯認(rèn)為，這種體積較小的存儲(chǔ)器“可以自動(dòng)收集并保存來(lái)自速度較慢的主內(nèi)存的數(shù)據(jù)，為后期使用做好準(zhǔn)備，從而免除了再次訪問(wèn)主存儲(chǔ)器帶來(lái)的麻煩”。20世紀(jì)60年代末，威爾克斯的提議在IBM 360/85超級(jí)計(jì)算機(jī)中得以實(shí)現(xiàn)，人們稱(chēng)之為“緩存”。
我們知道，IBM在20世紀(jì)60年代率先推動(dòng)緩存系統(tǒng)的部署應(yīng)用。不出意料，它也是早期緩存算法開(kāi)創(chuàng)性研究的發(fā)源地，也許他們?nèi)〉玫娜魏我豁?xiàng)成果都沒(méi)有拉斯洛·貝萊迪的算法重要。貝萊迪于1966年發(fā)表的那篇緩存算法論文是隨后15年里被引用最多的計(jì)算機(jī)科學(xué)研究成果。這篇論文解釋道，緩存管理的目標(biāo)是盡可能減少“頁(yè)面錯(cuò)誤”或“緩存缺失”。所謂緩存缺失，是指無(wú)法在緩存中找到所需數(shù)據(jù)，因此只能到較慢的主存中查找的現(xiàn)象。貝萊迪在文中寫(xiě)道，從本質(zhì)上講，最優(yōu)緩存清理策略就是在緩存已滿時(shí)，將未來(lái)最長(zhǎng)時(shí)間內(nèi)不會(huì)再次使用的數(shù)據(jù)從緩存中清理出去。今天，為了表示敬意，人們把那個(gè)無(wú)所不知、有先見(jiàn)之明，而且可以在分析未來(lái)情況基礎(chǔ)上執(zhí)行最優(yōu)緩存策略的那個(gè)假想算法稱(chēng)作貝萊迪算法。
我們可以嘗試隨機(jī)清理算法，將新數(shù)據(jù)添加到緩存中，并隨機(jī)覆蓋舊數(shù)據(jù)。隨機(jī)清理是早期高速緩存理論得出的一個(gè)令人吃驚的結(jié)果，雖然遠(yuǎn)非完美，但是效果也還不錯(cuò)。這也可能是一種巧合，因?yàn)橹灰幸粋€(gè)緩存，無(wú)論你如何維護(hù)，都可以提升系統(tǒng)的效率。不管怎么說(shuō)，你經(jīng)常使用的內(nèi)容通常還會(huì)很快回到緩存中。另一種簡(jiǎn)單的策略叫作先進(jìn)先出（FIFO）。這種算法總是清理或覆蓋在緩存中保存時(shí)間最久的內(nèi)容（與瑪莎·斯圖爾特問(wèn)的“我已擁有它多長(zhǎng)時(shí)間了”這個(gè)問(wèn)題有異曲同工之妙）。第三種方法是最近最少使用（LRU），即將閑置不用時(shí)間最長(zhǎng)的內(nèi)容清理掉（與之相對(duì)應(yīng)的斯圖爾特的問(wèn)題是“上次穿它或使用它是什么時(shí)候的事”）。
貝萊迪在若干情形下對(duì)隨機(jī)清理、先進(jìn)先出和最近最少使用的幾個(gè)變體進(jìn)行了比較，結(jié)果發(fā)現(xiàn)最近最少使用法始終表現(xiàn)出最接近未卜先知的效果。最近最少使用法的高效性得益于計(jì)算機(jī)科學(xué)家所謂的“時(shí)間局部性”：如果一個(gè)程序曾經(jīng)調(diào)用過(guò)某個(gè)信息，那么在不久的將來(lái)它可能會(huì)再次調(diào)用這個(gè)信息。
如果你能創(chuàng)建一個(gè)網(wǎng)頁(yè)內(nèi)容緩存，其實(shí)際地理位置更接近那些有需要的人，你就可以更快地為他們提供頁(yè)面服務(wù)。互聯(lián)網(wǎng)上的大部分流量現(xiàn)在都是由“內(nèi)容分配網(wǎng)絡(luò)”來(lái)處理的，這些網(wǎng)絡(luò)利用遍布世界各地的電腦維護(hù)流行網(wǎng)站的拷貝。因此，在用戶請(qǐng)求使用這些頁(yè)面時(shí)，他們可以從附近的一臺(tái)計(jì)算機(jī)獲取數(shù)據(jù)，而不必跨越千山萬(wàn)水，連接到原始服務(wù)器上。
最近，亞馬遜獲得了一項(xiàng)創(chuàng)新的專(zhuān)利，使它奉行的這條原則得到了進(jìn)一步發(fā)展。在媒體看來(lái)，這項(xiàng)“可預(yù)期包裹配送”專(zhuān)利似乎可以幫助亞馬遜在你下單之前就把商品送到你的手上。有人下訂單時(shí)，商品就已經(jīng)在他附近的大街上了。預(yù)測(cè)個(gè)人購(gòu)買(mǎi)行為是有挑戰(zhàn)性的，但是當(dāng)預(yù)測(cè)數(shù)千人的購(gòu)買(mǎi)行為時(shí)，大數(shù)定律就會(huì)生效。
迄今為止，我們見(jiàn)過(guò)的所有家居管理建議中，必不可少的一個(gè)“?？汀本褪恰拔镆灶?lèi)聚”這個(gè)存放概念。也許沒(méi)有人會(huì)像野口由紀(jì)夫那樣直言不諱地反對(duì)這條建議。他說(shuō)：“我必須強(qiáng)調(diào)，在我的方法中，一個(gè)基本原則就是不能把文件根據(jù)內(nèi)容分組?！币坏┱J(rèn)識(shí)到野口文件歸檔系統(tǒng)是最近最少使用原則的一個(gè)實(shí)例，我們就知道它不僅是一種有效策略，實(shí)際上還是最優(yōu)策略。
1987年，卡內(nèi)基-梅隆大學(xué)的心理學(xué)家、計(jì)算機(jī)科學(xué)家約翰·安德森為了解大學(xué)圖書(shū)館的信息檢索系統(tǒng)，查閱了大量資料。他的目標(biāo)，或者說(shuō)他自認(rèn)為的目標(biāo)，是弄清楚信息檢索系統(tǒng)的設(shè)計(jì)是否可以從人類(lèi)記憶研究那里獲取靈感。結(jié)果，他發(fā)現(xiàn)現(xiàn)實(shí)正好相反：信息科學(xué)有可能為人類(lèi)大腦研究填補(bǔ)某些空白。在安德森對(duì)人類(lèi)記憶的新描述中，其核心思想是，需要解決的可能不是存儲(chǔ)問(wèn)題，而是如何組織的問(wèn)題。他認(rèn)為，大腦的記憶能力基本上是無(wú)限的，但我們?cè)诖竽X中搜索的時(shí)間是有限的。安德森把大腦比喻成圖書(shū)館，不過(guò)這個(gè)圖書(shū)館只有一個(gè)無(wú)限長(zhǎng)的書(shū)架，也就是說(shuō)，是一個(gè)美國(guó)國(guó)會(huì)圖書(shū)館級(jí)別的野口文件歸檔系統(tǒng)。你可以在那個(gè)書(shū)架上放無(wú)數(shù)本書(shū)，但是，書(shū)的位置越靠近前面，就越容易被找到。
如果記憶面臨的基本問(wèn)題真的是一個(gè)組織管理的問(wèn)題，而不是存儲(chǔ)問(wèn)題，那么我們?cè)谒ダ嫌绊懶闹悄芰@個(gè)問(wèn)題上的看法就應(yīng)該改變。最近，圖賓根大學(xué)的邁克爾·瑞姆斯卡率領(lǐng)一組心理學(xué)家和語(yǔ)言學(xué)家完成了一項(xiàng)研究，結(jié)果發(fā)現(xiàn)，所謂的“認(rèn)知能力衰退”（滯后和檢索錯(cuò)誤）可能并不表明搜索過(guò)程變慢或者搜索能力退化，而是我們所面對(duì)的信息量不斷變大所帶來(lái)的一個(gè)不可避免的后果（至少是原因之一）。不管衰老還會(huì)帶來(lái)什么樣的難題，年長(zhǎng)的大腦必須管理數(shù)量更多的記憶存儲(chǔ)，因此，它其實(shí)每天都在解決更復(fù)雜的計(jì)算問(wèn)題。面對(duì)反應(yīng)速度更快的年輕人，老年人可以不屑一顧地說(shuō)：“這是因?yàn)槟闶裁炊疾恢?！?/p>
五、
時(shí)間調(diào)度理論：要事先行
“科學(xué)管理理論”提出者弗雷德里奇?泰勒，利用他的同事亨利?甘特的創(chuàng)意（甘特圖），將調(diào)度編程一種研究對(duì)象，他們富裕它視覺(jué)和概念的形式。但是，甘特圖沒(méi)有解決一個(gè)基本問(wèn)題，到底怎樣安排日程是最好的？直到幾十年之后的1954年，蘭德公司的數(shù)學(xué)家塞爾默·約翰遜在他發(fā)表的一篇論文里才第一個(gè)暗示這一問(wèn)題可以被解決。約翰遜的研究揭示了更深層次的兩點(diǎn)內(nèi)容：第一，時(shí)序安排可以通過(guò)算法表達(dá)；第二，存在最優(yōu)時(shí)序安排方案。這引發(fā)了一項(xiàng)龐大的研究，為大量假定工廠中不同數(shù)量和種類(lèi)的機(jī)器運(yùn)行提供策略。
約翰遜的理論是基于最小化雙機(jī)共同工作時(shí)間來(lái)降低總時(shí)間，在單機(jī)調(diào)度的情況下，如果我們要完成所有工作，那么所有的安排都應(yīng)該用同樣長(zhǎng)的時(shí)間完成，與先后順序無(wú)關(guān)。因此，單機(jī)調(diào)度的第一堂課是：明確你的目標(biāo)。我們只有知道如何保持得分才能宣布哪種安排最好。由此產(chǎn)生以下幾種研究理論：
1）如果你要降低最大延遲時(shí)間，那么最佳策略就是你先從截止日期最近的任務(wù)開(kāi)始，再以此類(lèi)推逐漸執(zhí)行。這一策略被直觀地稱(chēng)為最早到期日原則。
2）將完成時(shí)間總和最小化可以引申出一個(gè)非常簡(jiǎn)單的優(yōu)化算法——最短加工時(shí)間：總是先做能最快完成的任務(wù)。事實(shí)上，在面對(duì)不確定性時(shí)，最短加工時(shí)間的加權(quán)版本是一種最通用的調(diào)度策略。它提供了一個(gè)簡(jiǎn)單的時(shí)間管理方法：每接到一件新工作時(shí)，通過(guò)其將耗費(fèi)的時(shí)間來(lái)對(duì)其進(jìn)行重要性的劃分。如果該重要性高于當(dāng)前正在執(zhí)行的任務(wù)，就切換到新任務(wù)，不然就堅(jiān)持當(dāng)前任務(wù)。?
計(jì)算機(jī)科學(xué)能給我們提供用單機(jī)調(diào)度的運(yùn)用不同度量標(biāo)準(zhǔn)的最優(yōu)算法，但選擇哪種度量標(biāo)準(zhǔn)就取決于自己。這為我們提供了一種激進(jìn)的方法來(lái)重新思考“拖延”這一時(shí)間管理的經(jīng)典問(wèn)題。我們通常認(rèn)為拖延是一種錯(cuò)誤的算法，但如果它正好相反呢？如果它是一個(gè)錯(cuò)誤問(wèn)題的最佳解決方案呢？
重點(diǎn)不只是要把事情做好，更重要的是把權(quán)值更高的事情做好-在每一時(shí)刻做好最重要的工作，這聽(tīng)起來(lái)像是治愈拖延癥的一個(gè)行之有效的方法，但僅僅這樣還不夠。
優(yōu)先反轉(zhuǎn)和優(yōu)先繼承理論表明，想把事情做好的熱情不足以避免調(diào)度上的陷阱，光有把重要事情做好的熱情也不夠，要承諾堅(jiān)持做你所能做的最重要的事情。
有時(shí)候，最重要的事情要等不重要的事情完成之后才能進(jìn)行。當(dāng)某個(gè)任務(wù)在另一個(gè)任務(wù)完成之前無(wú)法啟動(dòng)時(shí)，調(diào)度理論家稱(chēng)之為“優(yōu)先約束”。
六、
貝葉斯法則，預(yù)測(cè)未來(lái)
谷歌的研究部主任彼得·諾維德曾進(jìn)行過(guò)一次題為“數(shù)據(jù)的不合理有效性”的著名演講，該演講深究了“數(shù)十億瑣碎的數(shù)據(jù)點(diǎn)最終如何能被理解”。媒體不斷告訴我們，我們生活在一個(gè)“大數(shù)據(jù)時(shí)代”，計(jì)算機(jī)可以篩選這數(shù)十億的數(shù)據(jù)點(diǎn)并發(fā)現(xiàn)一些肉眼看不到的細(xì)節(jié)。但跟日常生活聯(lián)系最密切的問(wèn)題往往是另一種極端。我們的生活充滿“小數(shù)據(jù)”，我們就像看到柏林墻的戈特一樣，也就是通過(guò)一個(gè)單一的觀察，做一個(gè)推論。
以中彩票或賭博為例。
貝葉斯的關(guān)鍵見(jiàn)解是，試圖使用我們看到的中獎(jiǎng)和未中獎(jiǎng)彩票來(lái)分析彩票來(lái)源于整體彩票池的方法，本質(zhì)上是在倒推。他說(shuō)，要做到這一點(diǎn)，我們需要先用假設(shè)向前推理。換句話說(shuō)，我們首先需要確定，如果各種可能場(chǎng)景都成真的情況下，我們中獎(jiǎng)的可能性有多少。這個(gè)被現(xiàn)代統(tǒng)計(jì)學(xué)家稱(chēng)為“可能性”的概率給了我們解決問(wèn)題所需要的信息。
他表示，如果我們提前真的不知道彩票的情況，然后當(dāng)我們第一次買(mǎi)的三張彩票中的一張彩票中獎(jiǎng)了，我們可以推測(cè)獎(jiǎng)池里彩票的總中獎(jiǎng)比例為2/3。如果我們買(mǎi)三張彩票，都中獎(jiǎng)了，那我們可以推測(cè)總中獎(jiǎng)比例正好是4/5。事實(shí)上，如果買(mǎi)n張彩票共w張中獎(jiǎng)，那么中獎(jiǎng)率就是中獎(jiǎng)數(shù)加1，除以所購(gòu)買(mǎi)的數(shù)目加2，即。 這種令人難以置信的簡(jiǎn)單的方法估計(jì)概率的簡(jiǎn)單方法被稱(chēng)為拉普拉斯定律，它很容易就能適用于任何你需要通過(guò)歷史事件來(lái)評(píng)估概率的情況。拉普拉斯定律的精髓就在于無(wú)論我們有一個(gè)單獨(dú)的數(shù)據(jù)點(diǎn)或數(shù)以百萬(wàn)計(jì)的數(shù)據(jù)，它都同樣適用。
描述這種關(guān)系的數(shù)學(xué)公式，將我們先前持有的觀念和我們眼前的證據(jù)結(jié)合起來(lái)，就形成了后來(lái)的貝葉斯法則。有點(diǎn)兒諷刺的是，真正重要的工作卻是由拉普拉斯完成的。它提供了一個(gè)非常簡(jiǎn)單的解決方案來(lái)如何處理現(xiàn)有的信念與觀察到的證據(jù)：將它們的概率相乘。每個(gè)假設(shè)的概率都是真實(shí)可能的，這就是所謂的先驗(yàn)概率，或者簡(jiǎn)稱(chēng)為“先驗(yàn)”。貝葉斯法則總是需要一些先驗(yàn)，即使它只是一個(gè)猜測(cè)。
理查德?戈特三世在1969年針對(duì)柏林墻倒塌的預(yù)測(cè)時(shí)設(shè)想，他到達(dá)柏林墻時(shí)的那一刻并不特殊，如果有任何一個(gè)時(shí)刻都有同樣的可能性，那么平均來(lái)講，他的到來(lái)應(yīng)該是在一個(gè)精確的中間點(diǎn)。如果我們假設(shè)我們到達(dá)的中間點(diǎn)有精確的時(shí)間，那么對(duì)于它在未來(lái)還可以持續(xù)多久的最佳猜測(cè)就變得很明顯：確切地說(shuō)就是它已經(jīng)存在的時(shí)間。這個(gè)簡(jiǎn)單的推理，被戈特稱(chēng)為“哥白尼原則”，因?yàn)楦绨啄?00年前曾經(jīng)問(wèn)道：我們?cè)谀模?/p>
哥白尼原則是應(yīng)用貝葉斯法則無(wú)信息先驗(yàn)的結(jié)果，應(yīng)用貝葉斯法則，我們首先需要給每個(gè)現(xiàn)象的持續(xù)時(shí)間分配一個(gè)先驗(yàn)概率。在認(rèn)識(shí)到哥白尼原則是無(wú)信息先驗(yàn)基礎(chǔ)上的貝葉斯法則之后，就可以回答很多關(guān)于其有效性的問(wèn)題。哥白尼原則在我們什么都不知道的情況下似乎是合理的、準(zhǔn)確的，如在1969年看到的柏林墻，我們不確定什么時(shí)間范疇是合適的。同時(shí)，在我們對(duì)某一對(duì)象的確有所了解時(shí)，就會(huì)感覺(jué)這是完全錯(cuò)誤的。預(yù)測(cè)一個(gè)90歲的人能活到180歲是不合理的，這恰恰是因?yàn)槲覀冴P(guān)于人類(lèi)壽命已經(jīng)了解了很多——在這種情況下，我們就可以預(yù)測(cè)得更好。我們給貝葉斯法則帶來(lái)的先驗(yàn)信息越豐富，我們便能從中得到越有用的預(yù)測(cè)。
真實(shí)世界的先驗(yàn)。從廣義上將，世界上有兩種類(lèi)型的事物：傾向于（或圍繞）某種“自然”價(jià)值的事物，以及與之相反的事物。
比如人的壽命，屬于前一類(lèi)，遵循所謂的“正態(tài)分布”，或稱(chēng)為“高斯分布”，以及被稱(chēng)為“鐘形曲線”。城市人口的分布可能就符合“冪律分布”，或稱(chēng)為“無(wú)標(biāo)度分布”。貝葉斯法則告訴我們，在基于有限證據(jù)進(jìn)行預(yù)測(cè)時(shí)，很少有事情是和好的先驗(yàn)一樣重要的，也就是說(shuō)良好的預(yù)測(cè)要有良好的直覺(jué)，要知道何時(shí)再處理一個(gè)正態(tài)分布，何時(shí)在處理一個(gè)冪律分布。事實(shí)證明，貝葉斯法則為我們處理這些情況各提供了一個(gè)簡(jiǎn)單但顯著不同的預(yù)測(cè)經(jīng)驗(yàn)法則。
對(duì)于任何冪律分布，貝葉斯法則表明，一個(gè)合適的預(yù)測(cè)策略就是相乘法則：將迄今觀察到的數(shù)量乘以一些常數(shù)。對(duì)于無(wú)信息先驗(yàn)，這個(gè)常數(shù)一般是2。而將正態(tài)分布作為貝葉斯法則的先驗(yàn)時(shí)，我們將運(yùn)用平均法則：使用分布的“自然”平均數(shù)作為指導(dǎo)。
正態(tài)分布的東西似乎太長(zhǎng)了，最后必然會(huì)很快結(jié)束。但冪律分布的東西存在的時(shí)間越長(zhǎng)，你可以預(yù)測(cè)它繼續(xù)下去的時(shí)間就越長(zhǎng)。 在這兩個(gè)極端之間，生活中實(shí)際上還有第三種事物：那些不具有更大或更小可能性結(jié)束的事物，只因?yàn)樗麄円呀?jīng)持續(xù)存在了一段時(shí)間。有時(shí)候事情是簡(jiǎn)單的、不變的。丹麥數(shù)學(xué)家瓦格納·厄蘭研究了這種現(xiàn)象，他將獨(dú)立事件之間的間隔形式化并推導(dǎo)出帶有他名字的函數(shù)：厄蘭分布。厄蘭分布給出了第三種預(yù)測(cè)法則——相加法則：總是預(yù)測(cè)事物只會(huì)再持續(xù)一個(gè)常量。
結(jié)論：這三個(gè)非常不同的最佳預(yù)測(cè)模式——相乘法則、平均法則和相加法則都是通過(guò)將貝葉斯法則應(yīng)用到冪律、正態(tài)和厄蘭分布上得出結(jié)果的。
七、
過(guò)度擬合，不要想太多
從根本上說(shuō)，過(guò)度擬合就是對(duì)數(shù)據(jù)的一種偶像崇拜，產(chǎn)生的原因是將重心放在我們能夠測(cè)量的數(shù)據(jù)而不是真正重要的問(wèn)題上。
舉例來(lái)講，過(guò)度擬合解釋了我們具有諷刺意味的味覺(jué)。如果按照進(jìn)化論來(lái)說(shuō)，味蕾的整個(gè)功能都是為了防止我們吃壞掉的東西，那么為什么我們最喜歡吃的食物都被認(rèn)為是對(duì)我們的健康有害的呢？答案是，味覺(jué)是我們身體的健康指標(biāo)。脂肪、糖和鹽是重要的營(yíng)養(yǎng)物質(zhì)，在長(zhǎng)達(dá)幾十萬(wàn)年的時(shí)間里，食用含有這些物質(zhì)的食物是持續(xù)性飲食的一個(gè)合理方法。 但當(dāng)我們能夠改善所食用的食物時(shí)，這種關(guān)系就被打破了。我們現(xiàn)在可以把脂肪和糖添加到食物中去，但這些食物的量已經(jīng)超出我們身體可承受的健康范圍，但是我們還是只喜歡吃那些食物，而不是吃蔬菜、谷物和肉類(lèi)這些構(gòu)成人類(lèi)正常飲食習(xí)慣的食物。換句話說(shuō)，我們可以過(guò)度擬合食物的味道。過(guò)度擬合的問(wèn)題也出現(xiàn)在運(yùn)動(dòng)健身和培訓(xùn)當(dāng)中，再比如在應(yīng)試教育中，學(xué)生技能偏向考試技巧，說(shuō)明開(kāi)始對(duì)考試本身這個(gè)機(jī)制出現(xiàn)過(guò)度擬合。
機(jī)器學(xué)習(xí)的研究已經(jīng)得出了一些具體的策略以檢測(cè)過(guò)度擬合，而最重要的問(wèn)題之一就是所謂的交叉驗(yàn)證。
從統(tǒng)計(jì)的觀點(diǎn)來(lái)看，過(guò)度擬合是我們對(duì)看到的實(shí)際數(shù)據(jù)太過(guò)敏感的體現(xiàn)。那么，解決方案也是直截了當(dāng)?shù)模何覀儽仨毱胶馕覀兊脑竿?，找到我們?yīng)該使用的對(duì)抗復(fù)雜性的模型進(jìn)行分析。 在幾個(gè)相互競(jìng)爭(zhēng)的模型中選擇一種方法就是奧卡姆的剃刀原理，它表明，所有的事情都是平等的，最簡(jiǎn)單的假設(shè)可能就是最正確的那個(gè)。
在20世紀(jì)60年代，蘇聯(lián)數(shù)學(xué)家安德烈·季霍諾夫給出了一種答案：引入一個(gè)額外項(xiàng)來(lái)計(jì)算懲罰更復(fù)雜的解決方案。如果我們引入復(fù)雜性懲罰，那么更復(fù)雜的模型需要做的不僅是做得更好，更重要的是解釋數(shù)據(jù)以證明其更大復(fù)雜性的合理性。計(jì)算機(jī)科學(xué)家將這個(gè)原則——使用約束來(lái)懲罰模型的復(fù)雜性，稱(chēng)為正則化。
那么這些復(fù)雜性懲罰是什么呢？1996年，生物統(tǒng)計(jì)學(xué)家羅伯特·蒂什拉尼開(kāi)發(fā)“套索算法”，通過(guò)對(duì)模型中各因素總和的懲罰，將這種下行壓力放到因素的總權(quán)重上，套索算法將驅(qū)使它們降為零，只有對(duì)結(jié)果又很大影響的因素才保留。同一類(lèi)原則復(fù)雜度懲罰原則也同樣出現(xiàn)在自然界中。例如，新陳代謝的負(fù)擔(dān)對(duì)生物體的復(fù)雜度起到剎車(chē)作用，對(duì)過(guò)度精細(xì)的機(jī)體運(yùn)行引入熱量懲罰機(jī)制，以免進(jìn)化成更復(fù)雜的大腦，因?yàn)閺倪M(jìn)化論的角度，一個(gè)更復(fù)雜的大腦無(wú)法提供足夠的報(bào)酬。
如果我們觀察生物（包括人類(lèi)）的進(jìn)化方式，我們會(huì)注意到一些有趣的現(xiàn)象：變化發(fā)生得很緩慢。這意味著，現(xiàn)代生物的屬性不僅受制于它們目前所處的環(huán)境，也由它們過(guò)去的歷史共同塑造而成。過(guò)度擬合的概念給我們提供了一個(gè)能在進(jìn)化的壓力下看到其長(zhǎng)處的機(jī)會(huì)。雖然交叉神經(jīng)纖維和改變用途的頜骨似乎已經(jīng)是最理想的安排，但至少我們應(yīng)該認(rèn)識(shí)到，我們并不一定要讓進(jìn)化去完全優(yōu)化生物，以適應(yīng)生態(tài)環(huán)境的每一點(diǎn)改變，這樣做會(huì)使其對(duì)環(huán)境的變化極其敏感。另一方面，必須利用現(xiàn)有的材料，施加一種有用的約束。這使得它很難引起生物體結(jié)構(gòu)的急劇變化，更難擬合。作為一個(gè)物種，受制于過(guò)去，就使我們不能完全地調(diào)整以適應(yīng)目前所知的情況，但這有助于我們?cè)谖粗奈磥?lái)保持身體強(qiáng)健。
在機(jī)器學(xué)習(xí)中，緩慢移動(dòng)的有點(diǎn)最明顯出現(xiàn)在一種稱(chēng)為早期停止的正則化技術(shù)中。在各種機(jī)器學(xué)習(xí)任務(wù)中，正則化的有效性表明，我們可以通過(guò)有意識(shí)地思考和少做一些事情來(lái)做出更好的決定。如果我們最先想到的因素可能是最重要的因素，那么如果思考的量超過(guò)某一個(gè)度的話，就不僅是浪費(fèi)時(shí)間和努力，它將會(huì)讓我們找到更糟糕的解決方案。早期停止為理性的論證而不是一味地推理提供了基礎(chǔ)。
如果你有很高的不確定性和有限的數(shù)據(jù)，那么務(wù)必提前停止。如果你不清楚你的工作將如何被評(píng)估，以及由誰(shuí)來(lái)評(píng)估，那么你就不值得花額外的時(shí)間來(lái)對(duì)你自己（或者其他人）的特質(zhì)做出所謂完美的判斷。不確定性越大，你所能衡量的東西和真正重要的東西之間的差距就越大，你就越應(yīng)該注意過(guò)度擬合的風(fēng)險(xiǎn)，也就是說(shuō)，你越喜歡簡(jiǎn)單，就應(yīng)該越早停下來(lái)。
八、
松弛，順其自然
正如計(jì)算機(jī)科學(xué)家在過(guò)去幾十年里所發(fā)現(xiàn)的那樣，無(wú)論我們的計(jì)算機(jī)處理速度有多快，我們?nèi)绾吻擅畹貙?duì)它們進(jìn)行編程，一個(gè)問(wèn)題的完美解決方案都是不存在的。事實(shí)上，沒(méi)有人能像計(jì)算機(jī)科學(xué)家那樣理解，在面對(duì)看似無(wú)法控制的挑戰(zhàn)時(shí)，你既不應(yīng)該永遠(yuǎn)辛苦工作，也不應(yīng)該放棄，但我們將會(huì)看到第三種嘗試。
"約束優(yōu)化“問(wèn)題：如何找到一組變量的最佳排列，并給出特定的規(guī)則和積分法。這就是”旅行推銷(xiāo)員問(wèn)題“，到目前為止還沒(méi)有得到解決的問(wèn)題。如果，如何最好地解決那些最佳答案似乎遙不可及的問(wèn)題，如何學(xué)會(huì)放松。
在計(jì)算機(jī)科學(xué)中最簡(jiǎn)單的放松形式之一就是約束松弛。在這項(xiàng)技術(shù)中，研究人員消除了一些問(wèn)題的約束，并著手解決他們希望得到解決的問(wèn)題。然后，在他們?nèi)〉靡欢ǖ倪M(jìn)展之后，他們?cè)噲D再將約束添加進(jìn)去。也就是說(shuō)，在把問(wèn)題帶回現(xiàn)實(shí)之前，他們會(huì)讓問(wèn)題暫時(shí)更容易處理。
旅行推銷(xiāo)員問(wèn)題，就像尋找最佳座位安排的問(wèn)題一樣，是一種特殊的最優(yōu)化問(wèn)題，稱(chēng)為“離散優(yōu)化”，即在解決方案中沒(méi)有平滑的連續(xù)統(tǒng)一體。推銷(xiāo)員要么到這個(gè)鎮(zhèn)子，要么到那個(gè)鎮(zhèn)，你要么在5號(hào)桌，要么在6號(hào)桌。兩者之間沒(méi)有灰色地帶。
有很多方法可以對(duì)一個(gè)問(wèn)題進(jìn)行松弛，我們已經(jīng)看到了三個(gè)最重要的問(wèn)題。首先，約束松弛，簡(jiǎn)單地消除一些約束，在回到現(xiàn)實(shí)之前，先在更寬松的問(wèn)題上取得進(jìn)展。第二，持續(xù)松弛，將離散的或二進(jìn)制的選擇變成連續(xù)體：當(dāng)決定是選冰紅茶還是檸檬水時(shí)，先想象一個(gè)50：50的“阿諾德·帕爾默”混合，然后再向上或向下延展。第三，拉格朗日松弛，把不可能的變成僅僅是懲罰，要學(xué)會(huì)扭曲規(guī)則的藝術(shù)（或打破規(guī)則，并接受后果）。例如，搖滾樂(lè)隊(duì)在決定將哪些歌曲放入一個(gè)有限的專(zhuān)輯中時(shí)，就要面對(duì)計(jì)算機(jī)科學(xué)家稱(chēng)之為的“背包問(wèn)題”——將一組不同大小和重要性的項(xiàng)目裝進(jìn)一個(gè)有限的集合中的難題。在嚴(yán)格的公式中，背包問(wèn)題是眾所周知的棘手問(wèn)題，但這并不妨礙我們松弛的搖滾明星們做決定。正如幾個(gè)著名的例子所證明的那樣，有時(shí)候稍微超過(guò)城市的宵禁，并付出相應(yīng)的懲罰，好過(guò)把節(jié)目限制在適當(dāng)?shù)臅r(shí)間內(nèi)。事實(shí)上，即使你沒(méi)有違規(guī)，你也可以想象它具有啟發(fā)性。
九、隨機(jī)性? ? ?十、網(wǎng)絡(luò)連接? ??十一、博弈論 （略）
