算法之道(第2版)

前言

前言：起初神創(chuàng)造天地。地是空虛混沌，淵面黑暗；神的靈運(yùn)行在水面上。神說："要有光?！本陀辛斯狻Ｉ窨垂馐呛玫?，就把光與暗分開了。神稱光為晝，暗為夜。有晚上，有早晨，這是頭一日?！窬驼罩约旱男蜗笤烊??！裾f："看??！我將遍地上一切結(jié)種子的菜蔬和一切樹上所結(jié)有核的果子，全賜給你們做食物。至于地上的走獸和空中的飛鳥，以及各樣在地上爬的有生命的物，我將青草賜給它們做食物。"事就這樣成了。神看著一切所造的都甚好。有晚上，有早晨，是第六日。天地萬物都造齊了。6天圣經(jīng)上寫著：神6天創(chuàng)造天地萬有，第7日安歇。對(duì)于神創(chuàng)論者來說，這是不可懷疑的事實(shí)。但對(duì)于進(jìn)化論者來說，6天創(chuàng)造一切根本就不可能。作為一本算法書，我們當(dāng)然不打算加入神創(chuàng)論和進(jìn)化論者的永無休止的爭(zhēng)論當(dāng)中去。我們關(guān)心的是這么一個(gè)問題：圣經(jīng)上為什么給出的是6天，而不是其他的時(shí)間長度。不管是神創(chuàng)論者還是進(jìn)化論者，弄清楚6這個(gè)數(shù)字的來歷很可能會(huì)對(duì)己方的觀點(diǎn)有所幫助。在這6天里，神將他的創(chuàng)作方程式重復(fù)了6次，每天1次。對(duì)于全能的神來說，他完全可以在1天、1秒或者任何他所愿意的時(shí)間長度里創(chuàng)造天地萬物，但卻為什么是不多不少的6天呢？而不管圣經(jīng)上的“1天”是多長，這個(gè)問題都是值得討論的。我們知道，任何一個(gè)自然數(shù)的約數(shù)中都有1和它本身，而所有小于它本身的因數(shù)叫做這個(gè)自然數(shù)的真約數(shù)。例如，6的所有真約數(shù)是1、2、3；數(shù)字8的真約數(shù)是1、2、4。如果一個(gè)數(shù)的真約數(shù)之和等于這個(gè)自然數(shù)本身，則這個(gè)自然數(shù)就稱為完全數(shù)，或者完美數(shù)。例如，6=1＋2＋3，因此6是完美數(shù)；而8(1+2+4，因此8不是完美數(shù)。因此，神6天創(chuàng)造世界，暗示著該創(chuàng)造是完美的！以完美數(shù)來昭示創(chuàng)造的完美，似乎合情合理。但問題是，完美數(shù)只有6這一個(gè)數(shù)嗎？如果不是，為什么不使用其他的完美數(shù)呢？答案是，完美數(shù)雖然不只有6這一個(gè)，但確實(shí)數(shù)量稀少。一直到現(xiàn)在(2009年6月)，數(shù)學(xué)家們探索了2600年，并且現(xiàn)代數(shù)學(xué)家們還借助了超級(jí)計(jì)算機(jī)的幫助，但也僅僅找到了47個(gè)完美數(shù)。其中第1個(gè)完美數(shù)是6，接下來的4個(gè)完美數(shù)分別是：28、496、8128、33550336。而第47個(gè)完美數(shù)有25956377個(gè)數(shù)位(注意，是數(shù)位，不是數(shù)值)，它的數(shù)值為：243112608×(243112609?1)。完美數(shù)的稀少昭示著達(dá)到完美的難度，而神選擇6天來創(chuàng)造天地萬有也許是因?yàn)?是最小的完美數(shù)，即創(chuàng)造天地萬有對(duì)于神來說是輕而易舉的一件事情……完美與算法完美數(shù)由于其各種神秘屬性(真約數(shù)之和等于自身只是其中的一種性質(zhì))而受到了特殊的關(guān)注。但到底哪些數(shù)是完美數(shù)則不是一件容易判斷的事情。顯然，按照完美數(shù)的定義，判斷一個(gè)數(shù)是否是完美數(shù)的不二法則是找出它的所有真約數(shù)，然后求和看看其是否等于自身。而這種方法效率太過低下，因?yàn)檫@意味著因式分解，而這是十分困難的(本書后面將會(huì)討論到這個(gè)問題)。如果判斷一個(gè)數(shù)是否是完美數(shù)就已經(jīng)非常困難，那么要找出所有的完美數(shù)則更是一個(gè)難上加難的任務(wù)。因?yàn)檫@就意味著將所有的數(shù)進(jìn)行上面描述的判斷驗(yàn)證：因式分解。這似乎是人類不可能完成的任務(wù)。即使用世界上超快的計(jì)算機(jī)來進(jìn)行計(jì)算，情況也不會(huì)有任何數(shù)量級(jí)的改善。顯然，我們需要新的解決方案，而不是發(fā)明或使用新的計(jì)算工具！研究這樣的解決方案就可以歸結(jié)到算法的范疇里，因?yàn)槿绾胃咝У亟鉀Q問題正是算法要研究的核心課題。有意思的是，判斷和搜索完美數(shù)是算法的研究范疇，而算法本身的追求卻也是“完美”。算法無處不在如果你覺得算法只是用來研究解決找出完美數(shù)之類的“漫無邊際的問題”，那就大錯(cuò)特錯(cuò)了。也許算法這個(gè)名詞聽上去很抽象，讓人聯(lián)想不到任何具體的物體。也許你會(huì)覺得算法與自己的生活并無太多關(guān)系，它只不過存在于那些閑得無聊的數(shù)學(xué)家或計(jì)算機(jī)專業(yè)人士的腦海中。但事實(shí)真是這樣嗎？當(dāng)然不是。如果我們告訴你算法就是解決各種問題的方法，你就不會(huì)覺得它太抽象，與生活無關(guān)了吧。事實(shí)是，算法無處不在。每個(gè)人每天都在使用不同的算法來活出自己的人生，比如你去食堂買飯會(huì)選擇一個(gè)較短的隊(duì)列，而有人則可能選擇一個(gè)推進(jìn)速度更快的隊(duì)列。每天起床后，你可能先讀一會(huì)兒書，再去吃早飯；另外一個(gè)人則可能先去吃早飯，然后再看書。所有這些行為都是算法或算法一部分的體現(xiàn)。也許運(yùn)行這些算法并不在你的思想意識(shí)里，也許你并不知道算法在幫助自己的生活，但它確實(shí)存在。這些算法也許沒有經(jīng)過精心設(shè)計(jì)，沒有經(jīng)過仔細(xì)分析，但它還是算法！2009年7月23日下午，我在游覽云南省大理市的蝴蝶泉時(shí)由于泉水邊的石頭很滑，在用泉水洗手時(shí)(導(dǎo)游金花說用該泉水洗手會(huì)帶來好運(yùn))不慎滑落到蝴蝶泉水(見圖3)里面全身濕透。(據(jù)說一天至多只會(huì)有一個(gè)人滑落到泉里，可見我的運(yùn)氣不錯(cuò)！看來“蝴蝶泉邊好梳妝”的歌詞也許應(yīng)該改為“蝴蝶泉里好沖涼”。)泉水冰冷透涼，而大理的氣溫又低。這樣，我就面臨一個(gè)是否更換全身衣服的選擇。問題是，旅游團(tuán)需要馬上趕去登游船游覽洱海風(fēng)光，而若找地方或者回旅店換衣服就將趕不上游船。如何處理這件事情就是一個(gè)算法問題：是先上游船再在船上找地方換衣服，還是找個(gè)地方換衣服而放棄游覽蒼山洱海。顯然不同的算法有著不同的收益和代價(jià)。如果能夠在游船上找到合適的地方更換衣服，則采用先上游船再換衣服的算法為佳；否則就是放棄游覽的算法更好，因?yàn)槿绻麅霾×孙@然就不劃算了。最后，我選擇了在游船上更換衣服的算法：在游船上找到了一個(gè)貴賓室更衣。算法由問題驅(qū)動(dòng)算法的發(fā)現(xiàn)總是由相關(guān)的問題驅(qū)動(dòng)的。拿排序來說，因?yàn)樯钪械教幎汲錆M次序，每個(gè)人都要接受自己在某個(gè)次序里的位置。比如，各種排名、評(píng)優(yōu)、民意調(diào)查等，最后的結(jié)果都體現(xiàn)為一個(gè)次序！看來，“沒有次序無以成方圓”并不是空穴來風(fēng)！而談到排序用的方法，人們很自然地想到了插入法。因?yàn)檫@種樸素的算法和人的思維方式非常類似：它就是人們打牌時(shí)整理手中撲克牌的算法。但是隨著數(shù)據(jù)量的增多，插入排序的效率缺陷迅速變?yōu)槿藗儫o法容忍的缺點(diǎn)。于是人們發(fā)明了歸并排序、堆排序、快速排序等，這些排序的方法大大改善了速度，但是人們卻并不滿足于此，因此又發(fā)明了效率更高的線性排序。表1給出的是各種排序算法平均情況下的效率比較：最上面一行的數(shù)字代表輸入的規(guī)模，如10表示一共有10個(gè)數(shù)據(jù)項(xiàng)，1M表示一共有100萬個(gè)數(shù)據(jù)項(xiàng)。其他格子里面的數(shù)據(jù)為相應(yīng)算法在相應(yīng)輸入規(guī)模下完成排序所需要的時(shí)間，單位為毫秒。所有輸入數(shù)據(jù)為隨機(jī)產(chǎn)生。一個(gè)個(gè)新的算法都是為了解決前面算法遺留的問題而產(chǎn)生的。從表1里的數(shù)字可以看出，一般來說，隨著新的算法出現(xiàn)，排序效率在不斷提高。不過，雖然每個(gè)算法似乎解決了前面算法的遺留問題，但新的問題也會(huì)被有意或無意地引入。例如，線性排序雖然將排序的時(shí)間復(fù)雜性降低到線性級(jí)，但各種前提條件極大地限制了其應(yīng)用范圍。也許這就是算法永遠(yuǎn)也不能或不會(huì)停止發(fā)展的一個(gè)原因吧。算法是計(jì)算機(jī)的靈魂因?yàn)槿瞬皇侨艿?，一個(gè)時(shí)刻只能做一件事情，所以做事情就要有一個(gè)步驟。由于算法要滿足人的這種特性，因此它通常表示為一個(gè)做事情的行為序列。因此，從一般意義上說，算法就是求解問題的步驟。由于計(jì)算機(jī)的計(jì)算操作完全是一步一步進(jìn)行，因此算法的上述性質(zhì)用于計(jì)算機(jī)是再合適不過了，可以說算法彌漫在計(jì)算機(jī)的一切行為上。如果說操作系統(tǒng)是計(jì)算機(jī)的心智，那么算法就是計(jì)算機(jī)的靈魂。理解靈魂當(dāng)然不是一件容易的事情，由于它高度抽象與簡潔，許多學(xué)生都望而卻步。先看一個(gè)紙牌魔術(shù)：1)任選一位觀眾將一副撲克牌充分洗好。2)背對(duì)觀眾，請(qǐng)觀眾隨機(jī)抽出一張牌，記住牌面，然后將這張牌放回整副牌的最上面。3)接過牌后，洗牌幾次。洗牌的時(shí)候保持最上面一張牌不動(dòng)。4)對(duì)觀眾說：“我來教你魔法，只要吹一口氣，就能把剛才你抽的牌吹到任意位置上”。5)請(qǐng)觀眾說出一個(gè)數(shù)字，比如說10，然后一邊吹氣，一邊想著剛才說的數(shù)字10。6)在吹完氣后，請(qǐng)觀眾一張一張地將上面的牌取出放在桌上。7)到第10張時(shí)，將牌翻開，發(fā)現(xiàn)并不是其原來抽的牌。8)接回整副牌，并把上一個(gè)步驟里取出堆放在桌上的牌收起，仍放在整副牌的最上面。9)然后洗牌幾次，洗牌的時(shí)候保持上面放回來的那堆牌不動(dòng)。10)從觀眾手上拿回剛才翻開的那張牌，插入最上面9個(gè)位置中的任意一個(gè)。11)對(duì)觀眾說：“你剛才不是在想著那個(gè)數(shù)字的時(shí)候吹的氣，而是在吹氣的時(shí)候想著那個(gè)數(shù)字，而這是完全不同的兩回事。我現(xiàn)在演示如何吹氣?！睂?duì)著牌吹一口氣。12)請(qǐng)觀眾從上到下數(shù)牌，到第10張時(shí)翻開。13)這張翻開的牌就是觀眾一開始抽的那張牌。讀者看明白了上面的這個(gè)魔術(shù)了嗎？這里面隱藏著一個(gè)算法。如果看懂了就可以在朋友面前一顯身手了。當(dāng)然，如果沒有看懂也沒有什么關(guān)系。算法本來就不是輕易讓人看懂的嘛。如果這些問題讀者都能回答，那么恭喜你?？磥硭惴ǚ治鰧?duì)于讀者來說將是件很容易的事情，不過可能也不一定。如果你回答不出這些問題，不用擔(dān)心，因?yàn)榛卮鹬T如此類的問題就是本書的目的。當(dāng)然了，本書回答的遠(yuǎn)不止這么幾個(gè)簡單問題，而是會(huì)闡述更重要的算法精髓：算法思想、戰(zhàn)略和分析！

