第8章 回溯法PPT讲稿.ppt

《第8章 回溯法PPT讲稿.ppt》由会员分享，可在线阅读，更多相关《第8章 回溯法PPT讲稿.ppt（51页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第8章章 回溯法回溯法第1页，共51页，编辑于2022年，星期一8.1 概概 述述 8.1.1 问题的解空间问题的解空间8.1.2 解空间树的动态搜索（解空间树的动态搜索（1）8.1.3 回溯法的求解过程回溯法的求解过程8.1.4 回溯法的时间性能回溯法的时间性能第2页，共51页，编辑于2022年，星期一 复复杂杂问问题题常常常常有有很很多多的的可可能能解解，这这些些可可能能解解构构成成了了问问题题的的解解空空间间。解解空空间间也也就就是是进进行行穷穷举举的的搜搜索索空空间间，所所以以，解解空空间间中中应应该该包包括括所所有有的的可可能能解解。确确定定正正确确的的解解空空间间很很重重要要，如

2、如果果没没有有确确定定正正确确的的解解空空间间就就开开始始搜搜索索，可可能能会会增增加加很很多多重重复复解解，或或者者根根本本就就搜搜索索不不到到正正确的解。确的解。8.1.1 问题的解空间问题的解空间 第3页，共51页，编辑于2022年，星期一(a)二维搜索空间无解 (b)三维搜索空间的解 图8.1 错误的解空间将不能搜索到正确答案例如：桌子上有6根火柴棒，要求以这6根火柴棒为边搭建4个等边三角形。第4页，共51页，编辑于2022年，星期一 对对于于任任何何一一个个问问题题，可可能能解解的的表表示示方方式式和和它它相相应应的的解解释释隐隐含含了了解空间及其大小。解空间及其大小。例例如如，对对

3、于于有有n个个物物品品的的0/1背背包包问问题题，其其可可能能解解的的表表示示方方式式可可以以有有以下两种：以下两种：（1）可可能能解解由由一一个个不不等等长长向向量量组组成成，当当物物品品i(1in)装装入入背背包包时时，解解向向量量中中包包含含分分量量i，否否则则，解解向向量量中中不不包包含含分分量量i，当当n=3时时，其其解解空空间间是：是：(),(1),(2),(3),(1,2),(1,3),(2,3),(1,2,3)（2）可能解由一个等长向量）可能解由一个等长向量x1,x2,xn组成，其中组成，其中xi=1(1in)表示物品表示物品i装入背包，装入背包，xi=0表示物品表示物品i没有

4、装入背包，当没有装入背包，当n=3时，其解空时，其解空间是：间是：(0,0,0),(0,0,1),(0,1,0),(1,0,0),(0,1,1),(1,0,1),(1,1,0),(1,1,1)第5页，共51页，编辑于2022年，星期一 为为了了用用回回溯溯法法求求解解一一个个具具有有n个个输输入入的的问问题题，一一般般情情况况下下，将将其其可可能能解解表表示示为为满满足足某某个个约约束束条条件件的的等等长长向向量量X=(x1,x2,xn)，其其中中分分量量xi(1in)的的取取值值范范围围是是某某个个有有限限集集合合Si=ai1,ai2,airi，所所有有可可能能的的解解向向量量构构成成了了问

5、问题的题的解空间解空间。第6页，共51页，编辑于2022年，星期一 问题的解空间一般用问题的解空间一般用解空间树解空间树（Solution Space Trees,也称状态空间树）的方式组织，树的也称状态空间树）的方式组织，树的根结点位于第根结点位于第1层，表示搜索的初始状态，第层，表示搜索的初始状态，第2层层的结点表示对解向量的第一个分量做出选择后到的结点表示对解向量的第一个分量做出选择后到达的状态，第达的状态，第1层到第层到第2层的边上标出对第一个分层的边上标出对第一个分量选择的结果，依此类推，从树的根结点到叶子量选择的结果，依此类推，从树的根结点到叶子结点的路径就构成了解空间的一个可能解

