2

我正在阅读 Anany Levtin 的算法设计和分析简介中的回溯算法设计技术。

我很难理解回溯算法的通用定义并将其映射到 4 皇后问题。

对于从更一般的角度来看的回溯算法设计技术，大多数回溯算法符合以下描述。

回溯算法的输出可以被认为是一个 n 元组 (x1, x2, x3,...,xn)，其中每个坐标 xi 是某个有限线性有序集合 Si 的一个元素。例如，对于 n 皇后问题，每个 Si 是整数 1 到 n 的集合。元组可能需要满足一些额外的约束（例如，n-queens 问题中的非攻击性要求）。

例如对于 4 个皇后问题，每个 Si 设置为 {1, 2, 3, 4}

回溯算法显式或隐式生成状态空间树，其节点表示部分构造的元组，其中第一个“i”坐标由算法的早期动作定义。如果这样的元组 (x1, x2, x3,.. xi) 不是一个解，算法会在 Si+1 中找到与 (x1, x2, x3...xi) 的值一致的下一个元素，并且问题约束并将其添加到元组中作为其 (i+1)st 坐标。如果这样的元素不存在，则算法回溯以考虑 xi 的下一个值，依此类推。

我对上述文字的问题是

  1. 作者的意思是“回溯算法显式或隐式生成状态空间树，其节点表示部分构造的元组，其中第一个“i”坐标由算法的早期动作定义。如果这样的元组（x1 , x2, x3,...元组作为它的 (i+1)st 坐标。" ?

    具体来说，作者所说的算法在 Si+1 中找到下一个元素是什么意思？

    请要求用 4 个皇后问题解释上述陈述。

  2. 如果元素不存在，算法回溯考虑下一个 xi 值？请用 4 个皇后问题解释这个语句。

谢谢！

4

1 回答 1

0

这种回溯的解释确实很难理解，因为它使用了很多正式的符号，没有用于特定目的或证明。让我试着用一种不太正式的方式来解释 4-queens 问题，这是一个很好的例子：

在回溯过程开始时，棋盘是空的。这是状态空间树的根。这个根有子节点，每个我们可以放置第一个皇后的可能性都有一个。我们不是在进入下一个级别之前构建每个子节点（这将导致状态空间树的 BFS），而是为第一个皇后选择一个可能的位置，从而构建一个子节点。从这个子节点中，我们再次有多个选项来放置第二个皇后，所以我们选择一个，依此类推。

如果我们到达无法放置剩余皇后的节点，我们将回溯 - 我们上一层到该节点的父节点并检查是否还有我们尚未探索的可能性。如果是，我们通过创建相应的子节点来探索它们，如果不是，我们再次回溯，再上一层，直到我们找到问题的解决方案（放置所有皇后）或者我们展开根节点的所有子节点并到达回溯操作期间的根节点 - 这意味着没有解决方案。

于 2012-06-14T18:32:30.130 回答