《数据结构16.ppt》由会员分享，可在线阅读，更多相关《数据结构16.ppt（84页珍藏版）》请在课桌文档上搜索。
1、第16章 回溯,学习内容,算法思想应用八皇后问题货箱装船0/1背包问题最大完备子图问题旅行商问题电路板排列,16.1 算法思想,在众多可能解中搜索可行解/最优解解空间至少包含一个可行解迷宫老鼠问题：入口出口的所有路径n个对象的0/1背包问题：所有n位二进制数，每个二进制位表示对象是否放入背包如何组织解空间？树或图,例16.1 迷宫问题,活节点，E节点,例16.1 迷宫问题（续）,开始节点为活节点，E节点若当前E节点可移动到一个新节点，则新节点变为活节点和新的E节点，旧节点仍为活节点若不能移动到新节点，则当前E节点变为“死节点”，需返回最近考察的活节点（回溯），该节点重新成为E节点,例16.2
2、0/1背包问题,n=3，w=20,15,15，p=40,25,25且c=30节点B：r=10,cp=40；移动到D不可行，E可行节点E，移动到J不可行，K可行可行解回溯到AC：r=30,cp=0，FL最优解,例16.3 旅行商问题,给定n顶点网络，找出包含所有顶点的最小耗费环路商人在城市间旅行，寻找最小花费（时间）的旅行下图：13241，耗费25,例16.3 旅行商问题（续）,钻孔问题、批量生产问题,回溯算法框架,子集树、排列树简单回溯：计算量太大加速分支限界函数不考察不可能产生最优解的节点,回溯算法框架,回溯法基本步骤定义一个解空间，它包含问题的解用适于搜索的方式组织该空间用深度优先搜索该空
3、间，用限界函数加速搜索同时产生解空间内存需求：开始节点起最长路径长度,16.2 应用,八皇后问题在国际象棋棋盘上放置8个皇后任何两个皇后之间都不能相互攻击,解决方法,随机放置显然不行，也不存在某种规则无遗漏地找出所有解，非常困难solve_from(Queens configuration)if configuration 已包含8个皇后打印结果elsefor configuration中每个未被攻击的位置p 在configuration中位置p添加一个皇后solve_from(configuration);将configuration中位置p的皇后去掉,四皇后问题求解示例,主函数,int m
4、ain()int board_size;print_information();cout board_size;if(board_size max_board)cout The number must be between 0 and max_board endl;else Queens configuration(board_size);/初始化空棋局 solve_from(configuration);/搜索所有解,回溯函数,void solve_from(Queens,Queens类,应提供的方法打印棋局添加皇后（向下一节点移动）删除皇后（回溯）判定棋盘格是否受到皇后攻击添加皇后不必尝试
5、每个棋盘格每个皇后必定独自占据一行、一列每行放置一个皇后count：已放置皇后数目下一皇后行号,Queens类定义,const int max_board=30;class Queens public:Queens(int size);bool is_solved()const;void print()const;bool unguarded(int col)const;void insert(int col);void remove(int col);int board_size;/棋盘大小要放置的皇后数目private:int count;/已放置皇后数目，下一个皇后所在行号 bool q
6、ueen_squaremax_boardmax_board;,构造函数和添加函数,Queens:Queens(int size)board_size=size;count=0;for(int row=0;row board_size;row+)for(int col=0;col board_size;col+)queen_squarerowcol=false;void Queens:insert(int col)queen_squarecount+col=true;,unguarded函数算法,是否受到攻击所在行、列、对角线是否有皇后行无需检查，放置方法已予以保证,列的检查,简单,对角线的检查
7、,对角线的检查（续）,四个方向：左上、左下、右上、右下以左上为例当前棋盘格rowcol要检查的棋盘格row-icol-i（i0）终止条件：row i=0（上边界）col i=0（左边界）循环条件row i=0&col i=0左下、右下无需检查下方还未放皇后,unguarded函数实现,bool Queens:unguarded(int col)const int i;bool ok=true;/如果在列和对角线上发现其它皇后，置为false，不再进行检查 for(i=0;ok,优化,上述简单算法对8皇后问题已足够但当棋盘规模增大，运行时间急剧增加,程序瓶颈在哪里？,递归调用和回溯过程，耗费了很
8、多时间，但这是程序的基本算法和框架，没有优化余地unguarded函数，使用了多个循环，耗费很多时间可考虑进行优化,unguarded函数的优化思想,关键每列、每行、每条对角线都至多允许放置一个皇后使用三个bool类型数组col_freei：真第i列没有皇后upward_freei：真第i个左下右上的对角线没有皇后downward_freei：真左上右下的对角线没有皇后,上对角线的处理,最长的左下右上对角线board_size-10,board_size-21,.,0board_size-1行列下标之和为定值row+col=(row i)+(col+i)用此值标识对角线左上角对角线（只含一个棋
9、盘格），此值为0向右下，第二条对角线，1.右下角最后一条对角线，2*board_size-2棋盘格(i,j)，所在左上对角线为i+j,下对角线的处理,行列下标之差为定值row col=(row+i)(col+i)取值范围-board_size+1board_size-1调整为02*board_size-1棋盘格(i,j)所在下对角线为i j+board_size 1一个棋盘格是否安全三个数组对应元素是否全为真,新的Queens类,class Queens public:Queens(int size);bool is_solved()const;void print()const;bool u
10、nguarded(int col)const;void insert(int col);void remove(int col);int board_size;private:int count;bool col_freemax_board;bool upward_free2*max_board-1;bool downward_free2*max_board-1;int queen_in_rowmax_board;/每个皇后所在列号;,构造函数,Queens:Queens(int size)board_size=size;count=0;for(int i=0;i board_size;i+)
11、col_freei=true;for(int j=0;j(2*board_size-1);j+)upward_freej=true;for(int k=0;k(2*board_size-1);k+)downward_freek=true;,放置皇后,void Queens:insert(int col)queen_in_rowcount=col;col_freecol=false;upward_freecount+col=false;downward_freecount-col+board_size-1=false;count+;,unguarded函数,bool Queens:unguard
12、ed(int col)const return col_freecol,优化效果,算法分析,皇后放置在棋盘任意8个位置限制每行放置一个皇后：88=16,777,216再限制每列只放置一个：8!=40,320再考虑对角线，搜索范围进一步缩小回溯法高效的原因剪枝搜索树，每个节点最多8个子节点对死节点不再向下搜索,搜索树,16.2.1 货箱装船问题,两艘船，载重量分别为c1和c2n个货箱，第i个重量为wi，且寻找将所有货箱装船的方法例16.4n=3，c1=c2=50，w=10,40,40，将货箱1、2装入1号船，货箱3装入2号船若w=20,40,40，则不存在装船方案,货箱装船问题,若 子集之和问题
13、：有n个数，找到一个子集使其和为c1若 分割问题：有n个数ai，找到子集使其和为NP问题,算法思想,若存在装船方案，则如下策略必然可找到一个装船方案尽可能将第一艘船装至重量极限将剩余货箱装入2号船第一步寻找货箱子集，总重量尽可能接近c10/1背包问题当重量为整数动态规划算法，O(minc1,2n)否则，回溯算法,第一种回溯算法,例16-5：n=4,w=8,6,2,3,c1=12,cw=8,cw=14，,cw=8,cw=10,cw=13，,cw=11,1,1,算法实现Loading类,templateclass Loading friend MaxLoading(T,T,int);private
14、:void maxLoading(int i);int n;/number of containers T*w,/container weight array c,/capacity of first ship cw,/weight of current loading bestw;/weight of best loading so far;,算法实现（续）递归函数,templatevoid Loading:maxLoading(int i)/Search from level i node.if(i n)/at a leaf if(cw bestw)bestw=cw;return;/che
15、ck subtrees if(cw+wi=c)/try xi=1 cw+=wi;maxLoading(i+1);cw-=wi;maxLoading(i+1);/try xi=0,算法实现（续）递归函数,templateT MaxLoading(T w,T c,int n)/Return weight of best loading.Loading X;/initialize X X.w=w;X.c=c;X.n=n;X.bestw=0;X.cw=0;/compute weight of best loading X.maxLoading(1);return X.bestw;,第二种回溯算法,利用
16、限界函数加速搜索：如果右子树不可能产生更好的解，不对它进行搜索已得到的最优解为bestw，Z是当前搜索第i层节点，若cw+rbestw，则无需搜索Z的右子树,例16.6,K的右子树和C的右子树都无需搜索,cw=8,cw=14，,cw=8,cw=10,cw=13，,cw=11,1,1,算法实现,templatevoid Loading:maxLoading(int i)/Search from level i node.if(i n)/at a leaf bestw=cw;return;/check subtrees r-=wi;if(cw+wi bestw)/try xi=0 maxLoadi
17、ng(i+1);r+=wi;,算法实现（续）,templateT MaxLoading(T w,T c,int n)/Return weight of best loading.Loading X;/initialize X X.w=w;X.c=c;X.n=n;X.bestw=0;X.cw=0;/initial r is sum of all weights X.r=0;for(int i=1;i=n;i+)X.r+=wi;/compute weight of best loading X.maxLoading(1);return X.bestw;,保存装船方案,templatevoid Lo
18、ading:maxLoading(int i)/Search from level i node.if(i n)/at a leaf for(int j=1;j bestw)/try xi=0 xi=0;maxLoading(i+1);r+=wi;,优化方案保存,bestx最多更新O(2n)次，复杂性O(n2n)两种改进方法用第2个算法，不保存方案，获得最优装载重量W后。以bestw=W运行第3个算法的修改版本cw+rbestwcw+r=bestw，第一次到达某个叶节点即停止修改算法3，在回溯时保存最优方案。当前节点在第i层，则当前最优方案（路径）为x1,.,xi-1,bestxi,.,bes
19、txn,消除递归迭代版本,templateT MaxLoading(T w,T c,int n,int bestx)/Return best loading and its value./Iterative backtracking version./initialize for root int i=1;/level of current node/x1:i-1 is path to current node int*x=new int n+1;T bestw=0,/weight of best loading so far cw=0,/weight of current loading r
20、=0;/sum of remaining container weights for(int j=1;j=n;j+)r+=wj;,消除递归迭代版本（续）,/search the tree while(true)/move down and left as far as possible while(i=n,消除递归迭代版本（续）,if(i n)/leaf reached for(int j=1;j=n;j+)bestxj=xj;bestw=cw;else/move to right child r-=wi;xi=0;i+;,消除递归迭代版本（续）,/back up if necessary w
21、hile(cw+r 0,消除递归迭代版本（续）,if(i=0)delete x;return bestw;/move to right subtree xi=0;cw-=wi;i+;,16.2.2 0/1背包问题,与货船装载算法非常类似，在递归过程种计算最大收益即可限界函数简单方法：cp当前节点收益，r还未搜索的物品的收益总和，若r+cpbestp，则无需搜索右子树更好的方法：按收益密度pi/wi将剩余物品排序，按递减顺序填充背包，第一个不能完全放入的放入一部分获得的收益上界更精确,例16.7,n=4,c=7,p=9,10,7,4,w=3,5,2,1在根节点，收益密度排序为物品4、3、1、2，
22、得到的解为x=1,0.2,1,1，收益为22,cp=9,cw=3，最大收益22,cp=cw=0，最大收益19,cp=9,cw=3，最大收益20,算法实现knap类,templateclass Knap friend Tp Knapsack(Tp*,Tw*,Tw,int);private:Tp Bound(int i);void Knapsack(int i);Tw c;/knapsack capacity int n;/number of objects Tw*w;/array of object weights Tp*p;/array of object profits Tw cw;/wei
23、ght of current packing Tp cp;/profit of current packing Tp bestp;/max profit so far;,限界函数,templateTp Knap:Bound(int i)/Return upper bound on value of/best leaf in subtree.Tw cleft=c-cw;/remaining capacity Tp b=cp;/profit bound/fill remaining capacity/in order of profit density while(i=n,递归函数,templat
24、evoid Knap:Knapsack(int i)/Search from level i node.if(i n)/at a leaf bestp=cp;return;/check subtrees if(cw+wi bestp)/try xi=0 Knapsack(i+1);,Object类,class Object friend int Knapsack(int*,int*,int,int);public:int operator=a.d);private:int ID;/object identifier float d;/profit density;,主函数,templateTp
25、 Knapsack(Tp p,Tw w,Tw c,int n)/Return value of best knapsack filling./initialize for Knap:Knapsack Tw W=0;/will be sum of weights Tp P=0;/will be sum of profits/define an object array to be sorted by/profit density Object*Q=new Object n;for(int i=1;i=n;i+)/array of profit densities Qi-1.ID=i;Qi-1.d
26、=1.0*pi/wi;P+=pi;W+=wi;,主函数（续）,if(W K;K.p=new Tp n+1;K.w=new Tw n+1;for(i=1;i=n;i+)/Ps and Ws in density order K.pi=pQi-1.ID;K.wi=wQi-1.ID;,主函数（续）,K.cp=0;K.cw=0;K.c=c;K.n=n;K.bestp=0;/find best profit K.Knapsack(1);delete Q;delete K.w;delete K.p;return K.bestp;,16.2.3 完备子图问题,令U为无向图G的顶点子集，当且仅当对于U中任意顶
27、点u、v，(u,v)是G中的一条边时，称U定义了G的一个完全子图当且仅当一个完全子图不包含在另一个更大的完全子图中时，称它为图G的一个完备子图最大完备子图,例16.8,左图，1,2为完全子图，但不是完备子图，因为包含于1,2,5最大完备子图，1,4,5，2,3,5也是最大完备子图,独立集和补图,当且仅当对U中任意顶点u、v，(u,v)不是G中一条边，称U定义了G的一个空子图当且仅当一个空子图不包含于另一个更大的顶点集合时，称它为图G的一个独立集最大独立集对于任意图G，它的补图G是具体同样顶点集合的图，且当且仅当(u,v)不是G的一条边时，它是G的一条边,例16.9,两个图互为补图2,4是左图的
28、最大独立集，也是右图的最大完备子图，1,3、3,4也是1,2,5，1,4,5，2,3,5恰好相反U是G的完全子图，则它是G的空子图，反之亦然,最大完备子图问题,找出一个图G的最大完备子图最大独立集问题，都是NP问题15.2节的最大无交叉网组集合问题：网组顶点，交叉边算法与16.3非常相似关键是新加入的节点必须保证完全子图的定义,算法实现,void AdjacencyGraph:maxClique(int i)/Backtracking code to compute largest clique.if(i n)/at leaf/found a larger clique,update for(
29、int j=1;j=n;j+)bestxj=xj;bestn=cn;return;/see if vertex i connected to others/in current clique int OK=1;for(int j=1;j i;j+)if(xj,算法实现（续）,if(OK)/try xi=1 xi=1;/add i to clique cn+;maxClique(i+1);xi=0;cn-;if(cn+n-i bestn)/try xi=0 xi=0;maxClique(i+1);,主函数,int AdjacencyGraph:MaxClique(int v)/Return si
30、ze of largest clique./Return clique vertices in v1:n./initialize for maxClique x=new int n+1;cn=0;bestn=0;bestx=v;/find max clique maxClique(1);delete x;return bestn;,16.2.4 旅行商问题,templateT AdjacencyWDigraph:TSP(int v)/Traveling salesperson by backtracking./Return cost of best tour,return tour in v1
31、:n./initialize for tSP x=new int n+1;/x is identity permutation for(int i=1;i=n;i+)xi=i;bestc=NoEdge;bestx=v;/use array v to store best tour cc=0;/search permutations of x2:n tSP(2);delete x;return bestc;,递归回溯函数,/类似全排列函数templatevoid AdjacencyWDigraph:tSP(int i)/Backtracking code for traveling salesp
32、erson.if(i=n)/at parent of a leaf/complete tour by adding last two edges if(axn-1xn!=NoEdge,递归回溯函数（续）,else/try out subtrees for(int j=i;j=n;j+)/is move to subtree labeled xj possible?if(axi-1xj!=NoEdge,16.2.5 电路板排列,将n个电路板放置到一个机箱的许多插槽中，电路板的排列放置方法n个电路板B=b1,b2,.,bnm个网组集合L=N1,N2,.,NmNi是B的子集，子集中的元素应连接起来连
33、接插槽,例16.11,B=b1,b2,b3,b4,b5,b6,b7,b8L=N1,N2,N3,N4,N5N1=b4,b5,b6，N2=b2,b3，N3=b1,b3N4=b3,b6，N5=b7,b8,电路板排列问题,x：电路排列，电路板xi放置在插槽idensity(x)：机箱中任意一对相邻插槽间所连电线数目中最大值相邻插槽间距相同由density(x)决定寻找电路板排列方式，使density最小,电路板排列问题,nm数组B，Bij=1：Nj包含bitotalj：Nj中电路板数量nowj：既在x1:i中又在Nj中的电路板数量nowj0且nowjtotalj，Nj在插槽i和i+1之间有连线,算法实
34、现,class Board friend ArrangeBoards(int*,int,int,int);private:void BestOrder(int i,int cd);int*x,/path to current node*bestx,/best arrangement found so far*total,/totalj=number of boards/with net j*now,/nowj=number of boards in/partial arrangement with net j bestd,/density of bestx n,/number of board
35、s m,/number of nets*B;/2D board array;,递归回溯函数,void Board:BestOrder(int i,int cd)/Backtracking search of permutation tree.if(i=n)/all boards placed for(int j=1;j=n;j+)bestxj=xj;bestd=cd;else/try out subtrees for(int j=i;j=n;j+)/try child with board xj as next one,递归回溯函数（续）,/update now,递归回溯函数（续）,/sear
36、ch subtree only if it may/contain a better arrangement if(ld bestd)/move to child Swap(xi,xj);BestOrder(i+1,ld);Swap(xi,xj);/reset now for(k=1;k=m;k+)nowk-=Bxjk;,主函数,int ArrangeBoards(int*B,int n,int m,int bestx)/Return best density./Return best arrangement in bestx.Board X;/initialize X X.x=new int
37、 n+1;X.total=new int m+1;X.now=new int m+1;X.B=B;X.n=n;X.m=m;X.bestx=bestx;X.bestd=m+1;,主函数（续）,/initialize total and now for(int i=1;i=m;i+)X.totali=0;X.nowi=0;/initialize x to identity permutation/and compute total for(i=1;i=n;i+)X.xi=i;for(int j=1;j=m;j+)X.totalj+=Bij;,主函数（续）,/find best arrangement X.BestOrder(1,0);delete X.x;delete X.total;delete X.now;return X.bestd;,
