算法 AC-1, AC-2 和 AC-3 /弧形一致/

我将为您提供关于返回的快速解释 AC-3. 但是如果您想更详细地阅读此内容，您应该阅读这本书：

人工智能：现代方法：Stewart Russell和Peter
nor 2003 Prentice Hall.

本书是关于会议限制问题的一章 /CSP/, 这解释了一切 AC-3 回来的方式。

你需要理解的第一件事就是是什么 CSP. 刨花板包含：

套变量 {A, B, C} , 您要找到一个值;

每个变量的域 Da, Db, Dc, 每个每个都包含可以采用变量的可能值;

一组类型限制 A > B + 2 和 C < B ...

现在你有 CSP, 您希望将值属于所有变量并继续尊重 resctictions. CSP 当所有变量都很重要并遵守所有限制的同时，它可以解决。

回溯是一种算法，允许您找到此问题的解决方案。 所以你从一个空白的条件开始 {}, 这意味着没有变异问题。 然后，您从变量集中选择一个变量。 /您选择所选变量的顺序可能会影响算法的性能，有一些启发式可以使用它，例如，MRV-MILLE剩余值。 .../.
现在假设我们选择第一个，现在我们从域中选择值 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 as和一致性之间的弧，如果：

A-> B是一致的： foreach 这里可能有值的值 B, 什么 B 可以观察遵守限制。

和 B->A 这是一致的： foreach 价值 B, 什么 B 可以在此处具有可能发生符合限制的值。

想象一下，你有以下限制。 A > B 和 B > C. 您将拥有以下一组弧： {A->B, B - >A, B - >C, C - >B}
现在是什么 AC-3, 在于他从上面的集合选择一个弧 A->B, 对于每个价值 a, 那 A 可以接受，试图检查是否有值 b, 那 B 也许，观察限制。 如果是，则域仍然是相同的，如果没有，则删除值和域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