最近点对问题算法比较 - 蛮力法与分治法 - 常规

一、实验题目

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

要求：

分别用蛮力法和分治法求解最近对问题
输入是平面上的N个点，输出是最近点对距离。
要求随机生成N个点的平面坐标。
分别对N=100，1000，3000，给出相应的C语言代码，统计算法运行时间(微秒)，分析算法的时间性能(提高)。

二、算法实现

1. 蛮力法

算法思路：

初始化最近点对距离为无穷大。
对于集合S中的每对点pi和pj，计算它们之间的距离dist(pi, pj)。
如果dist(pi, pj)小于当前最近点对距离，更新最近点对距离为dist(pi, pj)。
返回最近点对距离作为输出结果。

代码如下：

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

typedef struct Point {
    int x;
    int y;
} Point;

double distance(Point p1, Point p2) {
    return sqrt(pow(p1.x - p2.x, 2) + pow(p1.y - p2.y, 2));
}

double closestPairBruteForce(Point points[], int n) {
    double minDistance = INFINITY;

    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            double dist = distance(points[i], points[j]);
            if (dist < minDistance) {
                minDistance = dist;
            }
        }
    }

    return minDistance;
}

int main() {
    int n = 100;  // 可根据需要修改n的值

    Point points[n];

    // 随机生成n个点的坐标
    srand(time(NULL));
    for (int i = 0; i < n; i++) {
        points[i].x = rand() % 100;
        points[i].y = rand() % 100;
    }

    clock_t start = clock();
    double minDistance = closestPairBruteForce(points, n);
    clock_t end = clock();
    double time_taken = ((double)(end - start)) / CLOCKS_PER_SEC * 1000000;

    printf("最近点对距离: %lf\n", minDistance);
    printf("运行时间: %lf 微秒\n", time_taken);

    return 0;
}

2. 分治法

算法思路：

对输入点集按照x坐标进行排序。
如果点集中的点个数小于等于3，则使用蛮力法求解最近点对距离并返回。
将点集平分为左右两个子集，分别求解左右子集中的最近点对距离（递归调用）。
计算左右子集中最近点对距离的最小值。
在宽度为2d的带状区域内，找到距离中线最近的点对（最多6个点）。
计算带状区域内最近点对距离的最小值。
返回左右子集和带状区域内最近点对距离的最小值作为输出结果。

代码如下：

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

typedef struct Point {
    int x;
    int y;
} Point;

int compareX(const void* a, const void* b) {
    Point* p1 = (Point*)a;
    Point* p2 = (Point*)b;
    return (p1->x - p2->x);
}

int compareY(const void* a, const void* b) {
    Point* p1 = (Point*)a;
    Point* p2 = (Point*)b;
    return (p1->y - p2->y);
}

double distance(Point p1, Point p2) {
    return sqrt(pow(p1.x - p2.x, 2) + pow(p1.y - p2.y, 2));
}

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

double stripClosest(Point strip[], int size, double d) {
    double minDistance = d;

    qsort(strip, size, sizeof(Point), compareY);

    for (int i = 0; i < size; i++) {
        for (int j = i + 1; j < size && (strip[j].y - strip[i].y) < minDistance; j++) {
            double dist = distance(strip[i], strip[j]);
            if (dist < minDistance) {
                minDistance = dist;
            }
        }
    }

    return minDistance;
}

double closestPairDivideConquer(Point points[], int n) {
    if (n <= 3) {
        return closestPairBruteForce(points, n);
    }

    int mid = n / 2;
    Point midPoint = points[mid];

    double dl = closestPairDivideConquer(points, mid);
    double dr = closestPairDivideConquer(points + mid, n - mid);
    double d = min(dl, dr);

    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));
}

int main() {
    int n = 100;  // 可根据需要修改n的值

    Point points[n];

    // 随机生成n个点的坐标
    srand(time(NULL));
    for (int i = 0; i < n; i++) {
        points[i].x = rand() % 100;
        points[i].y = rand() % 100;
    }

    qsort(points, n, sizeof(Point), compareX);

    clock_t start = clock();
    double minDistance = closestPairDivideConquer(points, n);
    clock_t end = clock();
    double time_taken = ((double)(end - start)) / CLOCKS_PER_SEC * 1000000;

    printf("最近点对距离: %lf\n", minDistance);
    printf("运行时间: %lf 微秒\n", time_taken);

    return 0;
}

三、时间复杂度分析

蛮力法的时间复杂度为O(n^2)，在点数较少时可以接受，但对于点数较多的情况下效率较低。
分治法的时间复杂度为O(nlogn)，在点数较多时具有较高的效率。由于分治法在递归调用时需要进行排序操作，因此整体的时间复杂度为O(nlogn)。

四、总结

本文介绍了两种求解最近点对问题的算法：蛮力法和分治法。蛮力法简单易懂，但在点数较多时效率较低；分治法的时间复杂度更低，适用于处理大量数据。选择合适的算法取决于实际问题的规模和对效率的要求。