算法设计（第7章回溯和分支限界）

算法设计（第7章回溯和分支限界）7.1回溯和分支限界法的根本思想状态空间:问题〔实例〕的所有可能解0-1背包问题:{0,1}n旅行商问题:perms(V)7.1回溯和分支限界法的根本思想状态空间:问题〔实例〕的所有可能解穷举法:搜索整个状态空间0-1背包问题:{0,1}n旅行商问题:perms(V)O(n2n)O(n!)7.1回溯和分支限界法的根本思想状态空间:问题〔实例〕的所有可能解穷举法:搜索整个状态空间高效算法:缩小搜索空间(放弃无用的那局部状态空间)0-1背包问题:{0,1}n旅行商问题:perms(V)O(n2n)O(n!)剪枝7.1回溯和分支限界法的根本思想剪枝约束函数:除去违反约束条件的解限界函数:放弃不可能到达最优解的路径7.1回溯和分支限界法的根本思想搜索策略深度优先:回溯广度优先:分支限界7.20-1背包问题输入：n件物品的集合S(其中第i件物品的重量和价值分别为S[i].w和S[i].v)，以及背包的最大承重量W输出：S的一个子集A，其重量之和不大于W，且价值之和最大

w

vS:(3,8)(20,50)(5,12)(10,21)(5,10)W=307.20-1背包问题限界函数：当前背包价值加上剩余所有物品的价值30,0127,817,58第1个可行解:11100(70)12,7002,7002,70

w

vS:(3,8)(20,50)(5,12)(10,21)(5,10)W=3007,58bound:58+21+10=897.20-1背包问题限界函数：当前背包价值加上剩余所有物品的价值30,0127,817,58第1个可行解:11100(70)12,7002,7002,70

w

vS:(3,8)(20,50)(5,12)(10,21)(5,10)W=3007,58bound:58+10=6807,587.20-1背包问题限界函数：当前背包价值加上剩余所有物品的价值30,0127,817,58第1个可行解:11100(70)12,7002,7002,70

w

vS:(3,8)(20,50)(5,12)(10,21)(5,10)W=3007,58bound:8+12+21+10=5107,58027,87.20-1背包问题限界函数：当前背包价值加上剩余所有物品的价值30,0127,817,58第1个可行解:11100(70)12,7002,7002,70

w

vS:(3,8)(20,50)(5,12)(10,21)(5,10)W=3007,58bound:50+12+21+10=9307,58027,8030,07.20-1背包问题限界函数：当前背包价值加上剩余所有物品的价值30,0127,817,58第1个可行解:11100(70)12,7002,7002,70

w

vS:(3,8)(20,50)(5,12)(10,21)(5,10)W=3007,58bound:50+12+21+10=9307,58027,8030,0110,5015,627.20-1背包问题限界函数：当前背包价值加上剩余所有物品的价值30,0127,817,58第1个可行解:11100(70)12,7002,7002,70

w

vS:(3,8)(20,50)(5,12)(10,21)(5,10)W=3007,58bound:62+10=7207,58027,8030,0110,5015,6205,627.20-1背包问题限界函数：当前背包价值加上剩余所有物品的价值30,0127,817,58当前最优解:01101(72)12,7002,7002,70

w

vS:(3,8)(20,50)(5,12)(10,21)(5,10)W=3007,5807,58027,8030,0110,5015,6205,6210,727.20-1背包问题限界函数：当前背包价值加上剩余所有物品的价值30,0127,817,58当前最优解:01101(72)12,7002,7002,70

w

vS:(3,8)(20,50)(5,12)(10,21)(5,10)W=3007,58bound:50+21+10=8107,58027,8030,0110,5015,6205,6210,72010,5010,717.20-1背包问题限界函数：当前背包价值加上剩余所有物品的价值30,0127,817,58当前最优解:01101(72)12,7002,7002,70

w

vS:(3,8)(20,50)(5,12)(10,21)(5,10)W=3007,58bound:50+10=6007,58027,8030,0110,5015,6205,6210,72010,5010,7100,71010,507.20-1背包问题限界函数：当前背包价值加上剩余所有物品的价值30,0127,817,58当前最优解:01101(72)12,7002,7002,70

w

vS:(3,8)(20,50)(5,12)(10,21)(5,10)W=3007,58bound:12+21+10=4107,58027,8030,0110,5015,6205,6210,72010,5010,7100,71010,5000,307.20-1背包问题限界函数：当前背包价值加上剩余所有物品的价值30,0127,817,58当前最优解:01101(72)12,7002,7002,70

w

