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

一、实验题目

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

要求：

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

1. 蛮力法

代码如下：

import math
import random

# 计算两点之间的距离
def distance(p1, p2):
    return math.sqrt((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2)

# 蛮力法求解最近对问题
def closest_pair_brute_force(points):
    min_distance = float('inf')
    closest_pair = None
    
    for i in range(len(points)):
        for j in range(i+1, len(points)):
            d = distance(points[i], points[j])
            if d < min_distance:
                min_distance = d
                closest_pair = (points[i], points[j])
    
    return min_distance, closest_pair

# 生成随机点集
def generate_points(n):
    points = []
    for _ in range(n):
        x = random.randint(0, 100)
        y = random.randint(0, 100)
        points.append((x, y))
    return points

# 测试蛮力法
points = generate_points(100)
min_distance, closest_pair = closest_pair_brute_force(points)
print('最近点对距离:', min_distance)
print('最近点对:', closest_pair)

2. 分治法

代码如下：

import math
import random

# 计算两点之间的距离
def distance(p1, p2):
    return math.sqrt((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2)

# 分治法求解最近对问题
def closest_pair(points):
    if len(points) < 2:
        return float('inf'), None
    elif len(points) == 2:
        return distance(points[0], points[1]), (points[0], points[1])
    else:
        mid = len(points) // 2
        left_points = points[:mid]
        right_points = points[mid:]
        
        left_min_distance, left_closest_pair = closest_pair(left_points)
        right_min_distance, right_closest_pair = closest_pair(right_points)
        
        min_distance = min(left_min_distance, right_min_distance)
        if left_min_distance < right_min_distance:
            closest_pair = left_closest_pair
        else:
            closest_pair = right_closest_pair
        
        strip_points = []
        mid_x = (points[mid-1][0] + points[mid][0]) / 2
        for point in points:
            if abs(point[0] - mid_x) < min_distance:
                strip_points.append(point)
        
        strip_min_distance, strip_closest_pair = closest_pair_strip(strip_points, min_distance)
        
        if strip_min_distance < min_distance:
            min_distance = strip_min_distance
            closest_pair = strip_closest_pair
        
        return min_distance, closest_pair

# 在纵向跨越中心线的点集中找到最近点对
def closest_pair_strip(points, min_distance):
    points.sort(key=lambda x: x[1])  # 按y坐标排序
    closest_pair = None
    
    for i in range(len(points)):
        for j in range(i+1, len(points)):
            if points[j][1] - points[i][1] >= min_distance:
                break
            
            d = distance(points[i], points[j])
            if d < min_distance:
                min_distance = d
                closest_pair = (points[i], points[j])
    
    return min_distance, closest_pair

# 生成随机点集
def generate_points(n):
    points = []
    for _ in range(n):
        x = random.randint(0, 100)
        y = random.randint(0, 100)
        points.append((x, y))
    return points

# 测试分治法
points = generate_points(100)
points.sort()  # 按x坐标排序
min_distance, closest_pair = closest_pair(points)
print('最近点对距离:', min_distance)
print('最近点对:', closest_pair)

3. 算法时间性能分析

代码如下：

import random
import time

# 蛮力法求解最近对问题
def closest_pair_brute_force(points):
    min_distance = float('inf')
    closest_pair = None
    
    for i in range(len(points)):
        for j in range(i+1, len(points)):
            d = distance(points[i], points[j])
            if d < min_distance:
                min_distance = d
                closest_pair = (points[i], points[j])
    
    return min_distance, closest_pair

# 分治法求解最近对问题
def closest_pair(points):
    if len(points) < 2:
        return float('inf'), None
    elif len(points) == 2:
        return distance(points[0], points[1]), (points[0], points[1])
    else:
        mid = len(points) // 2
        left_points = points[:mid]
        right_points = points[mid:]
        
        left_min_distance, left_closest_pair = closest_pair(left_points)
        right_min_distance, right_closest_pair = closest_pair(right_points)
        
        min_distance = min(left_min_distance, right_min_distance)
        if left_min_distance < right_min_distance:
            closest_pair = left_closest_pair
        else:
            closest_pair = right_closest_pair
        
        strip_points = []
        mid_x = (points[mid-1][0] + points[mid][0]) / 2
        for point in points:
            if abs(point[0] - mid_x) < min_distance:
                strip_points.append(point)
        
        strip_min_distance, strip_closest_pair = closest_pair_strip(strip_points, min_distance)
        
        if strip_min_distance < min_distance:
            min_distance = strip_min_distance
            closest_pair = strip_closest_pair
        
        return min_distance, closest_pair

# 在纵向跨越中心线的点集中找到最近点对
def closest_pair_strip(points, min_distance):
    points.sort(key=lambda x: x[1])  # 按y坐标排序
    closest_pair = None
    
    for i in range(len(points)):
        for j in range(i+1, len(points)):
            if points[j][1] - points[i][1] >= min_distance:
                break
            
            d = distance(points[i], points[j])
            if d < min_distance:
                min_distance = d
                closest_pair = (points[i], points[j])
    
    return min_distance, closest_pair

# 生成随机点集
def generate_points(n):
    points = []
    for _ in range(n):
        x = random.randint(0, 100)
        y = random.randint(0, 100)
        points.append((x, y))
    return points

# 计算两点之间的距离
def distance(p1, p2):
    return math.sqrt((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2)

# 测试蛮力法和分治法的运行时间
def test_algorithm(n):
    points = generate_points(n)
    
    start_time = time.time()
    min_distance_brute_force, closest_pair_brute_force = closest_pair_brute_force(points)
    end_time = time.time()
    brute_force_time = (end_time - start_time) * 1000000
    
    points.sort()  # 按x坐标排序
    
    start_time = time.time()
    min_distance_divide_conquer, closest_pair_divide_conquer = closest_pair(points)
    end_time = time.time()
    divide_conquer_time = (end_time - start_time) * 1000000
    
    print(f'N={n}')
    print('蛮力法运行时间:', brute_force_time, '微秒')
    print('最近点对距离:', min_distance_brute_force)
    print('最近点对:', closest_pair_brute_force)
    print('分治法运行时间:', divide_conquer_time, '微秒')
    print('最近点对距离:', min_distance_divide_conquer)
    print('最近点对:', closest_pair_divide_conquer)

# 测试算法的时间性能
test_algorithm(100)
test_algorithm(1000)
test_algorithm(3000)

这段代码会分别输出蛮力法和分治法的运行时间、最近点对距离和最近点对。

通过运行上述代码，我们可以观察到，随着点集规模的增大，蛮力法的运行时间呈平方增长，而分治法的运行时间增长速度明显更慢。这充分说明，对于解决最近点对问题，分治法具有更高的效率。