6、。结点的路径就构成了解空间的一个可能解。第7页，共51页，编辑于2022年，星期一对对于于n=3的的0/1背背包包问问题题，其其解解空空间间树树如如图图8.2所所示示，树树中中的的8个叶子结点分别代表该问题的个叶子结点分别代表该问题的8个可能解。个可能解。对物品对物品1的选择的选择对物品对物品3的选择的选择对物品对物品2的选择的选择1111110000000112345781112141531069第8页，共51页，编辑于2022年，星期一 对于n=4的TSP问题，其解空间树如图8.3所示，树中的24个叶子结点分别代表该问题的24个可能解，例如结点5代表一个可能解，路径为12341，长度为各边

7、代价之和。243422343413142412123312134131312321214241434322434123124134图图8.3 n=4的的TSP问题的解空间树问题的解空间树5710121517212326283133 37 3942444749525457596264469111416202225273032 36 3841434648515356586163381319242935404550556021834241123434第9页，共51页，编辑于2022年，星期一8.1.2 解空间树的动态搜索（解空间树的动态搜索（1）回回溯溯法法从从根根结结点点出出发发，按按照照深深度度

8、优优先先策策略略遍遍历历解解空空间间树树，搜搜索索满满足足约约束束条条件件的的解解。在在搜搜索索至至树树中中任任一一结结点点时时，先先判判断断该该结结点点对对应应的的部部分分解解是是否否满满足足约约束束条条件件，或或者者是是否否超超出出目目标标函函数数的的界界，也也就就是是判判断断该该结结点点是是否否包包含含问问题题的的（最最优优）解解，如如果果肯肯定定不不包包含含，则则跳跳过过对对以以该该结结点点为为根根的的子子树树的的搜搜索索，即即所所谓谓剪剪枝枝（PruningPruning）；否否则则，进进入入以以该该结结点点为为根的子树，继续按照深度优先策略搜索。根的子树，继续按照深度优先策略搜索。

9、第10页，共51页，编辑于2022年，星期一例如，对于n=3的0/1背包问题，三个物品的重量为20,15,10，价值为20,30,25，背包容量为25，从图8.2所示的解空间树的根结点开始搜索，搜索过程如下：1不可行解不可行解价值价值=20价值价值=55 价值价值=30 价值价值=25价值价值=01111000000112811121415131069不可行解不可行解第11页，共51页，编辑于2022年，星期一 再如，对于n=4的TSP问题，其代价矩阵如图8.5所示，C=3 6 712 2 8 8 6 2 3 7 6 图图8.5 TSP问题的代价矩阵问题的代价矩阵第12页，共51页，编辑于20

10、22年，星期一2344221231341313123212142414322434123124134图图8.6 TSP问题的搜索空间问题的搜索空间5475441127464851 535838132429354045505560218342412341第13页，共51页，编辑于2022年，星期一 回回溯溯法法的的搜搜索索过过程程涉涉及及的的结结点点（称称为为搜搜索索空空间间）只只是是整整个个解解空空间间树树的的一一部部分分，在在搜搜索索过过程程中中，通通常常采采用用两两种种策略避免无效搜索：策略避免无效搜索：（1）用）用约束条件约束条件剪去得不到可行解的子树；剪去得不到可行解的子树；（2）用）

11、用目标函数目标函数剪去得不到最优解的子树。剪去得不到最优解的子树。这两类函数统称为这两类函数统称为剪枝函数剪枝函数（Pruning Function）。）。v 需需要要注注意意的的是是，问问题题的的解解空空间间树树是是虚虚拟拟的的，并并不不需需要要在在算算法法运运行行时时构构造造一一棵棵真真正正的的树树结结构构，只只需需要要存存储储从从根根结结点点到到当当前结点的路径。前结点的路径。第14页，共51页，编辑于2022年，星期一8.1.3 回溯法的求解过程回溯法的求解过程 由由 于于 问问 题题 的的 解解 向向 量量X=(x1,x2,xn)中中 的的 每每 个个 分分 量量xi(1in)都都属

