求解喇叭公式的贪婪算法-解网

问：

这是我几天来一直试图理解并最终解决的作业问题。到目前为止，我还没有成功。因此，任何指导、帮助理解或解决问题都是值得赞赏的。

系统将为您提供一组针对布尔变量的约束 {x₁， x₂， ...， x_n}。mn

约束有两种类型：相等约束：
x i = x j，对于某些不等式约束：x_i ！= x_j，对于某些约束
i != ji != j

设计一个高效的贪婪算法，给定相等和不等式约束的集合确定它是否是可能或不可能同时满足所有约束。
如果可以满足所有约束，您的算法应该输出对满足所有约束。

选择此问题的输入的表示形式并使用符号 Input： ...， Output： ....

用通俗易懂的英语描述你的贪婪算法。在什么感觉你的算法“贪婪”吗？

描述你的贪婪算法在伪代码中。

简要说明算法的正确性。

说明并证明算法的运行时间。越多算法越高效越好。

到目前为止，我发现这个问题与布尔满足性 （SAT）问题有关。我尝试将所有变量设置为 first，然后通过反例证明它不能同时满足所有约束。false

我对约束满足问题 （CSP）和 Horn SAT 感到困惑。我阅读了有关这些的某些文章以获得解决方案，这让我感到困惑。我的逻辑是创建一个树并应用 DFS 来检查是否满足约束条件，而 Horn SAT 解决方案则引导我进行数学证明。

任何帮助都是值得赞赏的，因为这是我的学习阶段，我不能一下子掌握它。:)

算法时间复杂度复杂度理论布尔逻辑贪婪

（非正式）分类：

所以首先，这不是布尔 SAT 问题，因为它是 NP 完备的。你的老师暗示这不是NP完备的，他要求一种有效的（即最多多项式时间）方法来解决问题。

建模（思考）问题：

将这个问题视为图表的一种方式，其中不等式代表一种边缘，而相等式代表另一种边缘：

以图形方式思考这个问题帮助我意识到这有点像图形着色问题：我们可以将所有节点设置为（unset），然后选择要设置为的任何节点，然后从该节点进行广度优先搜索以设置所有连接节点（将它们设置为 or ），检查是否有任何矛盾。如果我们为图的连接组件完成此操作，而没有发现矛盾，那么我们可以忽略该部分中的所有节点并随机设置另一个节点的值，等等。如果我们这样做，直到没有连接的组件留下，并且我们仍然没有矛盾，那么我们就以一种代表合法解决方案的方式设置了图形。?truetruefalse

溶液：

因为正好有元素，我们可以为 the 和另一个（每个 “bucket” 可以包含它所等价的数组，但如果我们想要 [复杂性将保持不变]，我们可以获得比这更高效的数组）。nequalitiesinequalities

您的数组数组可以想象成这样：equalities

这将代表：

0 == 1
1 == 2
3 == 4

请注意，这是一个不规则矩阵，需要空间。我们对矩阵做同样的事情。此外，设置这两个数组（数组的数组）会占用空间和时间的复杂性。2*minequalityO(m + n)

现在，如果存在一个解，{x 0， x 1， x 2， x 3}，那么 {！x₀，！x₁，！x ₂，！x₃} 也是一个解。证明：

（x i == x j） iff （！x_i == ！x_j)

因此，如果我们随机设置其中一个元素，它不会影响我们的解决方案。让我们将 x_i 设置为，并将其他设置为 [在数字上，我们将处理三个值：（false）、（true）和（unset）]。true?012

我们将这个数组称为（即使它还没有完成）。solution

现在，我们可以使用递归来考虑设置值的所有后果：

（下面的代码是假代码，因为提问者没有指定语言。我把它做了一些风格，但只是为了保持它的通用性并使用漂亮的格式颜色。c++

bool Set (int i, bool val) // i is the index
{
    if (solution[i] != '?')
        return (solution[i] == val);

    solution[i] == val;

    for (int j = 0; j < equalities[i].size(); j += 1)
    {
        bool success = Set(equalities[i][j], val);
        
        if (!success)
            return false; // Contradiction found
    }
    
    for (int j = 0; j < inequalities[i].size(); j += 1)
    {
        bool success = Set(inequalities[i][j], !val);
        
        if (!success)
            return false; // Contradiction found
    }

    return true; // No contradiction found
}


void Solve ()
{
    for (int i = 0; i < solution.size(); i += 1)
        solution[i] == '?';

    for (int i = 0; i < solution.size(); i += 1)
    {
        if (solution[i] != '?')
            continue; // value has already been set/checked
        
        bool success = Set(i, true);
        
        if (!success)
        {
            print "No solution";
            return;
        }
    ]
    
    print "At least one solution exists. Here is a solution:";
    print solution;
}

由于函数中的第一个条件，函数只能执行（超出 if 语句）次数。该函数只有在传递第一个语句时才能调用自身，它对每个节点值执行 1 次。每次函数传入函数的主体（超出语句范围）时，它所做的工作都与与相应节点关联的边数成正比。该函数最多可以调用该函数。因此，函数可以被调用的次数是，对应于求解过程中完成的工作量。ifSetnSetifnSetifSolveSetnO(m+n)

这里的一个诀窍是认识到函数需要调用函数时间，其中是图中连接的分量的数量。请注意，每个连接的组件都是相互独立的，因此适用相同的规则：我们可以合法地选择其元素之一的值，然后考虑后果。SolveSetCC

最快的解决方案仍然需要读取所有约束，并且需要在可能的情况下输出解决方案;因此，不可能得到一个比具有更好时间复杂度的解决方案。以上是一个具有时间和空间复杂性的贪婪算法。O(m)O(n)O(m+n)O(m+n)

有可能获得更好的空间复杂性（同时保持时间复杂度），甚至可能，但我不确定。O(m+n)O(1)

至于霍恩公式，我很尴尬地承认我对它们一无所知，但这个答案直接回应了作业中对你的所有要求。

求解喇叭公式的贪婪算法

Greedy Algorithm for solving Horn formulas

评论

（非正式）分类：

建模（思考）问题：

溶液：

评论