算法合集之《类比思想在解题中的应用》

《算法合集之《类比思想在解题中的应用》》由会员分享，可在线阅读，更多相关《算法合集之《类比思想在解题中的应用》（13页珍藏版）》请在金锄头文库上搜索。

1、类比思想在解题中的应用【关键字】 思想；类比；相似性；对应【摘要】： 类比，是一种试图建立未知的问题与已知的问题之间的联系，从而利用已知的解题方法去解决新的问题的思路。本文首先通过分析具体的例子，指出类比解题不仅仅是注意到了表面上的相似性，更是建立了已知问题和未知问题之间的对应关系。然后，本文将通过另一个例子，论述表面相似性与内在的对应之间的关系，并且指出利用类比解题的过程是从表面相似性上升到一一对应的过程。引：解题，从熟悉的地方开始 面对一个新的问题应该如何着手去分析解决呢？ 从熟悉的地方开始着手。这是生活中人们常常采用的方法：希望面对的难题与以前解决过的某个问题是相同的，或者至少类似的；由

2、此就可以获得值得借鉴的经验。面对一个陌生的问题，试图把它和某个熟悉的问题联系起来，借助熟悉的知识和熟悉的方法来解决新问题，是自然的想法。 这种寻找未知问题和已知问题之间联系的思想，可以称为类比。更确切的说，“如果两个系统的各自的各部分之间，存在某种一致的关系的话，则称两个系统是可以类比的。” 引自参考书目i（数学与猜想）第二章。 如何理解定义中所说的“一致的关系”呢？ 如果只简单的把“存在某种一致的关系”理解成一种含糊的相似性。那么类比就完全归结为人的主观的感觉，这种主观上的“似曾相识”是不能够作为分析问题、解决问题的依据的。然而类比的思想的确被广泛的应用于解决各种问题，说明类比的本质是另一种

3、比表面上的相似性更可靠和更有说服力的“一致关系”。事实上，类比是建立在两个问题之间的一种一一对应的映射关系。本文的第一部分，正是试图阐述这一本质上的“一致关系”。 然而两个问题之间的本质联系并不是那么容易得到的。人们在对问题的最初的分析中，注意到的往往还是表面上（甚至只是文字上）的相似性。希望直接得到两个问题之间相互对应和相互转化的关系是不现实的。因此，最初观察到的表面上的相似性虽然有些不可靠，但是至少它能够为分析问题指出方向，由此尝试着建立问题之间的对应关系。正如本文第二部分将要阐述的，利用类比解题的过程是从模糊到清晰，从表面到本质的分析过程。 接下来的两个部分，就将探讨类比过程中，表面的相

4、似和本质的对应之间的关系。类比的本质，一一对应的关系 类比作为一种分析问题的思想方法，目的是希望将不熟悉的知识转化为熟悉的知识，将未知的问题转化为已知的问题。 如何实现这一转化，取决于如何对两个问题进行类比。如果仅考虑到两个问题表面上的相似性，那么很可能会机械的模仿已知问题的解决方法，来解决新问题。这种想法缺乏严谨可靠的支持，难以保证在实际解题中能够成功。即使成功了，也是知其然而不知其所以然，没有发现问题之间本质的联系，往往得不到最好的解决方法。而当类比过程中两个问题之间存在一种对应关系，未知问题中的所有描述对象和操作，在已知问题中都有与之一一对应的内容，那么整个未知的问题就可以通过这种一一对

5、应的映射关系，转化为已知的问题，也就可以应用已知问题的解决方法来解决它。 下面的例子就是如此。【“整数拆分”与“因数分解”】 整数拆分：将一个正整数n，拆分为一组小于n的正整数的和（不考虑这组正整数排列的先后次序）。求总共有多少组可能的拆分。 问题来自参考书目ii（算法设计）4.2.4。 这是一道众所周知的组合计数问题。解决的方法有两种： 利用递归的枚举解题模型。(对应程序名DIVIDE1.PAS) 将问题描述为：求满足等式 的所有正整数组（a1，a2，a3，a4，am）的总数。为此，可以采用递归枚举的方法逐个确定每一个ai从而求出所有的解，并统计总数。 设D(k,n)为将n拆分成一组不小于k

