求解OptCovering問題的一個降維策略

【摘要】本文是對模OptCovering問題的降維策略進行研究.通過分塊算法將原問題劃分成若干子問題， 然后逐一解決子問題，這樣就達到降維的目的.

【關鍵詞】Covering；OptCovering；連通圖；降維算法

一、引言

Covering問題是許多問題的抽象模型，具有廣泛的應用背景和深刻的理論意義[1].例如如何布置機器人的位置，使得已知位置的諸服務對象能得到充分的服務的問題，就是一個Covering問題，其中圓盤的半徑R代表機器人的手臂長度[2].

所謂Covering問題，即是給定一個由平面的點組成的有窮點集N和一定個數直徑為D的圓盤，問如何布置這些圓盤的位置，才能將點集N中所有的點都覆蓋住.進一步地，如何用最少的圓盤將點集N中所有的點覆蓋住，即是OptCovering問題.顯然，OptCovering問題比Covering問題更困難.

Covering問題是著名的NP難度問題之一，不存在多項式時間復雜度的求解算法[2，3].于是，學者們設計了一些近似算法來求解Covering問題.文獻[1]中提出的著名的多項式時間復雜度的HochbanmMaass算法，其Shifting策略是一個既聰明又透徹的頗具理論意義的策略，但由于多項式的次數太高，計算時間增長太快，不利于解決實際問題.文獻[4]模擬萬有引力和屏蔽現象所引起的力學過程，給出了求解Covering問題的一個擬物方法.這一方法能較好地解決規模不算大的Covering問題（點的個數不多于50時），但問題規模較大時點的個數多于100時，這一方法就顯得無能為力了.而且，這一方法不利于解決OptCovering問題.

本文提出了一些解決大規模OptCovering問題的策略.核心思想是先將原問題轉化為一個圖論問題，劃分成若干子問題逐一解決，從而達到降維的目的；解決子問題運用動態規劃方法，其策略是不斷地搜索一些特殊的用且僅用一個圓盤覆蓋的子點集，逐一用一個圓盤來覆蓋.

二、降維策略

定理2N0是Covering問題的一個獨立集，用一個圓盤覆蓋N0則該圓盤覆蓋N0的方式是最優的.

【參考文獻】

[1]C. A. Rogers. Packing and Covering，Cambridge University Press.Cambridge 1964.

[2]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.