论文部分内容阅读
超平面覆盖问题是计算几何领域中一类典型的NP难问题,在实际生活中有着广泛的应用.针对NP难问题的难解性,人们提出了一些传统的方法用来求解这些NP难问题.但由于这些方法具有各自的局限性,不能满足实际应用中的各种需求,人们从新的理论角度为固定参数可解的NP难问题设计参数算法.通过深入分析直线覆盖问题（超平面覆盖问题的一个特例）的结构特征,并利用深度有界搜索树的方法,提出了一个时间复杂度为O（k3（0.736k）k＋nlogk）的确定性参数算法,极大地改进了当前最好的结果O（（k/2.2）2k＋nlogk）.通