第5章-回溯与分支限界

1第5章回溯与分支限界5.1回溯算法的基本思想和适用条件5.2回溯算法的设计步骤5.3回溯算法的效率估计和改进途径5.4分支限界

5.4.1背包问题5.4.2最大团问题5.4.3货郎问题

5.4.4圆排列问题

5.4.5连续邮资问题25.1回溯算法的基本思想和适用条件5.1.1几个典型例子四后问题0-1背包问题货郎问题（TSP）5.1.2回溯算法的适用条件35.1.1几个典型例子例5.1n后问题

4后问题：解是一个4维向量，<x1,x2,x3,x4>（放置列号）搜索空间：4叉树<1><4><2,4><2,4,1><2,4,1,3>8后问题：解是一个8维向量，<x1,x2,x3,x4,x5,x6,x7,x8>搜索空间：8叉树，一个解：<1,3,5,2,4,6,8,7>

4实例：V={12,11,9,8},W={8,6,4,3},B=13

结点：向量<x1,x2,x3,…,xk>（子集的部分特征向量）

搜索空间：子集树，2n片树叶

<0,1,1,1>可行解：

x1=0,x2=1,x3=1,x4=1.价值:28，重量:13<1,0,1,0>可行解：x1=1,x2=0,x3=1,x4=0.价值:21，重量:12例5.20-1背包问题<1><0><1,0,1,0><0,1,1,1>5<1,2,4,3>对应于巡回路线：12431长度：5+2+7+9=23

例5.3

货郎问题<1><1,2><1,4><1,2,4,3>12345249713<i1,i2,…,in>为巡回路线搜索空间：排列树,(n-1)!片树叶实例：6回溯算法的基本思想(1)适用问题：求解搜索问题和优化问题(2)搜索空间：树，结点对应部分解向量，树叶对应可行解(3)搜索过程：采用系统的方法隐含遍历搜索树(4)搜索策略：深度优先，宽度优先，函数优先，宽深结合等(5)结点分支判定条件：满足约束条件---分支扩张解向量不满足约束条件，回溯到该结点的父结点(6)结点状态：动态生成白结点(尚未访问)；灰结点(正在访问该结点为根的子树);

