算法实验二分治法最近点对问题

分治法算法分析与设计实验二

主要内容

•

•实验目的主要实验仪器设备和环境实验内容实验要求注意点

实验目的

•理解分治法的基本思想

•针对特定问题，可以设计出分治算法进行求解

主要实验仪器设备和环境

•每位学生一台计算机

•计算机的操作系统为

–windows 2000或Windows XP

•工具软件

–C++ IDE，JAVA IDE

实验内容二最近点对问题•问题描述

–对于平面上给定的N个点，给出所有点对的最短距离

–即，输入是平面上的N个点，输出是N点中具有最短距离的两点

•现要求随机生成N个点的平面坐标，应用穷举法编程计算出所有点对的最短距离

•现要求随机生成N个点的平面坐标，应用分治法编程计算出所有点对的最短距离

实验要求

•编程语言可以用C,C++或者JAVA，关键步骤必须有注释

•实验报告必须包含以下内容：算法设计的基本思路、程序清单以及针对测试数据的运行结果•实验报告电子版请发至[email protected]，Email标题：“学号姓名算法实验二最近点对”，附件请不要压缩，实验报告名：“学号姓名算法实验二最近点对”

注意点

•随机数的生成问题

•求解最近点对问题时的分治策略

•分解后子问题的解如何合并

编码提示

•随机数生成

–srand(time(0));//设置随机数种子

•要#include

–rand();//生成[0,MAX)之间的随机整数

•要#include

–for(inti=0;i

{

ran_num=rand() % 10;

cout

}//生成不大于10的随机整数

编码提示

•最近点对问题的分治策略

–S:平面上的二维点集合

–预处理：分别根据点的x轴和y轴坐标进行排序，得到X和Y,很显然此时X和Y中的点就是S中的点

编码提示

•Conquer

–两个递归调用，分别求出

和drSL和SR中的最短距离为dl

编码提示

•Combine–对于Y’L中的每一点，检查Y’R中的点与它的距离，

更新所获得的最近距离

算法实验二 分治法 最近点对问题

相关文章

算法实验二分治法最近点对问题