12、属于于一一个个有有限限集集合合Si=ai1,ai2,airi，因因此此，回回溯溯法法 可可 以以 按按 某某 种种 顺顺 序序（例例 如如 字字 典典 序序）依依 次次 考考 察察 笛笛 卡卡 儿儿 积积S1S2Sn中的元素。中的元素。初初始始时时，令令解解向向量量X为为空空，然然后后，从从根根结结点点出出发发，选选择择S1的的第第一一个个元元素素作作为为解解向向量量X的的第第一一个个分分量量，即即x1=a11，如如果果X=(x1)是是问问题题的的部部分分解解，则则继继续续扩扩展展解解向向量量X，选选择择S2的的第第一一个个元元素素作作为为解解向向量量X的的第第2个个分分量量，否否则则，选选择

13、择S1的的下下一一个个元元素素作作为为解解向向量量X的的第第一一个个分分量量，即即x1=a12。依依此此类类推推，一一般般情情况况下下，如如果果X=(x1,x2,xi)是是问问题题的的部部分分解解，则则选选择择Si+1的的第第一一个个元元素素作为解向量作为解向量X的第的第i+1个分量时，有下面三种情况：个分量时，有下面三种情况：第15页，共51页，编辑于2022年，星期一（1）如如果果X=(x1,x2,xi1)是是问问题题的的最最终终解解，则则输输出出这这个个解解。如如果果问题只希望得到一个解，则结束搜索，否则继续搜索其他解；问题只希望得到一个解，则结束搜索，否则继续搜索其他解；（2）如如果果

14、X=(x1,x2,xi1)是是问问题题的的部部分分解解，则则继继续续构构造造解解向向量量的的下下一个分量；一个分量；（3）如如果果X=(x1,x2,xi1)既既不不是是问问题题的的部部分分解解也也不不是是问问题题的的最最终解，则存在下面两种情况：终解，则存在下面两种情况：如如果果xi+1=ai1k不不是是集集合合Si1的的最最后后一一个个元元素素，则则令令xi+1=ai1k1，即选择即选择Si+1的下一个元素作为解向量的下一个元素作为解向量X的第的第i+1个分量；个分量；如如果果xi+1=ai1k是是集集合合Si1的的最最后后一一个个元元素素，就就回回溯溯到到X=(x1,x2,xi)，选选择择

15、Si的的下下一一个个元元素素作作为为解解向向量量X的的第第i个个分分量量，假假设设xi=aik，如如果果aik不不是是集集合合Si的的最最后后一一个个元元素素，则则令令xi=aik1；否否则则，就就继继续续回回溯到溯到X=(x1,x2,xi1)；第16页，共51页，编辑于2022年，星期一回溯法的一般框架递归形式advance(int k)1.对每一个xSk循环执行下列操作 1.1 xk=x;1.2 将xk加入X;1.3 if(X是最终解)flag=true;return;1.4 else if(X是部分解)advance(k+1);，主算法主算法1X=;2.flag=false;3.adva

16、nce(1);4.if(flag)输出解输出解X;else输出输出“无解无解”;回溯法的递归形式的一般框架如下：第17页，共51页，编辑于2022年，星期一回溯法的一般框架迭代形式1X=;2flag=false;3k=1;4while(k=1)4.1 当(Sk没有被穷举)循环执行下列操作 4.1.1 xk=Sk中的下一个元素;4.1.2 将xk加入X;4.1.3 if(X为最终解)flag=true;转步骤5;4.1.4 else if(X为部分解)k=k+1;转步骤4;4.2 重置Sk，使得下一个元素排在第1位;4.3 k=k-1;/回溯5if flag 输出解X;else 输出“无解”;回

17、溯算法的非递归迭代形式的一般框架如下：第18页，共51页，编辑于2022年，星期一8.1.4 回溯法的时间性能回溯法的时间性能 一一般般情情况况下下，在在问问题题的的解解向向量量X=(x1,x2,xn)中中，分分量量xi(1in)的的取取值值范范围围为为某某个个有有限限集集合合Si=ai1,ai2,airi，因因 此此，问问 题题 的的 解解 空空 间间 由由 笛笛 卡卡 儿儿 积积A=S1S2Sn构构成成，并并且且第第1层层的的根根结结点点有有|S1|棵棵子子树树，则则第第2层层共共有有|S1|个个结结点点，第第2层层的的每每个个结结点点有有|S2|棵棵子子树树，则则第第3层层共共有有|S1

