回溯设计技术的一般定义
在Anany Levtin的算法设计和分析介绍中，我阅读了回溯算法设计技术。
我在理解回溯算法的一般定义和映射到4皇后问题上有困难。
基于
的回溯算法设计技术从更一般的角度来看，大多数回溯算法都符合以下描述。
回溯算法的输出可以看作是n元组(x1，x2，x3，.，xn)，其中每个坐标xi都是有限线性序集Si的一个元素。例如，对于n皇后问题，每个Si是整数1到n的集合，元组可能需要满足一些附加的约束(例如，n皇后问题中的非攻击要求)。
例如，对于4个皇后问题，每个Si被设置为{1，2，3，4}
回溯算法显式地或隐含地生成状态空间树，其节点表示由算法早期动作定义的第一个"i“坐标的部分构造元组。如果这样一个元组(x1，x2，x3，. )算法在Si+1中找到与(x1，x2，x3...xi)值和问题约束值一致的下一个元素，并将其作为(i+1)st坐标添加到元组中。如果不存在这样的元素，则算法将返回考虑xi的下一个值，以此类推。
我对上述案文的问题如下：
- 是什么意思？“回溯算法显式地或隐式地生成状态空间树，它的节点用算法先前的动作定义的第一个"i”坐标表示部分构造的元组。如果这样的元组(x1、x2、x3、. xi)不是一个解决方案，则该算法会在Si+1中找到与(x1、x2、x3...xi)值和问题约束一致的下一个元素，并将其作为(i+1)st坐标添加到元组中。“
具体来说，作者所说的在Si+1中查找下一个元素是什么意思？
请用4皇后问题来解释上面的陈述。
- 如果元素不存在的话，算法回轨考虑下一个值？请用4皇后问题来解释这个问题。
谢谢!
回答 1
Stack Overflow用户
发布于 2012-06-14 18:32:30
这种回溯的解释确实很难理解，因为它使用了许多形式的表示法，而这些符号并不用于特定的目的或证明。让我尝试用不太正式的方式解释四皇后问题，这是一个很好的例子：
在回溯过程开始时，板是空的。这是状态空间树的根.这个根有子节点，每个子节点都有一个，我们可以在其中放置第一个皇后。与其在进入下一个级别之前构造每个子节点(这将导致状态空间树的BFS )，不如为第一个皇后选择一个可能的位置，从而构造一个子节点。从这个子节点，我们有多个选项来放置第二个皇后，所以我们选择一个，以此类推。
如果我们到达节点，在那里我们没有可能放置一个剩余的皇后，我们后退-我们走到那个节点的一个层次，父节点，并检查是否还有可能，我们还没有探索。如果是，我们通过创建相应的子节点来探索它们；如果不，我们将再次回溯，上升到另一个级别，直到我们找到了问题的解决方案(所有皇后都被放置)，或者我们扩展了根节点的所有子节点，并在回溯操作中到达根节点--这意味着没有解决方案。
https://stackoverflow.com/questions/10442850
复制相似问题
腾讯云开发者
