每周算法练习——最近对问题

felixzhao

发布于 2018-03-16 17:05:39

1K0

发布于 2018-03-16 17:05:39

文章被收录于专栏：null的专栏null的专栏

一、最近对问题的解释

看到算法书上有最近对的问题，简单来讲最近对问题要求出一个包含

个点的集合中距离最近的两个点。抽象出来就是求解任意两个点之间的距离，返回距离最小的点的坐标，以及最小距离。这里会使用到欧式距离的求法：

以上是二维的情况，这其实和相似性的计算是类似的，所以便想去实现这样的一个问题。

二、最近对问题的蛮力解法

蛮力法是最直接的方法，就是求解任意两个点之间的距离，返回坐标和最小的距离

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;
	}
}

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

如有侵权请联系 cloudcommunity@tencent.com 删除

其他

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

其他

登录后参与评论

0 条评论

热度