18、|S2|个个结结点点，依依此此类类推推，第第n+1层层共共有有|S1|S2|Sn|个个结结点点，他他们们都都是是叶叶子子结结点点，代代表表问问题题的的所有可能解。所有可能解。第19页，共51页，编辑于2022年，星期一在用回溯法求解问题时，常常遇到两种典型的解空间树：在用回溯法求解问题时，常常遇到两种典型的解空间树：（1）子集树子集树（Subset Trees）：当所给问题是从）：当所给问题是从n个元素的集合个元素的集合中找出满足某种性质的子集时，相应的解空间树称为子集树。中找出满足某种性质的子集时，相应的解空间树称为子集树。在子集树中，在子集树中，|S1|=|S2|=|Sn|=c，即每个结点

19、有相同数目的子树，即每个结点有相同数目的子树，通常情况下通常情况下c=2，所以，子集树中共有，所以，子集树中共有2n个叶子结点，因此，遍个叶子结点，因此，遍历子集树需要历子集树需要(2n)时间。（时间。（2）排列树排列树（Permutation Trees）：）：当所给问题是确定当所给问题是确定n个元素满足某种性质的排列时，相应的解空间个元素满足某种性质的排列时，相应的解空间树称为排列树。在排列树中，通常情况下，树称为排列树。在排列树中，通常情况下，|S1|=n，|S2|=n-1，|Sn|=1，所以，排列树中共有，所以，排列树中共有n!个叶子结点，因此，遍历排列个叶子结点，因此，遍历排列树需要

20、树需要(n!)时间。时间。第20页，共51页，编辑于2022年，星期一用概率方法估算回溯法所产生的结点数。用概率方法估算回溯法所产生的结点数。基本思想：假定约束函数是静态的（即在回溯法的执行过程基本思想：假定约束函数是静态的（即在回溯法的执行过程中，约束函数不随算法所获得信息的多少而动态改变），在解空中，约束函数不随算法所获得信息的多少而动态改变），在解空间树上产生一条随机路径，然后沿此路径估算解空间树中满足约间树上产生一条随机路径，然后沿此路径估算解空间树中满足约束条件的结点总数束条件的结点总数m。设。设x是所产生随机路径上的一个结点，且位于是所产生随机路径上的一个结点，且位于解空间树的第解

21、空间树的第i层，对于层，对于x的所有孩子结点，计算出满足约束条的所有孩子结点，计算出满足约束条件的结点数件的结点数mi，路径上的下一个结点从，路径上的下一个结点从x的满足约束条件的的满足约束条件的mi个孩子结点中随机选取，这条路径一直延伸，直到叶子结点或个孩子结点中随机选取，这条路径一直延伸，直到叶子结点或者所有孩子结点均不满足约束条件为止。者所有孩子结点均不满足约束条件为止。第21页，共51页，编辑于2022年，星期一QQ(4,1,1,1)=4+4+4+4 =16QQ(4,2)=4+42 =12QQQ(4,1,1,1)=4+4+4+4 =16QQQ(4,2)=4+42 =124皇后问题的随机

22、路径及路径上结点总数估算示例皇后问题的随机路径及路径上结点总数估算示例QQ随机路径中含有的结点总数的计算方法：随机路径中含有的结点总数的计算方法：假设第假设第1层有层有m0个满足约束条件的结点，每个结点有个满足约束条件的结点，每个结点有m1个满足约个满足约束条件的孩子结点，则第束条件的孩子结点，则第2层上有层上有m0m1个满足约束条件的结点，个满足约束条件的结点，同理，假设第同理，假设第2层上的每个结点均有层上的每个结点均有m2个满足约束条件的孩个满足约束条件的孩子结点，则第子结点，则第3层上有层上有m0m1m2个满足约束条件的结点，依此个满足约束条件的结点，依此类推，第类推，第n层上有层上有

