AC-1、AC-2和AC-3算法(弧一致性)

Question

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

Answer 1

我将给你一个快速的解释关于回溯和AC-3。但如果你想了解更多细节，你应该阅读这本书：

人工智能:现代方法: Stuart Russel和Peter Norvig 2003 Prentice Hall

这本书作为约束满足问题(CSP)的一章，解释了AC-3和回溯的所有内容。

您需要了解的第一件事是什么是CSP。CSP包含：

• 要对其求值的一组变量{A，B，C}；
• 每个变量Da，Db，Dc的一个域，每个变量都包含该变量可以采用的可能值；
• 一组限制，如A>B+2和C ...

现在，当你有一个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，关于restriction.

• and B->A是一致的:每个B可以取的值b都有一个A可以取的关于restriction.

的值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