AC-1、AC-2和AC-3算法（弧一致性）

Question

AC-1、AC-2和AC-3算法（弧一致性）

5

请问有人能给我解释一下AC-1、AC-2和AC-3算法吗？我需要理解这些算法并用代码实现它们。但首先，我想要真正理解它们，可它们对我来说太难了。是否能提供任何帮助呢？顺便说一下，我对回溯算法也不是很熟悉，我试着阅读和观看相关视频，但还是感到困惑！谢谢。

- user4491463

你确定 AC-1 和 AC-2 存在吗？ - Luis Alves

你可能想要明确提到上下文（超出回溯）。自适应编码？交替电流？AC²？ - greybeard

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Luis Alves · Accepted Answer

我将为您简要解释一下回溯和AC-3。但如果您想更详细地了解，请阅读以下书籍：

Artificial Intelligence: A Modern Approach : Stuart Russel and Peter Norvig 2003 Prentice Hall

该书有一章关于约束满足问题(CSP)，其中讲解了所有关于AC-3 和回溯的内容。

首先，您需要理解什么是CSP。CSP包含：

要确定值的变量集{A，B，C}；
每个变量Da，Db，Dc 的定义域，每个定义域包含变量可以取的可能值；
一组限制条件，例如A > B + 2 和 C < B ...

当您拥有CSP时，您希望将值分配给所有变量，并保持遵守限制条件。当所有变量都有一个值并同时遵守所有限制条件时，CSP得到解决。

回溯是一种算法，可让您为此问题找到解决方案。因此，您从一个空状态{}开始，这意味着没有变量具有值。然后从变量集中选择一个变量（您选择变量的顺序可能会影响算法的性能，您可以使用一些启发式方法来解决这个问题，例如MRV-剩余最小值...）。

现在假设我们首先选择A，然后从定义域Da中选择一个值（选择值的顺序也可能使用启发式方法）。假设Da = {1,2,3}。我们选择1。现在检查A = 1是否违反任何限制条件，否则它不是一个好的赋值。如果不违反，则让我们设置A = 1，现在我们处于状态{A = 1}。现在让我们继续这样做。

想象一下，您选择B和值1。这将违反限制条件A > B + 2。现在您有两个选项，如果您有另一个要测试的B值，则可以尝试。如果没有，则意味着A = 1不正确，您需要返回到状态{}并尝试A = 2等。

以下是回溯的伪代码：

function backtracking (csp) return a solution or fails
    return recursive_backtracking({}, csp) // {} is the initial state

function recursive_backtracking (state, csp) return a solution or fails
    if state is complete then return state // all variable have a value
    var <- selectNotAtributedVariable(csp)
    for each value in orderValues(csp, var) // values of the domain of var
        if var = value is consistent given the restrictions
            add {var = value} to state
            result = recursive_backtracking(state, csp)
            if result != fail then return result
            remove {var = value} from state
    return fail

请注意，selectNotAtributedVariable和orderValues是启发式算法（它们可能只返回集合的第一个元素）。

现在AC-3是什么以及为什么和何时使用它？首先，AC-3用作预处理步骤。您可以像这样使用它：

function solveCSP(csp)
    ac3(csp)
    return backtracking(csp)

这是关于“何时”回答的问题。基本上，AC-3在回溯过程中检测属性之间可能存在的冲突，并通过削减CSP变量的域来删除它们。当两个变量共享限制时，我们称之为它们之间存在一个弧。当且仅当以下两个条件都成立时，我们说A和B之间的弧是一致的：

A->B是一致的：对于A能够取得的每个值a，都有一个B可以取得的值b，使其符合限制。
B->A是一致的：对于B能够取得的每个值b，都有一个A可以取得的值a，使其符合限制。

想象一下，你有以下限制：A > B和B > C。您将拥有以下一组弧：{A->B, B->A, B->C, C->B}。现在AC-3所做的就是从以上集合中选择一个弧A->B，尝试检查A可以取哪些值以及是否存在一个值b，使B可以取得它，而且满足限制。如果是这样，则A的域保持不变，否则从A的域中删除值a。每次从域中删除一个值后，您都需要重新检查A的邻居（在这种情况下）。我的意思是，您需要重新检查B->A弧（不是因为它们在上面的集合中）。

这里是伪代码：

function AC3(csp) returns csp possibly with the domains reduced
    queue, a queue with all the arcs of the CSP
    while queue not empty
         (X,Y) <- getFirst(queue)
         if RemoveConsistentValues(X,Y, csp) then
              foreach Z in neighbor(X) - {Y}
                   add to queue (Z,X)
    return csp

function RemoveConsistentValues(X, Y, csp) returns true if a value was removed
    valueRemoved <- false
    foreach x in domain(X, csp)
        if there's no value of domain(Y, csp) that satisfies the restriction between X and Y then
            remove x from domain(X, csp)
            valueRemoved <- true
    return valueRemoved