上下文:backjumping是对vanilla回溯的优化。它通过智能地跳回到导致失败的节点(而不是回溯到按时间顺序排列的父节点)来减少搜索树的分支因子。
人工智能的第5章,现代方法,第3版,p149-150给出了如何在回跳期间创建冲突集的简短示例。
这个例子是关于着色Australia's map。
引用有问题的部分:
搜索分支的“终端”失败总是发生,因为变量的域变空;该变量具有标准冲突集。在我们的示例中,SA失败,其冲突集(例如){WA,NT,Q}。我们回到Q,Q吸收SA的冲突(当然减去Q本身)到它自己的直接冲突集合,即{NT,NSW};新的冲突集是{WA,NT,NSW}。也就是说,鉴于之前对{WA,NT,NSW}的分配,Q没有解决方案。因此,我们回溯到NT,这是最新的。 NT将{WA,NT,NSW} - {NT}吸收到其自己的直接冲突集{WA}中,给予{WA,NSW}(如前一段所述)。现在算法正如我们希望的那样回到新南威尔士州。
我很难理解强调的部分:
Q1的答案在前一段中,关键是决策顺序:
再次考虑部分分配{WA = red,NSW = red}(从我们之前的讨论来看,这是不一致的)。假设我们尝试T = red next然后分配NT,Q,V,SA。我们知道没有任何赋值可以用于最后四个变量,所以最终我们用完值来尝试NT。
NT是最新的,在这个例子正在讨论的时候它是堆栈的顶层。
我们回到新南威尔士州,因为这是与冲突集相交的最后决定。