[算法合集之退一步海阔天空——“目标转化思想”的若干应用.doc

退一步海阔天空——“目标转化思想”的若干应用 【关键字】让步假设 割补法 应用 【摘要】本文主要讨论在算法设计中，如何将不易求解的问题转化成为一个范围较大、但容易求解的问题，然后再将所扩大部分削减，最后得出所要的答案。讨论中主要是针对计算集合和组合数学中的一些常见问题进行剖析，同时也涉及了一些公理，如容斥原理等。在一些问题中并不一味追求一个完全理想的算法，而是将所用的方法取长补短，并讨论算法的利弊及对解题的帮助。 第一章 概述 古人常说：“退一步，海阔天空。”这是在教我们在待人接物中，要学会忍让；在追求目标时，要有所取舍。的确如此。但我们除了在行为举止中遵循古人的教诲之外，是否还可以从中得到一些启发呢？比方说，在做学问受阻而停滞不前时，能否将所不能解决的问题扩大求解呢？答案是肯定的，这正如数学界对“歌德巴赫猜想”的证明，“1+1”不行，暂且退一步，而且一退就退到了“9+9”，然后再一步步地向目标逼近，直到现在陈景润的“1+2”，不管这个猜想的证明最后能不能成功，它至少给了我们一点启发：在信息学中，也可以有“让步”，退一步，同样海阔天空。 在我们平时设计算法时，经常会遇到一些难以解决的问题，有时可以先将问题求解的范围扩大（如条件放松、给以适当假设（猜想）、目标放大等），然后再对新的问题求解，最后，将扩大部分“剪掉”，就解决了问题。例如2002NOI分区联赛（提高组）复赛第二题，整数划分。问题问的是：将一个自然数n分解成为k部分A1，A2，A3，……Ak（其中A1=A2=A3=……=Ak），问有多少种不同的分法？解题时，问题不易直接求解，必须先将它进行转化。不难发现，问题等价于：将一个自然数n分成若干份，其中最大的一份为k的分法总数。这时，可以令设G(n,k)表示这个值的大小，但这样仍然不利于解决问题，于是引入另外一个函数F(n,k)，表示将一个自然数n分解成若干份，其中最大一份不超过k的方法总数。于是，F(n.k)便满足以下递推关系： 这样，便可以用最常规的递推算法求解问题了，方法简单，每次运算也只需要进行一次加法运算，算法复杂度为O(NK)，最后就是所求。在这里，一开始先对问题进行转化，将难于求解的转化为可以求解的，但仍需进行累加，复杂度太高。于是就运用了上面所说的“让步”，将求解目标扩大到分得的允许最大一份小于k，最终得到一个二次方复杂度的算法。应当说，这里虽然也用了目标扩大的方法，但这退的只是一小步，只是达到了简化算法的目的，并不涉及解题模型的根本。 第二章 在计算几何中的应用 计算几何是近几年信息学竞赛经常涉及的领域，虽然考得不是很深，但一些常见的问题还是难倒了不少选手。这也许是因为现实世界与纯粹的数字世界有太大差异的缘故吧。例如遮挡问题，判断一件物体是否被另外的一件或几件物体遮挡，这在日常生活中想都不用想，看一眼就什么都清楚，但在计算几何中，就不是一件轻而易举的事情了。也正因为如此，“让步假设”才在计算几何中大有用武之地。例如许多涉及到多边形面积的问题就经常用到这一方法：求多边形面积、求多边形重心、判断点与多边形位置关系等等。对于这些问题，无论在日常计算或是实际的算法设计中都或多或少的引入了这一思想。例如小学时我们常做这样的习题：计算右图染色部分的面积。我们谁都知道要先求出矩形的面积，再将圆形面积求出，最后相减便得到结果。其实也可以将它看成这样一个过程：先假设圆形也是图形的一部分，它也染了色，于是整个图形便是一个矩形，然后将“假设”的部分拿掉，就得到了这个图形。由这种思想便产生了另外的一种更为科学的面积计算方法。 第一节 计算任意多边形的面积 学习计算几何，就不得不面对一个问题：计算平面图形面积。如果按图形的形状分，可将其分为折线图形和弧线图形，我们这里讨论的主要是折线图形的面积。折线图形又可以分为凸多边形和凹多边形（假设多边形的任意两条边都不相交，端点除外）。凸多边形面积比较好求，只须先将它分解成为若干个三角形，再用海伦公式或叉积面积计算公式就可以方便求出了，而对于凹多边形恐怕就要花费一番心思了。受到上面图形的启发，不难得到一种初学者常用的方法：先将一个凹多边形补足成为一个凸多边形，求其面积，再减多出来的部分。但这种方法显然带有瑕疵，例如下面的几个图形，虽然都可以补足成为一个凸多边形，但补足部分的面积计算就大相径庭了：第一个图形的多余部分是一个三角形，第二个的是一个凸多边形，最后一个则是一个凹多边形了。这种方法正违背了运用“割补”的最重要原则：方便。“割补法”的核心正是变复杂为简单，但如果无法降低其运算复杂度，割补就失去了它的意义了。 其实，求任意多边形的面积已经有一种经典的算法——叉积面积计算公式。假设笛卡儿坐标系中的一个任意多边形A1A2A3……Ak，各点的坐标分别是A1(X1,Y1)，A2