CAJ | 학술논문

超平面覆盖问题是计算几何领域中一类典型的NP难问题,在实际生活中有着广泛的应用.针对NP难问题的难解性,人们提出了一些传统的方法用来求解这些NP难问题.但由于这些方法具有各自的局限性,不能满足实际应用中的各种需求,人们从新的理论角度为固定参数可解的NP难问题设计参数算法.通过深入分析直线覆盖问题(超平面覆盖问题的一个特例)的结构特征,并利用深度有界搜索树的方法,提出了一个时间复杂度为O(k3(0.736k)k+n logk)的确定性参数算法,极大地改进了当前最好的结果O((k/2.2)2k+n logk).通过对上述算法在高维空间中的进一步扩展,提出了关于超平面覆盖问题时间复杂度为O(dkd+1 (dk)!/((d!)kk!)+nd+1)确定性参数算法,对当前的最好结果O(kd(k+1)+nd+1)有较大改进.
초평면복개문제시계산궤하영역중일류전형적NP난문제,재실제생활중유착엄범적응용.침대NP난문제적난해성,인문제출료일사전통적방법용래구해저사NP난문제.단유우저사방법구유각자적국한성,불능만족실제응용중적각충수구,인문종신적이론각도위고정삼수가해적NP난문제설계삼수산법.통과심입분석직선복개문제(초평면복개문제적일개특례)적결구특정,병이용심도유계수색수적방법,제출료일개시간복잡도위O(k3(0.736k)k+n logk)적학정성삼수산법,겁대지개진료당전최호적결과O((k/2.2)2k+n logk).통과대상술산법재고유공간중적진일보확전,제출료관우초평면복개문제시간복잡도위O(dkd+1 (dk)!/((d!)kk!)+nd+1)학정성삼수산법,대당전적최호결과O(kd(k+1)+nd+1)유교대개진.