回溯法在问题的解空间树中,按深度优先策略,从根结点出发搜索解空间树。算法搜索至解空间树的随意一点时,先推断该结点是否包括问题的解。假设肯定不包括,则跳过对该结点为根的子树的搜索,逐层向其祖先结点回溯;否则,进入该子树,继续按深度优先策略搜索。 回溯法:为了避免生成那些不可能产生最佳解的问题状态,要不断地利用限界函数(bounding function)来处死那些实际上不可能产生所需解的活结点,以降低问题的计算量。具有限界函数的深度优先生成法称为回溯法 回溯法基本思想: (1)针对所给问题,定义问题的解空间; (2)确定易于搜索的解空间结构; (3)以深度优先方式搜索解空间,并在搜索过程中用剪枝函数避免无效搜索 用递归方法实现回溯法。 void backtrack (int t) { if (t>n) output(x); else for (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); else t++;} } else t--; } } 遍历子集树 void backtrack (int t) { if (t>n) output(x); else for (int i=0;i<=1;i++) { x[t]=i; if (legal(t)) backtrack(t+1); } } 遍历排列树 void backtrack (int t) { if (t>n) output(x); else for (int i=t;i<=n;i++) { swap(x[t], x[i]); if (legal(t)) backtrack(t+1); swap(x[t], x[i]); } }
转载于:https://www.cnblogs.com/bhlsheji/p/4027195.html
相关资源:数据结构—成绩单生成器
转载请注明原文地址: https://win8.8miu.com/read-1551522.html