23、m0m1m2 mn-1个满足约束条件的结点，因个满足约束条件的结点，因此，这条随机路径上的结点总数为：此，这条随机路径上的结点总数为：m0+m0m1+m0m1m2+m0m1m2mn-1。第22页，共51页，编辑于2022年，星期一 在使用概率估算方法估算搜索空间的结点总数时，为了估算在使用概率估算方法估算搜索空间的结点总数时，为了估算得更精确一些，可以选取若干条不同的随机路径（通常不超过得更精确一些，可以选取若干条不同的随机路径（通常不超过20条），分别对各随机路径估算结点总数，然后再取这些条），分别对各随机路径估算结点总数，然后再取这些结点总数的平均值。例如，图结点总数的平均值。例如，图8.

24、7所示所示4皇后问题，搜索空间皇后问题，搜索空间的结点数取的结点数取4条随机路径结点总数的平均值，结果为条随机路径结点总数的平均值，结果为14。而。而4皇后问题的解空间树中的结点总数为皇后问题的解空间树中的结点总数为65，则回溯法求解，则回溯法求解4皇后皇后问题产生的搜索空间的结点数大约是解空间树中的结点总数的问题产生的搜索空间的结点数大约是解空间树中的结点总数的14/6521.5%，这说明回溯法的效率大大高于蛮力穷举法。，这说明回溯法的效率大大高于蛮力穷举法。第23页，共51页，编辑于2022年，星期一8.2 图问题中的回溯法图问题中的回溯法 8.2.1 图着色问题图着色问题 8.2.2 哈

25、密顿回路问题哈密顿回路问题第24页，共51页，编辑于2022年，星期一8.2.1 图着色问题图着色问题 图着色问题描述为：给定无向连通图图着色问题描述为：给定无向连通图G=(V,E)和正整和正整数数m，求最小的整数，求最小的整数m，使得用，使得用m种颜色对种颜色对G中的顶点着中的顶点着色，使得任意两个相邻顶点着色不同。色，使得任意两个相邻顶点着色不同。第25页，共51页，编辑于2022年，星期一 由于用由于用m种颜色为无向图种颜色为无向图G=(V,E)着色，其中，着色，其中，V的顶的顶点个数为点个数为n，可以用一个，可以用一个n元组元组C=(c1,c2,cn)来描述图来描述图的一种可能着色，其

26、中，的一种可能着色，其中，ci1,2,m(1in)表示赋予顶点表示赋予顶点i的颜色。的颜色。例如，例如，5元组元组(1,2,2,3,1)表示对具有表示对具有5个顶点的无向图的个顶点的无向图的一种着色，顶点一种着色，顶点1着颜色着颜色1，顶点，顶点2着颜色着颜色2，顶点，顶点3着颜色着颜色2，如此等等。如此等等。如果在如果在n元组元组C中，所有相邻顶点都不会着相同颜色，中，所有相邻顶点都不会着相同颜色，就称此就称此n元组为可行解，否则为无效解。元组为可行解，否则为无效解。第26页，共51页，编辑于2022年，星期一 回溯法求解图着色问题，首先把所有顶点的颜色初回溯法求解图着色问题，首先把所有顶点

27、的颜色初始化为始化为0，然后依次为每个顶点着色。在图着色问题的，然后依次为每个顶点着色。在图着色问题的解空间树中，如果从根结点到当前结点对应一个部分解空间树中，如果从根结点到当前结点对应一个部分解，也就是所有的颜色指派都没有冲突，则在当前结解，也就是所有的颜色指派都没有冲突，则在当前结点处选择第一棵子树继续搜索，也就是为下一个顶点点处选择第一棵子树继续搜索，也就是为下一个顶点着颜色着颜色1，否则，对当前子树的兄弟子树继续搜索，也，否则，对当前子树的兄弟子树继续搜索，也就是为当前顶点着下一个颜色，如果所有就是为当前顶点着下一个颜色，如果所有m种颜色都种颜色都已尝试过并且都发生冲突，则回溯到当前结

28、点的父已尝试过并且都发生冲突，则回溯到当前结点的父结点处，上一个顶点的颜色被改变，依此类推。结点处，上一个顶点的颜色被改变，依此类推。第27页，共51页，编辑于2022年，星期一D=1ACBDE1234567891011121314A=1B=2C=3D=3E=1(a)一个无向图一个无向图 (b)回溯法搜索空间回溯法搜索空间图图8.8 回溯法求解图着色问题示例回溯法求解图着色问题示例第28页，共51页，编辑于2022年，星期一 设数组colorn表示顶点的着色情况，回溯法求解m着色问题的算法如下：算法8.1图着色问题 1将数组colorn初始化为0；2k=1;3while(k=1)3.1 依次考

