【解決方法】バックトラッキングを介して制約充足問題を解決するにはどうすればよいですか

私は2つのアイテムのnセットを持っています:

["a", "b"]
["c", "d"]
["d", "a"]
["b", "c"]

そして、このセット (存在する場合) から、次の制約を満たすアイテムを少なくとも 1 つ見つけたいと考えています。

最初の制約は一種の除外チェックです (= 一緒に存在できないアイテムのセットのリストが与えられます)。このセットは次のようになります。

["c", "d"] // items "c" and "d" cannot exist together
...

2 番目の制約は、どのアイテムがどのアイテムが存在する必要があるかを指定します (= 一緒に存在する必要があるアイテムのセットのリストが与えられます)。このセットは次のようになります。

["b", "c"] // item "b" needs item "c" and vice versa
...

これらの制約を解決するために、元のセット (= この質問の最初のセット) の他のセットのアイテムを使用できます。

サンプル セットの解決策は次のとおりです (複数の解決策が存在する可能性があることに注意してください。有効な解決策が必要なだけです)。

Passed checks with items: 
a
b
c

この問題に取り組んでいる間に私が見つけた警告のいくつか:
– 解決策は再帰的でなければなりません
– アイテムが他のアイテムによって作成された除外のために「ロック」されている可能性があることを考慮する必要があります。これは、アイテムの別の組み合わせを使用する場合に回避できる可能性があります。

これを機能させる方法についてのアイデアは大歓迎です。

私が試したこと：

#include <iostream>
#include <vector>
#include <unordered_set>

using namespace std;

class Set {
public:
    std::string item1;
    std::string item2;

    Set(std::string i1, std::string i2) : item1(i1), item2(i2) {}
};

// Define a function to check if a given pair of items violates a constraint
bool ViolatesConstraints(std::string item1, std::string item2, const vector<pair<std::string, std::string>>& constraints) {
    for (const auto& constraint : constraints) {
        if ((constraint.first == item1 && constraint.second == item2) ||
            (constraint.first == item2 && constraint.second == item1)) {
            return true;
        }
    }
    return false;
}

// Define a function to recursively find all required items
void FindRequiredItems(std::string item, const vector<pair<std::string, std::string>>& inclusions, unordered_set<std::string>& requiredItems) {
    for (const auto& inclusion : inclusions) {
        if (inclusion.first == item) {
            requiredItems.insert(inclusion.second);
            FindRequiredItems(inclusion.second, inclusions, requiredItems);
        }
    }
}

int main() {
    // Define the list of sets and their items
    vector<Set> sets = { ... };

    // Define the list of constraint pairs
    vector<pair<std::string, std::string>> constraints = { ... };

    // Define the list of inclusion pairs
    vector<pair<std::string, std::string>> inclusions = { ... };

    // Initialize the best solution found so far
    bool passedChecks = false;
    unordered_set<std::string> usedItems;

    // Iterate over all sets to search for a solution
    for (const auto& set : sets) {
        // Check if the set's items violate any constraints
        if (ViolatesConstraints(set.item1, set.item2, constraints)) {
            continue;
        }

        // Check if the set's items satisfy all inclusions recursively
        unordered_set<std::string> requiredItems = { set.item1, set.item2 };
        for (const auto& requiredItem : requiredItems) {
            FindRequiredItems(requiredItem, inclusions, requiredItems);
        }
        if (requiredItems.size() == 5) {
            // Found a solution, update the best solution found so far
            passedChecks = true;
            usedItems.clear();
            usedItems.insert(set.item1);
            usedItems.insert(set.item2);
        }
        else {
            // Current solution doesn't satisfy all inclusions, continue searching
            continue;
        }

        // Search for a better solution
        for (const auto& nextSet : sets) {
            if (nextSet.item1 == set.item1 && nextSet.item2 == set.item2) {
                continue;  // skip current set
            }

            if (ViolatesConstraints(nextSet.item1, nextSet.item2, constraints)) {
                continue; // skip set whose items violate constraints
            }

            unordered_set<std::string> requiredItems = { nextSet.item1, nextSet.item2 };
            for (const auto& requiredItem : requiredItems) {
                FindRequiredItems(requiredItem, inclusions, requiredItems);
            }

            if (requiredItems.size() == 5) {
                // Found a better solution, update the best solution found so far
                passedChecks = true;
                    usedItems.clear();
                    usedItems.insert(nextSet.item1);
                usedItems.insert(nextSet.item2);
            }
        }
    }

    // Print the result
    if (passedChecks) {
        cout << "Passed checks with items:";
        for (const auto& item : usedItems) {
            cout << " " << item;
        }
        cout << endl;
    }
    else {
        cout << "Failed checks" << endl;
    }

    return 0;
}