我正在阅读有关回溯算法设计技术的文章 . 提到如下 .
回溯是蛮力方法的改进,它系统地在所有可用选项中搜索问题的解决方案 . 它通过假设解决方案由值的向量(v1,v2,...,vm)表示并且以深度优先的方式遍历向量的域直到找到解决方案来这样做 .
我对以上文字的质疑如下 .
作者用解决方案表示什么意思?
作者对载体的含义是什么意思?
谢谢你的澄清 .
我们以八皇后问题为例 .
解决方案是8个位置的向量,每个位置1个 . 向量属于空间: ([0,7]x[0,7])^8 . 这是一个非常大的空间,因此回溯算法将使用条件:'no queen should check another queen',以限制存在解向量的较小'domain'(子空间 ([0,7]x[0,7])^8 ) .
([0,7]x[0,7])^8
在这种情况下,算法将通过尝试第一个女王的允许值之一来创建解向量,给出向量: [ (0,0), X, X, X ...] . 然后使用条件,它将限制应搜索第二个位置的子空间,并继续这样做,直到找到合适的向量 .
[ (0,0), X, X, X ...]
深度优先意味着在移动到解决方案的域之前_1186621_算法将耗尽 [ (0,0), X, X, X ...] 定义的域中的所有潜在向量
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 ...]
. 然后使用条件,它将限制应搜索第二个位置的子空间,并继续这样做,直到找到合适的向量 .深度优先意味着在移动到解决方案的域之前_1186621_算法将耗尽
[ (0,0), X, X, X ...]
定义的域中的所有潜在向量