29、察每一种颜色，若顶点k的着色与其他顶点的着色不发生冲突，则转步骤3.2；否则，搜索下一个颜色；3.2 若顶点已全部着色，则输出数组colorn，返回；3.3 否则，3.3.1 若顶点k是一个合法着色，则k=k+1，转步骤3处理下一个顶点；3.3.2 否则，重置顶点k的着色情况，k=k-1，转步骤3回溯；第29页，共51页，编辑于2022年，星期一算法算法8.2 图着色问题图着色问题 void GraphColor(int n,int c ,int m)/所有数组下标从所有数组下标从1开始开始 for(i=1;i=1)colork=colork+1;while(colork=m)if Ok(k)

30、break;else colork=colork+1;/搜索下一个颜色搜索下一个颜色 if(colork=m&k=n)/求解完毕，输出解求解完毕，输出解 for(i=1;i=n;i+)coutcolori;return;C+描述第30页，共51页，编辑于2022年，星期一 else if(colork=m&kn)k=k+1;/处理下一个顶点处理下一个顶点 else colork=0;k=k-1;/回溯回溯 bool Ok(int k)/判断顶点判断顶点k的着色是否发生冲突的着色是否发生冲突 for(i=1;i=1)3.1 xk=xk+1，搜索下一个顶点，搜索下一个顶点;3.2 若若(n个顶点没

31、有被穷举个顶点没有被穷举)执行下列操作执行下列操作 3.2.1 若若(顶点顶点xk不在哈密顿回路上不在哈密顿回路上&(xk-1,xk)E)，转步骤转步骤3.3;3.2.2 否则，否则，xk=xk+1，搜索下一个顶点；，搜索下一个顶点；3.3 若数组若数组xn已形成哈密顿路径，则输出数组已形成哈密顿路径，则输出数组xn，算法结束；，算法结束；3.4 否则，否则，3.4.1 若数组若数组xn构成哈密顿路径的部分解，构成哈密顿路径的部分解，则则k=k+1，转步骤，转步骤3；3.4.2 否则，重置否则，重置xk，k=k-1，取消顶点，取消顶点xk的访问标志，的访问标志，转步骤转步骤3；第34页，共51

32、页，编辑于2022年，星期一算法算法8.4哈密顿回路问题哈密顿回路问题 void Hamiton(int n,int x,int c )/所有数组下标从所有数组下标从1开始开始 for(i=1;i=1)xk=xk+1;/搜索下一顶点搜索下一顶点 while(xk=n)if(visitedxk=0&cxk-1xk=1)break;else xk=xk+1;C+描述第35页，共51页，编辑于2022年，星期一 if(xk=n&k=n&cxk1=1)for(k=1;k=n;k+)coutxk;return;else if(xk=n&kn)visitedxk=1;k=k+1;else /回溯回溯 xk

33、=0;visitedxk=0;k=k-1;第36页，共51页，编辑于2022年，星期一8.3 组合问题中的回溯法组合问题中的回溯法 8.3.1 八皇后问题八皇后问题 8.3.2 批处理作业调度问题批处理作业调度问题第37页，共51页，编辑于2022年，星期一8.3.1 八皇后问题八皇后问题 八皇后问题是十九世纪著名的数学家高斯于八皇后问题是十九世纪著名的数学家高斯于1850年提出的。问题是：在年提出的。问题是：在88的棋盘上摆放八个皇后，使的棋盘上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上。可以把八皇后问题

