阐释求解求解OptCovering不足一个降维对策

【摘要】本文是对模OptCovering问题的降维策略进行研究.通过分块算法将原问题划分成若干子问题， 然后逐一解决子问题，这样就达到降维的目的.
【关键词】Covering；OptCovering；连通图；降维算法
一、引言
Covering问题是许多问题的抽象模型，具有广泛的应用背景和深刻的理论意义.例如如何布置机器人的位置，使得已知位置的诸服务对象能得到充分的服务的问题，就是一个Covering问题，其中圆盘的半径R代表机器人的手臂长度.
所谓Covering问题，即是给定一个由平面的点组成的有穷点集N和一定个数直径为D的圆盘，问如何布置这些圆盘的位置，才能将点集N中所有的点都覆盖住.进一步地，如何用最少的圆盘将点集N源于：毕业论文总结www.618jyw.com
中所有的点覆盖住，即是OptCovering问题.显然，OptCovering问题比Covering问题更困难.
Covering问题是著名的NP难度问题之一，不存在多项式时间复杂度的求解算法[2，3].于是，学者们设计了一些近似算法来求解Covering问题.文献中提出的著名的多项式时间复杂度的HochbanmMaass算法，其Shifting策略是一个既聪明又透彻的颇具理论意义的策略，但由于多项式的次数太高，计算时间增长太快，不利于解决实际问题.文献[4]模拟万有引力和屏蔽现象所引起的力学过程，给出了求解Covering问题的一个拟物方法.这一方法能较好地解决规模不算大的Covering问题（点的个数不多于50时），但问题规模较大时点的个数多于100时，这一方法就显得无能为力了.而且，这一方法不利于解决OptCovering问题.
本文提出了一些解决大规模OptCovering问题的策略.核心思想是先将原问题转化为一个图论问题，划分成若干子问题逐一解决，从而达到降维的目的；解决子问题运用动态规划方法，其策略是不断地搜索一些特殊的用且仅用一个圆盘覆盖的子点集，逐一用一个圆盘来覆盖.

二、降维策略

定理2N0是Covering问题的一个独立集，用一个圆盘覆盖N0则该圆盘覆盖N0的方式是最优的.
【参考文献】
C. A. Rogers. Packing and Covering，Cambridge University Press.Cambridge 1964.
Dorit S.Hochbaum，W.Maass.Approximation schemes for covering and packing problem in image processing and VLSI，Journal of the Association for Computing Machinery 32：1（1985），130-136.
[3]Garey M R，Johnson D S.Computing and Intractability：A Guide to the Theory of NP-Completeness.San Franciso：Freeman，1979.