一、問題描述
設一組點
，其中每個
點由其坐标
辨別，并且它們的順序是
。
目标是找到：
where:
二、蠻力法求解
解決問題的基本算法是周遊每對點并保持找到的最小距離 S。 最後，将傳回找到的最小距離。
僞代碼：
ALGORITHM S = BASIC (C = {p₁, p₂,…, pn}: Set of points)
S = Infinity
For each i from 1 to n-1:
For each j from i + 1 to n:
If (d (pi, pj) <S)
S = d (pi, pj)
End-If
End-For
End-For
Return S
三、分治法求解
算法設計：
1. 将問題劃分為子問題：
-原始問題 P = C 被分成 k = 2 個子問題 P1、P2，分别求解，進而産生 P1 的解 S1 和 P2 的 S2。--問題 P 被分成兩半， 假設 c 是集合 C 中的中心點，我們建立問題 P1 = {p1, p2,..., pc-1} 和問題P2 = {pc, pc + 1,..., pn }。是以， | P1 | 和 | P2 | 的大小大緻相同，問題C與原問題P具有相同的性質，它們是獨立的，可以單獨解決。 由于點是按 X 坐标排序的，我們可以将 P1 稱為“左側部分”，将 P2 稱為“右側部分”。
2. 基本情況的存在：
-當集合中的點數為 | P | <= 3 時，我們将停止除法。 在這種情況下，我們用基本算法解決。
3.合并子問題：
-S1 是子問題 P1 的點的最小距離，S2 是子問題 P2 的點的最小距離。 将 P1 的解 S1 和 P2 的 S2 結合起來，我們可以認為 S = min {S1, S2}。 但是，還需要考慮最近的點是 P1 中的一個，P2 中的另一個。 是以，我們将選擇 P1 的 X 坐标中距離中心為 min {S1, S2} 的點，以及 P2 在其 X 坐标系中距離中心為 min {S1, S2} 的點。 X 坐标，将左側選中的點與右側選中的點進行比較。
僞代碼：
ALGORITHM S = DC (C: Set of points ordered by their x coordinate)
if |C| <= 3 then:
Return S = BASIC (C)
else:
p_c ← Center point of C
P1 ← Points of C to p_c (not included)
P2 ← Points of C from p_c to n
S1 ← DC (P1)
S2 ← DC (P2)
S ← COMBINE (p_c, P1, S1, P2, S2)
Return S
End-if
ALGORITHM S = COMBINE (p_c: Central point of the p
P1: Subproblem of P (left part)
S1: Solution of P1,
P2: Subproblem of P (right part)
S2: Solution of P2):
PARTIAL = min {S1, S2}
S = PARTIAL
left←index the point of P1 farthest from p_c with d_x (p_left, pc) <= PARTIAL
right←index the point of P2 farthest from p_c with d_x (p_right, pc) <= PARTIAL
For each point p_i in P1 with i> = left:
For each point p_j in P2 with j <= right:
If d(p_i, p_j) < S:
S = d(p_i, p_j)
End-If
End-For
End-For
Return S
四、實驗代碼（部分代碼）
// 表示二維點的結構
typedef struct {
float x, y;
} Point;
//
// BASIC SOLUTION
//
/*
Basic algorithm: 将所有點互相比較。結果傳回點數
*/
float BASICO(const Point *cPoints, const int first, const int last) {
float S = -1; // 最近點的距離。初始化為 -1 表示無窮大
float dist; // 目前點的距離
for (int i = first; i < last; i++) {
for (int j = i+1; j < last; j++) {
// 計算 cPoints [i] 和 cPoints [j] 之間的距離
dist = distance(cPoints[i], cPoints[j]);
if (S == -1 || dist < S) {
S= dist; // 更新最近的點
}
}
}
// 傳回結果
return S;
}
//
// DC SOLUTION
//
float Merge(const Point *cPoints, const int first, const int center, const int last, const float S1, const float S2) {
const float partial= (S1 < S2)? S1:S2;
int centerLeft, centerRight; // 合并的中心位置
float distAux; // 比較的點的距離
float S; // 傳回的結果
S= partial; // 初始化結果
// 合并中央部分
// 搜尋問題 P1 在最右邊的點（左邊部分）
centerLeft = center;
distAux = 0;
do {
centerLeft--;
if (centerLeft >= first) {
distAux= distanceX(cPoints[center], cPoints[centerLeft]);
}
} while (centerLeft > first && distAux < partial);
// 搜尋問題 P2 在最左邊的點（右邊部分）
centerRight = center-1;
distAux= 0;
do {
centerRight++;
if (centerRight < last) {
distAux= distanceX(cPoints[center], cPoints[centerRight]);
}
} while (centerRight < last && distAux < partial);
if (centerRight < last) centerRight++;
// 在中央部分找到最小距離
for (int i = centerLeft; i < center; i++) {
for (int j = center; j < centerRight; j++) {
distAux = distance(cPoints[i], cPoints[j]);
if (S > distAux){
S = distAux;
}
}
}
return S;
}
/*
algorithm DC: 将所有的點分為 2
*/
float DC(const Point *cPoints, const int first, const int last) {
int center;
float S1, S2, S;
// 基本情況檢查：資料包含 2 或 3 個點
if (last - first <= 3) {
S = BASIC(cPoints, first, last);
} else {
center = (first + last) / 2;
S1= DC(cPoints, first, center);
S2= DC(cPoints, center, last);
S= Merge(cPoints, first, center, last, S1, S2);
}
return S;
}
float distance(const Point pi, const Point pj) {
float dx, dy;
dx = (pi.x - pj.x)*(pi.x - pj.x);
dy = (pi.y - pj.y)*(pi.y - pj.y);
return sqrt(dx + dy);
}
float distanceX(const Point pi, const Point pj) {
float dx, dy;
dx = (pi.x - pj.x)*(pi.x - pj.x);
return sqrt(dx);
}
完整版：https://download.csdn.net/download/weixin_47154327/19835120