目录
1. 引言
1.1 实验目的
1.2 实验内容
1.3 实验要求
2. 实验运行环境
2.1 硬件环境
2.2 软件环境
3. 程序设计说明
3.1 功能概述
3.2 程序目录结构的介绍
4 界面操作说明
4.1 鼠标输入点的界面操作
4.2 随机生成点的界面操作
5 实验结果及相关结论
6 程序使用的一些技巧和优点
6.1 使用的一些技巧
6.2 程序的优点
1. 引言
1.1 实验目的
通过使用普通方法和分治法对求平面上最近两点，比较在不同输入规模情况下Θ(n^2)和Θ(nlgn)算法的实际运行时间，加强对分治法的理解与掌握。
1.2 实验内容
实现求平面上最近点对的复杂度为Θ(nlgn) 的算法
A. 有图形界面，能够通过鼠标输入点，并标识出最近点对;
B. 能够随机生成大量平面点(要求可达到一百万个点)，并输出最近点对。
1.3 实验要求
要求交源码，可执行程序，实验报告。
2. 实验运行环境
2.1 硬件环境
CPU: 2.5 GHz Intel Core i7
内存:16.0GB
2.2 软件环境
操作系统:mac OS10.12
语言及编译平台:Java【jdk1.8】，Eclipse
3. 程序设计说明
3.1 功能概述
在主界面中，存在两个 Tab 控件，其中在“随 机产生点”控件中，用户可以输入 2～1000000 之间的一个整数，来表示随机产生的平面点数；在“鼠标生成点”Tab控件中， 用户能够通过鼠标点击输入点，通过计算后，使用红色标识出最近点对。
3.2 程序目录结构的介绍
在这次程序编写过程中，在mac 系统下采用了 Eclipse IDE 环境，求平面上点程序的目录截图如下:
A、其中mainScreen.java 是程序的主界面类，该界面手工编写，提高代码的可读性;该类生成了主界面，获取用户在前台界面的输入，后台获取到数据进行计算，然后返回，在界面中响应给用户，该类起到前后台交互的作用;
B、CalProcess.java是程序的后台实现类，该类实现了接受前台传入的参数， 使用普通方法和分治法计算平面最近点对的算法，然后将结果作为参数返回给前台;
C、pointsPanel.java是鼠标输入面板的实现类，该类接收鼠标在该面板上的点击事件，获取点击的坐标位置，画出点，并将点存至点集合中，同时存储坐标位置以便后来的计算。
D、pointsProperty.java是随机生成点的vo类，定义横纵坐标，并生成get和set方法。
E、RandomPoints.java是随机生成点的方法，并调用后台的两种方法，同时计算对应方法使用的时间。
3.3 程序实现方案
3.3.1 一般方法Θ(n2)的实现方案
普通方法：通过对所有的n个点进行两两匹配，算出两点之间距离的平方，然后进行比较來得到最短距离和最近点对。
3.3.2 分治法 Θ(nlgn)的实现方案:
分治法：
1.求出x的中位数，按照中位数，将点集合分成左右两个点集合。在左右集合中递归调用divided()方法，求出左右集合最近点对的距离，并得到最小值d。
2. 左右两侧收集距离中线小于d的点，分别存放于两个数组中。再将小于d的点的2个集合转化为数组类型，按y升序排序。再在距离中线最近的左右两个数组，求解更近的点。再利用分治法对点集合中的点x／y进行升序排序。最后合并排序结果。
3.3.3 总体实现方案:
1、在鼠标输入 Tab 面板中，创建完面板后，接收用户的鼠标点击事件，获取到点击的坐标，存储这些坐标点，同时进行界面的重绘來完成画点操作，实现的部分代码如下:
当用户点击“计算”按钮之后，将所有获取到的点坐标的序列作为参数传送到后台进行计算，然后根据计算结果修改面板(将最近点对标识为红色)。下图为点击计算按钮后，调用普通和分治法的操作：
下图为点击重置按钮执行的操作：
2、在随机生成点面板中，创建完面板后，用户输入一个 2～1000000的一个整数(其他输入为非法输入，将提示用户重新输入)，点击“开始计算”按钮之后，将获取到的用户输入数值作为参数传送到后台，之后进行计算，根据计算结果修改面板(将最近点对标识为红色)。如果用户输入的整数大于100000，将只使用分治法进行计算，因为使用普通方法所花的时间太长了。 其实现的部分代码如下:
4 界面操作说明
4.1 鼠标输入点的界面操作:
A、运行程序后得到如下界面:
B、通过鼠标点击蓝色眶内画点，可以得到如下界面:
C、点击“计算”按钮之后，将用红色标识出最近点对，如下图:
4.2 随机生成点的界面操作:
A、刚开始该 Tab 控件面板的界面如下:
B、输入一个整数，出现如下界面:
点击“计算”按钮，将出现下面的界面:
C、如果输入的整数大于 100000，比如说500000，点击“计算”按钮之后，将出现如下界面:
D、如果输入的整数大于 100000，比如说 1000000，计算结果如下:
5 实验结果及相关结论
通过在运行程序时，输入结果所等待时间的长短，可以很明显看出:在求解最近平面点对时，分治算法的性能明显优于普通算法，特别是当输入的整数越大，性能差别会越明显。针对不同的输入规模，一般法和分治法所花的时间对比如下表格和折线图展示:
生成的平面点数目一般法求解所花时间(单位为: 毫秒)分治法求解所花时间(单位为: 毫秒)
2 0 0
100 2 1
1000 3 14
10000 141 11
100000 9334 144
500000 太慢 984
1000000 几小时甚至算不出来 4683
从表格和折线图中可以看出，输入规模不断增大，一般法求解的所花时间也不断变长，当输入为 100000 时，所花的时间已经超过10秒了，当输入为 500000 时，所花的时间已经算得很慢了，所以对于输入为 1000000 时，该方法甚至会花费几个小时才能算出来;而输入为 20000000 时， 则几乎不可能算出来了。对于分治法，基本上也是随着输入规模的增大，所花费的时间也不断增多。
综上所述，Θ(n2)的普通算法和Θ(nlgn)的分治法随着输入规模 n 的增大， 两者的运行时间差别也越来越大。因此，在平时的编程时，特别是面对大数据输入之类的编程时，我们应该努力优化自己的算法，这样才能够有效的提高自己的程序运行效率。
6 程序使用的一些技巧和优点
6.1 使用的一些技巧
(1)由于实验要求能够处理 1000000 个点，所以随机生成点的坐标只设置 从-1000000～+1000000，这样能够减少计算两个点距离的时间;
(2)在比较最近点对时，只计算了两点之间距离的平方，而没有进行开方操作，这样也可以减少很多操作;
(3)在使用分治法求解，递归回溯的过程中，计算d*2d的矩形中所有点的最近点对时，每个点需要进行 7 次比较，本程序对位于同一侧的点对没有进行求解两点间距离平方的操作而是直接跳过，这样也可以节省不少时间。
6.2 程序的优点
(1)界面代码纯手工进行编写，可读性非常高;而且也具有一定的可交互性;
(2)排序时，没有使用 java 中 ArrayList 本身的排序算法，而是自己写了归并排序的算法，这样排序的速度会更快点;
(4)虽然使用 Java 进行编写，但是程序的运行速度还是比较快的，输入为 1000000 个点时，只花费了 4 秒多即可算出结果。
网友评论