一、問題描述

給定平面上的n個(gè)點(diǎn)，找其中的一對點(diǎn)，使得在n個(gè)點(diǎn)組成的所有點(diǎn)對中該點(diǎn)對間的距離最小。

二、解題思路及所選算法策略的可行性分析

思路：利用分治法來解決問題。遞歸子結(jié)構(gòu)求最接近點(diǎn)對總體可分為幾個(gè)步驟：

1、當(dāng)問題規(guī)模小于20，直接求解最小點(diǎn)對

2、將n個(gè)點(diǎn)組成的集合S分成2個(gè)子集S1和S2

3、遞歸求出兩個(gè)子集中的最接近點(diǎn)對并比較出最小點(diǎn)對，記錄距離dmin

4、以X坐標(biāo)為基準(zhǔn)找到所有點(diǎn)中線，在中線附近找出相距可能小于dmin的點(diǎn)對點(diǎn)，記錄于S3和S4

5、求S3和S4每點(diǎn)對距離，和dmin進(jìn)行比較，求解最接近點(diǎn)對

策略可行性分析：

設(shè)直線l上有2m個(gè)點(diǎn)，以m為中點(diǎn)將l分割成兩條線段dl,dr，然后求出dl和dr這兩點(diǎn)條線段中的最小點(diǎn)距d1,d2，此時(shí)d=min{d1,d2}，再通過計(jì)算出dl線段的中最大點(diǎn)與dr線段中的最小點(diǎn)之間的距離D，最小距離則為min{d,D}.

二維情況與此相似，最大的區(qū)別只是對于中線位置的點(diǎn)，二維情況只是針對中線旁好多可能點(diǎn)，再在Y軸方向上進(jìn)行點(diǎn)的篩選，以減少平方計(jì)算次數(shù)。

三、偽代碼描述及復(fù)雜度分析

Public static double closestPoint(S)

{

1、首先，遞歸結(jié)束條件，當(dāng)數(shù)組長度在一定范圍內(nèi)時(shí)直接求出最近點(diǎn)，蠻力求解

2、求所有點(diǎn)在X坐標(biāo)中的中位數(shù)midX

3、以midX為界將所有點(diǎn)分成兩組分別存放在兩個(gè)表中

4、將兩張表轉(zhuǎn)化為數(shù)組類型，并分別按X坐標(biāo)升序排列

5、求S1中的最近距離的兩個(gè)點(diǎn)

6、求S2中的最近距離的兩個(gè)點(diǎn)

7、求兩最近距離的最小值

8、在S1、S2中收集距離中線小于d1的點(diǎn)，分別存放于兩個(gè)表中

9、分別將表T3、T4轉(zhuǎn)換為數(shù)組類型的S3、S4，并將其分別按Y坐標(biāo)升序排列

10、求解S3、S4兩者之間可能的更近(相比于d1)距離 , 以及構(gòu)成該距離的點(diǎn)

}

復(fù)雜度分析：

設(shè)算法耗時(shí)T(n)。 算法第1步、第2步、第3步和第8步用了O(n)時(shí)間。第7步和第10步用了常數(shù)時(shí)間。第4步和第9步用了O(nlogn)時(shí)間。第5步和第6步分別用了T(n/2)時(shí)間。不過第4步和第9步是數(shù)組的排序預(yù)處理時(shí)間，所以不算在算法中。所以經(jīng)由預(yù)處理的算法所需計(jì)算時(shí)間滿足遞歸方程：

T(n)={?? O(1)????????? n<4

2T(n/2)+O(n)?? n>=4

由此，T(n)=O(nlogn)。

代碼實(shí)現(xiàn)

dcPoint.java

package 分治法;

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;

@Override

public int compareTo(dcPoint o) {

if(x == o.getX() && y == o.getY())

return 0;

else

return 1;

}

}

NPointPair.java

package 分治法;

import java.util.ArrayList;

import java.util.Random;

import java.util.Set;

import java.util.TreeSet;

public class NPointPair {

/**

* 最近點(diǎn)問題

* @param S

*/

public static dcPoint[] closestPoint(dcPoint [] S){

dcPoint[] result = new dcPoint[2];

/**

* 0.首先，解決該問題的邊界，當(dāng)數(shù)組長度在一定范圍內(nèi)時(shí)直接求出最近點(diǎn)，蠻力求解

*/

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.求所有點(diǎn)在X坐標(biāo)的中位數(shù)

*/

int minX = (int) Double.POSITIVE_INFINITY;//保證假設(shè)的初始最小值足夠大

int maxX = (int) Double.NEGATIVE_INFINITY;//保證假設(shè)的初始最大值足夠小

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為界將所有點(diǎn)分成兩組分別存放在兩個(gè)表中

*/

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.將兩張表轉(zhuǎn)化為數(shù)組類型，并分別按X坐標(biāo)升序排列

*/

dcPoint [] S1 = new dcPoint[T1.size()];

dcPoint [] S2 = new dcPoint[T2.size()];

T1.toArray(S1);

T2.toArray(S2);

mergeSort(S1, "x");//按X坐標(biāo)升序排列

mergeSort(S2, "x");//按X坐標(biāo)升序排列

/**

* 4.求S1中的最近距離的兩個(gè)點(diǎn)

*/

dcPoint[] result1 = new dcPoint[2];

result1 = closestPoint(S1);

/**

* 5.求S2中的最近距離的兩個(gè)點(diǎn)

*/

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;

else

result = result2;

/**

* 7.在S1、S2中收集距離中線小于d1的點(diǎn)，分別存放于兩個(gè)表中

*/

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轉(zhuǎn)換為數(shù)組類型的S3、S4，并將其分別按Y坐標(biāo)升序排列

*/

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)距離 , 以及構(gòu)成該距離的點(diǎn)

*/

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;//游標(biāo)變量, 另兩個(gè)游標(biāo)變量分別是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++];

//將排好序的段落拷貝到原數(shù)組中

System.arraycopy(tempArray, rightEnd-numOfElements+1, a, rightEnd-numOfElements+1, 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("最近的兩點(diǎn)分別是(" + 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)));

}

}

總結(jié)

以上是生活随笔為你收集整理的java最接近对点及距离_最接近点对问题_分治法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。