四后问题
描述
在4 * 4的方格棋盘上放置4个皇后棋子，使得没有两个皇后在同一行、同一列，也不在同一条45度的斜线上，问有多少种布局?
回溯算法的解一般是向量，而这个题也不例外，设4维向量的<x1,x2,x3,x4>，Xi中i表示第几个皇后，Xi表示在棋盘第i行的位置，比如其中一个解是<2,4,1,3>，如下图
分析此类问题，我们知道每个皇后在每一行都有4种取值方式，因此这是一颗n叉树，但是取值必须满足题干条件，可以作为开启回溯的条件。
流程
我们采用深度优先的方式进行分析，
1.第一行将第一个皇后放在第一列
2.第二行放在第一列，因为和第一个皇后同一列了，就触发回溯。
2.第二行放在第二列，因为和第一个皇后处于45°的位置，触发回溯。
3.第二行放在第三列，满足，继续进入第三列
4....
结论
1.四皇后问题中，叶节点就是一个解。
2.四皇后每一个节点的子树代表着下一个皇后可以放的列数，因为都是n，所以子树都是n叉树，故四皇后是一颗n叉树
3.四皇后的解至少有两个，因为棋盘可以沿着中心线翻折
0-1背包问题
描述
有n种物品，每种物品只有1个。第i种物品价值为vi，重量为wi，i=1，2，3...n.问如何选择放入背包的物品，使得总重量不超过B，而价值达到最大?
同样，此问题的解可用一个向量来表示，该向量就代表了所有的物品，如果对应物品为1，则表示装入背包，反之，没有被装入。
因此，回溯的每层可以表示为对应的物品，分支左右可以表示取或者不取（向量中表示为1或0）
总而言之，每一个节点也就是物品只有0和1两种状态，因此该树一棵二叉树，或者为子集树
流程
1.选择第一个物品，目前总重量为8，总价值为12。
2.再选择第二个物品，总重量为14 > 13，触发回溯。
3.不选择第二个物品，选择第三个商品，总重量是12，总价值为21。
4.再选择第四个物品，总重量为15 > 13，触发回溯。
5.不选择第四个物品，总重量为12，总价值为21，与目前最优解价值进行比较，如果最优解价值大于21则替换目前的最优解向量和最优解价值。
结论
1.背包问题只有在叶节点才能生成一个满足条件的解，而之后将该解和最优解比较。
2.背包问题必须遍历完所有的分支，才能够获得最终的解。
3.背包问题是一颗子集树。
货郎问题
描述
有n个城市，已知任两个城市之间的距离，求一条每个城市恰好经过一次的回路，使得总长度最小。
货郎问题中主要的一点就是每一个点（除了第一个点）其他点必须经过且只能经过1次，这就很像数学中的排列。
因此，我们采用一个向量来表示货郎问题的城市排列
流程
1.选择第一个城市作为起点，还有 3种选择方式，因此子树为一棵三叉树。
2.选择第二个城市，还有两种选择方式，因此子树为一棵二叉树，
3.选择第三个城市，只有一种选择，选择第四个城市。
4.叶节点计算所有的边长以及最后后一个节点到初始节点的和，也就是距离和。
5.与最短距离和比较，如果更小，记录最短路径值与最短路径向量解。
注意，货郎问题中不是每一个城市之间都可以互通的，也就是说不一定是一个团，如果碰到一个城市到不到未选城市中任何一个或者最后一个城市不可达开始城市，那么算法应该直接回溯。
结论
1.货郎问题是一颗分支不断减少的排列数（和数学的排列类似）
2.货郎问题也得遍历完所有的情况，比较后得出最优解。
回溯算法的特点
1.解都是用向量表示
2.搜索空间都是树
3.搜索策略多种，有深度优先、宽度优先和跳跃式遍历搜索树。
