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

Improved approximation algorithm for snowblower problem

作　　者：李建[1] 王海涛[1] 朱洪[1] 

机构地区：[1]复旦大学计算机科学与工程系,上海200433

出　　处：《吉林大学学报（工学版）》2007年第1期151-154,共4页Journal of Jilin University:Engineering and Technology Edition

基　　金：国家自然科学基金资助项目(60496321);上海市科技发展基金资助项目(O3JC14014)

摘　　要：提出了吹雪机问题的改进近似算法。首先给出了该问题最优解的2个下界,并分析了当待清除区域为单连通区域时问题的难度。对于矩形区域,给出了一个3倍近似度的近似算法。对于任意网格图,算法的近似度为5+ε(任意常数ε>0)。This paper proposes several approximation algorithms to improve the solution of snowblower problem. Two lower boundaries of the problem for the optimal solution are defined. The complexity of the problem is analyzed when the unexplored region is simply connected. For rectangular region, an algorithm of three-fold approximation is proposed. For arbitrary two-dimensional grid graph the degree of approximation of the algorithm is 5＋ε for any constant ε〉 0.

关 键 词：计算机应用 吹雪机问题 NP—hard近似算法 

分 类 号：TP361.2[自动化与计算机技术—计算机系统结构]