数学建模社区-数学中国

标题: 距离最近的点对 [打印本页]
作者: 韩冰    时间: 2004-10-4 05:18
标题: 距离最近的点对
<>给定n 个点（xi，yi）（1≤i≤n），要求找出其中距离最近的两个点。
: s, s) |% Z5 m' K" c4 F! k4 T; I3 f: B. ^
例14-7 假设在一片金属上钻n 个大小一样的洞，如果洞太近，金属可能会断。若知道任意两个洞的最小距离，可估计金属断裂的概率。这种最小距离问题实际上也就是距离最近的点对问题。- s+ U' D* e9 ~5 `7 u

" u$ [/ |, r! b# I通过检查所有的n(n- 1 ) / 2对点，并计算每一对点的距离，可以找出距离最近的一对点。这种方法所需要的时间为(n2 )。我们称这种方法为直接方法。图1 4 - 1 3中给出了分而治之求解算法的伪代码。该算法对于小的问题采用直接方法求解，而对于大的问题则首先把它划分为两个较小的问题，其中一个问题（称为A）的大小为「n /2ù，另一个问题（称为B）的大小为「n /2ù。初始时，最近的点对可能属于如下三种情形之一： 1) 两点都在A中（即最近的点对落在A中）；2) 两点都在B中；3) 一点在A，一点在B。假定根据这三种情况来确定最近点对，则最近点对是所有三种情况中距离最小的一对点。在第一种情况下可对A进行递归求解，而在第二种情况下可对B进行递归求解。
5 s+ a: K* Z6 I9 |" _" H$ U% h
' A) p% v0 J* W& L1 e  e4 B) q- T0 `; p3 I+ X6 f9 u
if (n较小) {用直接法寻找最近点对/ u5 f. S$ x; _' b5 b

: @/ A) R5 J$ J; r( gR e t u r n ; }0 ]2 m7 k; k8 q/ W