內(nèi)容概要

　　本書追求的目標(biāo)是算法背后的邏輯，是一本啟示書，而不是一本包羅萬象的算法大全。因此，本書甄選了那些最能展現(xiàn)算法思想、戰(zhàn)略和精華，并能夠有效訓(xùn)練算法思維的內(nèi)容。本書將算法的討論分為五篇：算法基礎(chǔ)篇、算法設(shè)計(jì)篇、算法分析篇、經(jīng)典算法篇、難解與無解篇。每篇分別討論算法的一個(gè)方面：基礎(chǔ)、設(shè)計(jì)、分析、經(jīng)典和難解問題。第2版還對(duì)進(jìn)程調(diào)度問題、跳轉(zhuǎn)表問題、概率分析應(yīng)用、遺傳算法等方面進(jìn)行了論述。
　　本書既可以作為大學(xué)本科或研究生的算法教材或參考書，也可以作為對(duì)算法有興趣的讀者提升認(rèn)知深度的讀物。

作者簡介

　　鄒恒明，美國密歇根大學(xué)（University of Michigan-Ann
Arbor）計(jì)算機(jī)科學(xué)與工程博士、中國科學(xué)院計(jì)算技術(shù)研究所碩士、華中科技大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)士。曾先后在美國IBM、美國國家數(shù)據(jù)公司、美國朗訊和美國EMC公司任職8年多?，F(xiàn)為上海交通大學(xué)教授。

