贪心与分治

贪心与分治主讲：薛杰目次1贪心法1.1贪心法简介1.2贪心法的优缺点及反例问题1.3贪心法的正确应用实例*1.4贪心法求取较优解2分治思想2.1分治思想简介2.2二分搜索中分治思想的体现2.3排序中分治思想的体现2.3.1快速排序中的分治思想2.3.2二路归并排序中的分治思想2.4运用分治思想解决乘幂问题贪心法1.1贪心法简介贪心法的基本思想，顾名思义，就是只考虑眼前的、局部的利益，忽略全局，见好就收。中国有些古话就能体现出这种思想，例如“好汉不吃眼前亏”、“今朝有酒今朝醉，明日愁来明日愁”等。贪心法广泛运用于求最优解、较优解的问题上，由于其基本思想相当简单，相信每个同学在现实生活中都用过。然而，要将贪心法运用得当却也绝非易事。因为贪心法并不是对任何问题都能保证正确的。所以说，贪心法是一门艺术，而对它的掌握和运用就可以体现出一个选手的素质高低。贪心法1.2贪心法的优缺点及反例问题上节解释了贪心法的基本思想，下面来说说这种思想的优缺点各在何处。贪心思想的优点是显而易见的。用两个字高度抽象地概括出来，就是“简单”。由于其思想简单，故而程序实现时时间复杂度和代码复杂度一般都非常低，且程序清晰易读，便于修改。而贪心法的缺点呢？可谓一言难尽。但只需根据“贪”这个字，就能大抵明白。古往今来，贪心的人数不胜数，有几个能有好下场呢？贪心法的弊病也在于此，有时难有好的下场。贪心法由于贪心法只注重局部的利益，根据眼前的利益大小就作出决定，目光短浅，往往会导致全局上的利益受损，从而无法得到全局上的最优。也就是我们常说的“小不忍则乱大谋”。这样一来就使得贪心法适用的范围变得很窄，很多问题仅能用贪心来获得较优解，而并不能够得出最优解。一个问题中，凡是用贪心算法无法得到全局上的最优解的数据，我们统称为这种贪心的反例。反例越少的贪心算法越优秀（当然有些题也有不存在反例的贪心算法，那是最好不过的了）。下面我们就来看一些贪心算法存在反例的例子，在这些例子中，贪心仅能取得较优解。贪心法【例一】数塔问题，描述如下有这么一个数塔，共有n层。第一层有一个数，第二层有两个数……依此类推，第n层有n个数。今有一人字塔顶走向塔底，每次下一层，下的过程中要么向左，要么向右。最后形成一条路线，将这条路线上所有的数加起来，得到一个和，要求这个和最大。（如图）贪心法这道题目的解应该是24，走法是自塔顶起右-左-左，路径是3-9-5-7。下面我们对这道题使用贪心法试试。贪心的原则是：自塔顶起，永远向着下一层左右两数中大的数走，如果左右两数等值，那么就向左走。我们先用题目的样例数据进行测试，塔顶3，下一层左边1，右边9；走向9，再下一层左边5，右边1；走向5，再下一层左边7，右边5；走向7，最后的路线是3-9-5-7，和为24，正确！这时候有的同学就会很自然地认为这道题目使用贪心算法是正确的。然而，事实如何呢？样例数据用贪心法能得出正确解仅能代表样例并非反例，并不能说明贪心法不存在反例。贪心法此题的贪心法反例其实是很容易构造的，请大家看这个数据：n=3，第一行是1，第二行是2、1，第三行是2、1、9999。这个数据的正确解是10001，走法是先右后左。让我们用刚才的贪心法模拟一下。得出结果是5，走的路径是两次都向左。为什么结果错误了呢？原来这个数据中有个超大的9999，只有一直向右走，才能取到这个9999。而如果使用贪心法，第一步贪图眼前的利益，取较大数2，向左走，无异于是南辕北辙。正是因为走第一步时只注重局部，一失足成千古恨，与最优解擦肩而过。贪心法现在让我们将原题作一个小小的改动。原题是每一步下一层，并且只能向左或向右。现在我们将题目改成每一步下一层，并且可以下到那一层的任意一个位置。这时候如果我们再使用贪心法进行求解效果又将如何呢？会不会还存在反例呢？经过测试，我们发现无论如何都构造不出反例来。为什么此时贪心法就没有反例呢？原因其实很简单。前者使用贪心，贪图了眼前的利益，对后面的取值产生了影响（例如向左走，那么右边一条永远不能取到），故而很可能错过最优解。而后者虽然也是贪图眼前的利益，但任何一步对后面的取值都是毫无影响的，也就是说不会因为贪小利而受到大损失。所以这时的贪心法是正确的。贪心法【例二】0/1背包问题，描述如下有一个固定容量的背包，容量为w，今有n个物件，每个物件有自身的体积vi，以及自身的价值pi。要从这n个物件中取出一些放入背包中（总体积不能超过背包容量），要求使得放入物品的总价值最大。请注意，每件物品只有一个，且物品不能被分割。这就是经典的0/1背包问题。本来这个问题有标准的解法，能够保证绝对正确。现在讲的是贪心法，那我们不妨用贪心法在这道题上试试。有趣的是，这道题倘若用贪心法，贪心原则并非唯一的，可以有好多种。贪心法下面我来列举三种最简单的贪心方式。第一种，由于背包容量有限，要想放更多的物品增加总价值，每次就尽量放体积最小的物品，也就是根据体积排序，从小到大依次放入。第二种，由于最后要使得价值最大，故而每一次总是尽量放置价值最大的物品，也就是根据物品的价值进行排序，从大到小依次放入。第三种，也是最合理的一种想法，要在有限的体积中尽量放置总价值最大的物品，那么一定要合理利用每一点容量。故而每一次总是尽量放入容量利用率最大的物品（即pi/vi最大的物品，每一份体积的价值最大）。根据p/v排序，从大到小依次放入。贪心法为什么会存在这样的反例呢？第三种贪心不是已经保证空间利用率最高了吗？原因在于，空间利用率最高并不能保证总价值最高！总价值=空间利用率*占用的总空间。第三种贪心法虽然保证空间利用率最高，但往往会导致最后背包内还剩下很大的空间没法放东西，也就是最后实际占用的总空间并不大。可见这三种贪心法各有各的缺陷，都是有反例的贪心法。但如果考试时你只想到了这三种贪心的方法，你将怎么办呢？你可以同时使用三种贪心，得出三个解，然后在三个解当中取最大的作为答案。这就是贪心的叠加，这样可以使得三种贪心互相取长补短（虽然也并非完全正确）。贪心法这三种贪心中，头两种肯定是不正确的。反例也是相当容易构造。第一种根据体积贪心，只要有一个体积较大的物品价值十分高，便无法得到最优解；第二种根据价值贪心，只要有一个价值较大的物品体积十分高，便也难得到最优解。那么第三种呢，第三种贪心方式是否也存在反例？第三种根据空间利用率来排序，看似十分科学，无懈可击。然而反例却还是存在的。请同学们看如下的一组数据，n=3，w=10，v1=6，p1=18，v2=5，p2=12，v3=5，p3=11。根据第三种贪心方式，背包里只能放第一件物品，总价值为18，但正确答案是放第二件和第三件，总价值可达23。贪心法1.3贪心法的正确应用实例以上我们说到的都是有反例的贪心法。当然，有些问题还存在无反例的贪心法。这时使用贪心法求得的必然是最优解，也就是说贪心法是绝对正确的。这类问题才是贪心法应用的关键。首先，我们来看一道与适才【例二】相似的问题，叫做可拆背包问题。【例二】中有一个规定，物品是不能被分割的。而在可拆背包问题中取消了这个规定，可以将物品进行分割，分割后的价值与原价值的比等于分割后的体积与原体积的比。除此之外与【例二】别无二致。对于可拆背包问题，就存在无反例的贪心法。贪心法下面我们用刚刚的第三种贪心试试。尽量取空间利用率最大的物件放置，如果放不下，就将该物件分割后放入背包。经过试验，我们发现这种贪心方法是不存在反例的，百分之百能够获得最优解。这是为什么呢？原因还在于这个公式：总价值=空间利用率*占用的总空间。由于物件可拆，占用的总空间成了一个定数（要么是背包的总容量，要么是所有物件的体积和），这时只要空间利用率达到最大，便能保证总价值最大。可见，可拆背包问题是贪心法成功应用的一个实例，因此它的标准算法就是贪心。贪心法【例三】喷泉放置问题，描述如下今有一长方形草坪，长边为l，短边为w。要在草坪短边的对称轴上放置一些喷洒半径为r的喷头，使得每一寸土地都得到喷洒。其中r大于w。问最少需要几个这样的喷头？如何放置？这也是一道十分简单的用贪心法来解决的问题。从矩形的左边开始放喷头。每一个喷头在摆放时尽量靠右，最后得出的答案必然是最少的。那么这个问题在使用这种贪心法的时候为什么不存在反例呢？这可以用等效替代的方法进行证明，等效替代是证明贪心正确的常用方法，下面我来证明一下。贪心法【例四】士兵排布问题，描述如下A国的阵地上有n个据点，有些据点之间有路相连，总共有n-1条路，并且任意两个据点之间有且仅有唯一的一种相同方式（n个据点和n-1条路组成一棵树）。现在A国要派一些士兵在这些据点戍守，要求任何一条路两端所连接的两个据点中至少要有一个据点有士兵戍守，不能两端据点都空。问最少需要几名士兵？（如图，黑色点表示有士兵戍守的据点）贪心法把这个问题抽象描述就是找一颗树的最小覆盖（取最少的点覆盖所有的边）。同样，这个问题也是可以用贪心法正确解决的。但是此时的贪心法应用起来就需要一定的技巧了，并不是根据任何原则贪心都正确。我们下面先来看这么一种贪心的思想。由于每一条边的两端都至少要有一个点被取到，所以每次都取能够“管”到的边最多的点，也就是度最大的点，然后在原树中删除这个点和它的所有连边，直到所有边都被删除为止。这种贪心法是否能保证一定得出最优解呢？表面上看似乎能。其实不然，让我们来看一组数据。贪心法根据点的度从大到小贪心被推翻了，下面我们来看看这道题标准的贪心是怎样的。由于题目给出的是一棵树，所以必然存在度为一的节点（也就是叶子节点）。找到这棵树的一个叶子节点。在这个叶子节点所连接的那个节点上放置一个士兵，并且把这两个节点连同它们所有的连边在原树中删除，剩下的必然还将是一棵树，继续如上的操作，直到所有边都被删除为止。经过试验发现，这种贪心法是不具有反例的。事实上这一点也可以用等效替代的方法证明。由此可见，即便是在一道题目中，贪心法也并非唯一的，而能否找出正确的贪心原则，是解题的关键。贪心法*1.4贪心法求取较优解当然，大部分问题用贪心法都是难以得到最优解的。但是面对有些问题时候，我们未必要得到最优解，只需要求取一个较优解就可以了。这时候，贪心法就成了首选的算法。比如【例二】0/1背包问题，如果变成了实际生活中的问题，根据空间利用率来贪心就可以得出一种较优解。又比如在运用启发式搜索、A*等人工智能算法时，启发函数（即估价函数）的值就可以用贪心法求取一个较优解来计算。总之，贪心法在较优解问题上的运用是相当广泛的。分治思想2.1分治思想简介分治思想是递归思想中的一个分支，简单地说是一种特殊的递归思想。分治就是“分而治之”，它是用“分”的思想来实现我们在递归思想中所讲到的缩小问题规模。它将一个复杂的问题分成若干个（一般情况下是两个，也就是二分）小规模的子问题加以解决，这些子问题相互间是独立的，并且与原问题相似。分治思想在解决查找、排序等问题时使用频繁，一般情况下时间复杂度中有个n的对数函数。分治思想2.2二分搜索中的分治思想体现二分搜索又称二分查找，很好得体现了分治思想。二分搜索必须针对一个有序的序列进行，在这个有序序列中查找一个给出的元素。二分搜索是这么做的。先找到这个序列中最中间的一个元素，这个元素将整个序列分成了左右两个等分。将需要查找的元素与这个元素进行比较，以确定在该元素的左边还是右边。这样一来，左右两个等分中必然有一个要被舍弃，问题的规模也就缩小到了一半。分治思想也就很好地体现了出来。那么，为什么一定要取最中间的那个元素作为切分点呢？可不可以找其它元素？分治思想找其它元素作为切分点当然也是可行的，例如找1/3处的元素作为切分点，最后也是能够获得正确解，找到给出的元素。然而，就算法的效率上来讲，找1/2处的元素作为切分点将序列等分效率是最高的。找其它元素作为切分点运算次数会多于等分。这一点是可以被证明的。首先，要查找的元素在序列中的每一个位置出现的概率是相等的。现在我们假设整个序列的长度为l。如果找1/a处的元素作为切分点（a1），有1/a的几率查找的元素在序列左半段，这时剩余序列的长度转化为l/a；有