君，已阅读到文档的结尾了呢~~
扫扫二维码，随身浏览文档
手机或平板扫扫即可继续访问
第七章 算法、复杂性与np-完全性理论
举报该文档为侵权文档。
举报该文档含有违规或不良信息。
反馈该文档无法正常浏览。
举报该文档为重复文档。
推荐理由：
将文档分享至：
分享完整地址
文档地址：
粘贴到BBS或博客
flash地址：
支持嵌入FLASH地址的网站使用
html代码：
&embed src='/DocinViewer--144.swf' width='100%' height='600' type=application/x-shockwave-flash ALLOWFULLSCREEN='true' ALLOWSCRIPTACCESS='always'&&/embed&
450px*300px480px*400px650px*490px
支持嵌入HTML代码的网站使用
您的内容已经提交成功
您所提交的内容需要审核后才能发布，请您等待！
3秒自动关闭窗口您所在位置： &
&nbsp&&nbsp&nbsp&&nbsp
多任务调度问题研究与实现.pdf135页
本文档一共被下载：
次 ,您可免费全文在线阅读后下载本文档
文档加载中...广告还剩秒
需要金币：200 &&
你可能关注的文档：
··········
··········
摘 要 本课题的研究对象是分布式环境下的多任务静态调度问题。研究求解该问题的高
效近似算法具有极高的理论价值和实践价值。这个问题是强 NP 完全的，是最难的组
合优化问题之一。各国学者已对它做了十多年的深入研究，并提出了多种调度模型和
算法。 一般用有向无回路图
Directed Acyclic Graph, DAG 来描述有优先关系的任务集，
目前文献中只给出了有向无回路图的存在性定义。本文提出了有向无回路图的两种构
造性定义，使 DAG 直观化、可操作化。然后将问题的约束归纳为任务约束、链路约
束和资源约束，给出了分布式环境下多任务静态调度问题的统一的、完整的描述和形
式化的定义，证明了这个问题是可计算的但也是强 NP 完全的，不存在任何常数近似
比的多项式时间近似算法。 遵循从简单到复杂、循序渐进的研究方法，深入地研究了同构环境下的多任务静
态调度问题。前人在这个问题的描述上，虽然采用加权的 DAG 描述问题，但没有建
立问题的约束和目标的完整数学模型，尤其是允许任务复制的情况；另外对资源的数
目，或者假设有无穷多，或者作为一个参数传入。本文将约束条件归纳为任务约束、
链路约束和资源约束，并将资源数限定为与任务数一样多，给出了允许任务复制情况
下问题的完整描述和两种数学模型。证明了对 n 个任务的问题，给定 n 个资源足够找
到无穷多资源时的最优解，使对问题的认识更深入，并使问题的描述更趋于实际。采
用三种不同的方法证明了问题具有可计算性，从不同的角度帮助加深对问题的理解，
有利于想出好的策略。 调度方法以优先级列表、任务分簇、任务复制最具代表性，其中基于任务复制的
正在加载中，请稍后...这是一篇旧文，点击以旧主题模式浏览。从无有 到无穷——算法之道(让你学不会算法都难)
算法之道(让你学不会算法都难)作者：邹恒明定价：39.00元出版社：机械工业出版ISBN：978-7-111-29494-8互动网预订地址：http://www./196344豆瓣讨论：/subject/4249686/
本书追求的目标是算法背后的逻辑，是一本启示书，而不是一本包罗万象的算法大全。因此，本书甄选了那些最能够展现算法思想、战略和精华，并能够有效训练算法思维的内容。本书将算法的讨论分为五大部分：算法基础篇、算法设计篇、算法分析篇、经典算法篇、难解与无解篇。每一个部分分别讨论算法的一大方面：基础、设计、分析、经典和难解问题。本书既可以作为大学本科或研究生的算法教材或参考书，也可以作为对算法有兴趣的读者提升认知深度的读物。
起初神创造天地。地是空虚混沌，渊面黑暗；神的灵运行在水面上。神说：&要有光&。就有了光。神看光是好的，就把光与暗分开了。神称光为昼，暗为夜。有晚上，有早晨，这是头一日。
神就照着自己的形象造人，
神说：&看哪！我将遍地上一切结种子的菜蔬，和一切树上所结有核的果子，全赐给你们作食物。至于地上的走兽和空中的飞鸟，以及各样爬在地上有生命的物，我将青草赐给它们作食物&。事就这样成了。
神看着一切所造的都甚好。有晚上，有早晨，是第6日。天地万物都造齐了。
图1& 米开朗基罗创作的西斯廷教堂穹顶画《创世纪》。这幅画里隐含着算法
圣经上写着：神6天创造天地万有，第7日安歇。
对于神创论者来说，这是不可怀疑的事实。但对于进化论者来说，6天创造一切根本就不可能。
作为一本算法书，我们当然不打算加入到神创论者和进化论者的永无休止的争论当中去。我们关心的是这么一个问题：圣经上为什么给出的是6天，而不是其他的时间长度。不管是神创论者还是进化论者，弄清楚6这个数字的来历很可能会对己方的观点有所帮助。在这6天里，神将他的创作方程式重复了6次，每天1次。对于全能的神来说，他完全可以在1天、1秒或者任何他所愿意的时间长度里创造天地万物，但却为什么是不多不少的6天呢？而不管圣经上的 &1天&是多长，这个问题都是值得讨论的。
我们知道，任何一个自然数的约数中都有1和它本身，而所有小于它本身的因数叫做这个自然数的真约数。例如，6的所有真约数是1、2、3；8的真约数是1、2、4。如果一个数的真约数之和等于这个自然数本身，则这个自然数就称为完全数，或者完美数。例如，6 = 1+2+3，因此6是完美数；而8 ( 1+2+4，因此8不是完美数。因此，神6天创造世界，暗示着该创造是完美的！
以完美数来昭示创造的完美，似乎合情合理。但问题是，完美数只有6这一个数吗？如果不是，为什么不使用其他的完美数呢？答案是，完美数虽然不止有6这一个，但确实数量稀少。一直到现在（2009年6月），数学家们探索了2600年，并且现代数学家们还借助了超级计算机，但也仅仅找到了47个完美数。其中第1个完美数是6，接下来的4个完美数分别是： 28、496、 336。而第47个完美数有25 956 377个数位，（注意，是数位，不是数值！）它的数值为：243 112 608 & (243 112 609 ? 1)。
完美数的稀少昭示着达到完美的难度，而神选择6天来创造天地万有也许是因为6是最小的完美数，即创造天地万有对于神来说是轻而易举的一件事情&
完美与算法
完美数由于其各种神秘属性（真约数之和等于自身只是其中的一个性质）而受到了特殊的关注。但到底哪些数是完美数则不是一件容易判断的事情。显然，按照完美数的定义，判断一个数是否是完美数的不二法则是找出它的所有真约数，然后求和看看其是否等于自身。然而这种方法效率太过低下，因为这意味着因式分解，而这是十分困难的（本书后面将会讨论到这个问题）。
如果判断一个数是否是完美数就已经非常困难，那么要找出所有的完美数则更是一个难上加难的任务。因为这就意味着将所有的数进行上面描述的判断验证：因式分解。这似乎是人类不可能完成的任务。即使用世界上超大的计算机来进行计算，情况也不会有任何数量级的改善。
显然，我们需要新的解决方案，而不是发明或使用新的计算工具！研究这样的问题就可以归结到算法的范畴里，因为如何高效地解决问题正是算法要研究的核心课题。
有意思的是，判断和搜索完美数是算法的研究范畴，而算法本身的追求却也是&完美&（见图2）。
图2& 算法所追求的理想就是完美
算法无处不在
如果你觉得算法只是用来研究解决找出完美数之类的&漫无边际的问题&，那就大错特错了。
也许算法这个名词听上去很抽象，让人联想不到任何具体的物体。也许你会觉得算法与自己的生活并无太多关系，它只不过存在于那些闲得无聊的数学家或计算机专业人士的脑海中。
但事实真是这样吗？当然不是。如果我们告诉你算法就是解决各种问题的方法，你就不会觉得它太抽象，与生活无关了吧。事实是，算法无处不在。每个人每天都在使用不同的算法来活出自己的人生，比如你去食堂买饭会选择一个较短的队列，而有人则可能选择一个推进速度更快的队列。每天起床后，你可能先读一会儿书，再去吃早饭；另外一个人则可能先去吃早饭，然后读书。所有这些行为都是算法或算法一部分的体现。也许运行这些算法并不在你的思想意识里，也许你并不知道算法在帮助着自己的生活，但它确实是存在的。这些算法也许没有经过精心设计，没有经过仔细分析，但它还是算法！
日下午，我在游览云南省大理市的蝴蝶泉时由于泉水边的石头很滑，在用泉水洗手时（导游金花说用该泉水洗手会带来好运）不慎滑落到蝴蝶泉水（见图3）里面，全身湿透。（据说一天至多只会有一个人滑落到泉里，可见本人运气不错！看来&蝴蝶泉边好梳妆&的歌词也许应该改为&蝴蝶泉里好冲凉&。）泉水冰冷透凉，而大理的气温又低。这样，我就面临一个是否更换全身衣服的决定。问题是，旅游团需要马上赶去登游船游览洱海风光，而若找地方或者回旅店换衣服就将赶不上游船。
如何处理这件事情就是一个算法问题：是先上游船再在船上找地方换衣服，还是找个地方换衣服而放弃游览苍山洱海。显然不同的算法有着不同的收益和代价。如果能够在游船上找到合适的地方更换衣服，则采用先上游船再换衣服的算法为佳；否则就是放弃游览的算法更好，因为如果冻病了显然就不划算了。最后，我选择了在游船上更换衣服的算法：在游船上找到了一个贵宾室更衣。
图3& 在蝴蝶泉水下洗个手也会涉及算法
算法由问题驱动
算法的发现总是由相关的问题驱动的。拿排序来说，因为生活中到处都充满次序，每个人都要接受自己在某个次序里的位置。比如，各种排名、评优、民意调查等，最后的结果都体现为一个次序！看来，&没有次序无以成方圆&并不是空穴来风！而谈到排序用的方法，人们很自然地想到插入法，因为这种朴素的算法和人的思维方式非常类似：它就是人们打牌时整理手中扑克牌的算法。
但是随着数据量的增大，插入排序的效率缺陷迅速变为人们无法容忍的缺点。于是人们发明了归并排序、堆排序、快速排序等，这些排序的方法大大改善了速度，但是人们却并不满足于此。因此又发明了效率更高的线性排序。表1给出的是各种排序算法平均情况下的效率比较：最上面一行的数字代表输入的规模，如10表示一共有10个数据项，1M表示一共有100万个数据项。其他格子里面的数据为相应算法在相应输入规模下完成排序所需要的时间，单位为毫秒。所有输入数据为随机产生。表1& 部分排序算法的时间效率比较&&&&&&&&&&&&& （单位：毫秒）排序算法&10&100&1K&10K&100K&1M冒泡排序&0...545&61&选择排序&0...488&47&插入排序&0...764&56&哈希排序/增量3&0...036&0.518&4.152&61堆排序&0.991&0.041&0.531&6.506&79归并排序&0...066&0.561&& 5.48&70快速排序&0...030&0.311&3.634&39基数排序/进制100&0..021&0.165&1.65&11.428&117基数排序/进制134&0.026&0.139&1.264&8.394&89
算法运行环境为Intel 酷睿2双核EGHz，Windows 7*64。
本表数据由作者所授&数据结构&课的胡嘉斌同学测试所得。
一个个新的算法都是为了解决前面算法遗留的问题而产生的。从表1里的数字可以看出，一般来说，随着新的算法的出现，排序效率在不断提高。不过，虽然每个算法似乎解决了前面算法的遗留问题，但新的问题也会被有意或无意地引入。例如，线性排序虽然将排序的时间复杂性降低到线性级，但各种前提条件极大地限制了其应用范围。也许这就是算法永远也不能或不会停止发展的一个原因吧。
算法是计算机的灵魂
因为人不是全能的，一个时刻只能做一件事情，因此做事情就要有一个步骤。由于算法要满足人的这种特性，它通常被表示为一个做事情的行为序列。因此，从一般意义上说，算法就是求解问题的步骤。由于计算机的计算操作完全是一步一步地进行，因此算法的上述性质用于计算机是再合适不过了，可以说算法弥漫在计算机的一切行为上。如果说操作系统是计算机的心智，那么算法就是计算机的灵魂。
理解灵魂当然不是件容易的事情，由于它高度抽象与简洁，许多学生都望而却步。我们先看一个纸牌魔术（见图4）：
任选一位观众将一副扑克牌充分洗好。
背对观众，请观众随机抽出一张牌，记住牌面，然后将这张牌放回整副牌的最上面。
接过牌后，洗牌几次。洗的时候保持最上面一张牌不动。
对观众说：&我来教你魔法，只要吹一口气，就能把刚才你抽的牌吹到任意位置上&。
请观众说出一个数字，比如说10，然后一边吹气，一边想着刚才说的数字10。
在吹完气后，请观众一张一张地将上面的牌取出放在桌上。
到第10张时，将牌翻开，发现并不是其原来抽的牌。
接回整副牌，并把上一个步骤里取出堆放在桌上的牌收起，仍放在整副牌的最上面。
然后洗牌几次，洗的时候保持上面放回来的那堆牌不动。
从观众手上拿回刚才翻开的那张牌，插入到最上面9个位置中的任意一个。
对观众说：&你刚才不是在想着那个数字的时候吹的气，而是在吹气的时候想着那个数字，而这是完全不同的两回事。我现在演示一下如何吹气&。对着牌吹一口气。
请观众从上到下数牌，到第10张时翻开。
这张翻开的牌就是观众一开始抽的那张牌。
图4& 算法无处不在，就连纸牌魔术都有其背后支持的算法
读者看明白了上面的这个魔术了吗？这里面隐藏着一个算法。如果看懂了就可以在朋友面前一显身手了。当然，如果没有看懂也没有什么关系。算法本来就不是轻易让人看懂的嘛。
对于一些吹毛求疵的人来说，也许会说这个纸牌魔术不是算法。至少这跟我们研究算法的人所打交道的常见算法不太一样。这没有什么关系，来看下面的一段伪代码：PARTITION(A,p,q)&&&// A是一个实数数组, p, q是该数组的上下限 x&A[p]&&&&&&// A[p]被选中i&p for j&p+1 to q do&& If A[j]& x then&&i&i+1&&A[i]?A[j]&&&// 交换A[i]和A[j]的内容A[p]?A[i]return i
读者能看出来这个伪代码程序片段完成的是什么功能吗？
要分析一个算法，似乎就更难了。读者能看出下面的C程序片段里面&laugh++&语句执行多少次吗？for (i=1; i&=n; i*=2)&&&&&& for (j=1; j&=i; j++) &&&&&&&&&&& laugh++;
如果这些问题读者都能回答，那恭喜你。看来算法分析对于你来说将是很容易的事情，不过可能也不一定。如果你回答不出这些问题，不用担心，因为回答诸如此类的问题就是本书的目的。当然了，本书回答的远不止这么几个简单问题，而是会阐述更重要的算法精髓：算法思想、战略和分析！
本书内容安排
本书追求的目标是算法背后的逻辑。所以，它不可能是一本包罗万象的算法大全，而是一本启示书。因此，本书甄选了那些最能够展现算法思想、战略和精华，并能够有效训练算法思维的内容。本书的选材遵循的规则是：书中选取的每个算法都在某个方面具有独特性，能够彰显算法的精髓。
本书将算法的讨论分为五大部分：算法基础篇、算法设计篇、算法分析篇、经典算法篇、难解与无解篇。每一个部分分别讨论算法的一大方面：基础、设计、分析、经典和难解问题。如图5所示。
图5& 本书内容框架
本书第一部分是算法基础篇，讨论基本的算法设计思想与算法分析方法和手段。内容包括从无有到无穷、计数与渐近、分治与递归三章。第1章讨论意念与现实、什么是算法、算法的表示、算法之魂、算法与计算机的关系、算法的范畴和为什么学习算法。第2章讨论算法的正确性、时空效率和时空特性分析、计数分析方法、算法设计、渐近表示与分析。第3章阐述算法设计的最基本战略：分治与递归。具体内容包括分而治之为上策、分治策略中的递归、求解递归表达式、乘法及乘方运算、矩阵乘法、斐波那契数的计算、VLSI 布线和多项式乘法。
第二部分为算法设计篇，讨论算法中常见且重要的战略或思想，内容包括动态规划思想、贪婪选择思想和随机化思想三章。第4章讨论什么是动态规划、流水装配线问题、最长共用之序列问题、最优二叉搜索树问题、记忆递归法、最优子结构、重叠子问题、动态规划与静态规划之间的关系。第5章介绍人在生活中潜意识地遵守的一种行为：贪婪。具体内容包括什么是贪婪、贪婪选择属性、背包问题、教室规划（排课）问题、最小生成树问题、霍夫曼编码问题、标准分治、动态规划和贪婪策略的比较。第6章讨论人生及算法中无处不在的随机，内容包括为什么要随机化、随机的平方，拉斯维加斯算法、蒙特卡罗算法、素性测试、矩阵乘积验证器、随机化最小生成树算法等。
第三部分为算法分析篇，主要介绍计数（渐近）分析之上的算法分析的另外三种重要手段：概率分析、摊销分析和竞争分析。第7章包括一切都在概率中、什么是概率分析、梦幻情人的代价、概率分析结果的有效性、正确概率分析的保障、梦幻情人的概率、随机排列问题和从无穷到无有。第8章讨论什么是摊销分析、摊销分析与数据结构、摊销分析的方法、聚类分析、会计分析、势能分析、动态表扩张及其摊销。第9章讨论竞争无处不在、在线算法和离线算法、竞争力、健忘对手和优良对手、线性表更新问题、前置移动算法及其竞争分析、聚类问题及其竞争分析、竞争分析与普通算法分析的比较。
第四部分是经典算法篇，内容包括排序与次序、搜索与哈希、最短路径问题三章。第10章内容包括插入排序、折半插入排序、归并排序、快速排序、随机化快速排序、排序下限、线性排序、求最大值、求最小值、求中值及任意次序选择。第11章内容包括搜索问题定义、顺序搜素、折半搜索、常数搜索、哈希搜索、哈希函数选择、哈希冲突的解决、随机化哈希、全域哈希和完美哈希。第12章内容包括单源单点最短路径、单源多点最短路径、多源多点最短路径。具体算法则包括穷举搜索算法、Dijkstra算法、Bellman-Ford算法、Floyd-Warshall算法和Johnson算法。
最后一部分是难解与无解篇，内容包括可解与不可解、NP完全问题和无解与近似三章。第13章讨论易解与难解、决策问题和优化问题、P和NP、确定性与非确定性。第14章讨论NP完全问题、多项式时间规约、如何证明一个问题是NP完全、库克定理、3-SAT问题、整数规划问题、独立集问题、汉密尔顿回路问题、弱NP完全、强NP完全和中NP完全。第15章内容包括难解问题、不可决定问题、程序终结的判断、难解之题的求解、智能穷举、近似算法、本地搜索、回溯策略、分支限界、贪婪近似策略、启发式搜索和模拟淬火算法。
本书以创世纪的6天为起点，寓意算法也有创始的一刻，将人类算法体系中优美而有代表性的内容囊括书中，最后以算法之道的随想作为结尾，构成了逻辑上一气呵成，思想上韵味深长的算法知识体系。
本书的特点
我相信，写书的目的是对读者有所启示，而不是用一大堆的公式或繁琐的推导来烦死或吓倒读者。虽然在一定的时候我们也会迫不得已地使用复杂的公式，但不必到处都引用复杂繁琐的表述，甚至将简单的东西也以繁琐的式子来表达。复杂的式子或许能给部分人带来一丝莫名其妙的快感，但对于大多数读者来说，也许就是&装腔作势罢了，真可憎恶&。基于此种认识，本书将以简洁的方式来表示复杂的概念。
在我读小学的时候，有一天在街上听到一个人吆喝&快来看，快来看开膛破肚表演！&有人问：&怎么开膛破肚？&卖艺的人说：&用刀将活人的胸膛破开，将里面的内脏拿出来给大家看，然后再缝上。&开膛破肚？这可是难得一见的事情。于是我按照艺人的指引进入一个很小的黑屋里。里面已经挤进了一些人，站在屋子四周。屋中间的床架上躺着一个上身赤裸的年轻人，旁边则站着一个手拿尖刀的&屠夫&。&屠夫&先叫每个观众交了一笔钱，然后开始了他的开膛破肚表演。
只见&屠夫&将尖刀举起，对着躺在床架上的年轻人喊道：&你要钱还是要命？& 年轻人很坚定地回答：&要钱！&&屠夫&连喊了三遍，得到的回答都是&要钱&。于是&屠夫&将尖刀快速砍下，刺进了年轻人的肚脐，血从尖刀的四周往外渗出。然后&屠夫&对着四周的观众喊道：&你们看这个人要钱不要命，你们给他一些钱吧。&很多人看到这个流血的场面，出于同情或害怕又向外掏钱。
令人遗憾的是，&屠夫&并没有遵守许诺将年轻人的腹部或者胸膛划开，也没有将脏器拿出来给大家看&&
这是江湖杂耍的一些小伎俩，但本书对算法进行的&开膛破肚&的分析却是实打实的！这也是本书最显著的特点：对算法的分析深入到以往没有深入的境界。本书更关注的是算法后面的逻辑脉络，强调一个算法为什么会出现，又为什么会是现在呈现的样子。通过挖掘算法背后的思维过程，本书淋漓尽致地展现了算法的精妙绝伦。
本书的第二个特点是结构紧凑：摒弃臃肿繁琐的内容堆砌，通过逻辑关系将算法各部分内容进行递进演绎，形成一个层次感强、由表入里的有机体。
本书的第三个特点是全新的角度：也许讲的是同样的算法、相似的问题，但是本书采纳的是完全不同的角度，这种独特的视角能把我们对算法的理解带到新的高度。
本书的第四个特点是新颖的结构：不同一般的章节组织，使条理更为清晰，内容上也包含了不少新的概念和理念。
本书的最后一个特点是写作风格轻松活泼：以讲故事的形式将概念和算法的精华娓娓道来，由浅入深，非常易于理解和消化。
上述这些特点赋予了本书与一般算法书或其他科技书籍的巨大不同（见图6）。
当然，本书也没有走另一个极端：过分强调语言的生动而忽视了严谨性。恰恰相反，本书力求兼顾这两个看似矛盾的方面。在书中我们看不到繁多的数学公式，取而代之的是精确的文字叙述。我认为，这种用严谨的语言代替数学形式化的方法更容易被读者接受。因为读者需要知道的，通常是蕴涵在各种公式或算法伪代码（或程序代码）背后的思想，而正是这些思想促成了所有精巧的算法。本书几乎没有讲述数据结构的内容，也不会讨论算法的程序设计实现，而是集中精力论述算法本身的特点。虽然有的人认为算法与数据结构和程序设计关系密切，但毕竟算法可以独立于它们而单独存在。事实上，早在计算机出现之前，算法就已经存在了。从相对的角度来看，算法是抽象的，数据结构与程序设计是具体的（当然从绝对意义上看，数据结构与程序设计也是很抽象的）。而越抽象就越具有普遍意义，也只有在比较抽象的层面上学习算法，才能看穿算法的精妙。
图6& 本书的特点
当然，本书的讨论也不可能完全脱离数据结构或程序，有时候也会提到它们，有时候甚至直接给出某个算法的具体程序实现片段，但所有对数据结构和程序的论及皆点到为止，以有利于对算法的掌握和体现算法实现为目的。而数据结构和程序设计的精妙讲解就留给数据结构和程序设计的课程来完成吧。
本书的使用方法
本书既可以作为大学本科或研究生的算法教材或参考书，也可以作为对算法有兴趣的读者提升认知深度的读物。如果作为教材使用，建议课程为4个学分，如果学时限制只有3个学分，建议将摊销分析、竞争分析和无解与近似这三章内容跳过。建议课堂讲解顺序按书中安排进行，因为本书内容是按照逻辑演绎顺序环环相扣的。按这种顺序讲解条理清晰、逻辑明朗、前后连贯，学生比较容易接受。
对于一般读者，本书可以作为一种算法思维的修养书来看，读者应当可以按照自己的时间和计划自行安排。或者休闲时翻看此书，斟酌算法，品味精妙，这不也是一件美事吗？
本书隐含7个悖论。如果读者能够发现这些悖论并找出答案，那恭喜你！因为你有一双发现真理的眼睛。不，应该说，你有一颗发现真理的心！如果读者没有发现这些悖论，也没关系，因为能够发现这些悖论的人毕竟不多，更不用说寻找到答案。而不管发现与否，这些悖论都不会妨碍读者对本书内容的理解。因为如果你发现了这些悖论，它们施加的是正面影响：读者对算法的理解深度会大大增加！而如果没有发现这些悖论，则对读者来说，这些悖论相当于不存在，自然也就无法对读者施加任何正面或负面的影响了。
另外，本书章节之间以隐示的方式留下了7个重要的算法奥秘，但能否察觉就看个人的理解了（见图7）。
图7& 本书隐含着7个悖论和7个奥秘
逻辑演绎、生活归纳、趣味交织，入木三分地揭示算法的奥妙；新的角度、新的分析、新的境界，耳目一新地阐述算法的精华。就让我们即刻开始精彩纷呈的算法之旅，Let the Fun Begin!
2009年9月于上海莘庄
第一篇& 算法基础篇第1章& 从无有到无穷&21.1& 意念与现实&31.2& 什么是算法&41.3& 算法的表示&61.4& 算法之魂&71.5& 如何比较速度&81.6& 算法与计算机的关系&91.7& 算法的范畴&101.8& 为什么学习算法&10思考题&11第2章& 计数与渐近&122.1& 算法的分析&122.2& 计数：算法分析的核心&142.3& 算法设计&152.4& 算法效率表示&162.5& 渐近分析&172.6& O、(、(表示&182.7& 最好、最坏、平均&192.8& O、(、(的另一类定义&212.9& O、(、(的性质&222.10& 要更快的计算机还是要更快的算法&22思考题&23第3章& 分治与递归&253.1& 分而治之为上策&263.2& 分治策略&283.3& 递归表达式求解&293.4& 分治策略举例1：乘方运算&353.5& 生命不能承受之重：矩阵乘法&363.6& 魔鬼序列：斐波那契序列&383.7& VLSI 布线&413.8& 多项式乘法&433.9& 分治就在潜意识深处&43思考题&43
第二篇& 算法设计篇第4章& 动态规划思想&464.1& 什么是动态规划&474.2& 流水装配线问题&484.3& 最长公共子序列&524.4& 最长公共子序列变种&554.5& 记忆递归法&554.6& 空间效率改善&564.7& 最优二叉搜索树&564.8& 最优子结构与重叠子问题&624.9& 动态规划与静态规划的关系&634.10& 动态规划与静态规划的相互转换&64思考题&65第5章& 贪婪选择思想&675.1& 仅有动态规划是不够的&675.2& 什么是贪婪&685.3& 背包问题&685.4& 贪婪选择属性&715.5& 教室规划问题&725.6& 最小生成树&765.7& Prim算法&805.8& 霍夫曼树和霍夫曼编码&835.9& 贪婪选择属性&885.10& 标准分治、动态规划和贪婪选择的比较&89思考题&90第6章& 随机化思想&926.1& 为什么要随机化&936.2& 随机的平方&946.3& 什么是随机化算法&956.4& 拉斯维加斯算法&966.5& 蒙特卡罗算法&976.6& 素性测试&976.7& 矩阵乘积验证器&1006.8& 随机化最小生成树算法&1026.9& 随机数的生成&1056.10& 随机化算法的应用&105思考题&106
第三篇& 算法分析篇第7章& 概率分析&1087.1& 一切都在概率中&1097.2& 什么是概率分析&1097.3& 梦幻情人的代价&1107.4& 概率分析结果的有效性&1147.5& 正确概率分析的保障&1157.6& 梦幻情人的概率&1157.7& 随机排列问题&1177.8& 南柯一梦：从无穷到无有&1197.9& 概率分析的其他应用&120思考题&121第8章& 摊销分析&1228.1& 什么是摊销分析&1238.2& 摊销分析与数据结构&1248.3& 摊销分析的几种方法&1248.4& 聚类分析&1258.5& 会计分析&1288.6& 势能分析&1308.7& 摊销分析应用：表格扩展的代价&1318.8& 运气不好就摊销&137思考题&138第9章& 竞争分析&1399.1& 什么是竞争分析&1399.2& 在线算法和离线算法&1419.3& 竞争力&1429.4& 健忘对手和优良对手&1429.5& 线性表更新问题&1439.6& 前置移动算法的竞争分析&1459.7& 聚类问题&1479.8& 竞争分析与普通算法分析&149思考题&149第四篇& 经典算法篇第10章& 排序和次序&15210.1& 排序无处不在&15210.2& 插入排序&15310.3& 归并排序&15610.4& 快速排序&15810.5& 随机化快速排序&16210.6& 排序的下限&16410.7& 线性排序&16510.8& 计数排序&16610.9& 基数排序&16810.10& 桶排序&17110.11& 次序选择&17510.12& 快速次序选择算法&17610.13& 随机快速次序选择算法&17810.14& 最坏情况下的线性选择算法&179思考题&181第11章& 搜索与哈希&18311.1& 搜索问题&18411.2& 顺序搜索&18411.3& 折半搜索&18511.4& 常数搜索&18611.5& 哈希搜索&18711.6& 哈希函数选择&18911.7& 哈希算法的碰撞问题&19311.8& 哈希表元素删除&20111.9& 随机化哈希&20211.10& 全域哈希&20311.11& 全域哈希构造&20411.12& 完美哈希&206思考题&208第12章& 最短路径&21112.1& 剑指罗马&21112.2& 最短路径问题&21312.3& 单源单点最短路径问题&21512.4& 单源多点最短路径问题&21812.4.1& 最短路径的性质&21912.5& Bellman-Ford算法&22612.6& 多源多点最短路径问题&23212.7& 天意难违&240思考题&240
第五篇& 难解与无解篇第13章& 可解与不可解&24413.1& 我们战无不胜吗&24513.2& 易解与难解&24513.3& 决策问题和优化问题&24613.4& 决策问题&24713.5& P类问题&24713.6& NP类问题&24813.7 （确定性）图灵机&24913.8& 非确定性图灵机&24913.9& 非确定性算法&25013.10& 回到NP类问题&25113.11& P和NP&25213.12& 搜索问题、决策问题和优化问题&25313.13& 有没有解和是否可决定&253思考题&254第14章& NP完全问题&25614.1& 玉龙雪山下的审判&25614.2& NP完全问题的定义&25714.3& NP完全的重要性&25814.4& 多项式时间规约&25914.5& 如何证明一个问题S是NP完全&25914.6& 第1个NP完全问题的证明&26014.7& 库克定理&26014.8& 3-SAT问题&26314.9& 证明NP难的技巧&26414.10& 整数规划&26514.11& 独立集问题&26614.12& 汉密尔顿回路问题&26814.13& 讨论：弱NP完全、强NP完全和中NP完全&271思考题&272第15章& 无解与近似&27315.1& 难解问题&27415.2& 不可决定问题&27415.3& 程序终结的判断&27515.4& 难解之题的求解&27615.5& 智能穷举、近似算法和本地搜索&27715.6& 智能穷举之回溯策略&27915.7& 智能穷举之分支限界&28015.8& 贪婪近似策略&28015.9& 启发式搜索策略&28115.10& 模拟淬火算法&282思考题&286结语& 算法之道&288附录& 算法随想&290参考文献&293
> 本站内容系网友提交或本网编辑转载，其目的在于传递更多信息，并不代表本网赞同其观点和对其真实性负责。如涉及作品内容、版权和其它问题，请及时与本网联系，我们将在第一时间删除内容！
文 / 邹恒明 1966年3月的一天,美国加州大学洛杉矶分校的Andrew J. Viterbi教授在给研究生讲解缠绕编码的时序译码算法SDCD.但不管他如何讲解,学生就是听不明白.思来想去,Viterbi觉得学生不能理解的原因是该算法的证明过于复杂.于是他开始考虑如何简化这个证明.在经历了持久的烦躁和困惑后,他灵感顿现:需要简化的不是算法的证明,而是算法本 ...
算法--两道百度笔试题 今天看到一位园友写了一篇关于百度的面试题的博客,成了评论头条,再下看了一下,非常感兴趣,那位博主的算法能力跟我一样需要提高,估计他的功力还在我之下,所以再下不才,在这里把自己的源码贴出来.
百度面试题(一):假设一整型数组存在若干正数和负数,现在通过某种算法使得该数组的所有负数在正数的左边,且保证负数和正数间元素 ...
&算法之道&读后
用了差不多2周时间看完了本书,看得还算细致,只是对很多数学证明没有深入研究.总体来讲,本书条理非常清晰,前后连贯,章节编排上符合正常逻辑思维.首先,作者介绍了算法的基础知识:什么是算法,如何学习算法.紧接着就介绍了算法的基本分析原则(渐近表示),在基础篇的最后讲解了分治与递归这个算法中的灵魂.算法的设计篇,作者着重 ...
http://blog.csdn.net/v_july_v/article/details/6305212
结构之法 算法之道 博客 十三个经典算法研究与总结.目录+索引 分类: 03.Algorithms(实现) 01.Algorithms(研究)
17:31 48576人阅读 评论(193) 收藏
KMP算法之道 修订于,心急的读者可以着重看&有趣的字符串匹配提示&,这个例子看懂了,KMP也就差不多了. 都是字符串匹配 最为朴素的匹配和Rabin-Karp算法 有限自动机进行字符串匹配 KMP算法之道(即本篇) &导论&是本好书啊,算法描述思路很清晰,力荐! 闲话 上午算法考试的时候,感觉OK,前一两 ...
15道常见的基础算法题: 1.合并排序,将两个已经排序的数组合并成一个数组,其中一个数组能容下两个数组的所有元素; 2.合并两个已经排序的单链表; 3.倒序打印一个单链表; 4.给定一个单链表的头指针和一个指定节点的指针,在O(1)时间删除该节点; 5.找到链表倒数第K个节点; 6.反转单链表; 7.通过两个栈实现一个队列;(没有贴出来) 8.二分查找; 9 ...
轻松学算法7:Dijkstra最短路算法 上一篇我们介绍了神奇的只有五行的Floyd最短路算法,它可以方便的求得任意两点的最短路径,这称为&多源最短路&.本周来来介绍指定一个点(源点)到其余各个顶点的最短路径,也叫做&单源最短路径&.例如求下图中的1号顶点到2.3.4.5.6号顶点的最短路径.
参考资料:http://blog.csdn.net/hguisu/article/details/7996185 更多数据挖掘算法:/linyiqun/DataMiningAlgorithm 链接分析 在链接分析中有2个经典的算法,1个是PageRank算法,还有1个是HITS算法,说白了,都是做链接分析的.具体是怎么做呢 ...