& `9 B; r0 D' p: S0 T$ \2 R// n较大
  V& t+ q1 j9 H& Q9 e  V
/ [4 I6 h  V" P/ F  j0 E8 I: L将点集分成大致相等的两个部分A和B! s4 P& ~* }% d2 M& u* E( S3 [

8 V( S$ Y3 o& z5 d确定A和B中的最近点对3 k: v$ d: Y9 d, A% f( |* \/ l
5 L3 K2 X! U2 E3 w' M5 W
确定一点在A中、另一点在B中的最近点对* t$ u' E, ^  [. O
- M) w: l6 C3 H( d  f6 }. O
从上面得到的三对点中，找出距离最小的一对点. ~! s: i5 K, s& q; }6 E

( G, q! X- c7 F# J5 j, O: Y% ?  [图14-13 寻找最近的点对
, x) t. ^( H+ Q
- x( S6 [" c; T7 Y8 @6 w8 }  O" z  p! z2 i0 ^0 }# f* ^
为了确定第三种情况下的最近点对，需要采用一种不同的方法。这种方法取决于点集是如何被划分成A、B的。一个合理的划分方法是从xi（中间值）处划一条垂线，线左边的点属于A，线右边的点属于B。位于垂线上的点可在A和B之间分配，以便满足A、B的大小。) c( l+ |% [4 O! T/ q, ^9 C3 a

8 i' V0 S; |6 N& C- f例2-8 考察图14-14a 中从a到n的1 4个点。这些点标绘在图14-14b 中。中点xi = 1，垂线x = 1如图14-14b 中的虚线所示。虚线左边的点(如b, c, h, n, i)属于A，右边的点(如a, e, f, j, k, l) 属于B。d, g, m 落在垂线上，可将其中两个加入A, 另一个加入B，以便A、B中包含相同的点数。假设d ,m加入A，g加入B。# @. _3 k0 l/ B7 e8 v( o
% ^" f) O7 C  L
设是i 的最近点对和B的最近点对中距离较小的一对点。若第三种情况下的最近点对比小。则每一个点距垂线的距离必小于，这样，就可以淘汰那些距垂线距离≥ 的点。图1 4 - 1 5中的虚线是分割线。阴影部分以分割线为中线，宽为2 。边界线及其以外的点均被淘汰掉，只有阴影中的点被保留下来，以便确定是否存在第三类点对（对应于第三种情况）其距离小于。用RA、RB 分别表示A和B中剩下的点。如果存在点对(p,q)，p?A, q?B且p, q 的距离小于，则p?RA，q?RB。可以通过每次检查RA 中一个点来寻找这样的点对。假设考察RA 中的p 点，p的y 坐标为p.y，那么只需检查RB 中满足p.y- ＜q.y＜p.y+ 的q 点，看是否存在与p 间距小于的点。在图14-16a 中给出了包含这种q 点的RB 的范围。因此，只需将RB 中位于×2 阴影内的点逐个与p 配对，以判断p 是否是距离小于的第三类点。这个×2 区域被称为是p 的比较区（comparing region）。
6 p! u: E& [; C3 k1 W4 B4 r8 }3 Z6 a; D" y, r$ V/ P7 G
例2-9 考察例2 - 8中的1 4个点。A中的最近点对为(b,h)，其距离约为0 . 3 1 6。B中最近点对为(f, j)，其距离为0 . 3，因此= 0 . 3。当考察是否存在第三类点时，除d, g, i, l, m 以外的点均被淘汰，因为它们距分割线x= 1的距离≥ 。RA ={d, i, m}，RB= {g, l}，由于d 和m 的比较区中没有点，只需考察i即可。i 的比较区中仅含点l。计算i 和l的距离，发现它小于，因此(i, l) 是最近的点对。/ K) ~7 j$ d- B& o4 V- k( P, r: r
1 A8 x4 Y  V" u9 T0 Z, z$ |5 F
为了确定一个距离更小的第三类点，RA 中的每个点最多只需和RB 中的6个点比较，如图1 4 - 1 6所示。
7 V# h  P' B6 T3 Z5 a! i3 E1 x( j
1. 选择数据结构0 T5 \$ U2 V4 ]4 d5 ?, u: G0 Y
* d& A7 f5 r; I  l5 _
为了实现图1 4 - 1 3的分而治之算法，需要确定什么是“小问题”以及如何表示点。由于集合中少于两点时不存在最近点对，因此必须保证分解过程不会产生少于两点的点集。如果将少于四点的点集做为“小问题”，就可以避免产生少于两点的点集。
* n. \1 P3 M! g" h1 K$ L
# U  X. L8 T3 E: p每个点可有三个参数：标号， x 坐标，y 坐标。假设标号为整数，每个点可用P o i n t l类（见程序1 4 - 8）来表示。为了便于按x 坐标对各个点排序，可重载操作符＜=。归并排序程序如1 4 -3所示。% M- q5 N+ f) v3 R

5 K3 x1 {) v' \* g程序14-8 点类# h+ O$ N1 |) [3 K' a3 |
3 ?; ~: g0 h# E' Q5 h. v) B
class Point1 {
1 m( T/ Y0 k# |& }0 m; j0 q. A' [6 h' V6 p
friend float dist(const Point1&amp;, const Point1&amp;);; ?! c# s, X# f+ |

  r% b  U: x2 Vfriend void close(Point1 *, Point2 *, Point2 *, int, int, Point1&amp;, Point1&amp;, float&amp;);3 \; O$ Z4 t9 t% |1 m5 N4 F

  z( f4 C' c* r% Sfriend bool closest(Point1 *, int, Point1&amp;, Point1&amp;,float&amp;);
( q$ ]$ V1 ^: s0 b; ]4 o3 @; _: [# a
friend void main();7 f& _- x  y5 n& r$ Z. t0 N% y
5 `- h- Y9 v) k9 e7 V$ J
p u b l i c :. ~/ i1 e4 o& n4 Z- m% t7 t

