关于吹雪机问题的改进近似算法

作者：李建; 王海涛; 朱洪

来源：吉林大学学报（工学版）, 2007, (1): 151-154.

DOI：10.3969/j.issn.1671-5497.2007.01.030

• 计算机应用
• 吹雪机问题
• NP-hard
• 近似算法

提出了吹雪机问题的改进近似算法.首先给出了该问题最优解的2个下界,并分析了当待清除区域为单连通区域时问题的难度.对于矩形区域,给出了一个3倍近似度的近似算法.对于任意网格图,算法的近似度为5+ε(任意常数ε＞0).

• 单位
  复旦大学