算法上机实验----最近点对

发表于 | 分类于
分治法求最近点对问题

定义数据结构

1
2
3
4
5
6
7
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
typedef struct _point {
    float x,y;
}Point;

数据结构的基本操作

创建+打印

1
2
3
4
5
6
7
8
9
10
11
12
Point newPoint(int x, int y) {
    Point p;
    p.x = x;
    p.y = y;
    return p;
}
void print_points(Point* points, int n) {
    for (int i = 0; i < n; i++) {
        printf("x: %.2f, y:%.2f\n",points[i].x, points[i].y);
    }
}

排序用的比较函数

1
2
3
4
5
6
7
8
9
10
11
int point_cmp_by_x(const void * a, const void *b) {
    Point* p1 = (Point*)a;
    Point* p2 = (Point*)b;
    if (p1->x == p2->x) return p1->y-p2->y;
    return p1->x-p2->x;
}
int point_cmp_by_y(const void * a, const void *b) {
    Point* p1 = (Point*)a;
    Point* p2 = (Point*)b;
    return p1->y-p2->y;
}

计算点对距离

1
2
3
float point_distance(Point p1, Point p2) {
    return sqrt(pow(p1.x-p2.x, 2) + pow(p1.y-p2.y, 2));
}

暴力求解法

每两个点计算一次距离取最短的。

1
2
3
4
5
6
7
8
9
10
11
float find_nearest_point(Point* points, int n) {
    float min_dis = 10000;
    if (n == 2) return point_distance(points[0], points[1]);
    for (int i = 0; i < n; i++) {
        for (int j = i+1; j < n; j++) {
            float dis = point_distance(points[i], points[j]);
            if (dis < min_dis) { min_dis = dis;}
        }
    }
    return min_dis;
}

递归求解法

主要思路：将点对按x排好序以后，分成两部分，递归找出左右两边最短的距离，然后再找出跟中线距离在递归找出的最小距离以内的左右两部分点，然后计算这些点对的距离。如果更短，更新最短距离。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
float find_nearest_point_recursive(Point* ps, int l, int r) {
    if (r-l+1 <= 3) {
        return find_nearest_point(ps+l, r-l+1);
    } else {
        int mid = (l+r)/2;
        float t1 = find_nearest_point_recursive(ps, l, mid);
        float t2 = find_nearest_point_recursive(ps, mid+1, r);
        float tmin = t1<t2?t1:t2;
        int ll = 0, lr = 0;
        Point* L = (Point*)malloc(sizeof(Point)*(mid+1-l));
        Point* R = (Point*)malloc(sizeof(Point)*(r-mid+1));
        for (int i = l; i <= mid; i++) {
            if (ps[i].x >= ps[mid].x-tmin) {
                L[ll++] = ps[i];
            }
        }
        for (int i = mid+1; i <= r; i++) {
            if (ps[i].x <= ps[mid].x+tmin) {
                R[lr++] = ps[i];
            }
        }
        
        float ttmin = tmin;
        for (int i = 0; i < ll; i++) {
            for (int j = 0; j < lr; j++) {
                float dis = point_distance(L[i], R[j]);
                if (dis < ttmin)
                    ttmin = dis;
            }
        }
        free(L);free(R);
        return ttmin;
    }
}

主函数

生成点对

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
double d_rand() {
    return 1.0*rand()/(double)(RAND_MAX);
}
int main() {
    int n = 40;
    int range = 60;
    Point points[100];
    for (int i = 0; i < n ; i++) {
        points[i] = newPoint( d_rand()*range, d_rand()*range);
    }
    
    qsort(points, n, sizeof(Point), point_cmp_by_x);
    print_points(points,n);
    printf("%f\n", find_nearest_point(points, n));
    printf("%f\n", find_nearest_point_recursive(points, 0, n-1));
    
    return 0;
}