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)。
内容来源:灯塔大数据