贪心算法_回溯法_分支限界.ppt

5.1 回溯法的基本思想 （3）状态空间树的动态有哪些信誉好的足球投注网站 例：0/1背包问题， n=3, w=[16,15,15], p=[45,25,25], c=30 5.1 回溯法的基本思想 （3）状态空间树的动态有哪些信誉好的足球投注网站 例：回溯法有哪些信誉好的足球投注网站解空间树时，通常采用两种策略避免无效有哪些信誉好的足球投注网站。 其一，用约束函数在扩展结点出剪去不满足约束的子树； 其二，用限界函数剪去得不到最优解的子树。 这两类函数通称为剪枝函数。 5.2 回溯法的算法框架 递归回溯的一般解法： Void traceback(int t) { If(tn) output(x); Else for(i=f(n,t);i=g(n,t);i++){ x[t]=h[i]; if(constraint(t)bound(t)) trackback (t+1); } } 5.2 回溯法的算法框架 迭代回溯的一般解法： Void iterativeBacktrack(int t) {t=1; While(t0){ if(f(n,t)=g(n,t)) for(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---; } } 5.5 回溯法的应用—0/1背包问题 int c,n,w[],p[],cw,cp,bestp; void backtrack(int i){ if(in){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) backtrack(i+1); } int bound( int i){ int cleft=c-cw; int bound=cp; while(i=nw[i]=cleft){ cleft-=w[i]; bound+=p[i]; i++; } if(i=n) bound+=pi]/w[i]*cleft; return bound; } 第六章 分支限界法(Branch and bound) 6.1 分支限界法的基本思想 6.2 0-1背包问题 6.3 回溯法与分支限界法对比 6.1 分支限界法的基本思想 1. 分支限界法与回溯法的不同 （1）求解目标：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。 （2）有哪些信誉好的足球投注网站方式的不同：回溯法以深度优先的方式有哪些信誉好的足球投注网站解空间树，而分支限界法则以广度优先或以最小耗费优先的方式有哪些信誉好的足球投注网站解空间树。 6.1 分支限界法的基本思想 2. 分支限界法基本思想 分支限界法常以广度优先或以最小耗费（最大效益）优先的方式有哪些信誉好的足球投注网站问题的解空间树。 在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。 此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。 6.1 分支限界法的基本思想 3. 常见的两种分支限界法 (两种选择下一个E节点的方法：) （1）队列式(FIFO)分支限界法 按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。 （2）优先队列式分支限界法 按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。 6.2 0-1背包问题 例：n=3,w=[16,15,15],p=[45,25,25],c=30 队列式(FIFO)分支限界法 A B C D E F G N O L M J K H I 1 1 1 1 1 1 1 0 0 0 0 0 0 6.2 0-1背包问题 优先队列式分支限界法 算法的思想 首先，要对输入数据进行预处理，将各物品依其单位重量价值从大到小进行排列。 在下面描述的优先队列分支限界法中，节点的优先级由已装袋的物品价值加上剩下的最大单位重量价值的物品装满剩余容量的价值和。 算法首先检查当前扩展结点的左儿子结点的可行性。如果该左儿子结点是可行结点，则将它加入到子集树和活结点优先队列中。当前扩展结点的右儿子结点一定是可行结点，仅当右儿子结点满足上界约束时才将它加入子集树