34、扩展到同一列或同一斜线上。可以把八皇后问题扩展到n皇后皇后问题，即在问题，即在nn的棋盘上摆放的棋盘上摆放n个皇后，使任意两个个皇后，使任意两个皇后都不能处于同一行、同一列或同一斜线上。皇后都不能处于同一行、同一列或同一斜线上。第38页，共51页，编辑于2022年，星期一 若若两两个个皇皇后后摆摆放放的的位位置置分分别别是是(i,xi)和和(j,xj)，在在棋棋盘盘上上斜斜率率为为-1的的斜斜线线上上，满满足足条条件件ij=xixj，在在棋棋盘盘上上斜斜率率为为1的的斜斜线线上上，满满足足条条件件ij=xixj，综综合合两两种种情情况况，由由于于两两个个皇皇后不能位于同一斜线上，所以，解向量后

35、不能位于同一斜线上，所以，解向量X必须满足约束条件：必须满足约束条件：|ixi|jxj|（式（式8.2）显显然然，棋棋盘盘的的每每一一行行上上可可以以而而且且必必须须摆摆放放一一个个皇皇后后，所所以以，n皇皇后后问问题题的的可可能能解解用用一一个个n元元向向量量X=(x1,x2,xn)表表示示，其其中中，1in并且并且1xin，即第，即第i个皇后放在第个皇后放在第i行第行第xi列上。列上。由由于于两两个个皇皇后后不不能能位位于于同同一一列列上上，所所以以，解解向向量量X必必须须满足约束条件：满足约束条件：xixj （式（式8.1）第39页，共51页，编辑于2022年，星期一1 2 3 4123

36、4皇后1皇后2皇后3皇后4图8.11 四皇后问题 为了简化问题，下面讨论四皇后问题。为了简化问题，下面讨论四皇后问题。四皇后问题的解空间树是一个完全四皇后问题的解空间树是一个完全4叉树，树的根结点表示搜索叉树，树的根结点表示搜索的初始状态，从根结点到第的初始状态，从根结点到第2层结点对应皇后层结点对应皇后1在棋盘中第在棋盘中第1行的可能行的可能摆放位置，从第摆放位置，从第2层结点到第层结点到第3层结点对应皇后层结点对应皇后2在棋盘中第在棋盘中第2行的可行的可能摆放位置，依此类推。能摆放位置，依此类推。第40页，共51页，编辑于2022年，星期一QQ QQ Q QQQQ Q QQ QQQQQQQ

