亚线性算法-平面图直径近似算法

Posted by PowderHan on February 3, 2019 已经被偷看过次啦QAQ

http://sc1.111ttt.cn/2016/1/11/09/204090932285.mp3



时间亚线性算法

平面图直径近似算法

问题描述

  • 输入: $n$个顶点的平面图,任意两点之间的距离存储在矩阵$D$中,即点$i$到点$j$的距离为$D_{ij}$

    输入大小是$m=n^2$
    最大的$D_{ij}$是图的直径
    点之间的距离对称且满足三角不等式

  • 输出:该图的直径和距离最大的$D_{ij}$
  • 要求:运行时间为$o(m)$

算法过程

  • 若扫描一遍$D$数组,则复杂度为$O(m)$
  • 若无法在要求时间内得到精确解,则应寻找近似算法

  • 近似算法

$1.$ 任意选择 $k$, $k \le m$
$2.$ 选择 $l$ 使得 $D_{kl}$最大
$3.$ 将$D_{k l}$作为近似直径解

算法分析

  • 近似比

由于满足三角不等式即 $D_{ij} <= D_{ik} + D_{kj}$
假设图的直径端点为 $i$, $j$
则有:
$D_{ij} \le D_{ik} + D_{kj} \le D_{kl} + D_{kl} = 2 * D_{kl}$

也就是说,该算法得到的近似解最坏情况下不会小于精确解的$\frac{1}{2}$
因此我们称这个算法的近似比为 $2$

  • 运行时间

    $O(n) = O(\sqrt{m})= o(m)$

近似算法

  • 近似算法是主要用于解决优化问题,能够给出一个优化问题的近似优化解的算法

  • 近似算法解的近似度

问题的每一个可能的解都具有一个代价
问题的优化解可能具有最大或最小代价
我们希望寻找问题的一个误差最小的近似优化解

  • 分析近似解代价与优化解代价的差距

$1.$ Ratio Bound
$2.$ 相对误差
$3.$ $(1+\varepsilon)$-近似

Ratio Bound


The total number of English words:163
The total number of Chinese words:897
欢迎点击下方的知乎图标关注我的知乎QAQ
毕生梦想-成为知乎大V
蟹蟹~