沈阳做网站公司,wordpress固定菜单栏,青海省住房与城乡建设厅网站,福州网站建站公司一、问题描述给定平面上的n个点#xff0c;找其中的一对点#xff0c;使得在n个点组成的所有点对中该点对间的距离最小。二、解题思路及所选算法策略的可行性分析思路#xff1a;利用分治法来解决问题。递归子结构求最接近点对总体可分为几个步骤#xff1a;1、当问题规模小…一、问题描述给定平面上的n个点找其中的一对点使得在n个点组成的所有点对中该点对间的距离最小。二、解题思路及所选算法策略的可行性分析思路利用分治法来解决问题。递归子结构求最接近点对总体可分为几个步骤1、当问题规模小于20直接求解最小点对2、将n个点组成的集合S分成2个子集S1和S23、递归求出两个子集中的最接近点对并比较出最小点对记录距离dmin4、以X坐标为基准找到所有点中线在中线附近找出相距可能小于dmin的点对点记录于S3和S45、求S3和S4每点对距离和dmin进行比较求解最接近点对策略可行性分析设直线l上有2m个点以m为中点将l分割成两条线段dl,dr然后求出dl和dr这两点条线段中的最小点距d1,d2此时dmin{d1,d2}再通过计算出dl线段的中最大点与dr线段中的最小点之间的距离D最小距离则为min{d,D}.二维情况与此相似最大的区别只是对于中线位置的点二维情况只是针对中线旁好多可能点再在Y轴方向上进行点的筛选以减少平方计算次数。三、伪代码描述及复杂度分析Public static double closestPoint(S){1、首先递归结束条件当数组长度在一定范围内时直接求出最近点蛮力求解2、求所有点在X坐标中的中位数midX3、以midX为界将所有点分成两组分别存放在两个表中4、将两张表转化为数组类型并分别按X坐标升序排列5、求S1中的最近距离的两个点6、求S2中的最近距离的两个点7、求两最近距离的最小值8、在S1、S2中收集距离中线小于d1的点分别存放于两个表中9、分别将表T3、T4转换为数组类型的S3、S4并将其分别按Y坐标升序排列10、求解S3、S4两者之间可能的更近(相比于d1)距离 , 以及构成该距离的点}复杂度分析设算法耗时T(n)。 算法第1步、第2步、第3步和第8步用了O(n)时间。第7步和第10步用了常数时间。第4步和第9步用了O(nlogn)时间。第5步和第6步分别用了T(n/2)时间。不过第4步和第9步是数组的排序预处理时间所以不算在算法中。所以经由预处理的算法所需计算时间满足递归方程T(n){ O(1) n42T(n/2)O(n) n4由此T(n)O(nlogn)。代码实现dcPoint.javapackage 分治法;public class dcPoint implements Cloneable, Comparable{public dcPoint() {x 0;y 0;}public dcPoint(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;Overridepublic int compareTo(dcPoint o) {if(x o.getX() y o.getY())return 0;elsereturn 1;}}NPointPair.javapackage 分治法;import java.util.ArrayList;import java.util.Random;import java.util.Set;import java.util.TreeSet;public class NPointPair {/*** 最近点问题* param S*/public static dcPoint[] closestPoint(dcPoint [] S){dcPoint[] result new dcPoint[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坐标升序排列*/dcPoint [] S1 new dcPoint[T1.size()];dcPoint [] S2 new dcPoint[T2.size()];T1.toArray(S1);T2.toArray(S2);mergeSort(S1, x);//按X坐标升序排列mergeSort(S2, x);//按X坐标升序排列/*** 4.求S1中的最近距离的两个点*/dcPoint[] result1 new dcPoint[2];result1 closestPoint(S1);/*** 5.求S2中的最近距离的两个点*/dcPoint[] result2 new dcPoint[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;elseresult 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坐标升序排列*/dcPoint [] S3 new dcPoint [T3.size()];dcPoint [] S4 new dcPoint [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(dcPoint[] a, String property){dcPoint[] tempArray new dcPoint[a.length];mergeSort(a, tempArray, 0, a.length - 1, property);}private static void mergeSort(dcPoint[] a, dcPoint [] 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(dcPoint [] a, dcPoint [] tempArray, int leftPos, int rightPos, int rightEnd, String property){int leftEnd rightPos - 1;int numOfElements rightEnd - leftPos 1;int tmpPos leftPos;//游标变量, 另两个游标变量分别是leftPos 和 rightPoswhile(leftPos leftEnd rightPos rightEnd){if(property.equals(x)){if(a[leftPos].getX() a[rightPos].getX())tempArray[tmpPos] a[leftPos];elsetempArray[tmpPos] a[rightPos];}else if(property.equals(y)){if(a[leftPos].getY() a[rightPos].getY())tempArray[tmpPos] a[leftPos];elsetempArray[tmpPos] a[rightPos];}elsethrow new RuntimeException();}while(leftPos leftEnd)tempArray[tmpPos] a[leftPos];while(rightPos rightEnd)tempArray[tmpPos] a[rightPos];//将排好序的段落拷贝到原数组中System.arraycopy(tempArray, rightEnd-numOfElements1, a, rightEnd-numOfElements1, numOfElements);}public static void main(String[] args) {Set testData new TreeSet();Random random new Random();int x 0;int y 0;for(int i 0;i 50;i){x random.nextInt(500);y random.nextInt(500);System.out.println(x: x y: y);testData.add(new dcPoint(x, y));}dcPoint [] S new dcPoint[testData.size()];S (dcPoint[]) 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());dcPoint [] result new dcPoint [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)));}}
