算法設(shè)計(jì)（第7章回溯和分支限界）7.1回溯和分支限界法的根本思想狀態(tài)空間:問題〔實(shí)例〕的所有可能解0-1背包問題:{0,1}n旅行商問題:perms(V)7.1回溯和分支限界法的根本思想狀態(tài)空間:問題〔實(shí)例〕的所有可能解窮舉法:搜索整個(gè)狀態(tài)空間0-1背包問題:{0,1}n旅行商問題:perms(V)O(n2n)O(n!)7.1回溯和分支限界法的根本思想狀態(tài)空間:問題〔實(shí)例〕的所有可能解窮舉法:搜索整個(gè)狀態(tài)空間高效算法:縮小搜索空間(放棄無用的那局部狀態(tài)空間)0-1背包問題:{0,1}n旅行商問題:perms(V)O(n2n)O(n!)剪枝7.1回溯和分支限界法的根本思想剪枝約束函數(shù):除去違反約束條件的解限界函數(shù):放棄不可能到達(dá)最優(yōu)解的路徑7.1回溯和分支限界法的根本思想搜索策略深度優(yōu)先:回溯廣度優(yōu)先:分支限界7.20-1背包問題輸入：n件物品的集合S(其中第i件物品的重量和價(jià)值分別為S[i].w和S[i].v)，以及背包的最大承重量W輸出：S的一個(gè)子集A，其重量之和不大于W，且價(jià)值之和最大

w

vS:(3,8)(20,50)(5,12)(10,21)(5,10)W=307.20-1背包問題限界函數(shù)：當(dāng)前背包價(jià)值加上剩余所有物品的價(jià)值30,0127,817,58第1個(gè)可行解: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背包問題限界函數(shù)：當(dāng)前背包價(jià)值加上剩余所有物品的價(jià)值30,0127,817,58第1個(gè)可行解: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背包問題限界函數(shù)：當(dāng)前背包價(jià)值加上剩余所有物品的價(jià)值30,0127,817,58第1個(gè)可行解: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背包問題限界函數(shù)：當(dāng)前背包價(jià)值加上剩余所有物品的價(jià)值30,0127,817,58第1個(gè)可行解: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背包問題限界函數(shù)：當(dāng)前背包價(jià)值加上剩余所有物品的價(jià)值30,0127,817,58第1個(gè)可行解: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背包問題限界函數(shù)：當(dāng)前背包價(jià)值加上剩余所有物品的價(jià)值30,0127,817,58第1個(gè)可行解: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背包問題限界函數(shù)：當(dāng)前背包價(jià)值加上剩余所有物品的價(jià)值30,0127,817,58當(dāng)前最優(yōu)解: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背包問題限界函數(shù)：當(dāng)前背包價(jià)值加上剩余所有物品的價(jià)值30,0127,817,58當(dāng)前最優(yōu)解: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背包問題限界函數(shù)：當(dāng)前背包價(jià)值加上剩余所有物品的價(jià)值30,0127,817,58當(dāng)前最優(yōu)解: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背包問題限界函數(shù)：當(dāng)前背包價(jià)值加上剩余所有物品的價(jià)值30,0127,817,58當(dāng)前最優(yōu)解: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背包問題限界函數(shù)：當(dāng)前背包價(jià)值加上剩余所有物品的價(jià)值30,0127,817,58當(dāng)前最優(yōu)解: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//搜索到葉節(jié)點(diǎn)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;//回溯到當(dāng)前節(jié)點(diǎn)

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è)加權(quán)連通圖G=<V,E,w>輸出：通過G中所有頂點(diǎn)且距離最短的一條回路7.3旅行商問題限界函數(shù)：當(dāng)前路徑長度0b10c18d40e54ae26d377.3旅行商問題限界函數(shù)：當(dāng)前路徑長度0b10c18d40e54ae26d37d23c457.3旅行商問題限界函數(shù)：當(dāng)前路徑長度0b10c18d40e54ae26d37d23c45e28c63e29c377.3旅行商問題限界函數(shù)：當(dāng)前路徑長度0b10c18d40e54ae26d37d23c45e28c63e29c37d34c837.3旅行商問題限界函數(shù)：當(dāng)前路徑長度0b10c18d40e54ae26d37d23c45e28c63e29c37d34c83c27b35d487.3旅行商問題限界函數(shù)：當(dāng)前路徑長度0b10c18d40e54ae26d37d23c45e28c63e29c37d34c83c27b35d48e547.3旅行商問題限界函數(shù)：當(dāng)前路徑長度0b10c18d40e54ae26d37d23c45e28c63e29c37d34c83c27b35d48e54d497.3旅行商問題限界函數(shù)：當(dāng)前路徑長度0b10c18d40e54ae26d37d23c45e28c63e29c37d34c83c27b35d48e54d49e35b547.3旅行商問題限界函數(shù)：當(dāng)前路徑長度0b10c18d40e54ae26d37d23c45e28c63e29c37d34c83c27b35d48e54d49e35b54d407.3旅行商問題限界函數(shù)：當(dāng)前路徑長度0b10c18d40e54ae26d37d23c45e28c63e29c37d34c83c27b35d48e54d49e35b54d40d6b19c27e44e387.3旅行商問題限界函數(shù)：當(dāng)前路徑長度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//搜索到葉節(jié)點(diǎn)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;//回溯到當(dāng)前節(jié)點(diǎn)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è)連通圖G=<V,E>輸出：對該圖進(jìn)行不相鄰著色所需的最小色數(shù)k7.4圖著色問題剪枝策略：當(dāng)前著色樹是否已大于等于最優(yōu)解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;