分治算法之最短点对问题

通过分治算法解决最短点对问题是每一个计算机院合格的学生都应该掌握的基础问题,其中分治的思想也是算法领域中经常用到的基本思想之一。接下来我们通过一道题来理解掌握分治法的思想。

问题

描述

众所周知,paulzhou的数学不太好。现在他有一个问题,希望你帮他解答:在二维平面上给出一些整数点,希望在这些点中找出两个距离最近的点,并且输出这两个点的距离。

输入

第1行输入T(1≤T≤100),代表有T组数据。

接下来的T行输入,每行包含一组测试数据。输入数据为一系列坐标。数据保证为严格的“(x1, y1) (x2, y2) (x3, y3) … ”格式。输入保证点的数量不超过100个。坐标均为非负整数,且不会超过100,输入字符串长度不会超过1000。

输出

每组测试数据输出一行,仅包含一个浮点数,代表最近的距离,输出保留四位小数(无需四舍五入)。

示例输入

示例输出

分治解法

通俗解释

那什么到底是分治算法呢?分治算法的思想是将原问题分解为几个规模较小但类似于原问题的子问题,递归地求解这些子问题,然后再集合这些子问题的解来建立原问题的解。

分治模式在递归时有三个步骤:

    将问题分解成若干个子问题,这些子问题是原问题的规模较小的情况。
    解决这些子问题,递归地求解各个子问题,如果这些子问题规模已经足够小,就直接求解这些子问题,否则继续将这些问题分解成为子问题。
    合并这些子问题的解

该题解法

关于这道题分治思想的运用,就是将大的点对组分成两个部分,分别求这个点组的距离最短的两个点的距离,也就是将这个大问题分为了两个相似的小问题。为了能够平均分配像个子点组,我们按照x坐标的大小顺序排列点组,以中位数为界分成了两个点对组,分别求两个点对组最短距离。一直这么递归下去,直到该点组只有两个点或者一个点:当只有两个点的时候,直接返回这两个点的距离,而当只有一个点的时候,返回无穷大,然后比较这两个点对组最短距离,取最小的为最短距离。

将点组分为两个大小类似的点组,并不断递归,直到组只有一个点或者两个点

但是这样还是有一个问题,当某个点组的最点点队在A组,另外一个点在B组的时候,该怎么取到最短点呢?一种办法是遍历A组的点和B组的点,然后计算出最短的点,但是这样的效率太低了。我们需要一个能有效减少遍历数量的方法。

所以为了简化我们的计算,并且我们只需要比较在AB组分界处的点,我们已经知道了目前相对而言的“最短距离”,那么潜在的最短距离的两个点只会存在于\(x \in \left [ \alpha – \Delta, \alpha + \Delta \right ]\)。(其中\(\alpha\)为之前取的中位数点的x坐标,\(\Delta\)则为当前已知的最短两个点的距离)这是因为合并的目的是防止最短的距离的两个点在A组一个在B组,倘若存在,那么这两个点到分界线的距离一定小于当前的最短距离\(\Delta\)所以我们只需要检测\(x \in \left [ \alpha – \Delta, \alpha + \Delta \right ]\)中的点。同样的道理,对于某一个特定的点\(A\left (x_{0}, y_{0} \right )\)他的潜在最短对应点一定存在于\(y \in \left [ y_{0} – \Delta, y_{0} + \Delta \right ]\),考虑到最极端的情况,一个点最多只需要计算6次判断是否存在更短的长度。通过这样的方式能够将两个子组合并起来。

复杂度计算和比较

暴力破解算法

对于一个有n个元素的点组,要判断最短点的算法需要计算每一个可能的线的长度,总共需要计算\(\frac{n^2}{2} – \frac{n}{2}\)次距离,因此最后的时间复杂度是\[O\left ( n^{2} \right )\]

分治算法

考虑到最极端的情况,若有一个n个元素的点组,获得他的最短距离为\(T\left ( n \right )\),假若最后分到的每一个组的2个点的组。首先计算中位数的时间复杂度是\(O\left ( n \log{n} \right )\) (排序算法的时间复杂度是\(O\left ( n \log_{2}{n} \right )\),这里应该进行预排序优化,从而之后的分治算法中就可以不再需要排序了。)分组的时间复杂度是\(2O\left ( \frac{n}{2} \right )\)。计算这两个子组的时间为\(2T\left ( \frac{n}{2} \right )\)合并两个子组的时间复杂度为\(O\left ( n \right )\),显而易见,优化后的时间复杂度为\[O\left ( n \log_{2}{n} \right )\]

两种算法对比

拿到这种题,头脑里首先闪现的当然就是暴力破解,也就是通过暴力计算所有距离,得到最小的距离。这种算法简单可行,是一个人都能想出来。但是缺点就是当数据量特别特别大的时候,这种算法耗费的时间会呈几何倍数增长时间。显而易见,从图中能看见两者时间消耗的对比。

两种算法的时间复杂曲线图

我的解法