分治法和蛮力法求解最近对问题

《分治法和蛮力法求解最近对问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、蛮力法与分治法求解最近对问题摘要：在计算机科学理论和程序设计实践中，往往会面对众多的问题，面对这些问题，人们想到了很多算法来解决。最常见也最常用的是蛮力法，在解决问题和研究算法过程中，人们常在不断探索和寻求许多好的算法来求解同一个问题。本文就最近对问题，分别对蛮力法和分治法的思想、复杂度、效率做了一定的讲述，并对两个方法在此问题中的效率进行了简单分析。关键字：蛮力法、分治法、效率。一．引言通常我们所说的最接近对问题是指平面上（即二维坐标平面）给定n个点，找其中的一对点，使得在n个点的所有点对中,，该点对的距离最小。在求解这个问题时，我们可以采用很多算法来实现。最朴素的解法就是

2、蛮力法，所谓蛮力法就是将是一种简单直接地解决问题的方法,常常直接基于问题的描述和所涉及的概念定义，来求解问题。这样一来，显得蛮力法确实比较实用而方便。往往事物都有两面性，此算法确实简单实用，可是效率却比较低。所以我们针对不同问题时，要采用合适的算法来求解，达到效率和求解难度综合起来达到一个比较好的极点。本文在研究最近对问题时又采用了分治法，所谓分治法，就是分而治之即把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题直到问题解决。本文只是针对一个比较简单的问题最近对问题采用两个不同算法求解进行分析解剖。二．算法概述及实用范围2.1、蛮力法蛮力法是一种

3、简单直接地解决问题的方法，常常直接基于问题的描述和所涉及的概念定义，来求解问题。虽然巧妙和高效的算法很少来自于蛮力法，但它仍是一种重要的算法设计策略：4（1）适用泛围广，是能解决几乎所有问题的一般性方法；（2）常用于一些非常基本、但又十分重要的算法（排序、查找、矩阵乘法和字符串匹配等）；（3）解决一些规模小或价值低的问题；（4）可以做为同样问题的更高效算法的一个标准；（5）可以通过对蛮力法的改进来得到更好的算法。2、分治法分治法，就是分而治之即把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题直到问题解决。分治法在求解问题时，效率比较高，也是一种重

4、要的算法策略：（1）该问题的规模缩小到一定的程度就可以容易地解决；（2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；（3）利用该问题分解出的子问题的解可以合并为该问题的解；（4）该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。三．算法的基本思想及复杂度分析3.1．蛮力法（1）基本思想蛮力法求解最近对问题的过程是：分别计算每一对点之间的距离，然后通过排序找出距离最小的一对，为了避免对同一对点计算两次距离，只考虑i

5、免求平方根操作，因为求平方根时要浪费时间，而在求解此问题时，求解平方根并没什么更大的意义。如果被开方的数越小，则它的平方根也越小。因此，算法的基本操作就是求平方即可，其执行次数为：T(n)==2=n（n-1）=O（n）3.2.分治法（1）基本思想用分治法解决最近对问题，就是将集合S分成两个子集S1和S2，每个子集中有n/2个点。然后在每个子集中递归的求其最接近的点对，在求出每个子集的最接近点对后，关键问题是如何实现分治法中的合并步骤4，如果组成S的最接近点对的2个点都在S1中或都在S2中，则问题很容易解决。但是，如果这2个点分别在S1和S2中，则对于S1中任一点p，S2中最多

6、只有n/2个点与它构成最接近点对的候选者，仍需计算才能得到准确结果。（2）复杂度分析应用分治法求解含有n个点得最近对问题，其时间复杂性可由下面的递推式表示：T（n）=2T（n/2）+f(n)合并子问题的解的时间f（n）=O（1），由通用分治递推式的主定理可得：T（n）=O（nlogn)为提高算法效率，在算法中采用预排序技术，即在使用分治法之前，预先将S中的n个点依其y坐标排序好。经过预排序处理后的算法所需的计算时间T(n)满足递归方程：当n小于4时，T(n)=O(1)；当n大于等于4时，T(n)=2T(n/2)+O(n)。由此易知，T(n)=O(nlogn)。预排序所需的计算

7、时间显然为O(nlogn)。因此，整个算法所需的计算时间为O(nlogn)在点的个数比较少的时候，蛮力法所用时间比分治法少，点数比较多的情况下，分治法的优势就很明显了，所用时间明显比蛮力法少。四．算法描述（1）蛮力法在最近对问题中的算法描述intClosestPoints(intn,intx[],inty[],int&index1,int&index2)minDist=+∞;for(i=1;i