网站设计找谁做,微信公众号平台登陆,哪方面的网站,哈尔滨关键词搜索排名查了一下#xff0c;上篇知其所以然#xff08;以学习算法为例#xff09; 是08年7月写的#xff0c;现在已经是10年11月#xff0c;过去了两年零4个月#xff0c;这说明了三件事情#xff1a;1#xff0c;一个问题其实你可以一直放在脑子里面#xff0c;利用暗时间 对…查了一下上篇知其所以然以学习算法为例 是08年7月写的现在已经是10年11月过去了两年零4个月这说明了三件事情1一个问题其实你可以一直放在脑子里面利用暗时间 对其软泡硬磨时间足够久你总会有一点新的感悟问题其实就像那句老话说的那样不怕贼偷就怕贼惦记聚精会神的思考一天也许比不上惦记一个星期据说数学家庞加莱就特别会惦记问题 。 2事实上当你感觉懂了的时候你至少得反问自己一句真的懂了吗当你确信自己真的懂了的时候你至少得讲给别人听别人听懂了吗考察你自己是否真 懂了的一个很好的依据是你是否有一种“哦原来是这样啊这下再也不可能忘记了”的感觉。3我其实没有忘记这个博客。如我之前说的记录只是学习和思考的副作用 只要还在学习和思考就必然会有新的记录。 我有一个习惯看定理必看证明。一个你不明白其证明的定理在我看来比不知道这个定理还要糟糕因它给你造成一种懂了的错觉。在没有明白背后的证明之前任何一个定理对你来说都是等价的——等价于背乘法口诀 只不过有的长一点有的短一点。一个原本美妙的定理把其证明扔掉就是真正的买椟还珠暴殄天物。 从现实意义来说去理解一个定理的证明会带来巨大的好处首当其冲的好处就是你很难再忘掉它 。这一点其实很容易解释——在理解一个定理的证明之前定理对你而言是一堆没有内在联系的词句而在理解了证明之后定理就归约为 证 明它所需的条件加上逻辑“逻辑”本来就存在于你的大脑里面而证明的过程中除了公理和用到的常见定理往往没几条之外宽泛地说需要你去记的一般 来说也只有一个或两个关键的insights也就是我们常说的证明中的神来之笔比如几何证明里面的某条看上去莫名其妙的辅助线一旦你知道了这条辅助 线那么整个证明就毫无难处那么该定理的信息量便直接缩减为一条辅助线的信息量虽然看上去这一步信息并没有缩减多少但是如果你考虑到类似的辅助线不 仅会用在这个特定的定理上往往会在很多地方用到。很多关键的证明手法是通用的。那么其实你就是把所有以这个辅助线为关键证明手法的定理的集合的信息量归 约为了这条辅助线。如果你进而甚至能够理解了作这条辅助线的思想精髓那就更牛逼了因为解决问题的思路更具有一般性理解了寻找正确的辅助线的思路你 就根本不需要去记得某条特定辅助线的作法你就把所有以作一条或几条辅助线为证明核心的定理的集合的信息量归约为了这个“寻找辅助线的思路”。 这是一个树状的知识结构越往上层走需要记忆的节点就越少 。所谓触类旁通者其实便是因为他擅长去理解解法背 后的更具一般性的东西。所以我还有一个习惯就是看到美妙的证明和解法总是会去一遍又一遍的去反复揣摩试图理解想出这个证明的人到底是怎么想出来的有 没有什么一般性的方法可循很多时候在这样揣摩的过程中你会理解到更深刻的东西对问题性质更深刻的认识对解决问题的思路更深刻的认识这些认识不 仅对于你理解当前这个定理或问题有极大的帮助同时也有助于你解决以后会遇到的表面不同但本质一样的问题。 与看定理必看证明类似看一个问题的解法必然要看解法所诞生的过程背后是否隐藏着更具一般性的解决问题的思路和原则。否则一个解法就只是一个问题的解法跟背口诀一样。即便记住了也无法推广即便当时记住了也容易遗忘。 举个经典的例子每本算法书都会讲动态规划每本讲动态规划的书都会讲背包问题每次讲背包问题都会讲可重复背包和01背包我们就拿《Algorithms》这本还算不错 的算法书对背包问题的讲解来说吧重复背包问题的递归公式是这样的 K(W) max { K(W-Wi) Vi : Wi W } 这个公式的理解倒是很简单为了把问题降阶我们在最终的最优解里面去掉一个元素对这个元素的可能性进行讨论它必然是任何Vi之一前提是Wi W否则就装不下而在去掉这个元素之后剩下的元素肯定构成问题 K(W-Wi) 的最优解于是递归关系出现了。 此外也可以这样来理解要拿一组最优元素那么总得开始一个个拿吧对第一个拿的元素进行讨论而问题的最优解等于讨论的各个分支的最优解中的最优者如果拿掉Vi之后剩下来要怎么拿才能最优呢这就是一个 K(W-Wi) 的问题了。 01背包问题就大不一样了——每个物品都只有一件拿掉之后就不能再拿了。我们不妨看看重复背包问题的解法是不是能用到01背包上呢还是讨论第一 个拿的元素设被拿掉的是第i个元素问题就归结为把剩下的物品注意可拿的物品少了一件最优地装入容量为 W-Wi 的包里所以问题的参数便变成了两个一个是背包剩余容量 W-Wi另一个是剩余可拿的物品集合 S\{i} 表示去掉i之后的子集显而易见第二个参数是物品集合的各种可能的子集那么其可能性个数就是 2^n 这就导致子问题的个数是 2^n 由于要依次计算每个子问题那么算法复杂度显然也是 2^n 是不可接受的。 那么《Algorithms》上又是怎么来讲解01背包问题的解法的呢以下是原文 Our earlier subproblems now become completely useless. We must therefore refine our concept of a subproblem to carry additional information about the items being used. We add a second parameter, 0 j n: K(W, j) maximum value achievable using a knapsack of capacity w and items 1..j: The answer we seek is K(W, n). 首先作者说了之前重复背包问题的解法在这里完全废掉了所以我们必须重新定义子问题并且子问题的条件必须要包含目前拿剩下的物品。以上这些都还不错关键是接下来就让人吐血了。作者接着说道我们 给子问题加上一个新的参数j… 凭什么啊 还是让我们回顾一下这样一幅经典的漫画 吧 “我们给子问题加上一个参数j”这就像你在看数学证明时看到无比邪恶的“我们考虑 …“一样一看到这样的句 子你就知道这个问题的证明远远不像看上去那么简单之所以你一路看下去理解上全无困难那完全是因为作者直接把最重要的一个insight告诉你了 举个很简单的例子证明素数无最大谁都会第一时间想到去反证假设存在一个最大的素数P那么找到比P大的素数就是证明中最关键的一步怎么找的一般 书上是不会说的你会看到书上这样说假设P是最大的素数那么我们考虑P’ 小于等于P的所有素数的乘积1。那么P’一来显然大于P二来不能被小于它的所有素数整除那么P’就成了大于P的素数。 如果你经常注意反证法你会发现一个有趣的现象反证法里面经常会有这样一句“我们考虑”而“我们考虑”后面几乎肯定接着一个天外飞仙一般的 insight。素数无最大这个古老的证明里面的“我们考虑”尚算是比较有迹可循的我们想要构造一个更大的素数而素数的等价定义就是“不能被小于它的 所有素数整除为了达到这个目的构造的方法就较明显了。但是有非常非常多的证明其中关键的一步就跟嗑药磕出来做梦做出来走路跌跟头跌出来的一样不 信去翻一翻《Proofs from THE Book 》让你完全不知道他怎么想到的。 话说回来虽然有很多数学证明的关键步骤是很难逆向工程的因为很多时候想出那个关键步骤的本人其实也是尝试了各种方法撞了无数堵墙在寻求证法 的尝试空间中作了N次回溯才“妙手偶得”与其说是妙手偶得不如说是绞尽脑汁但并非全无章法可循否则陶哲轩也不会写出《Solving Mathematical Problems 》这样的著作来而求解问题也就成了真正的Black Art了。 算法的解法则比精妙的数学证明稍加更容易逆向工程一点。只要你有耐心仔细地去琢磨算法的关键步骤和本质总能从中窥探到一些更general的思想和思路来。 此外很多经典问题算法书上的讲法虽然时时令我们失望但如果去网上一搜则通常会发现更优秀的解释来。比如背包问题就是如此 。 简单地说如果你对于每个问题都能真正弄清以下这几个问题的答案那么可以肯定的是你的理解记忆以及学习的效率都会得到质的提高 为什么这种解法是对的 为什么那种解法是错的 为什么这种解法不是最优的 证明为什么没有更优的解法。 回到人民群众喜闻乐见的经典例子背包问题。为什么01背包问题的正确高效算法是正确高效的。表面的解释是因为01背包问题的子问题定义 是 K(W, j)其两个维度相乘的可能性一共有nW种也就是说一共要计算nW个子问题而计算每个子问题的复杂度是O(1)的。 但是如果仅仅满足于这样的解释可以说是隔靴搔痒并没有触及到本质。算法本质上可以看做是在一个解空间当中的搜索问题所以要分析一个算法的好坏首先弄清它的解空间的结构然后分析它是怎么来探索这个解空间的。 弄清解空间的是第一步例如排序算法其解空间可以看做是所有可能的下标排列组合其中有且仅有一个排列是正确的排序排列简单起见假设元素各不相 同。那么一个算法在探索这个解空间方面的行为就决定了它的效率高低最简单的如果一个算法每次只能检查解空间中的一个点那么这个算法的复杂度就是解 空间的大小。对排序算法而言也就是n!。从这个角度来看我们就会很容易的发现所有基于比较的排序算法其复杂度为什么是以O(nlogn)为下界的 因为一次比较操作最多有两个结果ab或ab既然只有两种结果那么最多只能将解空间进行2分如果每次都能完美的2分那么找到那个 唯一点最终需要的步骤就是log(n!) O(nlogn)。如此就不难理解什么基于比较的排序算法的复杂度最好不过如此了 。 回到01背包问题01背包问题的解空间其实也是类似的。一次选取就是一个01数组其中每个元素代表其所对应的物品要不要选取。很显然这个解空 间的大小是2^n。在01背包的算法里面每当我们解出K(W, j)需要O(W)次计算之后解空间就会被折半排除掉1/2的可能性一共如此做n次就能得到最终解。由于每次折半的代价是O(W)便不难理 解为什么算法复杂度是O(nW)了。 那么为什么每次计算出K(W,j)就能使解空间折半呢那就需要来看看这个算法是如何探索解空间的算法探索解空间的方式在其递归公式里面 K(W, j) max { K(W, j-1), K(W-Wj, j – 1) Vj } 也就是说首先看你要不要选取第一个物品有两种可能性两个分支每个分支都是一个更低阶的子问题即在其中的任意一个分支下都要决定要不要选 取第二个物品又是两个分支如此下递归去可以构建出一棵有2^n方个叶子节点的树每条从根结点到叶子节点的路径“01..101”就对应一个解 其中每个分叉代表“选”或“不选”当前的物品。 建立在对这个解空间的理解上我们再来看为什么01背包问题的正确解法能做到O(nW)。首先你最好将这棵树画在纸上其中每个节点都是一个子问 题K(W,j)每条分叉都是0或1。当我们计算出所有的K(W, 1)需要O(W)次操作之后我们容易注意到所有离叶子节点的距离为1的内部节点K(W, 2)到叶子节点的两个分支都必然只能取其一了也就是说有一半的叶子节点被排除掉了对解空间折半。当我们进而计算出K(W,2)之后同样的道理 我们容易看到到叶子节点距离为2的内部节点的两个分支也只能取其一了这就进而再次将解空间折半。由于每次折半需要O(W)的复杂度所以就不难理解算 法的总复杂度为O(nW)了。另一种理解的方法是当我们计算出K(W,j)的时候从内部节点K(W,j)到根节点的唯一路径便确定了。经过O(nW) 次计算从根节点到那个唯一解叶子节点的路径便完全确定了。 知道怎么做是从正确高效解法得到的而知道为什么必须得那样做则往往是从错误低效的解法当中得到的。 然而遗憾的是绝大多数算法书或教程都只顾一上来就告诉你正确的做法是什么对于一些常见的错误解法或者常见的低效解法却根本不加分析。经验告 诉我们理解错误的做法为什么错误同样甚至更为重要往往是在理解了错误的解法为什么错误之后我们才能深刻的体会到为什么正确的解法是如此正确。 还是拿经典的背包问题来作例子你几乎看不到哪本书会告诉你一个典型的低效解法为什么低效的深刻原因。我们都知道动态规划的核心在于子问题的划分 同样的问题不同的划分办法得到的复杂度完全不一样。前面已经提到了重复背包问题的思路在01背包问题上会带来指数级的复杂度但是为什么呢如果你满 足于说因为如果拿重复背包问题的思路来解01背包问题那么子问题定义的第二个维度物品的子集见前文是指数级的那么要计算所有子问题当然是 指数级的。那么你只是看到这个问题的表象。 如果从对解空间的探索方式来说可以容易看出这个现象的本质我们回顾一下01背包问题的正确高效算法 K(W, j) max { K(W, j-1), K(W-Wj, j – 1) Vj } 这个算法讨论的是两种情况“要”或者“不要”选取第j个物品这两种情况所对应的解空间是完全不交的这就有效地将解空间划分为了不重复的两个部分。 而再来看利用重复背包问题思路的解法 K(W, S) max { K(W-Wi, S\{i}) Vi : Wi W } 这里讨论的是首先拿掉哪一个物品还是那句话讨论的每一个分支都对应了算法对解空间的一个切分我们容易看出在“先拿物品i”和”先拿物品j “这两个分支里面存在大量的重复因为先拿物品i再拿j和先拿物品j再拿i对应的是完全一样的一组选取。事实上如果你将这个递归公式画成树状结构 会发现有n!个叶子节点。n!是什么概念01背包问题的解空间大小本质上就只有2^n次方穷举也不过O(2^n)的复杂度结果这样一切分却变成了 n!可见这种对解空间的切分方法的冗余度是多么高了。你不妨看看每一次计算K(W, S)子问题能对解空间排查多少呢是否能像前面正确的算法那样每次都能有效排查一半情况理解了这一点之后我们便注意到在划分解空间也就是定义子问 题的时候的一个原则就是在建立递归公式的时候尽量将解空间进行不交的切分。同时我们便有了趁手的工具去分析一个动态规划的解法的效率。 最后再举一个例子算法书上几乎必讲的霍夫曼树。你所看的算法书在讲霍夫曼树的时候给了证明吗讲过霍夫曼树的历史八卦 吗也许你看了霍夫曼树的构造方法之后觉得“哦这样啊显然”。但是你可曾想到在最优编码这个问题上连香农本人之前给出的解法 都只是suboptimal的而且霍夫曼本人在得到这个算法之前也是绞尽脑汁几近放弃。如果你10分钟就“理解”了那么百分之百只是背了课文而已。 扩展阅读 1.Bop的豆瓣主页http://book.douban.com/subject/3004255/ 2.互动网购买链接http://www.china-pub.com/38070 3.“《编程之美》IT人求职面试必读”链接http://www.google.com.hk/search?complete1hlzh-CNnewwindow1q 编程之美-微软技术面试心得邹欣metaaqfoq 4.《我是一只IT小小鸟》豆瓣链接http://book.douban.com/subject/4006425/转载于:https://www.cnblogs.com/bvbook/archive/2010/11/26/1888348.html
