分治法和蛮力法求解最近对问题供参习.doc

蛮力法与分治法求解最近对问题
摘要:在计算机科学理论和程序设计实践中,往往会面对众多的问题,面对这些问题,人们想到了很多算法来解决。最常见也最常用的是蛮力法,在解决问题和研究算法过程中,人们常在不断探索和寻求许多好的算法来求解同一个问题。本文就最近对问题,分别对蛮力法和分治法的思想、复杂度、效率做了一定的讲述,并对两个方法在此问题中的效率进行了简单分析。
关键字:蛮力法、分治法、效率。

通常我们所说的最接近对问题是指平面上(即二维坐标平面)给定n 个点,找其中的一对点,使得在n 个点的所有点对中,,该点对的距离最小。在求解这个问题时,我们可以采用很多算法来实现。最朴素的解法就是蛮力法,所谓蛮力法就是将是一种简单直接地解决问题的方法,常常直接基于问题的描述和所涉及的概念定义,来求解问题。这样一来,显得蛮力法确实比较实用而方便。往往事物都有两面性,此算法确实简单实用,可是效率却比较低。所以我们针对不同问题时,要采用合适的算法来求解,达到效率和求解难度综合起来达到一个比较好的极点。本文在研究最近对问题时又采用了分治法,所谓分治法,就是分而治之即把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题直到问题解决。本文只是针对一个比较简单的问题最近对问题采用两个不同算法求解进行分析解剖。

、蛮力法
蛮力法是一种简单直接地解决问题的方法,常常直接基于问题的描述和所涉及的概念定义,来求解问题。虽然巧妙和高效的算法很少来自于蛮力法,但它仍是一种重要的算法设计策略:
(1)适用泛围广,是能解决几乎所有问题的一般性方法;
(2)常用于一些非常基本、但又十分重要的算法(排序、查找、矩阵乘法和字符串匹配等);
(3)解决一些规模小或价值低的问题;
(4)可以做为同样问题的更高效算法的一个标准;
(5)可以通过对蛮力法的改进来得到更好的算法。
2、分治法
分治法,就是分而治之即把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题直到问题解决。分治法在求解问题时,效率比较高,也是一种重要的算法策略:
(1)该问题的规模缩小到一定的程度就可以容易地解决;
(2)该问题可以分解为若干个规模较小的相同问题,即该问题具有最优子结构性质;
(3)利用该问题分解出的子问题的解可以合并为该问题的解;
(4)该问题所分解出的各个子问题是相互独立的,即子问题之间不包含公共的子子问题。


(1)基本思想
蛮力法求解最近对问题的过程是:分别计算每一对点之间的距离,然后通过排序找出距离最小的一对,为了避免对同一对点计算两次距离,只考虑i<j的那些点对(Pi,Pj)。
(2)复杂度分析
算法的基本操作是计算两个点的欧几里得距离。在求欧几里得距离时,我们要避免求平方根操作,因为求平方根时要浪费时间,而在求解此问题时,求解平方根并没什么更大的意义。如果被开方的数越小,则它的平方根也越小。因此,算法的基本操作就是求平方即可,其执行次数为:
T(n)= =2=n(n-1)=O(n)

(1)基本思想
用分治法解决最近对问题,就是将集合S分成两个子集S1和S2,每个子集中有n/2个点。然后在每个子集中递