首页 > 代码库 > 分治法-最近距离问题Java实现
分治法-最近距离问题Java实现
分治算法，有很多典型的问题，如最近点问题、线性选择问题、整数划分问题、大整数成绩问题、棋盘覆盖问题、循环赛日程表、二分搜索、Strassen矩阵乘法、汉诺塔等。准备花些时间逐个解决这些问题，并用Java实现，从最近点问题开始。网上找到一些代码，标题如“java 用蛮力法和分治法求解最近对有关问题”，虽然体现了分治，但划分不够彻底，因此我重新对其进行了实现。
一、基本思想及策略：
首先，说说分治的思想。分治， “分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础，如排序算法(快速排序，归并排序)，傅立叶变换等。问题的规模越小，越容易直接求解，解题所需的计算时间也越少。
分治通过减小问题规模，对问题各个击破，其策略是：对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。
二、分治法适用的情况
分治法所能解决的问题一般具有以下几个特征：
1 该问题的规模缩小到一定的程度就可以容易地解决
2 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。
3 利用该问题分解出的子问题的解可以合并为该问题的解；
4 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。
第一条特征是绝大多数问题都可以满足的，因为问题的计算复杂性一般是随着问题规模的增加而增加；
第二条特征是应用分治法的前提它也是大多数问题可以满足的，此特征反映了递归思想的应用；、
第三条特征是关键，能否利用分治法完全取决于问题是否具有第三条特征，如果具备了第一条和第二条特征，而不具备第三条特征，则可以考虑用贪心法或动态规划法。
第四条特征涉及到分治法的效率，如果各子问题是不独立的则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然可用分治法，但一般用动态规划法较好。
三、分治法的基本步骤
分治法在每一层递归上都有三个步骤：
step1 分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；
step2 解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题
step3 合并：将各个子问题的解合并为原问题的解。
四、以最近点问题为例
最近点对问题：给定平面上的N个点，找出距离最近的两个点。不仔细分析算法的效率及优化过程，直接说说该问题的解决思路：
0 如果数组长度(即点的个数)在一定范围内时直接求出最近点，蛮力求解
1 求出这些点的X坐标的中位数mid
2 以mid为界将所有点分为两组，分表放在表T1、T2中
3 将T1、T2表转换为数组S1、S2，并将S1、S2分别按X坐标升序排列
4 求S1中的点的最近距离
5 求S2中点的最近距离
6 求4、5中的两距离的最小值，记为d1
7 在S1、S2中搜集距离中线(x=mid)小于d1的点，分别存放于表T3、T4中
8 将表T3、T4转换为数组类型S3、S4，并将S3、S4分别按Y坐标升序排列
9 求S3、S4两者之间可能的最近距离(与d1作比较)
五、代码参考
package ly.ccnu.AlgorithmDesign;
import java.util.ArrayList;
import java.util.Random;
import java.util.Set;
import java.util.TreeSet;
public class DevideAndConquer {
/**
* 最近点问题
* @param S
*/
public static Point[] closestPoint(Point [] S){
Point[] result = new Point[2];
/**
* 0.首先，解决该问题的边界，当数组长度在一定范围内时直接求出最近点，蛮力求解
*/
double dmin = Double.POSITIVE_INFINITY;
double tmpmin = 0;
if(S.length <= 20){
for(int i = 0; i < S.length; i ++){
for(int j = i + 1; j < S.length; j ++){
tmpmin = Math.sqrt(Math.pow(S[i].getX() - S[j].getX(), 2)) + Math.pow(S[i].getY() - S[j].getY(), 2);
if(tmpmin < dmin){
dmin = tmpmin;
result[0] = S[i];
result[1] = S[j];
}
}
}
return result;
}
/**
*1.求所有点在X坐标的中位数
*/
int minX = (int) Double.POSITIVE_INFINITY; //保证假设的初始最小值足够大
int maxX = (int) Double.NEGATIVE_INFINITY; //保证假设的初始最大值足够小
for(int i = 0; i < S.length; i++){
if(S[i].getX() < minX)
minX = S[i].getX();
if(S[i].getX() > maxX)
maxX = S[i].getX();
}
int midX = (minX + maxX)/2;
/**
* 2.以midX为界将所有点分成两组分别存放在两个表中
*/
ArrayList T1 = new ArrayList();
ArrayList T2 = new ArrayList();
for(int i = 0; i < S.length; i++){
if(S[i].getX() <= midX) //是否要=号？
T1.add(S[i]);
if(S[i].getX() > midX)
T2.add(S[i]);
}
/**
* 3.将两张表转化为数组类型，并分别按X坐标升序排列
*/
Point [] S1 = new Point[T1.size()];
Point [] S2 = new Point[T2.size()];
T1.toArray(S1);
T2.toArray(S2);
mergeSort(S1, "x"); //按X坐标升序排列
mergeSort(S2, "x"); //按X坐标升序排列
/**
* 4.求S1中的最近距离的两个点
*/
Point[] result1 = new Point[2];
result1 = closestPoint(S1);
/**
* 5.求S2中的最近距离的两个点
*/
Point[] result2 = new Point[2];
result2 = closestPoint(S2);
/**
* 6.求两最近距离的最小值
*/
double d1 = Math.sqrt(Math.min(Math.pow(result1[0].getX() - result1[1].getX(), 2) + Math.pow(result1[0].getY() - result1[1].getY(), 2),
Math.pow(result2[0].getX() - result2[1].getX(), 2) + Math.pow(result2[0].getY() - result2[1].getY(), 2)));
if(Math.pow(result1[0].getX() - result1[1].getX(), 2) + Math.pow(result1[0].getY() - result1[1].getY(), 2) <
Math.pow(result2[0].getX() - result2[1].getX(), 2) + Math.pow(result2[0].getY() - result2[1].getY(), 2))
result = result1;
else
result = result2;
/**
* 7.在S1、S2中收集距离中线小于d1的点，分别存放于两个表中
*/
ArrayList T3 = new ArrayList();
ArrayList T4 = new ArrayList();
for(int i = 0; i < S1.length; i++){
if(midX - S1[i].getX() < d1)
T3.add(S1[i]);
}
for(int i = 0; i < S2.length; i++){
if(S2[i].getX() - midX < d1){
T4.add(S2[i]);
}
}
/**
* 8.分别将表T3、T4转换为数组类型的S3、S4，并将其分别按Y坐标升序排列
*/
Point [] S3 = new Point [T3.size()];
Point [] S4 = new Point [T4.size()];
T3.toArray(S3);
T4.toArray(S4);
mergeSort(S3, "y");
mergeSort(S4, "y");
/**
* 求解S3、S4两者之间可能的更近（相比于d1）距离 , 以及构成该距离的点
*/
double d = Double.POSITIVE_INFINITY;
for(int i = 0; i < S3.length; i ++){
for(int j = 0; j < S4.length; j ++){
if(Math.abs(S3[i].getY() - S4[j].getY()) < d1){
double tmp = Math.sqrt(Math.pow(S3[i].getX() - S4[j].getX(), 2) + Math.pow(S3[i].getY() - S4[j].getY(), 2));
if(tmp < d){
d = tmp;
result[0] = S3[i];
result[1] = S4[j];
}
}
}
}
return result;
}
private static void mergeSort(Point[] a, String property){
Point[] tempArray = new Point[a.length];
mergeSort(a, tempArray, 0, a.length - 1, property);
}
private static void mergeSort(Point[] a, Point [] tempArray, int left, int right, String property){
if(left < right){
int center = (left + right) >> 1;
//分治
mergeSort(a, tempArray, left, center, property);
mergeSort(a, tempArray, center + 1, right, property);
//合并
merge(a, tempArray, left, center + 1, right, property);
}
}
private static void merge(Point [] a, Point [] tempArray, int leftPos, int rightPos, int rightEnd, String property){
int leftEnd = rightPos - 1;
int numOfElements = rightEnd - leftPos + 1;
int tmpPos = leftPos; //游标变量, 另两个游标变量分别是leftPos 和 rightPos
while(leftPos <= leftEnd && rightPos <= rightEnd){
if(property.equals("x")){
if(a[leftPos].getX() <= a[rightPos].getX())
tempArray[tmpPos++] = a[leftPos++];
else
tempArray[tmpPos++] = a[rightPos++];
}else if(property.equals("y")){
if(a[leftPos].getY() <= a[rightPos].getY())
tempArray[tmpPos++] = a[leftPos++];
else
tempArray[tmpPos++] = a[rightPos++];
}else
throw new RuntimeException();
}
while(leftPos <= leftEnd)
tempArray[tmpPos++] = a[leftPos++];
while(rightPos <= rightEnd)
tempArray[tmpPos++] = a[rightPos++];
//将排好序的段落拷贝到原数组中
System.arraycopy(tempArray, rightEnd-numOfElements+1, a, rightEnd-numOfElements+1, numOfElements);
}
public static void main(String[] args) {
Set<Point> testData = http://www.mamicode.com/new TreeSet();>
package ly.ccnu.AlgorithmDesign;
/**
* 建立自己的类Point
*/
class Point implements Cloneable, Comparable<Point>{
public Point() {
x = 0;
y = 0;
}
public Point(int x, int y) {
this.x = x;
this.y = y;
}
public void setX(int x) {
this.x = x;
}
public void setY(int y) {
this.y = y;
}
public int getX() {
return x;
}
public int getY() {
return y;
}
private int x;
private int y;
@Override
public int compareTo(Point o) {
if(x == o.getX() && y == o.getY())
return 0;
else
return 1;
}
}
六、遗留问题
1、TreeSet有重复元
2、堆栈溢出java.lang.StackOverflowError(当点的数量很多，但集中在一块区域的时候)
若哪位大侠有幸看到并发现解决了问题，还望指教！