关键词: 精确覆盖问题, 分支降阶, 加权分治, 时间复杂度

Abstract: Exact cover problem is one of the classical NP-Hard problems in combinatorial optimization, which is widely applied in many fields. Firstly, the mathematical properties of the exact cover problem are studied in this paper, and the corresponding branch and reduction rules are proposed according to the mathematical properties to reduce the scale of the problem. Secondly, a backtracking algorithm based on branch and reduction is designed to solve the problem. Then, the time complexity of the precise algorithm is O(1.4656^k)through conventional technical analysis. Finally, the measure and conquer technique is applied to the time complexity of the algorithm. The time complexity of the algorithm is reduced to O(1.3842^k). Finally, an example is given to further illustrate the principle of the algorithm and the algorithm is compared with other precise algorithm. The research results demonstrate that the algorithm is feasible and effective.

Key words: exact cover problem, branch and reduction, measure and conquer, time complexity