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

Question

Minimum Set Cover是一个问题，您必须找到覆盖每个元素所需的最少集合数。例如，假设我们有一组 X=array(1,2,3,4,5,6) 和另外 5 个集合 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 算法。

希望这对您有所帮助。 . .