vS:(3,8)(20,50)(5,12)(10,21)(5,10)W=3007,5807,58027,8030,0110,5015,6205,6210,72010,5010,7100,71010,5000,307.20-1背包问题FunctionRec_Backtrack_Knapsack(i,cw,cv,W:int;S:Item[];x:int[];v_best:refint;x_best:refint[])beginletn=|S|;if(i=n)then//搜索到叶节点if(cv>v_best)then(x_best,v_best)(x,cv);return;if(cw+S[i].w≤W)thencwcw+S[i].w;cvcv+S[i].v;x[i]1;Rec_Backtrack_Knapsack(i+1,cw,cv,W,S,x,refv_best,refx_best);//左子树

cwcw–S[i].w;cvcv–S[i].v;//回溯到当前节点

if(Bound(i+1,cw,cv,S)>v_best)thenx[i]0;Rec_Backtrack_Knapsack(i+1,cw,cv,W,S,x,refv_best,refx_best);//右子树7.20-1背包问题AlgorithmRec_Backtrack_Knapsack(W:int;S:Item[])beginletn=|S|;letx=newint[n];let(x_best,v_best)=GetFirstSolution(W,S);Rec_Backtrack_Knapsack(0,0,0,W,S,x,refv_best,refx_best);return(x_best,v_best);end7.3旅行商问题输入：一个加权连通图G=<V,E,w>输出：通过G中所有顶点且距离最短的一条回路7.3旅行商问题限界函数：当前路径长度0b10c18d40e54ae26d377.3旅行商问题限界函数：当前路径长度0b10c18d40e54ae26d37d23c457.3旅行商问题限界函数：当前路径长度0b10c18d40e54ae26d37d23c45e28c63e29c377.3旅行商问题限界函数：当前路径长度0b10c18d40e54ae26d37d23c45e28c63e29c37d34c837.3旅行商问题限界函数：当前路径长度0b10c18d40e54ae26d37d23c45e28c63e29c37d34c83c27b35d487.3旅行商问题限界函数：当前路径长度0b10c18d40e54ae26d37d23c45e28c63e29c37d34c83c27b35d48e547.3旅行商问题限界函数：当前路径长度0b10c18d40e54ae26d37d23c45e28c63e29c37d34c83c27b35d48e54d497.3旅行商问题限界函数：当前路径长度0b10c18d40e54ae26d37d23c45e28c63e29c37d34c83c27b35d48e54d49e35b547.3旅行商问题限界函数：当前路径长度0b10c18d40e54ae26d37d23c45e28c63e29c37d34c83c27b35d48e54d49e35b54d407.3旅行商问题限界函数：当前路径长度0b10c18d40e54ae26d37d23c45e28c63e29c37d34c83c27b35d48e54d49e35b54d40d6b19c27e44e387.3旅行商问题限界函数：当前路径长度0b10c18d40e54ae26d37d23c45e28c63e29c37d34c83c27b35d48e54d49e35b54d40d6b19c27e44e38c28b36e54e36b55e11b30c65c19b377.3旅行商问题FunctionRec_Backtrack_TSP(V:set<int>;w:int[,];i,cv:int;x:int[];v_best:refint;x_best:refint[])beginletn=|V|;if(i=n)then//搜索到叶节点cvcv+w[x[n-1],V[0]];if(cv<v_best)then(x_best,v_best)(x,cv);return;foreach(uVux[0..i-1])doif(cv+w[x[i-1],u]<v_best)thenx[i]u;cvcv+w[x[i-1],u];Rec_Backtrack_TSP(V,w,i+1,cv,x,refv_best,refx_best);//递归搜索

x[i]0;//回溯到当前节点cvcv-w[x[i-1],u];end7.3旅行商问题AlgorithmRec_Backtrack_TSP(V:set<int>;E:set<intint>;w:int[,])beginletx=newint[|V|];let(x_best,v_best)=GetFirstSolution(V,w);Rec_Backtrack_TSP(V,w,0,cv,x,refv_best,refx_best)returnv_best;end7.4图着色问题输入：一个连通图G=<V,E>输出：对该图进行不相邻着色所需的最小色数k7.4图着色问题剪枝策略：当前着色树是否已大于等于最优解AlgorithmBacktrack_MinColoring(G:Graph)beginletn=|G.V|,k=,x=newint[n],p=newint[n],i=1;x[0]1;while(i>0)doletj=p[i];while(j<k)doif(d:0d<i:x[d]=j(G.V[d],G.V[i])G.E)thenjj+1;elsebreak;if(jk)then//回溯ii-1;