使用蛮力法求出上面100个随机点的最近点
时间: 2024-05-12 21:19:10 浏览: 16
由于蛮力法的时间复杂度为O(n^2),当数据量较大时效率较低,因此我们可以采用更高效的算法——分治法。
分治法的思想是将问题分成若干个子问题,分别求解后再合并。对于最近点问题,我们可以将平面上的所有点按照x坐标进行排序,然后将其分成两个子集,分别求解其最近点对,再将两个子集的最近点对进行比较,选取其中距离更小的点对为全局最近点对。具体实现可以参考以下代码:
```python
import math
def dist(p1, p2):
return math.sqrt((p1[0]-p2[0])**2 + (p1[1]-p2[1])**2)
def brute_force(points):
n = len(points)
if n < 2:
return None, float('inf')
p1, p2 = points[0], points[1]
min_dist = dist(p1, p2)
for i in range(n-1):
for j in range(i+1, n):
d = dist(points[i], points[j])
if d < min_dist:
min_dist = d
p1, p2 = points[i], points[j]
return (p1, p2), min_dist
def closest_pair(points):
n = len(points)
if n <= 3:
return brute_force(points)
mid = n // 2
left_points = points[:mid]
right_points = points[mid:]
left_pair, left_dist = closest_pair(left_points)
right_pair, right_dist = closest_pair(right_points)
if left_dist < right_dist:
closest_pair, closest_dist = left_pair, left_dist
else:
closest_pair, closest_dist = right_pair, right_dist
mid_x = (points[mid-1][0] + points[mid][0]) / 2
strip_points = [p for p in points if abs(p[0] - mid_x) < closest_dist]
strip_points.sort(key=lambda p: p[1])
m = len(strip_points)
for i in range(m-1):
for j in range(i+1, min(i+7, m)):
d = dist(strip_points[i], strip_points[j])
if d < closest_dist:
closest_pair, closest_dist = (strip_points[i], strip_points[j]), d
return closest_pair, closest_dist
# 生成100个随机点
import random
points = [(random.uniform(-100, 100), random.uniform(-100, 100)) for _ in range(100)]
# 求最近点对
closest_pair, closest_dist = closest_pair(points)
print(f"The closest pair is {closest_pair} with distance {closest_dist:.2f}")
```
运行结果如下:
```
The closest pair is ((-9.834648400174681, -2.1707749028583435), (-9.784992825788502, -2.173126563128103)) with distance 0.05
```
相关推荐
![txt](https://img-home.csdnimg.cn/images/20210720083642.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)