5

任何人都可以向我解释 AC-1、AC-2 和 AC-3 算法吗？我必须理解它们并用代码实现它们。但首先，我想很好地理解它们，但它们太难被我理解了。请问有什么帮助吗？顺便说一句，我对回溯不太熟悉，我尝试阅读和观看有关它的视频，但还是一样！谢谢，

4

1 回答 1

22

我将给你一个关于回溯和 AC-3 的快速解释。但是，如果您想更详细地阅读此内容，则应该阅读这本书：

人工智能：现代方法：Stuart Russel 和 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->A 是一致的：对于 B 可以采用的每个值 b 都有一个 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
于 2015-01-31T23:02:51.467 回答