集合覆盖c++的贪心算法

Question

Minimum Set Cover是一个问题，您必须找到覆盖每个元素所需的最小集合数量。例如，假设我们有一组X=array(1,2,3,4,5,6)和另一组S，其中

S[1] = array(1, 4)   
S[2] = array(2, 5)   
S[3] = array(3, 6)  
S[4] = array(1, 2, 3)   
S[5] = array(4, 5, 6) 

问题是找到覆盖X的每个元素的S的最小集合数量。因此，很明显，在我们的例子中，最小集合覆盖将是S[4]和S[5]，因为它们覆盖了所有元素。有人知道如何在C++中实现这段代码吗？请注意，这是NP完全的，因此没有快速算法来解决它。C++中的任何解决方案都将受到欢迎。顺便说一句，这不是一个家庭作业，我需要在Quine–McCluskey项目中使用这个算法来生成解决方案的最后一部分。

提前谢谢。

Answer 1

因此，您所处的状态是，您使用Quine & McCluskey方法确定了所有主要隐含关系。然后，您已经创建了主隐含关系表，并提取了基本的主隐含关系。您检查了行和列的优势，消除了多余的行和列。但后来你结束了，只剩下一个循环核心。

     Ac Bc Ab bC aB aC 
  3   X  X
  5         X  X
  7   X     X
  9               X  X
 11      X        X
 13            X     X

现在，您想要使用集合覆盖问题来找出所有最小必要的素蕴涵。

为此，您可以使用Petrick的方法。这是一种精确的方法，会给出一组最小的结果。其实现相当简单。10行代码：

using MintermSet = std::set<MinTermNumber>;
using Minterm = std::set< BooleanVariable>;
using MintermVector = std::vector<MinTermNumber>;

using MaxtermSet = std::set<MaxTermNumber>;
using ConjunctiveNormalForm = std::set<MaxtermSet>;

using ProductTerm = std::set<BooleanVariable>;
using ProductTermVector = std::vector<ProductTerm>;

// Disjunctive Normal Form
using DNF = std::set<ProductTerm>;
// Conjunctive Normal Form
using CNF = std::vector<DNF>;


class PetricksMethod
{
public:
    // Functors operator
    ProductTermVector operator()(const CNF& cnf);
protected:
};


#include "petrick.hpp"

#include <algorithm>

// Functor operator for applying Petricks methhod

ProductTermVector PetricksMethod::operator ()(const CNF& cnf)
{
    // We select an iterative approach. Start with the first Element of the CNF (which is a DNF)
    // And we sorte the result of each iterative operation again in this element
    DNF resultingDNF{ cnf[0] };
    // We will always start with the element 1 (not element 0) becuase in 0 is the initial value
    // or respectively the intermediate result
    for (CNF::size_type dnfInCnfIndex = 1; dnfInCnfIndex < cnf.size(); ++dnfInCnfIndex)
    {
        // Result of multipliyong out od the intermediate (initial) value with the current CNF Product term
        DNF intermediateCalculatedDNF;
        // Now go through all elements of the intermediate (initial) product term/DNF
        // For (1+2)(3+4)  this would be the (1+2) part
        for (const ProductTerm& productTermLeftSide : resultingDNF)
        {
            // Next we will iterate over all Minterms in the next DNF
            // For (1+2)(3+4)  this would be the (3+4) part
            for (const ProductTerm& productTermRightSide : cnf[dnfInCnfIndex])
            {
                ProductTerm productTerm{ productTermLeftSide }; // Resulting Product term is now 1
                // Add all elements from the right side
                productTerm.insert(productTermRightSide.begin(), productTermRightSide.end());   // Resulting Product term is now 1,2
                intermediateCalculatedDNF.insert(std::move(productTerm));  // Store this one
                // And continue to add more product terms. The stl::set will ensure the idempotence law and prevent memory waste
            }
        }
        // And now add all found terms to the result and continue with the next element of the right hand side
        // Please note: also here the set will prevent double terms
        resultingDNF = std::move(intermediateCalculatedDNF);
    }

    // Now we have the result (with 10 lines of code). The result contains all product terms in DNF
    // But for our prupose we are only interested in the minimum size terms
    // so, lets find the element with the minimu size (can be more than one)
    uint minLength{ narrow_cast<uint>(std::min_element(resultingDNF.begin(), resultingDNF.end(), [](const ProductTerm & left, const ProductTerm & right) noexcept {return left.size() < right.size(); })->size()) };
    // And from the big list of the DNF with all product terms, we copy all elements having the minimu size to the result. These are our best coverage sets
    ProductTermVector cheapestVector;
    // Copy result and return it to caller
    std::copy_if(resultingDNF.begin(), resultingDNF.end(), std::back_inserter(cheapestVector), [&minLength](const ProductTerm& pt) noexcept {return pt.size() == minLength; });
    return cheapestVector;
}

所有这些都是你可以在GitHub上找到的软件的一部分。您还可以看到一个完全实现的Quine & McCluskey算法。

希望这能有所帮助。。。