書籍目錄

前言
第一篇　算法基礎(chǔ)篇
　第1章　從無有到無窮
　　1.1　意念與現(xiàn)實(shí)
　　1.2　什么是算法
　　1.3　算法的表示
　　1.4　算法之魂
　　1.5　如何比較速度
　　1.6　算法與計(jì)算機(jī)的關(guān)系
　　1.7　算法的范疇
　　1.8　為什么學(xué)習(xí)算法
　　思考題
　第2章　計(jì)數(shù)與漸近
　　2.1　算法的分析
　　　2.1.1　正確性分析
　　　2.1.2　時(shí)空效率分析
　　　2.1.3　時(shí)空特性分析
　　2.2　計(jì)數(shù)：算法分析的核心
　　2.3　算法設(shè)計(jì)
　　2.4　算法效率表示
　　2.5　漸近分析
　　2.6　表示
　　2.7　最好、最壞、平均
　　2.8　另一類定義
　　2.9　性質(zhì)
　　2.10　要更快的計(jì)算機(jī)還是要更快的算法
　　思考題
　第3章　分治與遞歸
　　3.1　分而治之為上策
　　3.2　分治策略
　　3.3　遞歸表達(dá)式求解
　　　3.3.1　遞歸樹法
　　　3.3.2　替換解法
　　　3.3.3　大師解法
　　3.4　分治策略舉例1：乘方運(yùn)算
　　3.5　生命中不能承受之重：矩陣乘法
　　3.6　魔鬼序列：斐波那契序列
　　　3.6.1　由底至上
　　　3.6.2　使用通式
　　　3.6.3　使用矩陣乘方
　　3.7　VLSI 布線
　　3.8　多項(xiàng)式乘法
　　3.9　分治就在潛意識(shí)
　　思考題
第二篇　算法設(shè)計(jì)篇
　第4章　動(dòng)態(tài)規(guī)劃思想
　　4.1　什么是動(dòng)態(tài)規(guī)劃
　　4.2　流水線問題
　　4.3　最長公共子序列
　　　4.3.1　第一種解法：蠻力策略
　　　4.3.2　第二種解法：動(dòng)態(tài)規(guī)劃
　　4.4　最長公共子序列變種
　　4.5　記憶遞歸法
　　4.6　空間效率改善
　　4.7　最優(yōu)二叉搜索樹
　　　4.7.1　遞歸解法
　　　4.7.2　計(jì)算最優(yōu)答案
　　4.8　最優(yōu)子結(jié)構(gòu)與重疊子問題
　　　4.8.1　最優(yōu)子結(jié)構(gòu)
　　　4.8.2　重疊子問題
　　4.9　動(dòng)態(tài)規(guī)劃與靜態(tài)規(guī)劃的關(guān)系
　　4.10　動(dòng)態(tài)規(guī)劃與靜態(tài)規(guī)劃的相互轉(zhuǎn)換
　　思考題
　第5章　貪婪選擇思想
　　5.1　僅有動(dòng)態(tài)規(guī)劃是不夠的
　　5.2　什么是貪婪
　　5.3　背包問題
　　5.4　貪婪選擇屬性
　　5.5　教室規(guī)劃問題
　　5.6　最小生成樹
　　　5.6.1　Kruskal算法的正確性
　　　5.6.2　Kruskal算法的時(shí)間分析
　　5.7　Prim算法
　　5.8　霍夫曼樹和霍夫曼編碼
　　　5.8.1　霍夫曼樹
　　　5.8.2　霍夫曼編碼
　　　5.8.3　霍夫曼編碼的無前綴編碼性質(zhì)
　　5.9　進(jìn)程調(diào)度問題
　　5.10　貪婪選擇屬性
　　5.11　標(biāo)準(zhǔn)分治、動(dòng)態(tài)規(guī)劃和貪婪選擇的比較
　　思考題
　第6章　隨機(jī)化思想
　　6.1　為什么要隨機(jī)化
　　6.2　隨機(jī)的平方
　　6.3　什么是隨機(jī)化算法
　　6.4　拉斯維加斯算法
　　6.5　蒙特卡羅算法
　　6.6　素性測(cè)試
　　6.7　矩陣乘積驗(yàn)證器
　　6.8　隨機(jī)化最小生成樹算法
　　　6.8.1　Karger-Klein-Tarjan算法
　　　6.8.2　結(jié)點(diǎn)降低算法
　　　6.8.3　線性時(shí)間最小生成樹算法
　　　6.8.4　線性時(shí)間最小生成樹算法的時(shí)間成本分析
　　6.9　隨機(jī)數(shù)的生成
　　6.10　隨機(jī)化算法的應(yīng)用
　　思考題
第三篇　算法分析篇
　第7章　概率分析
　　7.1　一切都在概率中
　　7.2　什么是概率分析
　　7.3　夢(mèng)幻情人的代價(jià)
　　　7.3.1　直接分析
　　　7.3.2　最壞情況分析
　　　7.3.3　最好情況分析
　　　7.3.4　平均情況分析
　　　7.3.5　平均情況下成本的概率分析
　　　7.3.6　概率分析結(jié)果的有效性
　　　7.3.7　正確概率分析的保障
　　7.4　夢(mèng)幻情人的概率
　　7.5　隨機(jī)排列問題
　　7.6　跳轉(zhuǎn)表問題
　　　7.6.1　跳轉(zhuǎn)表插入操作
　　　7.6.2　隨機(jī)化跳轉(zhuǎn)表構(gòu)建算法
　　7.7　南柯一夢(mèng)：從無窮到無有
　　7.8　概率分析的其他應(yīng)用
　　思考題
　第8章　攤銷分析
　　8.1　什么是攤銷分析
　　8.2　攤銷分析與數(shù)據(jù)結(jié)構(gòu)
　　8.3　攤銷分析的幾種方法
　　8.4　聚類分析
　　　8.4.1　棧操作的聚類分析
　　　8.4.2　二進(jìn)制計(jì)數(shù)器的聚類分析
　　8.5　會(huì)計(jì)分析
　　8.6　勢(shì)能分析
　　　8.6.1　棧操作的勢(shì)能分析
　　　8.6.2　二進(jìn)制計(jì)數(shù)器的勢(shì)能分析
　　8.7　攤銷分析應(yīng)用：表格擴(kuò)展的代價(jià)
　　　8.7.1　動(dòng)態(tài)表插入操作的聚類分析
　　　8.7.2　動(dòng)態(tài)表插入操作的會(huì)計(jì)分析
　　　8.7.3　動(dòng)態(tài)表插入操作的勢(shì)能分析
　　8.8　運(yùn)氣不好就攤銷
　　思考題
　第9章　競(jìng)爭(zhēng)分析
　　9.1　什么是競(jìng)爭(zhēng)分析
　　9.2　在線算法和離線算法
　　9.3　競(jìng)爭(zhēng)力
　　9.4　健忘對(duì)手和優(yōu)良對(duì)手
　　9.5　線性表更新問題
　　9.6　前置移動(dòng)算法的競(jìng)爭(zhēng)分析
　　9.7　聚類問題
　　　9.7.1　聚類問題的次優(yōu)解算法
　　　9.7.2　CLUSTERING-ALGORITHM算法的競(jìng)爭(zhēng)分析
　　9.8　競(jìng)爭(zhēng)分析與普通算法分析
　　思考題
第四篇　經(jīng)典算法篇
　第10章　排序與次序
　　10.1　排序無處不在
　　10.2　插入排序
　　　10.2.1　插入排序的效率分析
　　　10.2.2　折半插入排序
　　10.3　歸并排序
　　10.4　快速排序
　　　10.4.1　快速排序的過程
　　　10.4.2　快速排序的時(shí)間復(fù)雜性分析
　　　10.4.3　最壞情況分析
　　　10.4.4　最好情況分析
　　　10.4.5　平均情況分析
　　10.5　隨機(jī)化快速排序
　　10.6　排序的下限
　　10.7　線性排序
　　10.8　計(jì)數(shù)排序
　　10.9　基數(shù)排序
　　　10.9.1　基數(shù)排序的正確性
　　　10.9.2　基數(shù)排序的時(shí)間效率分析
　　10.10　桶排序
　　　10.10.1　桶排序的定義
　　　10.10.2　桶排序的正確性
　　　10.10.3　桶排序的時(shí)間復(fù)雜性分析
　　10.11　次序選擇
　　10.12　快速次序選擇算法
　　10.13　隨機(jī)快速次序選擇算法
　　10.14　最壞情況下的線性選擇算法
　　　10.14.1　杠桿點(diǎn)好壞分析
　　　10.14.2　算法時(shí)間復(fù)雜性分析
　　思考題
　第11章　搜索與散列
　　11.1　搜索問題
　　11.2　順序搜索
　　11.3　折半搜索
　　11.4　常數(shù)搜索
　　11.5　散列搜索
　　11.6　散列函數(shù)選擇
　　　11.6.1　直接散列
　　　11.6.2　除法（模除法）散列
　　　11.6.3　乘法散列
　　　11.6.4　乘法散列的賭徒原理
　　　11.6.5　乘方取中法
　　11.7　散列算法的碰撞問題
　　　11.7.1　開放尋址散列
　　　11.7.2　開放尋址散列的時(shí)間成本
　　　11.7.3　開放尋址下成功搜索的時(shí)間成本
　　　11.7.4　封閉尋址散列
　　　11.7.5　探尋序列的設(shè)計(jì)
　　　11.7.6　封閉尋址散列的效率分析
　　　11.7.7　搜索不成功的時(shí)間成本
　　　11.7.8　成功搜索的效率分析
　　11.8　散列表元素刪除
　　11.9　隨機(jī)化散列
　　11.10　全域散列
　　11.11　完美散列
　　思考題
　第12章　最短路徑
　　12.1　劍指羅馬
　　12.2　最短路徑問題
　　12.3　單源單點(diǎn)最短路徑問題
　　　12.3.1　深度優(yōu)先與廣度優(yōu)先搜索
　　　12.3.2　深度優(yōu)先解法
　　12.4　單源多點(diǎn)最短路徑問題
　　　12.4.1　最短路徑的性質(zhì)
　　　12.4.2　Dijkstra最短路徑算法
　　　12.4.3　Dijkstra算法舉例
　　　12.4.4　Dijkstra算法與洪水泛濫
　　　12.4.5　Dijkstra算法的正確性
　　　12.4.6　Dijkstra算法的時(shí)間復(fù)雜性
　　12.5　Bellman-Ford算法
　　　12.5.1　負(fù)權(quán)重的應(yīng)對(duì)方式
　　　12.5.2　Bellman-Ford算法的正確性
　　　12.5.3　負(fù)循環(huán)檢查問題
　　　12.5.4　Bellman-Ford算法的時(shí)間復(fù)雜性
　　12.6　多源多點(diǎn)最短路徑問題
　　　12.6.1　多源多點(diǎn)最短路徑問題解決思路
　　　12.6.2　直接動(dòng)態(tài)規(guī)劃解法
　　　12.6.3　矩陣乘法解法
　　　12.6.4　Floyd-Warshall算法
　　　12.6.5　Johnson算法
　　　12.6.6　Johnson等效變換
　　　12.6.7　差限問題解決
　　12.7　天意難違
　　思考題
第五篇　難解與無解篇
　第13章　易解與難解
　　13.1　我們戰(zhàn)無不勝嗎
　　13.2　易解與難解
　　13.3　決策問題和優(yōu)化問題
　　13.4　決策問題
　　13.5　P類問題
　　13.6　NP類問題
　　13.7?。ù_定性）圖靈機(jī)
　　13.8　非確定性圖靈機(jī)
　　13.9　非確定性算法
　　13.10　回到NP類問題
　　13.11　P和NP
　　13.12　搜索問題、決策問題和優(yōu)化問題
　　13.13　有沒有解和是否可決定
　　思考題
　第14章　NP完全問題
　　14.1　玉龍雪山下的審判
　　14.2　NP完全問題的定義
　　14.3　NP完全的重要性
　　14.4　多項(xiàng)式時(shí)間規(guī)約
　　14.5　如何證明一個(gè)問題S是NP完全問題
　　14.6　第1個(gè)NP完全問題的證明
　　14.7　庫克定理
　　14.8　3-SAT問題
　　14.9　證明NP難的技巧
　　14.10　整數(shù)規(guī)劃
　　14.11　獨(dú)立集問題
　　14.12　漢密爾頓回路問題
　　14.13　討論：弱NP完全、強(qiáng)NP完全和中NP完全
　　思考題
　第15章　無解與近似
　　15.1　難解問題
　　15.2　不可決定問題
　　15.3　程序終結(jié)的判斷
　　15.4　難解之題的求解
　　15.5　智能窮舉、近似算法和本地搜索
　　15.6　智能窮舉之回溯策略
　　15.7　智能窮舉之分支限界
　　15.8　貪婪近似策略
　　15.9　啟發(fā)式搜索策略
　　15.10　模擬退火算法
　　　15.10.1　模擬退火算法的思想
　　　15.10.2　模擬退火算法的基本循環(huán)
　　　15.10.3　退火算法描述
　　15.11　基因／遺傳算法
　　　15.11.1　生物進(jìn)化與遺傳
　　　15.11.2　遺傳算法的基本要義
　　　15.11.3　遺傳算法的實(shí)現(xiàn)
　　　15.11.4　遺傳算法的基本運(yùn)算過程
　　　15.11.5　遺傳算法的現(xiàn)狀
　　15.12　概率盡在一切中
　　思考題
結(jié)語　算法之道
附錄　算法隨想
參考文獻(xiàn)

