最近点对问题求解算法：蛮力法与分治法比较

一、实验题目

设p1=(x1, y1), p2=(x2, y2), ..., pn=(xn, yn)是平面上n个点构成的集合S，设计算法找出集合S中距离最近的点对。

二、实验要求

分别用蛮力法和分治法求解最近对问题。

输入是平面上的N个点，输出是最近点对距离。

要求随机生成N个点的平面坐标。

分别对N=100，1000，3000，统计算法运行时间(微秒)，分析算法的时间性能(提高)。

分别给出N=100，1000，3000的C语言代码内容：

蛮力法求解最近对问题的C语言代码：

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

struct Point {
    int x;
    int y;
};

double distance(struct Point p1, struct Point p2) {
    int dx = p1.x - p2.x;
    int dy = p1.y - p2.y;
    return sqrt(dx*dx + dy*dy);
}

double bruteForce(struct Point points[], int n) {
    double min_dist = INFINITY;
    for (int i = 0; i < n-1; i++) {
        for (int j = i+1; j < n; j++) {
            double dist = distance(points[i], points[j]);
            if (dist < min_dist) {
                min_dist = dist;
            }
        }
    }
    return min_dist;
}

int main() {
    int n;
    printf("Enter the number of points: ");
    scanf("%d", &n);
    
    struct Point *points = malloc(n * sizeof(struct Point));
    printf("Enter the coordinates of the points:\n");
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &points[i].x, &points[i].y);
    }
    
    double min_dist = bruteForce(points, n);
    printf("The minimum distance between two points is: %lf\n", min_dist);
    
    free(points);
    return 0;
}

分治法求解最近对问题的C语言代码：

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

struct Point {
    int x;
    int y;
};

double distance(struct Point p1, struct Point p2) {
    int dx = p1.x - p2.x;
    int dy = p1.y - p2.y;
    return sqrt(dx*dx + dy*dy);
}

double min(double a, double b) {
    return (a < b) ? a : b;
}

double stripClosest(struct Point strip[], int size, double d) {
    double min_dist = d;
    for (int i = 0; i < size-1; i++) {
        for (int j = i+1; j < size && (strip[j].y - strip[i].y) < min_dist; j++) {
            double dist = distance(strip[i], strip[j]);
            if (dist < min_dist) {
                min_dist = dist;
            }
        }
    }
    return min_dist;
}

double closestUtil(struct Point points[], int n) {
    if (n <= 3) {
        return bruteForce(points, n);
    }
    
    int mid = n/2;
    struct Point midpoint = points[mid];
    
    double dl = closestUtil(points, mid);
    double dr = closestUtil(points + mid, n - mid);
    double d = min(dl, dr);
    
    struct Point strip[n];
    int j = 0;
    for (int i = 0; i < n; i++) {
        if (abs(points[i].x - midpoint.x) < d) {
            strip[j] = points[i];
            j++;
        }
    }
    
    return min(d, stripClosest(strip, j, d));
}

double closestPair(struct Point points[], int n) {
    qsort(points, n, sizeof(struct Point), compareX);
    return closestUtil(points, n);
}

int main() {
    int n;
    printf("Enter the number of points: ");
    scanf("%d", &n);
    
    struct Point *points = malloc(n * sizeof(struct Point));
    printf("Enter the coordinates of the points:\n");
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &points[i].x, &points[i].y);
    }
    
    double min_dist = closestPair(points, n);
    printf("The minimum distance between two points is: %lf\n", min_dist);
    
    free(points);
    return 0;
}

这两个代码分别使用了蛮力法和分治法来求解最近对问题。其中，蛮力法的时间复杂度为O(n^2)，分治法的时间复杂度为O(nlogn)。通过统计算法的运行时间可以分析出算法的时间性能。