6、的正整数的和的解的数目。 例如，a1可以选取1n/2之间的任意整数，剩下的n-a1可以拆分成不小于a1的若干个整数的和。于是对于a1，有； 而对a2，有 由此不难得出问题的递归求解式 ; 问题的解等价于 ( 减一以除去n = n的拆分方案 )。 由于原问题只要给出解的总数，而这一算法在计算过程中求出了所有的解，所以枚举算法的效率在n较大的时候是很低的。 母函数解题模型。(对应程序名DIVIDE2.PAS) 设拆分的这组正整数中1出现的次数为x1，2出现的次数为x2，等等，那么问题可以描述为：求不定方程 的整数解的总数。于是就可以利用构造母函数，来求不定方程的整数解的个数。方法如下： 利用母函数

7、计算不定方程整数解的总数的一般方法，请参见参考书目iii（组合数学及其在计算机科学中的应用）。 拆分中不选取1可以表示为x0=1，取一个1表示为x，取两个1为x*x=x2，取k个1为xk。由加法原理得到选取1的所有方案为 ； 不选取2可以表示为1，取一个2表示为x2，取两个2为x2*x2=x4，取k个为x2k，由加法原理得到选取2的所有方案为 ； 同理，对于正整数r，选取k个表示为xk*r，由加法原理得到选取r的所有方案为 ； 再由乘法原理，同时选取1,2,n-1的方案可以表示为 由于要使最后的和等于n，所以g(x)展开式中的系数，就是问题的解。对于这类母函数，无法直接用通项公式计算其展开式的

8、系数，但是可以通过逐次进行的多项式的乘法求解展开式。这在程序实现中相当于一个线性表的归并算法，而计算过程中也不必求出方程实际的解，速度较上一种方法快得多。（程序和运行效率的比较，请见附录） 因数分解：将一个正整数n，分解为除1和它本身的因数的乘积的形式，不考虑因数的先后顺序，求所有可能的分解方案的总数。 将一个正整数分成若干个正整数，这种表述是熟悉的。事实上，这和整数拆分中的表述是相似的。虽然两个问题之间的区别是显然的：一个是拆成乘积的形式；一个是拆成和的形式。但是两个问题都是计算一个整数分成若干个整数的方案数目。 于是，在注意到了两个问题表面上的相似后，确定“因数分解”的问题也可以用枚举法来

9、解决。不妨着手模仿整数拆分的解题模型，将问题描述为：求满足等式的所有正整数组（a1，a2，a3，a4，am）的总数。可以发现，两个问题的描述是非常相似的，只是把加号换成了乘号。可以直接做这样的变换而不改动其它内容的关键在于：加法和乘法都满足交换律和结合律。它们是两种非常相似的运算。由以上的描述出发，模仿“整数拆分”的D(k,n)，同样可以定义F(k,n)为将n分解成一组不小于k的正整数的积的解的数目， 则容易推导出 ; 而 F(2,n)-1 就是问题的解。 由于采用的是枚举法，在n的因子很多时，程序的速度是非常慢的。(对应程序名P1.PAS) 以上的解题模型和“整数拆分”的方法是出奇的类似的。

10、然而，机械的模仿所能做到的也只有这些了。它无法解释两个问题为什么如此类似。 然而，有一点已经被提了出来：两者之所以是相似的，关键在于加法和乘法是相似的。那么加法和乘法之间，究竟是怎样的关系呢？ 为了回答这个问题，要引入同构的定义： 设有两个集合A，B，“”和“”为分别定义在两个集合上的（二元）运算。那么称A和运算“”构成一个代数系统A，B和运算“”构成代数系统B，。 如果存在一个一一对应的映射，使得对于所有的xA，yA， 都有，则称代数系统A，和B，是同构的。 如果两个代数系统是同构的，那么显然其中一个系统中的问题总可以转化为另一个系统中的问题。 现在借助简单的中学知识，就可以知道R，+与R+

