摘要
提出了吹雪机问题的改进近似算法。首先给出了该问题最优解的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.
出处
《吉林大学学报（工学版）》
EI
CAS
CSCD
北大核心
2007年第1期151-154,共4页
Journal of Jilin University:Engineering and Technology Edition
基金
国家自然科学基金资助项目(60496321)
上海市科技发展基金资助项目(O3JC14014)
