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

任何人都可以向我解释 AC-1、AC-2 和 AC-3 算法？我必须理解它们并用代码实现它们。但首先，我想很好地理解它们，但它们太难了，我无法理解。请问有什么帮助吗？顺便说一句，我对回溯不太熟悉，我尝试阅读和观看有关它的视频，但还是一样!谢谢， 最佳答案 我将为您提供有关回溯和AC-3的快速解释。但是如果你想更详细地阅读这方面的内容，你应该阅读这本书: 这本书是关于约束满足问题(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 statefunction 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 cspfunction 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关于algorithm - AC-1、AC-2 和 AC-3 算法(电弧一致性)，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/28257422/