11、，*是同构的： 设，则有恒有成立。 对数函数ln(x)就是把乘法转化为加法的工具。 有了这些作为基础，我们就可以很有信心的利用母函数解决因数分解问题。 首先假设整数n有除1和n以外因数共m个，为p1、p2、p3pm，而设每个因数pi在分解的式子中出现次数分别为xi，那么问题可以描述成：求方程 的非负整数解的数目。接着，利用ln(x)把乘法转化为加法，对等式两边取对数，就得到对应的线性方程；欲求它的非负整数解的个数，利用加法原理和乘法原理构造母函数（推导过程参见“整数拆分”的相应段落）， 则g(x)展开式的项的系数就是问题的解。与整数拆分的求解方法类似的，利用线性表的归并算法，就可以求出解来。(

12、对应程序名P2.PAS) 与递归枚举算法相比，算法的效率同样也大大的提高了。（程序和运行效率的比较，请见附录）如果仅仅凭借表面上观察到的相似性，而不清楚乘法和加法代数系统之间存在着同构的关系，是不容易得出利用母函数的解题模型的。这个例子中最有启发性的，莫过于同构概念的引入。为了说明两个同构的代数系统之间的关系，借助了一个一一映射，这个映射使两个系统的不同运算之间产生了一种对应关系：；这样A集合中关于运算的每一个问题，都与B集合中关于运算的一个问题相对应。于是可以把A，中的问题转化为B，中的问题来解决。实现这种转化正是利用类比思想解题的目的，而寻找这种一一对应的关系则是类比的实质。只要发现了这种

13、一一对应的关系，就能够应用解决已知问题的方法去解决新问题。同构只是代数系统中的概念，然而对应的关系可以应用到其它问题中，因此用类比解题是不局限于代数系统之内的。下面的例子就属于另一个不同方面。目的是在进一步说明类比的表象和它的本质之间的关系。从表面的相似到内在的对应 类比的本质是揭示已知问题与未知问题之间一一对应的关系。但是，正如引言中说的，本质往往不容易被发现，而表面的相似性却首先被观察到。所以，不应该忽视表面的相似性；相反，应该沿着相似性所指出的方向开始分析，尝试发现问题之间的本质联系。 在分析下面这个例子的过程中，将着重说明这一点。【平面分割空间问题】 一个平面把空间分成独立的两个部分，

14、两个平面把空间分成4个部分。n个平面，最多能把整个空间分割成多少个部分。 问题来自参考书目i（数学与猜想）第三章。 立体空间的情况是陌生的，而且不容易描述。虽然同样是“分割”问题。但是正常情况下，不会把它和“整数拆分”联系起来，因为两者处理的对象（整数和空间平面）是完全不同的。那么，究竟如何把这个问题和已知的知识联系起来呢？这个时候，即使是表面的相似性，也能够为解题提供一条线索。 类比的目的是将未知的、复杂的东西化为已知的、简单的东西。空间上的问题是复杂的，而平面上的问题则是简单的。而且空间和平面的关系，与平面和直线的关系，是相似的。平面把空间分割成两个部分，直线也把平面分割成两个部分。 于是

15、得到了另一个与例题相类似的问题：n条直线，最多能把整个平面分割成多少个部分。 这实际上是本届（第五届）分区联赛初赛的一道填空题。 这道题容易解决得多。它的解决方法是利用数学归纳法（如图）：一条直线，把平面分割为两个部分（A和B）；增加一条直线，它与第一条直线相交，被分为两段射线，每一段射线又把所在的区域（例如A）分成两部分（A1和A2）；因此增加了2个部分；共有2+2=4个部分。 再增加一条直线，它与前两条直线相交，被分为三段，每一段又把所在区域（例如B1）分成两部分(B11和B12)；总共增加了3个部分；共有4+3=7个部分； 由此类推，设前k-1条直线共把平面分为Ak-1个部分。加入第k条直线，与前k-1条直线相交，被分为k段，每一段把所在区域分为两部分；总共增加了k部分；总共有Ak-1+k个部分。 于是得到了递推关系 A1=2； Ak=Ak-1+k； 由此不难计算出通项公式： ； 于是直线分割平面的问题就解决了。 解决这一问题对“平面分割空间问题”有何帮助？既然空间和平面，与平面和直线的关系相似，那么直接把平面换成空面，把直线换成平面，就可以直接用以上的过程来证明未知的问题了吗？显然是不可以的。这仅仅是根据主观的相似得出的机械的