2 ^, b; ]4 A- i% g; F3 @" Bint operator&lt;=(Point1 a) const
7 d! }( `8 b0 B! \7 {
. r& V  X% Y# ~6 A{return (x &lt;= a.x);}
$ j9 d! ^; S) i* u- y) ^
0 L, S" N# F5 @: x! q1 Kp r i v a t e :
$ }7 m/ A5 @/ J# v
' L2 L5 ~4 m8 I: G" v+ n% @% H- U, I1 Vint ID; // 点的编号8 V# E. F, j# [  {
4 G! y$ v) N% e! }! g: [
float x, y; // 点坐标
9 Q$ P+ E3 E) G6 D4 j% B- Y' K, L9 D; ~9 d6 v# ?
} ;
! w7 J7 Q2 B; j/ y' E) L$ [8 F# V; o+ j1 E. r5 P* }& |: `" H) }
class Point2 {& t; M% G+ E# `& [1 ~! m
9 A  G! L4 q' B. l
friend float dist(const Point2&amp;, const Point2&amp;);
% o- w( ~2 `7 b* E1 d$ D. C( d8 j; [' P
friend void close(Point1 *, Point2 *, Point2 *, int, int, Point1&amp;, Point1&amp;, float&amp;);8 t$ Y1 g/ \9 @

& e, u4 a" b7 E1 ?" t$ vfriend bool closest(Point1 *, int, Point1&amp;, Point1&amp;, float&amp;);
; A) R5 x0 a) i5 T* P
# |) o# n  F$ F4 I) D" }friend void main();
& U; Q' }0 j1 u( S0 ^1 p, z: z5 V
p u b l i c :
2 h% `! f! J% j! e, {7 H( N
/ l$ G/ W, q& rint operator&lt;=(Point2 a) const% ^5 }1 Q) o" p8 v; I
4 M- ?! @6 D; ~
{return (y &lt;= a.y);}2 ^6 Q0 Z, c/ c/ I6 j

! S" v4 V- J) v/ X- M/ s4 op r i v a t e :
0 y! I4 ~/ w8 O0 ?1 I$ A" \3 s4 X. [$ J2 L) u
int p; // 数组X中相同点的索引
2 V* V  @4 }& S3 D9 o
8 Q' @, U: ?' l/ i/ Cfloat x, y; // 点坐标
' B! u" [5 l, e+ b8 z" e/ P$ A7 W% o- ]% Z0 F+ \+ w; C- }
} ;
9 N$ }/ A' X: m1 }& m, t" P8 S/ L
0 a! s, g& V) ]- [所输入的n 个点可以用数组X来表示。假设X中的点已按照x 坐标排序，在分割过程中如果当前考察的点是X [l :r]，那么首先计算m= (l+r) / 2，X[ l:m]中的点属于A，剩下的点属于B。计算出A和B中的最近点对之后，还需要计算RA 和RB，然后确定是否存在更近的点对，其中一点属于RA，另一点属于RB。如果点已按y 坐标排序，那么可以用一种很简单的方式来测试图1 4 - 1 6。按y 坐标排序的点保存在另一个使用类P o i n t 2 (见程序14-8) 的数组中。注意到在P o i n t 2类中，为了便于y 坐标排序，已重载了操作符＜＝。成员p 用于指向X中的对应点。
0 T: Z9 j5 D4 w/ w  ]5 }/ W% Y: y0 }1 M: c/ w
确定了必要的数据结构之后，再来看看所要产生的代码。首先定义一个模板函数d i s t (见程序1 4 - 9 )来计算点a, b 之间的距离。T可能是P o i n t 1或P o i n t 2，因此d i s t必须是P o i n t 1和P o i n t 2类的友元。
8 n4 W7 u  T8 X) n! J
; h7 b$ |4 _& \/ H+ C5 g8 h9 |程序14-9 计算两点距离
+ a$ b1 B8 B7 A. Y
7 v0 u- T; c" z9 `- `2 `template<CLASS T>( T6 R9 D, }7 z: \5 u/ X$ a

