专栏首页python读书笔记《python算法教程》Day10 - 平面最近点对问题平面最小点对问题介绍代码演示

《python算法教程》Day10 - 平面最近点对问题平面最小点对问题介绍代码演示

今天是《python算法教程》的第10篇读书笔记。笔记的主要内容是使用python实现求最小点对的时间复杂度为O(nlogn)的算法。

平面最小点对问题介绍

在几何学中,有一个基本问题:在一个平面的n个点中,求距离最近的两个点。 最直接的思路是遍历所有的点对,通过比较所有点对的距离找出距离最近的两点,即暴力算法。但是,这个思路的时间复杂度为O(n^2)。显然,这种算法的时间复杂度是不能接受的。 因此,是否可以考虑通过分治法的思路,将上述问题的解法的时间复杂度控制在O(nlog2n)?答案是可以的。具体的算法讲解可参考下述博文:

https://blog.csdn.net/lishuhuakai/article/details/9133961

但运用分治法求解上述问题时,需要注意一点,距离最小的两个点可能不在于同一个分组的点集中,而是分别来自于不同的点集中。

代码演示

暴力算法

#计算两点的距离
import math
def calDis(seq):
    dis=math.sqrt((seq[0][0]-seq[1][0])**2+(seq[0][1]-seq[1][1])**2)
    return dis

#暴力算法主体函数
def calDirect(seq):
    minDis=float('inf')
    pair=[]
    for i in range(len(seq)):
        for j in range(i+1,len(seq)):
            dis=calDis([seq[i],seq[j]])
            if dis <minDis:
                minDis=dis
                pair=[seq[i],seq[j]]
    return [pair,minDis]

分治法求解

#求出平面中距离最近的点对(若存在多对,仅需求出一对)
import random
import math

#计算两点的距离
def calDis(seq):
    dis=math.sqrt((seq[0][0]-seq[1][0])**2+(seq[0][1]-seq[1][1])**2)
    return dis

#生成器:生成横跨跨两个点集的候选点,由于点集是按纵坐标升序排序,right点集的点的纵坐标必定大于u的纵坐标,故只需检查纵坐标是否大于u[1]+dis,且只需最多检查right点集中纵坐标最小的6个点
def candidateDot(u,right,dis):
    cnt=0
    for v in right:
        cnt+=1
        if v[1]>u[1]+dis or cnt>3:
            break
        yield v

#求出横跨两个部分的点的最小距离
def combine(left,right,resMin):
    med_x=(left[-1][0]-right[0][0])/2
    dis=resMin[1]
    minDis=resMin[1]
    pair=resMin[0]
    for u in left:
        if u[0]<med_x-dis:
            continue
        for v in candidateDot(u,right,dis):
            dis=calDis([u,v])
            if dis<minDis:
                minDis=dis
                pair=[u,v]
    return [pair,minDis]


#分治求解
def divide(seq):
    #求序列元素数量
    n=len(seq)
    #按点的纵坐标升序排序
    seq=sorted(seq,key=lambda y:y[1])
    #递归开始进行
    if n<=1:
        return None,float('inf')
    elif n==2:
        return [seq,calDis(seq)]
    else:
        half=int(n/2)
        left=seq[:half]
        resLeft=divide(left)
        right=seq[half:]
        resRight=divide(right)
        #获取两集合中距离最短的点对
        if resLeft[1]<resRight[1]:
            resMin=combine(left,right,resLeft)
        else:
            resMin=combine(left,right,resRight)
        pair=resMin[0]
        minDis=resMin[1]
    return [pair,minDis]

    
seq=[(random.randint(0,100000),random.randint(0,1000000)) for x in range(100000)]
print(sorted(seq,key=lambda y:y[0]))
print("优化算法",divide(seq))

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 《python算法教程》Day9 - 快速排序法快速排序法简介代码展示

    这是《python算法教程》第9篇读书笔记,笔记的主要内容为快速排序法。 快速排序法简介 快速排序法运用分治法的方式,将需要排序的序列细分成小序列进行排序。 ...

    billyang916
  • 《算法图解》NOTE 4 快速排序法1.递归与分治法2.快速排序法的实现3.快速排序法的时间复杂度(用渐近表示法表示)

    billyang916
  • 《python算法教程》Day11 - 分治法求解平面凸包问题平面凸包问题简介分治法求解思路点与直线的位置判断代码示例

    这是《python算法教程》的第11篇读书笔记,笔记主要内容是使用分治法求解凸包。 平面凸包问题简介 在一个平面点集中,寻找点集最外层的点,由这些点所构成的凸多...

    billyang916
  • TSR:基于深度学习的超分辨率技术及应用

    本技术能够在图片 size 只有原来 25% 的情况下将图片还原到与原图的同等效果,在空间的应用可以节省用户 75% 的流量。

    QQ空间开发团队
  • 回顾:单细胞入门-读一篇scRNA-seq综述

    本来想看这篇文章 A general and flexible method for signal extraction from single-cell RN...

    生信技能树jimmy
  • JavaScript能做什么?

    JavaScript除了做前端开发,还能做什么? 很多朋友学习的第一门编程语言就是JavaScript,学习的过程中一定会思考这个问题:“JavaScript除...

    企鹅号小编
  • 【JS】308- 深入理解ESLint

    小沈是一个刚刚开始工作的前端实习生,第一次进行团队开发,难免有些紧张。在导师的安排下,拿到了项目的 git 权限,开始进行 clone。

    pingan8787
  • docker安装篇,第二篇 在Ubuntu18.04上开启RESTful API接口,HTTP与HTTPS接口访问

    本教程参考以下docker官方文档,如在使用本教程过程中存在问题,可翻阅原文官方文档: https://docs.docker.com/install/lin...

    cn華少
  • Docker Cheat Sheet

    “使用Docker,开发人员可以使用任何工具链以任何语言构建任何应用程序。”Dockerized“应用程序完全可移植,可以在任何地方运行 - 同事的OS X和W...

    iOSDevLog
  • 大部分程序员还不知道的 Servelt3 异步请求,原来这么简单?

    这是我们日常最常用同步请求模型,所有动作都交给同一个 Tomcat 线程处理,所有动作处理完成,线程才会被释放回线程池。

    andyxh

扫码关注云+社区

领取腾讯云代金券