当前位置:文档之家 > 最近对蛮力分治实验报告

最近对蛮力分治实验报告

1 《算法设计与分析》实验报告一

学号: 1004091130

姓名: 金玉琦 日期: 2011-10-13

得分:

一、实验内容:

最近对问题,即找出一个点集合中距离最近的点对,分别运用蛮力法和分治法性能解决该问题,对两种算法进行性能比较。 二、所用算法的基本思想及复杂度分析:

1.分治法

1)基本思想

我们用分治法解决最近对问题,就是将集合S 分成两个子集S 1和S2,每个子集中有n/2个点。然后在每个子集中递归的求其最接近的点对,在求出每个子集的最接近点对后,关键问题是如何实现分治法中的合并步骤,如果组成S 的最接近点对的2个点都在S1中或都在S2中,则问题很容易解决。但是,如果这2个点分别在S1和S2中,则对于S1中任一点p ,S2中最多只有n/2个点与它构成最接近点对的候选者,仍需计算才能得到准确结果。

2)复杂度分析

应用分治法求解含有n 个点得最近对问题,其时间复杂性可由下面的递推式表示:

T (n )=2T (n /2)+f (n )

合并子问题的解的时间f (n )=O (1),由通用分治递推式的主定理可得,T (n )=O (nlog 2n )

2.蛮力法

1)基本
思想

1)基本思想

蛮力法求解最近对问题的过程是:分别计算每一对点之间的距离,然后找出距离最小的一对,为了避免对同一对点计算两次距离,只考虑i

2)复杂度分析

算法的基本操作是计算两个点的欧几里得距离。注意到在求欧几里得距离时,避免了球平方根操作,原因是:如果被开方的数越小,则它的平方根也越小。所以,算法的基本操作就是求平方,其执行次数为:

T(n)=∑-=11n i ∑+=n i j 12 =2∑-=-11

)(n i i n =n (n-1)=O (n 2) 三、源程序及注释:

#define LENGTH 10000

#define min(X,Y) ((X)<(Y)?(X):(Y))

#include

#include

#include

下载Word文档免费下载:

最近对蛮力分治实验报告下载

(共6页)

实验报告 蛮力分治动态最大字段

实验报告 蛮力分治动态最大字段 - 《算法设计与分析》实验报告一 学号: 日期: 1004091130 2011-11-03 姓名: 得分: 金玉琦 一、实验内容: 实验内容: 分别用...

实验1++递归与分治算法

序列进行快速排序 实验结果 《 算法分析与设计》实验报告 -6- 实验体会 本次实验做的是集合之中距离最近的点对,首先对最近点对进行分析,可以用蛮力 法和分治法...

蛮力法分治法求最近对

蛮力分治法求最近对 - 实验题目 设 p1=(x1, y1), p2=(x2, y2), …, pn=(xn, yn)是平面上 n 个点构 成的集合 S,设计算法找出集合 S 中距离...

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

蛮力法和分治法解决最近对问题 - 算法分析与复杂型设计作业 学专班 院业级 计算机与控制工程学院 计算机软件与理论 Y130701 郑晓璐 20130789 学生姓名流...

实验项目1:蛮力法与分治法应用

实验项目 1:蛮力法与分治法应用 1、 目的与要求: 实验目的:了解蛮力法和分治法的基本思想,学会运用蛮力法和分治法解 决实际系统设计应用中碰到的问题。 实验要求...

最接近点对 分治法

最接近点对 分治法 - 刚做完实验上交的实验报告,内源代码可在vs2010运行。... 刚做完实验上交的实验报告,内源代码可在...(3)分别用蛮力法和分治法求解最近对问题...

求最大字段的三种方法—— 动态规划 蛮力 分治算法

求最大字段的三种方法—— 动态规划 蛮力 分治算法 - 昆明理工大学信息工程与自动化学院学生实验报告 ( 2011 —2012 学年 第 1 学期 ) 课程名称: 开课实验室...

分别用蛮力法、分治法、减治法实现a的N次方

分别用蛮力法、分治法、减治法实现a的N次方_计算机软件及应用_IT/计算机_专业资料。《算法设计与分析》实验报告一学 日号: 期: 2012.11.5 姓得名: 分: 一...

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

c++ 蛮力分治法求解最近对问题 - C++蛮力法求解最近对问题 1、蛮力法求解最近对 #include iostream #include math.h #include time.h #...

蛮力法、分治法和动态规划法设计最大子段和问题的算法

蛮力法、分治法和动态规划法设计最大子段和问题的算法 - 算法设计与分析实验报告 实验题目 给定由 n 个整数组成的序列(a1, a2, …, an),求该序列形如 整数...