我正在阅读回溯算法设计技术。如下所述。
回溯是蛮力方法的改进，它系统地在所有可用选项中搜索问题的解决方案。它通过假设解决方案由值的向量(v1, v2, ..., vm)表示，并以深度优先的方式遍历向量的域，直到找到解决方案。
我对上述文字的问题如下。
作者所说的解决方案由向量表示是什么意思？
作者所说的向量域是什么意思？
感谢您的澄清。
问问题
1252 次
1 回答
3
我们以八皇后问题为例。
解是一个 8 个位置的向量，每个皇后 1 个。向量属于空间：([0,7]x[0,7])^8。这是一个非常大的空间，因此回溯算法将使用条件：“没有皇后应该检查另一个皇后”，以限制([0,7]x[0,7])^8存在解向量的较小“域”（的子空间）。
在这种情况下，算法将通过尝试第一个皇后的允许值之一来创建一个解向量，给出向量：[ (0,0), X, X, X ...]。然后使用该条件，它将限制应该搜索第二个位置的子空间，并继续这样做，直到找到合适的向量。
深度优先意味着在移动到解决方案的域之前，[ (0,1), X, X, X ...]算法将耗尽定义域中的所有潜在向量[ (0,0), X, X, X ...]
于 2012-05-02T12:04:02.503 回答