章節(jié)摘錄

版權(quán)頁：第1章 從無有到無窮在第一類弗里德曼宇宙模型中，第四維—時(shí)間，正如空間一樣，在范圍上是有限的。它如一根具有兩個(gè)端點(diǎn)或邊界的線。因此時(shí)間具有終結(jié)，而且它也有一個(gè)開端。事實(shí)上，在宇宙具有我們觀測(cè)到的物質(zhì)總量的情形下，由愛因斯坦方程得出的所有解中，都有一個(gè)非常重要的特征：在過去某一時(shí)刻(大約137億年以前)相鄰星系之間的距離必須為零。換言之，整個(gè)宇宙被擠壓在零尺度的單獨(dú)一點(diǎn)，就像一個(gè)半徑為零的球。那時(shí)，宇宙的密度和時(shí)空曲率都為無限大。它是我們稱做大爆炸的時(shí)刻?！允返傥?霍金《時(shí)間簡史》這個(gè)零尺度的單獨(dú)一點(diǎn)被物理學(xué)家稱做“原點(diǎn)”。它的另一個(gè)名字是奇異點(diǎn)(singularity)。但是零尺度是什么意思呢？霍金曾解釋過：零尺度就是不占空間。那么不占空間是什么意思呢？也許讀者猜出來了：沒有(nothing)！即虛無。實(shí)際上，物理學(xué)家們普遍認(rèn)為在原點(diǎn)之外沒有空間，空間也是大爆炸后的產(chǎn)物。也就是說，宇宙是從無到有的，用希臘文來說就是Ex Nihilo(見圖1-1)。圖1-1 Ex Nihilo：宇宙從無到有的一剎那整個(gè)宇宙從無到有對(duì)一般人來說都很難理解，而這個(gè)原點(diǎn)是誰或者如何放在那里也是眾說紛紜。不過，這不是本書準(zhǔn)備要討論的問題。本書關(guān)心的是算法，而算法具有一個(gè)與宇宙起源類似的性質(zhì)：從無到有。不過這個(gè)從無到有卻有著非同一般或者說更加豐富的意義，下面將詳細(xì)分析。1.1 意念與現(xiàn)實(shí)先看一個(gè)例子。給你一個(gè)無限容積的罐子和無限個(gè)球，球從1開始連續(xù)編號(hào)。在差1分鐘到零點(diǎn)時(shí)：將標(biāo)號(hào)為1～10的10個(gè)球放進(jìn)罐子，然后將10號(hào)球從罐子拿出。在差1/2分鐘到零點(diǎn)時(shí)：將標(biāo)號(hào)為11～20的10個(gè)球放進(jìn)罐子，然后將20號(hào)球從罐子拿出。在差1/4分鐘到零點(diǎn)時(shí)：將標(biāo)號(hào)為21～30的10個(gè)球放進(jìn)罐子，然后將30號(hào)球從罐子拿出?！瓦@樣將游戲進(jìn)行下去。假定放球和取球不占時(shí)間，請(qǐng)問，當(dāng)時(shí)鐘指向零點(diǎn)時(shí)，罐子里還剩多少個(gè)球？這個(gè)答案似乎很直接：無限個(gè)球！這是因?yàn)樗芯幪?hào)不是10n(n≥1)的球在放進(jìn)去罐子里后就不會(huì)再拿出來；而在零點(diǎn)之前這種放球、取球的次數(shù)是無限的。因此，罐子里面的球數(shù)在零點(diǎn)時(shí)將是無數(shù)個(gè)。但是你很確信這個(gè)答案嗎？現(xiàn)在來讓我們改變拿球的方式，將每次拿10、20、30、…號(hào)球分別變?yōu)槟?、2、3、…號(hào)球，即第x次拿球，所拿出來的球的編號(hào)是x。結(jié)果又會(huì)怎樣呢？這個(gè)時(shí)候，神奇的事情發(fā)生了。這個(gè)罐子里面的球數(shù)將為0。我們來看，對(duì)于任意一個(gè)球，設(shè)其編號(hào)為n，則在差(1/2)n?1分鐘到零點(diǎn)時(shí)該球?qū)⒈蝗〕?。也就是說，對(duì)于任意球n，在零點(diǎn)時(shí)它都不在罐子里。因此，零點(diǎn)時(shí)罐子里球的個(gè)數(shù)為0。對(duì)于有些人來說，這個(gè)答案似乎不可接受。但又確實(shí)找不到駁斥的辦法。你能找出來嗎？也許這個(gè)答案是合理的，因?yàn)槟们蝽樞虻淖兓沟盟惴òl(fā)生了變化，即我們實(shí)際上討論的是兩個(gè)算法。可仔細(xì)一想又覺得不對(duì)，因?yàn)閮蓚€(gè)算法都是每次放進(jìn)10個(gè)球，拿出1個(gè)球，即從根本上說，這是兩個(gè)一樣的算法，怎么會(huì)有截然相反的結(jié)果呢(見圖1-2)圖1-2 到底剩多少個(gè)球？不同的拿球順序有不同的結(jié)果，如果我們?cè)俅胃淖冊(cè)囼?yàn)中拿球的方式，將拿某個(gè)特定標(biāo)號(hào)的球改為取出任意標(biāo)號(hào)的球，即：在差1分鐘到零點(diǎn)時(shí)：將標(biāo)號(hào)為1～10的10個(gè)球放進(jìn)罐子，然后從罐子任意拿出一球。在差1/2分鐘到零點(diǎn)時(shí)：將標(biāo)號(hào)為11～20的10個(gè)球放進(jìn)罐子，然后從罐子任意拿出一球。在差1/4分鐘到零點(diǎn)時(shí)：將標(biāo)號(hào)為21～30的10個(gè)球放進(jìn)罐子，然后從罐子任意拿出一球?！@種拿球方式又將產(chǎn)生何種結(jié)果呢？答案仍然是無有，即0(本書將在第1章對(duì)這個(gè)問題進(jìn)行正面解析)。太不可思議了吧！這三個(gè)本質(zhì)相同的算法怎么有如此匪夷所思的結(jié)果呢？如果非要說這三個(gè)算法有什么不同，那就是拿球時(shí)的標(biāo)號(hào)不同。難道是，標(biāo)號(hào)的不同使最后球的數(shù)量發(fā)生了變化?沒錯(cuò)。就是這個(gè)標(biāo)號(hào)對(duì)結(jié)果產(chǎn)生了深遠(yuǎn)影響。從某種意義上說，標(biāo)號(hào)是虛的，它只存在于我們的想象中，但確實(shí)對(duì)現(xiàn)實(shí)結(jié)果產(chǎn)生了影響，即我們的思維使算法發(fā)生了變化?；蛟S從另一個(gè)角度來看，這個(gè)問題就是：無有就是無窮，無窮就是無有。它們之間也許根本沒有什么不同，它們的不同只存在于人們的想象或者意念中。也許這是為什么無窮的符號(hào)(是由兩個(gè)0連接而成的，從左右兩面看都是無有，而從中間看則是無窮，如圖1-3所示。圖1-3 無有和無窮的區(qū)別也許只存在于人類的思維中從這個(gè)意義上說，算法是一種思維方式(algorithmic thinking)，或者說一種哲學(xué)。而本書就是從算法思維的角度出發(fā)，闡述算法的靈魂。1.2 什么是算法究竟什么是算法呢？顧名思義，算法就是計(jì)算的辦法或法則。這里的計(jì)算指的當(dāng)然不只是加、減、乘、除等算術(shù)運(yùn)算，而是廣義的做任何事情的計(jì)算，而辦法和法則意味著使用它就可以解決需要的問題。算法的歷史可以追溯到9世紀(jì)的古波斯。最初它僅表示“阿拉伯?dāng)?shù)字的運(yùn)算法則”。后來，它被賦予更一般的含義，即所謂的一組確定的、有效的、有限的解決問題的步驟。這是算法的最初定義，注意，這個(gè)定義里面沒有包括“正確”。推動(dòng)算法傳播的是生活在美索不達(dá)美亞的Al Khwarizmi于9世紀(jì)一本以阿拉姆語(Aramaic)著述的教科書。該書列舉了加、減、乘、除、求平方根和計(jì)算圓周率數(shù)值的方法。這些步驟的特點(diǎn)是：簡單、沒有歧義、機(jī)械、有效和正確—這就是算法。注意，這個(gè)定義加上了“正確”這個(gè)詞。幾百年后，當(dāng)十進(jìn)制計(jì)數(shù)法在歐洲被廣泛使用時(shí)，“算法”(algorithm)這個(gè)單詞被人們創(chuàng)造出來以紀(jì)念A(yù)l Khwarizmi先生。由上面提到的定義可推知，算法作為解決問題的方法，它必須具備以下特點(diǎn)：?確定性，即無歧義，能讓人照著執(zhí)行。?可行性，算法中的運(yùn)算都是基本的，理論上能夠由人用紙和筆完成。?有限性，在有限輸入下，算法必須能在有限步驟內(nèi)實(shí)現(xiàn)有限輸出。此外，算法必須有輸出、計(jì)算的結(jié)果，通常還有至少一個(gè)輸入量。這是因?yàn)樗惴ㄓ靡越鉀Q的問題的描述均包括輸入和輸出。

編輯推薦

《算法之道(第2版)》既可以作為大學(xué)本科或研究生的算法教材或參考書，也可以作為對(duì)算法有興趣的讀者提升認(rèn)知深度的讀物。

圖書封面

圖書標(biāo)簽Tags

無

評(píng)論、評(píng)分、閱讀與下載

---

    算法之道(第2版) PDF格式下載

---