artificial-intelligence - 后跳、CSP、AIMA 书

Question

背景：回跳是对原版回溯的优化。它通过智能地跳回到导致失败的节点（而不是回溯到按时间顺序排列的父节点）来减少搜索树的分支因子。

人工智能的第 5 章，一种现代方法，第 3 版，p149-150给出了一个简短示例，说明如何在回跳期间创建冲突集。

这个例子是关于为澳大利亚地图着色的。

引用有问题的部分：

搜索分支的“终端”失败总是因为变量的域变空而发生；该变量具有标准冲突集。在我们的例子中，SA 失败了，它的冲突集是（比如说）{WA,NT,Q}。我们回跳到 Q，Q 将 SA 中的冲突集（当然减去 Q 本身）吸收到它自己的直接冲突集中，即 {NT,NSW}；新的冲突集是 {WA,NT,NSW}。也就是说，从 Q 开始没有解，给定前面对 {WA,NT,NSW} 的赋值。因此，我们回溯到 NT，这是其中最近的一个。NT 将 {WA,NT,NSW} - {NT} 吸收到它自己的直接冲突集 {WA} 中，得到 {WA,NSW}（如上一段所述）。现在算法回跳到 NSW，正如我们所希望的那样。

我正在努力理解强调的位：

1. 回溯到新台币。NT以什么方式/为什么是最新的？
2. 回跳到新南威尔士州。为什么？

标签： artificial-intelligencebacktrackingconstraint-programming

Answer 1

Q1的答案在上一段，关键是决策顺序：

再次考虑部分赋值 {WA = red, NSW = red}（根据我们之前的讨论，它是不一致的）。假设我们接下来尝试 T = red，然后分配 NT、Q、V、SA。我们知道对于最后四个变量没有赋值可以工作，所以最终我们用完了值来尝试 NT。

NT 是最新的，因为它是讨论此示例时堆栈的顶部。

我们回跳到 NSW，因为这是与冲突集相交的最后一个决策。