集合覆盖问题降阶算法

摘要

集合覆盖问题是运筹学与计算机科学中的一个NP难题.首先将该问题转化为一个等价的二分图,给出该问题的上下界算法；接着给出该问题的数学性质,这些数学性质能降低问题的规模,加快算法的求解速度；然后将数学性质和上下界方法结合起来形成一个降阶算法,并给出了算法的时间复杂度分析.该算法不仅可以单独使用,还可以与其它算法结合起来使用达到更好的效果.最后通过多个示例进一步说明算法的原理及应用情况.%The set covering problem (SCP) is a classical NP-hard problem in operation research and computer science. A SCP was transformed into an equivalent bipartite graph (BG) and an upper-lower bound algorithm for SCP or BG was proposed. Some mathematical properties of SCP or BG were, presented which can decrease the size of the problem and can speed up the algorithm. A new reduction algorithm for SCP was proposed by combining the mathematical properties with the upper-lower bound algorithm. Then the worst-case time complexity of the new reduction algorithm was analysed. The reduction algorithm proposed can be used alone, or cooperating with other algorithms to get more effective results. Several instances were solved and analyzed to illustrate the principles and applications of the algorithm.