algorithm - 回溯算法设计技术定义

Question

我正在阅读有关回溯算法设计技术的文章。提述如下。

Backtracking is a refinement of the brute force approach, which systematically searches for a solution to a problem among all available options. It does so by assuming that the solutions are represented by vectors (v1, v2, ..., vm) of values and by traversing, in a depth first manner, the domains of the vectors until the solutions are found.

我对以上文字的提问如下。

1. 作者所说的解决方案由向量表示是什么意思？

2. 作者所说的向量域是什么意思？

感谢您的澄清。

Answer 1

我们以八皇后问题为例。

解决方案是一个包含 8 个位置的向量，每个皇后 1 个。向量属于空间:([0,7]x[0,7])^8。这是一个非常大的空间，所以回溯算法将使用条件:'no queen should check another queen'，限制到一个较小的'domain'(的子空间([0,7]x[0,7 ])^8) 存在解向量的地方。

在这种情况下，算法将通过尝试第一个皇后的允许值之一来创建解决方案向量，给出向量:[ (0,0), X, X, X ...]。然后使用条件限制第二个位置应该搜索的子空间，一直这样做直到找到合适的向量。

深度优先意味着在移动到解决方案的域之前 [ (0,1), X, X, X ...] 该算法将耗尽定义域中的所有潜在向量通过 [ (0,0), X, X, X ...]