回溯法：具有限界凼数的深度优先搜索法称为回溯法，具有“通用解题法”之称
两类问题：存在性问题：求满足某些条件的一个或全部元组，这些条件称为约束条件。

如果不存在这样的元组，算法应返回No；优化问题：给定一组约束条件，在满足约束条件的元组中求使某目标函数达到最大（小）值的元组。

满足约束条件的元组称为问题的可行解。

回溯法和分支限界法不同：每次只构造侯选解的一个部分，然后评估这个部分构造解，如果加上剩余的分量也不可能求得一个解,就绝对不会生成剩下的分量
问题的解向量：回溯法希望一个问题的解能够表示成一个n元式(x1,x2,…,xn)的形式。

显约束：对分量xi的取值限定。

隐约束：为满足问题的解而对不同分量之间施加的约束。

解空间：对于问题的一个实例，解向量满足显式约束条件的所有多元组，构成了该实例的一个解空间。

为了避免生成那些不可能产生最佳解的问题状态，要不断地利用限界凼数来处死那些实际上不可能产生所需解的活结点，以减少问题的计算量。

解空间：子集树。

可行性约束凼数：Σwixi≤C 上界凼数： Bound()
子集树回溯框架：void backtrack (int t){if(t>n) output(x);elsefor(int i=f(n,t);i<=g(n,t);i++) {x[t]=h(i);if (constraint(t)&&bound(t)) backtrack(t+1);}}//递归方法
void iterativeBacktrack(){int t=1;while(t>0){if(f(n,t)<=g(n,t)) for (int i=f(n,t);i<=g(n,t);i++) {x[t]=h(i);if(constraint(t)&&bound(t)) {if(solution(t)) output(x);elset++;}}elset--;}}//迭代方法
回溯法求解步骤1、针对所给问题，定义问题的解空间；2、确定易于搜索的解空间结构；3、以深度优先方式搜索解空间，并在搜索过程中用剪枝凼数避免无效搜索。

限界凼数(上界的计算方法) :r是当前尚未考虑的剩余物品价值总和,cp是当前价值,bestp是当前最优价值. 当cp+r<=bestp时,可剪去右子树贪心策略计算方法：将剩余物品按照单位重量价值排序,然后依次装入物品,直至装不下时,再装入该物品的一部分而装满背包.该价值是右子树中解的一个上界. Bound(int i){ Typew cleft=c-cw; Typep b=cp; while(i<=n&&w[i]<=cleft){cleft-=w[i]; b+=p[i]; i++;}if (i<=n) b+=p[i]/w[i]*cleft;return b;}//计算上界
常用剪枝凼数：用约束凼数在扩展结点处剪去丌满足约束的子树；用限界凼数剪去得不到最优解的子树。

剪枝策略Constraint(t): True:当前扩展结点处的取值满足问题的约束条件False:当前扩展结点处的取值不满足问题的约束条件, 可剪去子树。

Bound(t):True:当前扩展结点处的取值未使目标凼数越界False:当前扩展结点处的取值已使目标凼数越界,可剪去子树
0-1背包问题
子集树:当所给的问题是从n个元素的集合S中找出满足某种性质的子集时相应的解空间树。

0/1背包问题子集树通常有2n个叶结点，结点总数为2n+1-1。

遍历解空间树需要Ω(2n)的计算时间
0-1背包回溯法伪码：Backtrack(int i){if (i>n){ bestp=cp; return;} if (cw+w[i]<=c){ cw+=w[i]; cp+=p[i]; Backtrack(i+1); cw-=w[i];cp-=p[i];}if (Bound(i+1)>bestp) //x[i]=0; 右子树Backtrack(i+1); }
装载问题策略：(1)首先将第一艘轮船尽可能装满；(2)将剩余的集装箱装上第二艘轮船。

用回溯法设计解装载问题的O(2n)计算时间算法。

上界凼数(不选择当前元素)：当前载重量cw+剩余集装箱的重量r<=当前最优载重量bestw
解空间树。