黑结点(该结点为根的子树遍历完成)(7)存储：当前路径7设P(x1,x2,…,xi)为真表示向量<x1,x2,…,xi>满足某个性质(n后问题中i个皇后放置在彼此不能攻击的位置）多米诺性质：例5.4求不等式的整数解

5x1+4x2

x3

10,1

xi

3,i=1,2,3

P(x1,…,xk):意味将x1,x2,…,xk代入原不等式的相应部分使得左边小于等于10不满足多米诺性质变换：令x3=3

x3’,5x1+4x2+x3’

13

，1

x1,x2

3,0

x3’

25.1.2回溯算法的适用条件85.2

回溯算法的设计步骤(1)定义搜索问题的解向量和每个分量的取值范围解向量为<x1,x2,…,xn>确定xi的可能取值的集合为Xi

,i=1,2,…,n.(2)当x1,x2,…,xk-1确定以后计算xk

取值集合Sk,Sk

Xk

(3)确定结点儿子的排列规则(4)判断是否满足多米诺性质(5)搜索策略----深度优先、宽度优先等(6)确定每个结点分支约束条件(7)确定存储搜索路径的数据结构9算法5.1

ReBack(k)1.ifk>nthen<x1,x2,…,xn>是解

2.elsewhileSk

do3.

xk

Sk中最小值

4.Sk

Sk–{xk}5.计算Sk+16.ReBack(k+1)

算法5.2

ReBacktrack(n)输入：n输出：所有的解

1.fork

1ton

计算Xk2.ReBack(1)回溯算法的递归实现10算法5.3

Backtrack(n)

输入：n

输出：所有的解1.对于i=1,2,…,n确定Xi2.k

13.计算Sk4.whileSk

do5.xk

Sk中最小值;Sk

Sk–{xk}6.ifk<nthen7.k

k+1;计算Sk8.else<x1,x2,…,xn>是解

9.ifk>1thenk

k-1；goto4

回溯算法的迭代实现11回溯算法解决问题的步骤回溯算法也叫试探法，它是一种系统地搜索问题的解的方法。用回溯算法解决问题的一般步骤：1针对所给问题，定义问题的解空间，它至少包含问题的一个（最优）解。2确定易于搜索的解空间结构,使得能用回溯法方便地搜索整个解空间。3以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索。

回溯法的搜索过程涉及的结点（称为搜索空间）只是整个解空间树的一部分，在搜索过程中，通常采用两种策略避免无效搜索：（1）用约束条件剪去得不到可行解的子树；（2）用目标函数剪去得不到最优解的子树。这两类函数统称为剪枝函数（PruningFunction）。需要注意的是，问题的解空间树是虚拟的，并不需要在算法运行时构造一棵真正的树结构，只需要存储从根结点到当前结点的路径。回溯法的求解过程

由于问题的解向量X=(x1,x2,…,xn)中的每个分量xi(1≤i≤n)都属于一个有限集合Si={ai1,ai2,…,airi}，因此，回溯法可以按某种顺序（例如字典序）依次考察笛卡儿积S1×S2×…×Sn中的元素。初始时，令解向量X为空，然后，从根结点出发，选择S1的第一个元素作为解向量X的第一个分量，即x1=a11，如果X=(x1)是问题的部分解，则继续扩展解向量X，选择S2的第一个元素作为解向量X的第2个分量，否则，选择S1的下一个元素作为解向量X的第一个分量，即x1=a12。依此类推，一般情况下，如果X=(x1,x2,…,xi)是问题的部分解，则选择Si+1的第一个元素作为解向量X的第i+1个分量时，有下面三种情况：（1）如果X=(x1,x2,…,xi＋1)是问题的最终解，则输出这个解。如果问题只希望得到一个解，则结束搜索，否则继续搜索其他解；（2）如果X=(x1,x2,…,xi＋1)是问题的部分解，则继续构造解向量的下一个分量；（3）如果X=(x1,x2,…,xi＋1)既不是问题的部分解也不是问题的最终解，则存在下面两种情况：①如果xi+1=

ai＋1k不是集合Si＋1的最后一个元素，则令xi+1=

ai＋1k＋1，即选择Si+1的下一个元素作为解向量X的第i+1个分量；②如果xi+1=

ai＋1k是集合Si＋1的最后一个元素，就回溯到X=(x1,x2,…,xi)，选择Si的下一个元素作为解向量X的第i个分量，假设xi=

aik，如果aik不是集合Si的最后一个元素，则令xi=

aik＋1；否则，就继续回溯到X=(x1,x2,…,xi－1)；例5装载问题例5.5n个集装箱装上2艘载重分别为c1和c2的轮船，wi为集装箱i的重量，且问是否存在一种合理的装载方案将n个集装箱装上轮船？如果有，给出一种方案.

求解思路：令第一船装载量为W1，用回溯算法求使W1-c1达到最小的装载方案<x1,x2,…,xn>，如果回答Yes,否则回答No.问题满足多米诺性质，搜索策略：深度优先算法算法5.4Loading(W,c1),输入：集装箱重量W=<w1,w2,…,wn>,c1是第一条船的载重输出：使第一条船装载最大的方案<x1,x2,…,xn>，其中xi=0,1

1.Sort(W);//对w1,w2,…,wn按照从大到小排序2.B

;best

;i

1;3.whilei

ndo4.if装入i后重量不超过c15.thenB

B

wi;x[i]

1;i

i+1;elsex[i]

0;i

i+1;if

B<bestthen记录解；Best

B;Backtrack(i)；ifi=1thenreturn最优解elsegoto3.实例算法5.5Backtrack(i)1.whilei>1andx[i]=0do2.i

i

1;ifx[i]=1thenx[i]

0;B

B+wi;i

i+1;实例W=<90,80,40,30,20,12,10>,c1=152,c2=130复杂性：W(n)=O(2n)00101290002040308000例6

图的着色问题例5.6着色问题：给定无向连通图G和m种颜色，用这些颜色给图的顶点着色，每个顶点一种颜色.要求是：G的每条边的两个顶点着不同颜色.给出所有可能的着色方案；如果不存在着这样的方案，则回答“No”.

则搜索空间为深度n的m叉完全树.将颜色编号为1,2,…,m，结点<x1,x2,…,xk>：x1,x2,…,xk

{1,2,..,m},1k

n，表示顶点1着颜色x1，顶点2着颜色x2，…，顶点k着颜色xk.约束条件：该顶点邻接表中的顶点与该顶点没有同色；搜索策略：深度优先时间：O(nmn)19实例<1><1,2><1,2,1><1,2,1,3><1,2,1,3,1><1,2,1,3,1,2><1,2,1,3,1,2,3>12332131231213220提高效率的途径根据对称性，只需搜索1/3的解空间即可.当1和2确定,即<1,2>以后，只有1个解，因此在<1,3>为根的子树中也只有1个解.由于3个子树的对称性，总共有6个解.进一步分析，在取定<1,2>以后，不可以扩张成<1,2,3>,因为可以检查是否有和1,2,3都相邻的顶点.如果存在,例如7,则没有解.所以可以从打叉的结点回溯，而不必搜索它的子树.21

5.3回溯算法的效率估计

与改进途径MonteCarlo(蒙特卡罗)方法估计搜索树中的结点，背景：蒙特卡罗方法于20世纪40年代美国在第二次世界大战中研制原子弹的“曼哈顿计划”计划的成员乌拉姆和冯·诺伊曼首先提出。数学家冯·诺伊曼用驰名世界的赌城—摩纳哥的MonteCarlo1．从根开始，随机选择一条路经，直到不能分支为止,

即从x1,x2,…,依次对xi

赋值，每个xi的值是从当时的

Si中随机选取，直到向量不能扩张为止.

2．假定搜索树的其他|Si|

1个分支与以上随机选出的路径一样，计数搜索树的点数.

3．重复步骤1和2，将结点数进行概率平均.22算法5.6MonteCarlo输入：n,t

为正整数，n为皇后数，t为抽样次数输出：sum,即t次抽样路径长度的平均值1．sum

0//sum为t次结点平均数

2．fori

1totdo//取样次数t3.m

Estimate(n)//m为本次结点总数

4.sum

sum+m

5.sumsum/t算法实现23m为输出——本次取样结点总数，k为层数，r1为本层分支数,r2为上层分支数，n为树的层数算法5.7Estimate(n)1.m

1;r2

1;k

1//m为结点总数

2.Whilek

ndo3.ifSk=thenreturnm4.r1

|Sk|*r2//r1为扩张后结点总数

5.m

m+r1//r2为扩张前结点总数

6.xk

随机选择Sk

的元素

7.r2

r18.k

k+1子过程24估计四后搜索树的结点数case1．<1,4,2>：1+4+4

2+4

2=21case2．<2,4,1,3>:44+1=17case3．<1,3>：1+4

1+4

2=13实例Case3:<1,3>Case1:<1,4,2>Case2:<2,4,1,3>25估计结果假设4次抽样测试：case1:1次，case2:1次，case3:2次，平均结点数＝(21×1+17×1+13×2)/4=16搜索空间访问的结点数为17搜索空间26影响算法效率的因素最坏情况下的时间W(n)=(p(n)f(n))

其中p(n)

为每个结点时间，f(n)为结点个数影响回朔算法效率的因素（1）搜索树的结构分支情况：分支均匀否、树的深度：对称程度：对称适合裁减（2）解的分布在不同子树中分布多少是否均匀分布深度（3）约束条件的判断：计算简单27（1）根据树分支设计优先策略：结点少的分支优先，解多的分支优先（2）利用搜索树的对称性剪裁子树（3）分解为子问题:

求解时间f(n)=c2n，组合时间T=O(f(n))

如果分解为k个子问题，每个子问题大小为n/k

求解时间为改进途径分支限界法（分支+限界）常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。分支：按广度优先的策略进行搜索限界：为加快搜索速度而采用启发式信息剪枝的策略组合优化问题的相关概念目标函数（极大化或极小化）约束条件搜索空间中满足约束条件的解称为可行解使得目标函数达到极大(或极小)的解称为最优解285.4

分支限界29分支限界技术（极大化）设立代价函数函数值以该结点为根的搜索树中的所有可行解的目标函数值的上界父结点的代价不小于子结点的代价设立界代表当时已经得到的可行解的目标函数的最大值界的设定初值可以设为0可行解的目标函数值大于当时的界，进行更新搜索中停止分支的依据不满足约束条件或者其代价函数小于当时的界

30实例：布线问题印刷电路板将布线区域划分成nXm个方格如图所示。精确的电路布线问题要求确定连接方格a的中点到方格b的中点的最短布线方案。在布线时，电路只能沿直线或直角布线。为了避免线路相交，已布了线的方格做了封锁标记，其它线路不允穿过被封锁的方格。31背包问题的实例：

对变元重新排序使得实例：背包问题排序后实例

32结点<x1,x2,…,xk>的代价函数

分支策略----深度优先

代价函数与分支策略确定33x2=20x1=1x2=2

1x2=3201x1=010实例345.4.2

最大团问题例5.9最大团问题：给定无向图G=<V,E>,求G中的最大团.相关知识：无向图G=<V,E>,

G的子图：G’=<V’,E’>,其中V’

V,E’

E,

G的补图：Ğ=<V,E’>,E’是E关于完全图边集的补集

G中的团：G的完全子图

G的点独立集：G的顶点子集A，且u,v

A,{u,v}

E.

最大团：顶点数最多的团

最大点独立集：顶点数最多的点独立集命题：U是G的最大团当且仅当U是Ğ的最大点独立集35结点<x1,x2,…,xk>的含义：已检索k个顶点，其中xi=1对应的顶点在当前的团内搜索树为子集树约束条件：该顶点与当前团内每个顶点都有边相连界：当前图中已检索到的极大团的顶点数代价函数：目前的团扩张为极大团的顶点数上界

F=Cn+n

k

其中Cn

为目前团的顶点数（初始为0），

k为结点层数时间：O(n2n)算法设计3623514顶点编号顺序为1,2,3,4,5,对应x1,x2,x3,x4,x5,xi=1当且仅当i在团内分支规定左子树为1，右子树为0.

B为界，F为代价函数值.最大团的实例37a：得第一个极大团{1,2,4},顶点数为3,界为3；b：代价函数值F=3,回溯；c：得第二个极大团{1,3,4,5},顶点数为4,修改界为4；d：不必搜索其它分支,因为F=4,不超过界；e：F=4,不必搜索.最大团为{1,3,4,5},顶点数为4.23514实例求解a,B=3

b,F=3c,B=4d,F=4e,F=4TSP问题

TSP问题是指旅行家要旅行n个城市，要求各个城市经历且仅经历一次然后回到出发城市，并要求所走的路程最短。271563134253984C=∞31583∞67916∞42574∞38923∞(a)一个无向图(b)无向图的代价矩阵图9.4无向图及其代价矩阵采用贪心法求得近似解为1→3→5→4→2→1，其路径长度为1+2+3+7+3=16，这可以作为TSP问题的上界。把矩阵中每一行最小的元素相加，可以得到一个简单的下界，其路径长度为1+3+1+3+2=10，但是还有一个信息量更大的下界：考虑一个TSP问题的完整解，在每条路径上，每个城市都有两条邻接边，一条是进入这个城市的，另一条是离开这个城市的，那么，如果把矩阵中每一行最小的两个元素相加再除以2，如果图中所有的代价都是整数，再对这个结果向上取整，就得到了一个合理的下界。

lb=((1+3)+(3+6)+(1+2)+(3+4)+(2+3))/2=14

于是，得到了目标函数的界[14,16]。需要强调的是，这个解并不是一个合法的选择（可能没有构成哈密顿回路），它仅仅给出了一个参考下界。

部分解的目标函数值的计算方法

例如图9.4所示无向图，如果部分解包含边(1,4)，则该部分解的下界是lb=((1+5)+(3+6)+(1+2)+(3+5)+(2+3))/2=16。

271563134253984C=∞31583∞67916∞42574∞38923∞(a)一个无向图(b)无向图的代价矩阵图9.4无向图及其代价矩阵41→2lb=142356781×startlb=141→3lb=141→4lb=161→5lb=192→3lb=162→4lb=162→5lb=193→2lb=163→4lb=153→5lb=14×910115→2lb=195→4lb=141415×4→2lb=16174→2lb=184→5lb=151213×5→2lb=2016×分支限界法求解TSP问题示例425.4.3货郎问题例5.10货郎问题：给定n个城市集合C={c1,c2,…,cn},从一个城市到另一个城市的距离dij

为正整数，求一条最短且每个城市恰好经过一次的巡回路线.货郎问题的类型：有向图、无向图.设巡回路线从1开始，解向量为<i0=1,i1,i2,…,in-1>,

其中i1,i2,…,in-1为{2,3,…,n}的排列.搜索空间为排列树，结点<i0,i1,i2,…,ik

>表示得到k步路线1234524971343为部分巡回路线扩张成全程巡回路线的长度下界时间O(n!)：计算O((n

1)!)次，代价函数计算O(n)约束条件：令B={i0=1,i1,i2,…,ik

},则

ik+1

{2,…,n}

B界：当前得到的最短巡回路线长度代价函数L：设顶点ci

出发的最短边长度为li，dj

为选定巡回路线中第j段的长度，则算法设计445.4.4

圆排列问题例5.11圆排列问题：给定n个圆的半径序列,将各圆与矩形底边相切排列,求具有最小长度ln

的圆的排列顺序.解为<i1,i2,…,in>为1,2,…,n的排列，解空间为排列树.部分解向量<i1,i2,…,ik>：表示前k个圆已排好.令B={i1,i2,…,ik

},下一个圆选择