分治算法,有很多典型的问题,如最近点问题、线性选择问题、整数划分问题、大整数成绩问题、棋盘覆盖问题、循环赛日程表、二分搜索、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 = new TreeSet<Point>(); 
		 
		Random random = new Random(); 
		 
		int x = 0; 
		int y = 0; 
		 
		for(int i = 0;i < 600;i++){ 
			x = random.nextInt(50); 
			y = random.nextInt(50); 
			System.out.println("x:" + x + "  y:" + y); 
			testData.add(new Point(x, y)); 
		} 
		 
		Point [] S = new Point[testData.size()]; 
		S = (Point[]) testData.toArray(S); 
		 
		for(int i = 0; i < S.length; i ++){ 
			System.out.println("(" + S[i].getX() + ", " + S[i].getY() + ")"); 
		} 
		 
		System.out.println(testData.size()); 
		 
		Point [] result = new Point [2]; 
		 
		result = closestPoint(S); 
		 
		System.out.println("最近的两点分别是(" + result[0].getX() + ", " + result[0].getY()  
				+ ") 和 (" + result[1].getX() + ", " + result[1].getY() + "), 最近距离为:"  
				+ Math.sqrt(Math.pow(result[0].getX() - result[1].getX(), 2) + Math.pow(result[0].getY() - result[1].getY(), 2))); 
		 
	} 
} 

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(当点的数量很多,但集中在一块区域的时候)

若哪位大侠有幸看到并发现解决了问题,还望指教!

发布评论

分享到:

IT虾米网

微信公众号号:IT虾米 (左侧二维码扫一扫)欢迎添加!

JVM调优:利用jdk自带工具jstat详解
你是第一个吃螃蟹的人
发表评论

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。