每周学点大数据 | No.16平面图直径

No.16期

平面图直径

小可：好的，关于图的基本内容我听懂了。

Mr. 王：很好，图能够对很多现实问题进行数学抽象，方便通过计算机的手段进行抽象。而平面图指的就是可以铺在平面上的图，且这个图铺在平面上时仅能在顶点处相交，边与边之间不能相交。我们要求出平面图的直径。

小可：图的直径，就是图中最远的两个点间的最短距离吧。

Mr. 王：是的。在这个问题中，我们已知的是任意两点间的最短路径，要求的是图的直径。你来说说这个问题的输入输出，再来分析一下问题的输入规模。

小可：

输入：有m个顶点的平面图，任意两点之间的距离存储在矩阵D中，即点i到点j的距离为Di。

输出：最大的Dij也就是图的直径。

一共有m个顶点，每两个顶点间都有一个最短距离，所以输入数据一共有m2个。

Mr. 王：很好，我们就设m2=n，同时简化一下这个问题，这个图满足这样的要求，即点与点之间的距离是对称的，而且满足三角不等式。

小可：这就像现实中的双向公路一样，A地到B地的距离和B地到A地的距离是一致的，三角形的两边之和大于第三边，嗯，这样的算法也是很朴素的。不过我觉得这个问题只要扫描一次整个数组，看看哪个值最大不就可以了吗？

Mr. 王：这样的确可以得到正确答案，不过对于n来说它是线性时间的，可是我们要求的时间复杂度是亚线性的o(n)。

小可疑惑地说：如果连所有的数据都不能遍历一次，万一没有遍历到的数据就是最大的，那岂不是造成了错误的结果？

Mr. 王：前面我们提到过，规定的时间界限比较苛刻，我们无法在规定的时间内得到精确解，有的时候不得不牺牲一些精度，通过近似算法给出一个近似解，这个近似解“差不多”是我们可以接受的就好。但是非常重要的一点是，我们一定要知道这个近似结果“差多少”。

我们先来看看这个算法：

（1）任意选择（k ≤m）。

（2）选择使得Dkl最大的l。

（3）输出Dkl。

小可思索了一下，说：这个结果还真是差不少啊。

Mr. 王笑着说：那我们就来看看这个结果究竟“差多少”。在这个例子中，我们试着求出算法得出的值和精确值的比是多少。

首先，Dij ≤Dik + Dkj，这是三角不等式的结论。又有Dik + Dkj ≤Dkl + Dkj = 2Dkj，这是由算法的第2步决定的，每个Dkx都要比Dkl小。于是，Dij≤2Dkj，因而近似比为2。也就是说，即使在最坏的情况下，也不会小于最优解的1/2。那么时间复杂度是多少呢？

小可：输入一共有n个距离，而我们只访问了数组中的一行，也就是m个数据。又因为n=m2，所以复杂度是O(m)，也就是

它的确是一个亚线性算法。

Mr. 王：很好，我们来总结一下关于近似算法的内容。近似算法是一类主要求解最优化问题的算法，但近似算法给出的不是最优解，而是近似最优解，不过其效率要远远高于求出精确解的算法，这才是提出近似算法的意义所在。

但是我们一定要知道，近似解和最优解究竟相差多少。一般来说，有3种衡量办法：近似比、相对误差和(1+ε)-近似。

其中最常用的是近似比（Ratio Bound），近似比是这样定义的：

如果近似算法A 具有近似比p(n)的话，那么满足

其中n是输入规模的大小，C是近似解的代价，C*是最优解的代价。

小可：那为什么要取两种比的较大值呢？

Mr. 王：因为我们求解的最优化问题不只包含最大化问题，还有最小化问题。对于最大化问题，C*比C小；而对于最小化问题，C比C*要大。所以这样定义才能覆盖两种问题。可以看出，近似比是一个大于1的值，而且其越大，说明这个算法越坏，或者说与最优解差得越远。

小可：那如果近似比为1，得到的就是精确解了吗？

Mr. 王：是的。现在简单介绍一下相对误差。相对误差就是对于任意输入，有|C-C*|/C*，其中C是近似解的代价，C*是最优解的代价；而如果一个近似算法满足|C-C*|/C*≤ε(n)，那么其相对误差界为ε(n)。

内容来源：灯塔大数据