algorithm - AC-1、AC-2 和 AC-3 算法(弧相容性)

Question

谁能给我解释一下 AC-1、AC-2 和 AC-3 算法？我必须理解它们并用代码实现它们。但首先，我想很好地理解它们，但它们太难了，我无法理解。有什么帮助吗？顺便说一句，我对回溯不太熟悉，我试着阅读和观看有关它的视频，但还是一样!谢谢，

Answer 1

我将快速解释一下回溯和 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 可以采用的每个 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