4.8 最近对问题

最近对问题

1 最近对问题 暴力求解

问题描述

• 给定平面上n个点。找其中的一对点。使得在n个点组成的所有点对中，该点对之间的距离最小。

问题分析

• 找出一个包含n个点的集合中距离最近的两个点。
• 题直观的解决方法便是Brute Force(暴力求解)。时间复杂度为O（n^2）

选择策略

• 分别计算每一点对之间的距离，然后从中找出距离最小的那一对。为了避免同一点对计算两次，可以只考虑i<j的点对(Pi, Pj)

算法设计

• 算法 bruteForceClosesPoints(P)

//蛮力法求解平面中距离最近的两点
//输入：一个n(n≥2)个点的列表P，P1=(x1, y1)，…，Pn=(xn, yn)
//输出：两个最近点的下标
dmin←∞
for i←0 to n-2 do
  for j←i+1 to n-1 do
    d←(xi-xj)2+(yi-yj)2
    if d<dmin
        dmin←d; index1←i; index2←j;
return index1,index2

正确性证明

算法分析

$O(n^2)$

程序设计

2 最近对问题——分治法

参考文献

• https://blog.csdn.net/sinat_35678407/article/details/82874216
• https://zhuanlan.zhihu.com/p/74905629
• http://www.360doc.com/content/19/0303/18/32937624_818850914.shtml

算法设计

正确性证明

算法分析

算法实现