; n- k; l, ~: C. x( E: A' ninline float dist(const T&amp; u, const T&amp; v); j% p: Q; _* k  r/ e( @
% x% O0 r4 X- }5 u
{ / /计算点u 和v之间的距离
+ X. Y& {4 M/ N7 \9 J( X7 ^+ H6 d: Y; I1 p" |* ], K. B
float dx = u.x-v. x ;) z; Y! P1 p7 y, x3 r- d

: c' B1 P$ X; F  W, m! U% mfloat dy = u.y-v. y ;* @) m" e, A4 P1 @, A+ H

- [$ X* K$ N  q+ N# D+ Ureturn sqrt(dx * dx + dy * dy);
; A  Q) Z( `* Y3 f! y2 N  M; C5 E
, @; b- O# q5 \}
  r7 [/ n9 V; v7 N% ^7 c
! G  y  b# m( g# X( Q$ a2 y$ i如果点的数目少于两个，则函数c l o s e s t (见程序1 4 - 1 0 )返回f a l s e，如果成功时函数返回t r u e。当函数成功时，在参数a 和b 中返回距离最近的两个点，在参数d 中返回距离。代码首先验证至少存在两点，然后使用M e rg e S o r t函数(见程序14-3) 按x 坐标对X中的点排序。接下来把这些点复制到数组Y中并按y 坐标进行排序。排序完成时，对任一个i，有Y [i ] . y≤Y [i+ 1 ] . y，并且Y [i ] .p给出了点i 在X中的位置。上述准备工作做完以后，调用函数close (见程序1 4 - 11 )，该函数实际求解最近点对。/ d$ Y# S( y# p9 M5 R$ c
4 Z0 r) _, V. v1 S% T% k; `2 ]$ k
程序14-10 预处理及调用c l o s e
3 O7 g9 q5 H, a: i& L: o1 Y7 N
. z9 q' V* [, I+ e4 X& Z" Z/ a) ]6 ybool closest(Point1 X[], int n, Point1&amp; a, Point1&amp; b, float&amp; d)2 @3 u0 ]0 L2 W( E
5 U( C0 J% M  _
{// 在n &gt;= 2 个点中寻找最近点对: M; q! G8 G% I! {' I, e  ^

" j( _; ^' F1 G& c+ T// 如果少于2个点，则返回f a l s e5 c4 s7 Y. k* y6 |1 l5 B

7 a  g: x0 `8 V" M// 否则，在a 和b中返回距离最近的两个点- f' {# A- ?6 x5 c

& l+ y3 V# A! @if (n &lt; 2) return false;) N) _& W$ H) ^7 i

; c4 F; ^2 L0 P6 G3 k// 按x坐标排序
7 l, d0 \- a4 ]' g" `4 e3 X/ ?
0 }( [3 N+ k1 X7 r: W' lM e r g e S o r t ( X , n ) ;
' E+ E( J' F2 u0 n0 k; k' e
) Z7 `- {3 b% r* {7 G5 w// 创建一个按y坐标排序的点数组
0 p1 L4 d6 a- T, a( h2 L; R. g8 P! z1 F. ^6 l6 ^
Point2 *Y = new Point2 [n];& \( e% f' {3 Q8 g
' ?" @- P) f+ @& w
for (int i = 0; i &lt; n; i++) {1 Z3 n/ |: [+ _7 ?! D5 Q

" Z, Y1 d$ p4 G6 X// 将点i 从X 复制到Y! E" f& A: O8 A5 _/ W% V$ S1 b
3 u: T& F2 V1 g4 L8 N- J  p
Y.p = i;3 ?7 g' z8 u+ j5 ~
* w! W7 O4 _+ |5 b4 `+ E2 Q
Y.x = X.x;$ L6 P1 a( X2 ~
+ _3 M$ W+ _1 `" Q; [
Y.y = X.y;8 k5 Q4 D9 P3 E! z" H0 ^
/ X' e& a" R- O( w
}
0 I2 d5 h/ X# }$ Y" R1 `' _# o' y3 f! W8 `* D# P& h; e4 \
M e r g e S o r t ( Y,n); // 按y坐标排序: }" |" W- I# c7 N

; q9 K. D2 K6 h1 A// 创建临时数组
& ]7 b  A4 ~$ Q# t4 A9 J7 ?2 _5 g) s0 u( M
Point2 *Z = new Point2 [n];
- ~; ^9 L/ K+ w/ z+ b0 j# [0 O8 S) Z- @. o4 S/ F
// 寻找最近点对
; G; p8 l0 p8 R% m2 h  b8 n7 w9 L& u) e' k! a8 _
c l o s e ( X , Y, Z , 0 , n - 1 , a , b , d ) ;: ~6 A: U& Z' i; O- u
: U- y& p- c, S% f
// 删除数组并返回& q; Z% Q8 B+ r) R
& h' w" t: w' o2 I& D$ z
delete [] Y;
6 E. `: w1 Y$ X5 D  Y  B! m* [* I- ^; @" ^3 v% S' ?: d
delete [] Z;
. O% L5 u& v& y1 z1 M9 v# W/ R
) I& n/ Y" L( `) Wreturn true;
' x! ~. @* m! T, d& |1 _$ J1 O8 y  E$ D. ]( Y# v
}
0 {9 d. ]) r- e& Z# F! a4 E) ~; w- z6 p  r: P
程序1 4 - 11 计算最近点对
6 u! P1 `% Q. x/ p( `3 S" f! Z9 q1 M6 u8 w
void close(Point1 X[], Point2 Y[], Point2 Z[], int l, int r, Point1&amp; a, Point1&amp; b, float&amp; d): t, d; M- l" T$ @

: R6 }9 {* g; t& p{//X[l:r] 按x坐标排序
/ p: k$ X0 ]; l6 u: }
' R) u/ S+ J- R* I//Y[l:r] 按y坐标排序
$ p: Y+ `1 J, j& Z9 X1 X$ X
$ H; V) X; X( N+ `9 Oif (r-l == 1) {// 两个点
8 s. E7 Z' L" E' O3 `* S5 U9 \9 k
a = X[l];
# Q4 `& g1 Y- x4 r% A: s6 q- G5 j/ w( N
( X4 e; g. ?9 `4 zb = X[r];( t7 R; u) x3 s% w
5 K1 O# h5 f! ^& l0 N* ]
d = dist(X[l], X[r]);( A* F8 y3 r$ R/ i" m

3 K0 G, [+ Q  _: g5 dr e t u r n ; }
5 t% A# e# s) |4 V2 d+ L3 m+ G$ q4 `/ n  L$ I- ]- p, q. ]
if (r-l == 2) {// 三个点3 s! @  H+ C! @! g( W2 ^8 R! b) |

6 z) Z' ^" l7 a- ?* L// 计算所有点对之间的距离' o, f2 n& i1 f6 s* X5 I9 ~$ S! x
! t0 j7 n+ c7 J8 L4 W2 e
float d1 = dist(X[l], X[l+1]);
- H1 A4 v- A& P1 _) g8 ~; i7 u' Y2 D. N3 p0 V- ?
float d2 = dist(X[l+1], X[r]);
4 R" z, r. X4 ^, X: X0 q- Y0 U- {
float d3 = dist(X[l], X[r]);; t  F: s/ V+ S7 \( D
/ {+ Q1 [  `: Z3 r- g
// 寻找最近点对3 g' a) b/ b- g

& d* C7 i- p$ y5 ~- {' Gif (d1 &lt;= d2 &amp;&amp; d1 &lt;= d3) {' D1 E0 @9 Y' X, U

# c$ |0 Z( L) K5 K' Oa = X[l];
8 k% Z# s$ T* F8 E! B" r3 w
8 m8 ?8 M0 K, g& ]& ub = X[l+1];! P1 o- x' ~: c, `: u& f! Y
$ Y/ M1 d8 p8 @0 J( l6 {. e3 t
d = d1;7 n( x6 ]( O* ^2 O& a

6 D5 L% ^0 `# Jr e t u r n ; }
# I+ u, @8 E( A7 w. b
4 `! v+ G* t' ~# n3 Gif (d2 &lt;= d3) {a = X[l+1];
0 f4 z; L( \" E, Y5 m2 T- s
' [# Q9 k  B5 {b = X[r];
5 d4 ?5 e# [# r  w- X% x7 [4 `2 a* x: t# P% Z8 {; B8 n9 v
d = d2;}
. a3 B% z/ k- K) n9 W% S$ E* Y1 A
else {a = X[l];, G9 [2 z, ?# ~$ @8 C/ H: U
3 y2 H& e7 [& n9 x2 O
b = X[r];8 y1 X9 A" D; D2 h& N8 w8 P7 S
( K+ R1 ]2 v6 H# E7 p2 t
d = d3;}
: W% V* o$ k( R7 [" `9 z' C, _2 Z
6 @# d: |3 d: A+ h! l- _! K2 wr e t u r n ; }7 v- |8 H* r3 e& t) g

+ B& s* ]0 ^, H/ F) o. H9 n! Q+ ^/ /多于三个点，划分为两部分+ T8 n! t* p' @2 R: \

* o+ B0 m/ n" B- Q1 Rint m = (l+r)/2; // X[l:m] 在A中，余下的在B中# {; x2 c* e2 x$ T
' B3 F) R3 E8 n+ k& u
// 在Z[l:m] 和Z [ m + 1 : r ]中创建按y排序的表" y- C$ e$ R, A- V* C: J8 K1 R2 J

+ `( L7 [1 ^/ `, i- [int f = l, // Z[l:m]的游标
8 Z+ b5 z6 C6 X0 g# c- V! z: t) ]
g = m+1; // Z[m+1:r]的游标1 x: s9 y1 O( W8 `' T1 F

8 G4 G7 G, F# Y* b# P% Qfor (int i = l; i &lt;= r; i++). w" x& L: o$ S1 p7 z

& P9 I' s7 N9 i6 d- [; _. Aif (Y.p &gt; m) Z[g++] = Y;& i) n- ^& z" E! c

* j4 \$ H, O1 uelse Z[f++] = Y;
9 p' z% M- Y+ F$ t! O
# A) e7 n) U- A) M// 对以上两个部分进行求解# y0 ~, s. U- H1 {
9 y" B4 d) U5 f; O/ w" D
c l o s e ( X , Z , Y, l , m , a , b , d ) ;
3 ?6 R& F: n9 ^8 A+ d
. n0 F# I+ Y! J& U2 I: [8 S+ yfloat dr;# [( e( d" X+ J  I5 _0 I% M3 J( @
& a" e( ?  `" v/ M. R0 @
Point1 ar, br;3 }) ~# M, J( v
( f9 C: Q5 ]. F0 p7 o: B
c l o s e ( X , Z , Y, m + 1 , r, a r, b r, d r ) ;# s, A: e/ y4 e. `) ]

. q' w& [$ x9 b, |% q// (a,b) 是两者中较近的点对
4 S* f. O  K& G( C9 l8 D
- P) n# w& Z  J0 Y7 _" }if (dr &lt; d) {a = ar;
. z" M* w7 [: F+ O7 l  ?( X) p) }' {% \" l0 P
b = br;6 P, {/ {- O  o# n
/ a, i+ d/ ?+ K( ]
d = dr;}
8 w- F) t- ?3 B- ~1 p* h4 T9 K3 m$ |' |/ m$ H! e2 l, D6 h
M e r g e ( Z , Y,l,m,r);// 重构Y3 G. {3 J0 I2 `0 G) \0 p
: O. t  Y8 e: r1 E$ c
/ /距离小于d的点放入Z
/ H4 P! [- l" j5 G! _& G+ Q
5 B6 T  W* S: Z' p( yint k = l; // Z的游标
5 L1 P7 V+ b. R
  W% \8 w  e( ^$ e* Wfor (i = l; i &lt;= r; i++)
% `) l. p  I+ P% v" l( X( M! y. n$ p, B3 h
if (fabs(Y[m].x - Y.x) &lt; d) Z[k++] = Y;$ s5 a$ G0 J8 R- F

0 V. g- X8 n: ?- k# n// 通过检查Z [ l : k - 1 ]中的所有点对，寻找较近的点对
6 @) M# t6 ?% B$ i5 {# J/ k' t, {. X6 a% \# Z( B: Y) C' A
for (i = l; i &lt; k; i++){# P  t6 k$ `+ }

4 v' M3 |4 e" z# N  ?for (int j = i+1; j &lt; k &amp;&amp; Z[j].y - Z.y &lt; d;, i* g+ q) M3 T3 n5 N& g$ F
, y9 F, L7 G3 R+ F+ ?, W( z
j + + ) {
  b4 q: O0 G, y' h8 }" {8 w1 [) y: i1 m/ Z8 V% v1 @" k6 f
float dp = dist(Z, Z[j]);
: t7 d- k  A+ [  c' A6 t' o- W$ l- Q( W+ t# y( c" C2 B
if (dp &lt; d) {// 较近的点对
  u' L: D' r4 s2 U$ P* I
3 y5 F1 m) ~. }2 U& `- T& W% [d = dp;# l4 O0 L" R9 d9 {6 i# b

/ w! z9 n# z* ~a = X[Z.p];; Q2 s! l5 X- g3 I" _9 g! Q

+ j! N$ L" x$ j* r9 k3 Yb = X[Z[j].p];}2 V9 \# G. e' E. c4 X& Y% _5 s

8 K' Z- @0 S6 L7 S; k* p}
8 s7 c. a3 I4 N; ]# ?' ]& i, T3 }9 ?' t& m7 I% U
}" n6 M) z- q' K2 b9 a* `
2 i$ a/ i" R' P' C& ]. r
}0 ]0 _' c$ M. ?) L" p
6 O& g  X& |3 m( U) b" C) l' q' J% j
函数c l o s e（见程序1 4 - 11）用来确定X[1:r] 中的最近点对。假定这些点按x 坐标排序。在Y [ 1 : r ]中对这些点按y 坐标排序。Z[ 1 : r ]用来存放中间结果。找到最近点对以后，将在a, b中返回最近点对，在d 中返回距离，数组Y被恢复为输入状态。函数并未修改数组X。
# m4 ]; L- z. f& p6 C1 t: q' l+ G9 P
首先考察“小问题”，即少于四个点的点集。因为分割过程不会产生少于两点的数组，因此只需要处理两点和三点的情形。对于这两种情形，可以尝试所有的可能性。当点数超过三个时，通过计算m = ( 1 + r ) / 2把点集分为两组A和B，X [ 1 : m ]属于A，X [ m + 1 : r ]属于B。通过从左至右扫描Y中的点以及确定哪些点属于A，哪些点属于B，可以创建分别与A组和B组对应的，按y 坐标排序的Z [ 1 : m ]和Z [ m + 1 : r ]。此时Y和Z的角色互相交换，依次执行两个递归调用来获取A和B中的最近点对。在两次递归调用返回后，必须保证Z不发生改变，但对Y则无此要求。不过，仅Y [ l : r ]可能会发生改变。通过合并操作（见程序1 4 - 5）可以以Z [ 1 : r ]重构Y [ 1 : r ]。
) }- V# l9 x3 K
# E9 \: u) ?% ]/ j( h& Q" |为实现图1 4 - 1 6的策略，首先扫描Y [ 1 : r ]，并收集距分割线小于的点，将这些点存放在Z [ 1 : k - 1 ]中。可按如下两种方式来把RA中点p 与p 的比较区内的所有点进行配对：1) 与RB 中y 坐标≥p.y 的点配对；2) 与y 坐标≤p.y 的点配对。这可以通过将每个点Z [ i ]（1≤i &lt; k，不管该点是在RA+ @/ W/ f) [8 |6 n; d5 W

1 ?3 W. z  K2 k5 W0 |+ ?还是在RB中）与Z[j] 配对来实现，其中i＜j 且Z [ j ] . y - Z [ i ] . y＜ 。对每一个Z [ i ]，在2 × 区域内所检查的点如图1 4 - 1 7所示。由于在每个2 × 子区域内的点至少相距。因此每一个子区域中的点数不会超过四个，所以与Z [ i ]配对的点Z [ j ]最多有七个。
/ U# |' V! v* ^
3 c0 H' Z- N! U  w2 t! k& B2. 复杂性分析9 J( o' x4 B/ ^

6 b& t" Y- ^8 O令t (n) 代表处理n 个点时，函数close 所需要的时间。当n＜4时，t (n) 等于某个常数d。当n≥4时，需花费(n) 时间来完成以下工作：将点集划分为两个部分，两次递归调用后重构Y，淘汰距分割线很远的点，寻找更好的第三类点对。两次递归调用需分别耗时t (「n /2ù」和t (?n /2?).
" d7 o5 x5 P9 _
2 H2 I& h( j. w5 @. W这个递归式与归并排序的递归式完全一样，其结果为t (n) = (nl o gn)。另外，函数c l o s e s t还需耗时(nl o gn)来完成如下额外工作：对X进行排序，创建Y和Z，对Y进行排序。因此分而治之最近点对求解算法的时间复杂性为(nl o gn)。</P>



欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) Powered by Discuz! X2.5