看到算法书上有最近对的问题,简单来讲最近对问题要求出一个包含
个点的集合中距离最近的两个点。抽象出来就是求解任意两个点之间的距离,返回距离最小的点的坐标,以及最小距离。这里会使用到欧式距离的求法:
以上是二维的情况,这其实和相似性的计算是类似的,所以便想去实现这样的一个问题。
蛮力法是最直接的方法,就是求解任意两个点之间的距离,返回坐标和最小的距离
Java代码实现
package org.algorithm.closestpair;
/**
* 蛮力法是最显然的方法,也是最直接的方法
*
* @author dell
*
*/
public class ClosestPairProblem01 {
public static final int length = 20;// 点的个数
// 主函数
public static void main(String args[]) {
// 存放x和y
Point p[] = new Point[length];
for (int i = 0; i < length; i++) {
p[i] = new Point(Util.createXY(), Util.createXY());
}
// 打印出每个点的坐标
for (int i = 0; i < length; i++) {
System.out.println(i + "\t" + p[i].getX() + "\t" + p[i].getY());
}
// 计算出最近对
double result[] = Util.closestPair(p, length);
System.out.println("最近对为:");
System.out.println((int) result[0] + "\t" + (int) result[1] + "\t"
+ Math.sqrt(result[2]));
}
}
最终的结果
分治的思想是将一个问题划分成几个独立的子问题,分别对子问题的求解,最终将子问题的解组合成原始问题的解。个人理解的分治法与现在的并行十分相似,如在演化计算中,由于运算规模比较大,十分强调是否可以并行计算,本身演化计算又特别适合做并行。再如Map-Reduce,同样是一种并行的计算方式。如何将原始问题划分成子问题成为分治的关键。
在最近对问题中,首先通过一维坐标将整个空间分成坐标点个数相同的两个区间,如下图:
(图片摘自:http://www.cnblogs.com/AdaByron/archive/2011/10/07/2200966.html)
分别计算出区域
和
上的最小值
和
,此时,取中间的部分,因为在我们将坐标点分开的过程中,中间的点对可能距离比区域
和
上的最小值还要小,
。最终返回所有可能解的最小值。
Java代码实现
package org.algorithm.closestpair;
import java.util.Collection;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
import java.util.TreeSet;
/**
* 主要通过分治的思想求解
*
* @author dell
*
*/
public class ClosestPairProblem02 {
public static final int length = 20;// 点的个数
// 主函数
public static void main(String args[]) {
// 存放x和y
Point p[] = new Point[length];
for (int i = 0; i < length; i++) {
p[i] = new Point(Util.createXY(), Util.createXY());
}
// 打印出每个点的坐标
for (int i = 0; i < length; i++) {
System.out.println(i + "\t" + p[i].getX() + "\t" + p[i].getY());
}
// 计算出最近对
int middle = length / 2;
Set<Double> st = new TreeSet<Double>();
for (int i = 0; i < length; i++) {
st.add(p[i].getX());
}
// System.out.println(st);
// 找到middle位置的x的值
Iterator<Double> it = st.iterator();
int index = 0;
double middleValue = 0;
while (it.hasNext()) {
if (index == middle) {
middleValue = it.next();
break;
}
index++;
it.next();
}
// System.out.println(middleValue);
// 将前一半放入到mpLeft中,后一半放入到mpRight中
Map<Integer, Point> mpLeft = new HashMap<Integer, Point>();
Map<Integer, Point> mpRight = new HashMap<Integer, Point>();
for (int i = 0; i < length; i++) {
if (p[i].getX() < middleValue) {
mpLeft.put(i, p[i]);
} else {
mpRight.put(i, p[i]);
}
}
// System.out.println(mpLeft.size() + "\t" + mpRight.size());
// 分别计算左右两边的最小距离
Collection<Point> cLeft = mpLeft.values();
Collection<Point> cRight = mpRight.values();
Point pLeft[] = cLeft.toArray(new Point[0]);
Point pRight[] = cRight.toArray(new Point[0]);
double d1[] = Util.closestPair(pLeft, pLeft.length);
double d2[] = Util.closestPair(pRight, pRight.length);
Set<Integer> stKeyLeft = mpLeft.keySet();
Set<Integer> stKeyRight = mpRight.keySet();
Integer[] iLeft = stKeyLeft.toArray(new Integer[0]);
Integer[] iRight = stKeyRight.toArray(new Integer[0]);
d1[0] = iLeft[(int) d1[0]];
d1[1] = iLeft[(int) d1[1]];
d2[0] = iRight[(int) d2[0]];
d2[1] = iRight[(int) d2[1]];
double d[];
// d1和d2中的距离的最小值
if (d1[2] < d2[2]) {
d = d1;
} else {
d = d2;
}
// System.out.println(d);
// 存放中间的[middleValue-d,middleValue+d]之间的点
Map<Integer, Point> mpMiddle = new HashMap<Integer, Point>();
for (int i = 0; i < length; i++) {
if (p[i].getX() >= (middleValue - d[2])
&& p[i].getX() <= (middleValue + d[2])) {
mpMiddle.put(i, p[i]);
}
}
Collection<Point> cMiddle = mpMiddle.values();
Point pMiddle[] = cMiddle.toArray(new Point[0]);
double d3[] = Util.closestPair(pMiddle, pMiddle.length);
Set<Integer> stKeyMiddle = mpMiddle.keySet();
Integer[] iMiddle = stKeyMiddle.toArray(new Integer[0]);
d3[0] = iMiddle[(int) d3[0]];
d3[1] = iMiddle[(int) d3[1]];
double dMin[];
if (d3[2] < d[2]) {
dMin = d3;
} else {
dMin = d;
}
System.out.println(dMin[0] + "\t" + dMin[1] + "\t" + Math.sqrt(dMin[2]));
}
}
运行结果:
自我感觉这段代码写得特别复杂,希望看到这篇博客的朋友们提点意见,帮助我提高下我的写代码的能力。
这里我还构造了公共的代码:
Point类:
package org.algorithm.closestpair;
/**
* 主要用于存储坐标
*
* @author dell
*
*/
public class Point {
private double x;// x的坐标
private double y;// y的坐标
public Point(double x, double y){
this.x = x;
this.y = y;
}
public double getX() {
return x;
}
public void setX(double x) {
this.x = x;
}
public double getY() {
return y;
}
public void setY(double y) {
this.y = y;
}
}
工具类:
package org.algorithm.closestpair;
public class Util {
// 计算两个点之间的距离的平方
public static double distance(Point x1, Point x2) {
return (Math.pow((x1.getX() - x2.getX()), 2) + Math.pow(
(x1.getY() - x2.getY()), 2));
}
// 随机产生坐标
public static double createXY() {
return Math.random() * 10;
}
// 计算最近对
public static double[] closestPair(Point p[], int length) {
double maxDistance = Double.MAX_VALUE;// 设置一个最大值
double result[] = new double[3];
for (int i = 0; i < length - 1; i++) {
for (int j = i + 1; j < length; j++) {
double tmp = Util.distance(p[i], p[j]);
if (tmp < maxDistance) {
maxDistance = tmp;
result[0] = i;
result[1] = j;
}
}
}
result[2] = maxDistance;
return result;
}
}