37、 Q(a)(b)(c)(d)(e)(f)(g)(h)(i)(j)QQ Q回溯法求解回溯法求解4皇后问题的搜索过程皇后问题的搜索过程第41页，共51页，编辑于2022年，星期一算法算法8.5n皇后问题皇后问题 void Queue(int n)for(i=1;i=1)xk=xk+1;/在下一列放置第在下一列放置第k个皇后个皇后 while(xk=n&!Place(k)xk=xk+1;/搜索下一列搜索下一列 if(xk=n&k=n)/得到一个解，输出得到一个解，输出 for(i=1;i=n;i+)coutxi;return;C+描述第42页，共51页，编辑于2022年，星期一 else if(xk

38、=n&kn)k=k+1;/放置下一个皇后放置下一个皇后 else xk=0;/重置重置xk，回溯，回溯 k=k-1;bool Place(int k)/考察皇后考察皇后k放置在放置在xk列是否发生冲突列是否发生冲突 for(i=1;ik;i+)if(xk=xi|abs(k-i)=abs(xk-xi)return false;return true;第43页，共51页，编辑于2022年，星期一8.3.2 批处理作业调度问题批处理作业调度问题 n个个作作业业1,2,n要要在在两两台台机机器器上上处处理理，每每个个作作业业必必须须先先由由机机器器1处处理理，然然后后再再由由机机器器2处处理理，机机器

39、器1处处理理作作业业i所所需需时时间间为为ai，机机器器2处处理理作作业业i所所需需时时间间为为bi（1in），批批处处理理作作业业调调度度问问题题要要求求确确定定这这n个个作作业业的的最最优优处处理理顺顺序序，使使得得从从第第1个个作作业业在在机机器器1上上处处理理开开始始，到最后一个作业在机器到最后一个作业在机器2上处理结束所需时间最少。上处理结束所需时间最少。第44页，共51页，编辑于2022年，星期一显然，批处理作业的一个最优调度应使机器显然，批处理作业的一个最优调度应使机器1没有空闲时间，且机器没有空闲时间，且机器2的空闲时间最小。可以证明，存在一个最优作业调度使得在机器的空闲时间最

40、小。可以证明，存在一个最优作业调度使得在机器1和和机器机器2上作业以相同次序完成。上作业以相同次序完成。例：三个作业例：三个作业1,2,3，这三个作业在机器，这三个作业在机器1上所需的处理时间为上所需的处理时间为(2,3,2)，在机器，在机器2上所需的处理时间为上所需的处理时间为(1,1,3)，则最佳调度方案，则最佳调度方案是是(1,3,2)、(3,1,2)和和(3,2,1)，其完成时间为，其完成时间为8。作业作业1:2作业作业2:3作业作业3:2空闲空闲:2作业作业1:1机器机器1机器机器2作业作业2:1作业作业3:3(a)调度方案调度方案(1,2,3)，最后完成时间为，最后完成时间为10作

41、业作业1:2作业作业2:3作业作业3:2空闲空闲:2作业作业1:1机器机器1机器机器2作业作业2:1作业作业3:3(b)调度方案调度方案(1,3,2)，最后完成时间为，最后完成时间为8第45页，共51页，编辑于2022年，星期一作业作业2:3作业作业1:2作业作业3:2空闲空闲作业作业2:1机器机器1机器机器2作业作业1:1作业作业3:3(c)调度方案调度方案(2,1,3)，最后完成时间为，最后完成时间为10作业作业2:3作业作业3:2作业作业1:2空闲空闲:3作业作业2:1机器机器1机器机器2作业作业1:1作业作业3:3(d)调度方案调度方案(2,3,1)，最后完成时间为，最后完成时间为9第

42、46页，共51页，编辑于2022年，星期一作业作业2:3作业作业3:2作业作业1:2空闲空闲:2作业作业2:1机器机器1机器机器2作业作业1:1作业作业3:3(e)调度方案调度方案(3,1,2)，最后完成时间为，最后完成时间为8作业作业2:3作业作业3:2作业作业1:2空闲空闲:2作业作业2:1机器机器1机器机器2作业作业2:1作业作业3:3(f)调度方案调度方案(3,2,1)，最后完成时间为，最后完成时间为8第47页，共51页，编辑于2022年，星期一算法算法8.6批处理作业调度问题批处理作业调度问题void BatchJob(int n,int a,int b,int&bestTime)/

43、数组数组x存储具体的作业调度，下标从存储具体的作业调度，下标从1开始；开始；/数组数组sum1存储机器存储机器1的作业时间，的作业时间，/sum2存储机器存储机器2的作业时间，下标从的作业时间，下标从0开始开始 for(i=1;i=1)xk=xk+1;while(xk=n)if(Ok(k)sum1k=sum1k-1+axk;sum2k=max(sum1k,sum2k-1)+bxk;if(sum2kbestTime)break;else xk=xk+1;C+描述第48页，共51页，编辑于2022年，星期一 else xk=xk+1;if(xk=n&kn)k=k+1;/安排下一个作业安排下一个作业

44、 else if(xksum2k)bestTime=sum2k;xk=0;/重置重置xk，回溯，回溯 k=k-1;bool Ok(int k)/作业作业k与其他作业是否发生冲突（重复）与其他作业是否发生冲突（重复）for(i=1;ik;i+)if(xi=xk)return false;return true;第49页，共51页，编辑于2022年，星期一8.4 实验项目实验项目0/1背包问题背包问题1.实验题目实验题目 给定n种物品和一个容量为C的背包，物品i的重量是wi，其价值为vi，0/1背包问题是如何选择装入背包的物品（物品不可分割），使得装入背包中物品的总价值最大?2.实验目的实验目的（1）掌握回溯法的设计思想；（2）掌握解空间树的构造方法，以及在求解过程中如何存储求解路径；（3）考察回溯法求解问题的有效程度。第50页，共51页，编辑于2022年，星期一3.实验要求实验要求（1）设计可能解的表示方式，构成解空间树；（2）设计回溯算法完成问题求解；（3）设计测试数据，统计搜索空间的结点数；第51页，共51页，编辑于2022年，星期一