0027算法笔记回溯法回溯法与装载问题Word格式.docx
《0027算法笔记回溯法回溯法与装载问题Word格式.docx》由会员分享，可在线阅读，更多相关《0027算法笔记回溯法回溯法与装载问题Word格式.docx（17页珍藏版）》请在冰点文库上搜索。
为了避免生成那些不可能产生最佳解的问题状态，要不断地利用限界函数（boundingfunction）来处死那些实际上不可能产生所需解的活结点，以减少问题的计算量。
具有限界函数的深度优先生成法称为回溯法。
（5）回溯法的基本思想
基本思想：
用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。
在任何时刻，算法只保存从根结点到当前扩展结点的路径。
如果解空间树中从根结点到叶结点的最长路径的长度为h（n），则回溯法所需的计算空间通常为O（h（n））。
而显式地存储整个解空间则需要O（2h（n））或O（h（n）!
）内存空间。
解题步骤：
1）针对所给问题，定义问题的解空间；
2）确定易于搜索的解空间结构；
3）以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。
常用剪枝函数：
用约束函数在扩展结点处剪去不满足约束的子树；
用限界函数剪去得不到最优解的子树。
递归回溯：
回溯法对解空间作深度优先搜索，因此，在一般情况下用递归方法实现回溯法。
[cpp]
viewplain
copy
1.void
backtrack
（int
t）
2.{
3.
if
（t>
n）
4.
output（x）;
//已到叶子结点，输出结果
5.
else
6.
for
i=f（n,t）;
i<
=g（n,t）;
i++）
{
7.
x[t]=h（i）;
8.
（constraint（t）&
&
bound（t））
9.
backtrack（t+1）;
10.
}
11.}
f（n,t），g（n,t）：
表示当前扩展结点处未搜索过的子树的起始编号和终止编号。
h（i）：
表示在当前扩展结点处x[t]的第i个可选值。
迭代回溯：
采用树的非递归深度优先遍历算法，可将回溯法表示为一个非递归迭代过程。
iterativeBacktrack
（）
int
t=1;
while
0）
（f（n,t）<
=g（n,t））
（solution（t））
t++;
11.
12.
13.
t--;
14.
15.}
子集树与排列树：
子集树：
当所给的问题是从n个元素的集合S中找出满足某种性质的子集时，相应的解空间称为子集树。
例如，那个物品的0-1背包问题所相应的解空间树就是一颗子集树。
这类子集问题通常有2^n个叶节点，其节点总个数为2^（n+1）-1。
遍历子集树的任何算法均需要O（2^n）的计算时间。
用回溯法遍历子集树的一般算法可描述如下：
i=0;
=1;
x[t]=i;
（legal（t））
9.}
排列树：
当所给问题是确定n个元素满足某种性质的排列时，相应的解空间树称为排列树。
排列树通常有n!
个叶子节点。
因此遍历排列树需要O（n!
）的计算时间。
用回溯法遍历排列树的一般算法可描述如下：
i=t;
=n;
swap（x[t],
x[i]）;
10.}
2、装载问题
问题描述：
有一批共n个集装箱要装上2艘载重量分别为c1和c2的轮船，其中集装箱i的重量为wi，且
，装载问题要求确定是否有一个合理的装载方案可将这些集装箱装上这2艘轮船。
如果有，找出一种装载方案。
例如：
当n=3,c1=c2=50,且w=[10,40,40]时，则可以将集装箱1和2装到第一艘轮船上，而将集装箱3装到第二艘轮船上；
如果w=[20,40,40]，则无法将这3个集装箱都装上轮船。
基本思路：
容易证明，如果一个给定装载问题有解，则采用下面的策略可得到最优装载方案。
（1）首先将第一艘轮船尽可能装满；
（2）将剩余的集装箱装上第二艘轮船。
将第一艘轮船尽可能装满等价于选取全体集装箱的一个子集，使该子集中集装箱重量之和最接近C1。
由此可知，装载问题等价于以下特殊的0-1背包问题。
用回溯法设计解装载问题的O（2^n）计算时间算法。
在某些情况下该算法优于动态规划算法。
算法设计：
用回溯法解装载问题时，用子集树表示其解空间显然是最合适的。
用可行性约束函数可剪去不满足约束条件
的子树。
在子集树的第j+1层的结点z处，用cw记当前的装载重量，即cw=
，则当cw>
c1时，以结点z为根的子树中所有结点都不满足约束条件，因而该子树中的解均为不可行解，故可将该子树剪去。
（该约束函数去除不可行解，得到所有可行解）。
可以引入一个上界函数，用于剪去不含最优解的子树，从而改进算法在平均情况下的运行效率。
设z是解空间树第i层上的当前扩展结点。
cw是当前载重量；
bestw是当前最优载重量；
r是剩余集装箱的重量，即r=
。
定义上界函数为cw+r。
在以z为根的子树中任一叶结点所相应的载重量均不超过cw+r。
因此，当cw+r<
=bestw时，可将z的右子树剪去。
递归回溯具体代码如下：
1.#include
"
stdafx.h"
2.#include
<
iostream>
3.using
namespace
std;
5.template
class
Type>
6.class
Loading
7.{
//friend
Type
MaxLoading（Type[],Type,int,int
[]）;
//private:
public:
void
Backtrack（int
i）;
n,
//集装箱数
*x,
//当前解
*bestx;
//当前最优解
15.
*w,
//集装箱重量数组
16.
c,
//第一艘轮船的载重量
17.
cw,
//当前载重量
18.
bestw,
//当前最优载重量
19.
r;
//剩余集装箱重量
20.};
21.
22.template
23.void
:
Backtrack
24.
25.template<
26.Type
MaxLoading（Type
w[],
bestx[]）;
27.
28.int
main（）
29.{
30.
n=3,m;
31.
c=50,c2=50;
32.
33.
w[4]={0,10,40,40};
34.
bestx[4];
35.
36.
m=MaxLoading（w,
bestx）;
37.
38.
cout<
轮船的载重量分别为：
endl;
39.
c
（1）="
c<
c
（2）="
c2<
40.
41.
待装集装箱重量分别为：
42.
w（i）="
;
43.
i=1;
44.
45.
w[i]<
46.
47.
48.
49.
回溯选择结果为：
50.
m
（1）="
m<
51.
x（i）="
52.
53.
54.
55.
bestx[i]<
56.
57.
58.
59.
m2=0;
60.
j=1;
j<
j++）
61.
62.
m2=m2+w[j]*（1-bestx[j]）;
63.
64.
m
（2）="
m2<
65.
66.
if（m2>
c2）
67.
68.
因为m
（2）大于c
（2）,所以原问题无解！
69.
70.
return
0;
71.}
72.
73.template
74.void
i）//
搜索第i层结点
75.{
76.
（i
>
n）//
到达叶结点
77.
78.
（cw>
bestw）
79.
80.
for（int
81.
82.
bestx[j]=x[j];
//更新最优解
83.
bestw=cw;
84.
85.
86.
return;
87.
88.
89.
r-=w[i];
90.
（cw
+
w[i]
=
c）
//
搜索左子树
91.
92.
x[i]
1;
93.
cw
+=
w[i];
94.
Backtrack（i+1）;
95.
cw-=w[i];
96.
97.
98.
r
99.
100.
搜索右子树
101.
Backtrack（i
1）;
102.
103.
r+=w[i];
104.}
105.
106.template<
107.Type
bestx[]）//返回最优载重量
108.{
109.
Loading<
X;
110.
//初始化X
111.
X.x=new
int[n+1];
112.
X.w=w;
113.
X.c=c;
114.
X.n=n;
115.
X.bestx=bestx;
116.
X.bestw=0;
117.
X.cw=0;
118.
//初始化r
119.
X.r=0;
120.
121.
122.
123.
X.r+=w[i];
124.
125.
126.
X.Backtrack
（1）;
127.
delete
[]X.x;
128.
X.bestw;
129.}
迭代回溯具体代码如下：
5.template<
6.Type
w[
],
bestx[
]）;
8.int
9.{
20.
22.
23.
25.
26.
28.
29.
50.}
53.template
54.Type
w[],Type
c,int
n,int
bestx[]）//迭代回溯法，返回最优载重量及其相应解，初始化根结点
55.{
//当前层，x[1:
i-1]为当前路径
*x=new
bestw=0,
cw=0,
r=0;
r+=w[j];
while（true）//搜索子树
while（i<
=n
cw+w[i]<
=c）//进入左子树
71.
73.
cw+=w[i];
74.
x[i]=1;
75.
i++;
（i>
n）//到达叶结点
else//进入右子树
x[i]=0;
（cw+r<
=bestw）
//剪枝回溯
i--;
0
!
x[i]）
//从右子树返回
（i==0）
[]x;
bestw;
104.
1
升级会员 