算法设计与分析
目录
算法设计与分析 (1)
第6章回溯与分支限界 (3)
6.1回溯法的设计技术 (3)
6.2用回溯法求解装载问题 (7)
6.3用回溯法求解n皇后问题 (9)
6.4用回溯法求解0-1背包问题 (11)
6.5用回溯法求解旅行商问题 (13)
6.6 分支限界法的设计技术 (15)
6.7 用分支限界法求问题的解 (15)
本章小结 (15)
参考文献 (16)
第6章回溯与分支限界
内容导读
回溯法(Back Tracking Algorithm)与分支限界法（Branch and Bound Algorithm）都是基本的算法设计策略，属于树的搜索技术的范畴。在使用这两种算法求解问题前，均需要把解空间规划成一棵解空间树，并且在求解过程中使用剪枝策略来提高搜索效率。
回溯法也称试探法，可以把它看成是一个在约束条件下对解空间树进行深度优先搜索的过程，并在搜索过程中剪去那些不满足条件的分支。当用回溯法搜索到解空间树的某个结点时，如果发现当前路径不满足约束条件或不是历史最优时，则放弃对该结点的子树的搜索，并逐层向其祖先结点返回。否则，进入该结点的子树，继续进行深度优先搜索。实质上，这是一个先根遍历解空间树的过程，只是这个棵树不是遍历前预先建立的，而是隐含在遍历过程当中的。
分支限界法则是以最小代价优先的方式在解空间树上进行搜索，它可以找出满足问题约束的一个可行解，或者是从满足约束条件的可行解中找出一个使得目标函数达到极值的最优解。这里的可行解在搜索树中表现为一条由根到叶子结点的路径，这条路径上权值的和为可行解的值。其中，最优解就是使可行解的值达到最优的那条路径。分支限界算法的核心思想就是增加更多的约束条件，剪掉更多的分支，当对当前的树结点进行扩展时，一次性产生其所有儿子结点，并抛弃那些不可能产生可行解或最优解的结点，即剪枝；对于留下的儿子结点，计算一个函数值（限界），然后选取一个最有利的结点继续进行扩展，使得搜索朝着最优解的分支推进。重复这个过程直到找到最优解或没有可扩展的结点。
6.1回溯法的设计技术
6.1.1算法思想
回溯算法是一种有组织的系统最优化搜索技术，用它可以求解问题的所有解、一组解或一个解。例如经典的n皇后问题，它是指在一个n*n的棋盘上放置n个不能够互相攻击的皇后的问题。按照国际象棋的规则，任意两个皇后之间不能处在同一行、同一列和同一斜线上，否则皇后就可以攻击与之处在同一行、同一列或同一斜线上的棋子。如图6-1所示为一个4个皇后的合理摆放格局。那么，如何找到这样一个格局或者找到所有满足要求的解呢？
图6-1 4皇后的一个格局
可以采用这样一种策略：设每一行的棋格为一层，用x i代表第i层皇后的摆放位置（共有4个值，表示棋格的列），那么，4皇后问题可以描述为一个4元组（x1，x2，x3，x4），这4个元素代表每一层皇后的摆放位置（列），当它们都取得满足题目要求值时，则得到一组解。图6-2展示了4皇后问题的求解过程：（1）第一层，由于没有其它皇后，4个摆放位置均可摆放，x1的值可取1、2、3、4。
（2）第二层，可针对于x1的每一个取值进行扩展，为第二层皇后选择位置，即给x2赋值。那么，针对于x1=1，x2有4个位置可以选择。尝试摆放的过程如下：x2=1的位置，不能摆放，因为两个皇后在同一列上，因此，不对其继续进行扩展，回退到上一层进行重新摆放。x2=2的位置不能摆放，因为两个皇后在同一对角线上，再次回退到上一层。尝试在x2=3位置摆放，此时，满足要求，第二层摆放成功，可沿这分支继续进行扩展。
（3）第三层，沿x2=3的位置进行扩展，给x3进行赋值。由图6-2可知，由这一分支而下的所尝试均不满足要求，最终回退至第二层，它同时也宣告了x2=3摆放的失败，即沿这一分支不可能找到解，则再回溯到第一层，重新摆放皇后、为x2取值，让x2=4，满足要求，沿此分支进行扩展。
（4）第三层，沿x2=4尝试向下扩展，给x3取值，方法与上面描述的相同，尝试成功，则继续向下搜索，不成功则返回上一层，给x3重新取值……，依此，直到第4层摆放完毕，且x1、x2、x3、x4均得到满足要求的值，则找到一组解，如图6-2中的X(2,4,1,3)。
通过上述不断的测试，可以把n皇后问题的所有解全部找出来。这个求解策略就是回溯法。
图6-2 4皇后问题的回溯过程
采用回溯法求解问题，需要将问题的解表达为n元组(X1,…,X i,…X n)，其中X i选自有限集S i，当选出一组值X=(x1,…,x i,…x n)能够使评价函数P(x1,…,x i,…x n) 满足问题的某种约束条件或到达极值，则X为此问题的解或最优解。这里4皇后问题的评价函数就是对“同一行、同一列和同一斜线”的判断。
若采用枚举搜索技术，则需要枚举出所有可能的n元组，并用P(X1,…,X i,…X n)去一一评价，所需的时空复杂性一般令人难以接受。回溯法可以看作枚举搜索技术的改进，它通过剪枝技术（参看（2）、（3）、（4）中的回溯），可以避免搜索所有可能的解。
回溯法的基本策略是每次只考虑一个分量，逐次扩大建立n元组，并随时用评价函数P i(X1,…,X i,…X n)去判断正在形成的n元组是否有成功的希望，一旦确定部分元组(X1,…,X i)不能求出解时，则立即停止这种搜索，“剪掉”以当前结点为根的分枝，并逐次向上一个分量回溯，然后向其它分支继续探索。
上述搜索过程通常会形成一棵包含问题解的树，称之为解空间树。树的每一个结点表示问题求解过程中的一个状态，从树根到其它结点的全部路径构成了问题的解空间，每条自根到叶子的路径代表了解空间中的一个元组，所有满足约束条件的元组构成了问题的解集合，而约束描述了X i彼此相关的情况。解空间树是在求解的过程中，一个结点一个结点逐步生成的，为了更好的理解和讲解算法，可以将这些结点分为活结点、扩展结点和死结点三类。在解空间树中那些已经生成了部分子结点，但还没有全部生产完毕的结点叫做活结点；当前正在生成子结点的活结点叫做扩展结点；那些不再进一步扩展或已经将全部子结点生成完毕的结点叫做死结点。
6.1.2算法框架
通过4皇后问题生成解的过程，可以了解到回溯算法是从开始结点进行深度优先搜索，并通过剪枝技术提高搜索效率的算法策略，其过程可描述如下：
(1)开始结点是一个活结点，也是一个扩展结点；
(2)如果能从当前的扩展结点移动到一个新的结点，那么这个新结点将变成一个活结点和可扩展结点，旧的扩展结点仍是一个活结点。
(3)如果不能移动到一个新结点(已经找到一个解或违反约束的情况)，当前的扩展结点就变成了一个死结点，便只能返回到最近被考察的活结点(回溯),这个活结点就变成了新的扩展结点。
(4)当找到了最优解或者没有活结点的时候（回溯尽了所有的活结点），搜索过程结束。
根据这一描述过程，可以得到回溯算法策略的框架：
输入：n
6.1.3回溯算法的适用条件
回溯算法需要满足多米诺性质，才能得到正确的应用。
多米诺性质设向量X i=
P(X i+1)→P(X i) i∈(0,n)
其中，n代表解向量的维数。
【例6-1】求满足下列不等式的所有整数解：
5x1+4x2-x3≤10 1≤x i≤3 i=1, 2, 3
解：令X i=
x1
x2
x3
图6-3 例6-1的解空间树
注意图6-3的虚线部分，当x1=1、x2=2时，P(x1,x2)= 5x1+4x2=5*1+4*2=13>10，不满足约束条件，x2=2这条分支将被剪去，然而，当x1=1、x2=2、x3=3时，P(x1,x2,x3)= 5x1+4x2- x3=5*1+4*2 - 3=10，满足约束条件，即<1, 2, 3>是不等式的解，显然，此例中P(X3)不真蕴涵P(X2)，违反了多米诺性质，从而丢解了。如果令x’3=4-x3，将原不等式变换为：
x1+4x2+x’3≤10 1≤x i, x’3≤3 i=1, 2
则该不等式满足多米诺性质，可以使用回溯法，对所得到的解x1、x2、x’3转换成原不等式的解x1、x2、x3即可。
6.2回溯算法的经典例题
6.2.1装载问题
【例6-2】有一批共n个集装箱要装上一艘载重量为c的轮船，其中集装箱i的重量为w i。找出一种最优装载方案，将轮船尽可能装满，即在装载体积不受限制的情况下，将尽可能重的集装箱装上轮船。
问题分析
假设集装箱数量n=5，轮船的载重量c=10，每个集装箱的重量w={7,2,6,5,4}即w1=7，w2=2，w3=6，w4=5，w5=4。5个物品的装载可以表示为一个五元组X=（x1，x2，x3，x4，x5），每个x代表一个集装箱，其值表示装载情况，由于每个集装箱装载只有两种可能：装和不装，所以，x i (i=1,2,3,4,5，表示集装箱编号)只能从0和1中选择其一，其中，0表示不装，1表示装载。能否装载当前的集装箱，要看船上已装箱子的重量加上当前箱子的重量是否超过轮船的载重量，这个判断构成了评估函数P。
用回溯法进行求解，可以生成一棵解空间树。因为有5个集装箱可以选择装载，所以最多判断到第5个箱子时，一轮搜索结束，并能得到问题的部分解，因此，问题的解空间树高为5，如图6-4所示。解空间树的每一层代表一个集装箱，它有两个分支，左分支代表装载：x i =1，右分支代表不装载：x i =0。
执行的过程为：
（1）选择第一个集装箱x1=1，判断是否超过船的载重：w1×x1＝7×1＝7<10，可装载。
（2）选择第二个集装箱x2=1，判断是否超过船的载重：w1×x1+ w2×x2＝7+2×1＝9<10，可装载。
（3）选择第三个集装箱x3=1，判断是否超过船的载重：w1×x1+ w2×x2+ w3×x3＝9+6×1＝15>10，不可装载。观察图6-4，当不选择第三个集装箱时，第三层最左端下方结点以下的分支被裁掉（图6-4中虚线所示，即不再往下尝试），应当沿此结点的弧线向上回溯到第二层下面的结点，并沿其右分支继续选择，令x3 =0，有w1×x1+ w2×x2+ w3×x3＝9+6×0＝9<10。
（4）选择第四个集装箱x4 =1，判断是否超过船的载重：w1×x1+ w2×x2+ w3×x3+ w4×x4=9+5×1＝14>10，不可装载。同（3）一样，应当沿此结点的弧线向上回溯到第三层下面的结点，并沿其右分支继续选择，令x4 =0，有w1×x1+ w2×x2+ w3×x3+ w4×x4＝9+5×0＝9<10。
（5） 选择第五个集装箱x 5=1，判断是否超过船的载重：w 1×x 1+ w 2×x 2+ w 3×x 3+ w 4×x 4+ w 5×x 5=9+4×1＝13>10，不可装载。同（4）一样，应当沿此结点的弧线向上回溯到第四层下面的结点，并沿其右分支继续选择，令x 5 =0，有w 1×x 1+ w 2×x 2+ w 3×x 3+ w 4×x 4+ w 5×x 5＝9+4×0＝9<10。因为一共有5个集装箱，所以，至此全部选择完成。
第（5）步选择完成后，到达图6-4中的A 点，得到一组结果X=(1,1,0,0)，船共装载两个集装箱、重量为9。在搜索完解空间树后，可得到最优装载为标号G 对应的解X=(0,0,1,0,1)，装载重量为10。
初始状态1:装入A
X=(1,1,0,0,0)
B
X=(1,0,0,0,0)
C
X=(0,1,1,0,0)
D
X=(0,1,0,1,0)
E
X=(0,1,0,0,1)
F
X=(0,1,0,0,0)
G
X=(0,0,1,0,1)H X=(0,0,1,0,0)I
X=(0,0,0,1,1)J X=(0,0,0,1,0)K X=(0,0,0,0,1)
不可行,x 1x 3
图6-4 装载问题的回溯过程
结合上述实例的分析，不难列出此问题的数学模型：
对于n 个集装箱的装载问题，可将该问题的解定义为一个n 元组(x 1,…,x i ,…x n ), i ∈Z, 1≤i ≤n, x i ∈{0,1},x i =1表示装入集装箱i ，x i =0表示不装入集装箱i 。
目标函数：max ∑w i x i n i=1
约束条件s.t. {∑w i x i n i=1≤c
x i ∈{0,1},i =1,2,…n w i >0
其中，w i 表示第i 个集装箱的重量。 满足多米诺条件：令P(x 1, x 2,…,x k )为∑w i x i k i=1>c 1，从而
∑w i x i k i=1>c 1→∑w i x i k+1
i=1>c 1
再来分析一下这个问题的时间复杂度，由图6-4可知，装载问题的解空间树自顶向下共32条路径，正好是25，构成了一棵完全二叉树。这不是巧合，装载问题的回溯法求解过程构造了一棵选择树，在第4章中曾介绍过选择树的时间复杂度与所选择物品的数量有关，由n 个物品构成的选择树，时间复杂度为2n 。但幸运的是，回溯法不需要对所有分支进行搜索，存在很多剪枝操作，如图6-4中的虚线部分，因此，在6.1节中介绍回溯算法策略时，有“回溯法可以看作枚举搜索技术的改进”的说法。
? 计算模型
（1） 数据结构定义 设：
● 静态数据结构：轮船载重量为c ，集装箱数量为n ，集装箱重量数组w[]，这些变量在运算中不会发生改变。
● 动态数据结构：i 表示搜索的层数，加入一个集装箱后计算出的当前载重量nowc 、当前解x[]、当前最优重量maxc 、当前最优解maxx[]，剩余的集装箱重量r （初值为全部集装箱重量），这些值都是边测试边生成的，当所有计算全部完成后，maxc 和maxx[]就是题目要求的最优值和最优解。
（2） 迭代公式
{maxc =nowc ，maxx[]=x[] i >n 且nowc >maxc (1)nowc =nowc +w [i ]， x [i ]=1 nowc +w [i ]<=c (2)nowc =nowc ?w [i ]，x [i ]=0 nowc +r >maxc (3)
其中，式（1）表示搜索到最后一个集装箱后，判断当前累加值nowc是否大于上一次计算的最大值，若大于，则替换最大值和最优解。式（2）表示若当前集装箱重量加上已装船的集装箱重量没超过船的总装载量，则可以装船，它的判断条件即是评价函数。式（3）表示，若式（2）不满足且剩余集装箱重量r与已装船集装箱重量nowc的和超过现装载最大重量，则可能还存在最优解，可以继续装载，装载前要除去尝试装载的
输出：最优值maxc和最优解maxx[]
6.2.2n皇后问题
【例6-3】经典的n皇后问题是指在一个n*n的棋盘上放置n个皇后，按照国际象棋的规则，任意两个皇后之间不能处在同一行、同一列和同一斜线上，否则皇后就可以攻击与之处在同一行、同一列或同一斜线上的棋子。请给出满足条件的所有方案。
?问题分析
详见6.1.1算法思想。
?计算模型
（1）数据结构
棋盘格子数为n*n 个，但皇后的摆放位置可以用一维数组x[]来表过，数组元素的下标为皇后所在的行数，数组元素的值为皇后所在列数。设皇后数量为n ，并用sum 记录可行解的数量。i 代表搜索的层次或深度。
（2） 摆放过程就是依次给x[i]赋连续的正整数，要保证一个互相不攻击的格局，其计算模型如下：
{x [i ]=k i ∈[1,n ],k ∈[1,n ] (1)x [i ]≠x [j ] i ≠j (2)|x [i ]?x [j ]|≠|i ?j | (3)
其中，式（1）在第i 行依次尝试每个位置k （从1到n ），当i 从1取到n 时，则每一行的正确位置被找到。式（2）是当保证皇后处在不同行（i ≠j ）上时列也不同（x[i]≠x[j]）。式（3）保证任意两个皇后都不能处在一条斜率为1（
|x i ?x j ||i?j |
=1）的斜线上。
式（1）是一个摆放的过程，而式（2）与式（3）共同构成了对式（1）中所取得的值的一个评价，所以
输出：皇后的摆放位置x[]，可以有多组
6.2.3 0-1背包问题
【例6-4】已知有n 件物品，物品i 的重量为wi 、价值为p i 。现从中选取一部分物品装入一个背包内，
背包最多可容纳的总重量是m ，如何选择才能使得物品的总价值最大？如果限定每种物品只能选择0个或1个，则该类问题被称为0-1背包问题。
? 问题分析
依据题意，从一个具体实例着手，对背包问题进行分析，找出其中的设计规律。假设物品数量n=3，物品重量w={10,20,30}，物品价值p={60,100,120}，背包最多可容纳的重量m=50。根据题意，问题的解空间为长度等于3的0和1的组合，设定一个三元组X=（x 1，x 2，x 3）存储解。其解空间树如图6-5所示，图中每个结点代表一个状态，树根代表初始状态，此时背包中物品的总量和总价都是0。第一层结点2个状态，分别代表x 1取1和取0的情况，依次类推，第二层结点4个状态，对应x 2的取值情况，第三层结点8个状态，对应x 3的取值情况。从根结点到叶子一共有8条路径，每条路径都是由x 1、x 2和x 3构成的一个解。其中A ，B ，C ，D ，E ，F 是可行解，D 是其中的最优解，其他叶子结点是不可行解。
1:装入初始状态
背包容量m=50背包总重bagw=0背包总价bagp=0
背包总重bagw=10背包总价背包总重背包总价bagp=160背包总重超重，回溯
A
X=(1,1,0)
背包总重bagw=30背包总价bagp=160
A
B
X=(1,0,1)
背包总重bagw=40背包总价bagp=180
B
C
C
X=(1,0,0)
背包总重bagw=10背包总价bagp=60
D
D
X=(0,1,1)
背包总重bagw=50背包总价bagp=220
E E
X=(0,1,0)
背包总重bagw=20背包总价bagp=100
F
X=(0,0,1)
背包总重bagw=30背包总价bagp=120
F
G
图6-5 0-1背包问题的回溯过程
基于这棵树用回溯法求解0-1背包问题的过程与最优装载问题的思路一样，即从根结点开始对这棵完全二叉树进行深度优先遍历或者说先根遍历。每访问一个结点，都要判断装载物品的重量是否超出了背包的容量，如果没超，则将物品i 加入背包（x i =1），计算背包中物品的总价值，如果超了，则向上回溯，走右分支（x i =0）。图中具体给出了x1=1，x2=1和x3=1时先根搜索的判断及回溯过程。图中C 、E 及G 结点可以剪掉，用虚线表示，这是因为它们的左兄弟是可行解，而且要优于它们。
基于上述分析，可以将背包问题的解定义为一个n 元组(x 1,…x i ,…x n )，x i ∈{0,1}，i=1,2,…n 。x i =0时表示弃选第i 个物品，x i =1时候，表示将第i 个物品装入背包内。因此，背包的问题的数学模型如下：
目标函数：max ∑p i x i n i=1
约束条件s.t. {∑w i x i n i=1≤m x i ∈{0,1},i =1,2,…n p i >0, w i >0
? 计算模型 （1） 数据结构
● 静态数据结构：背包容量m ，物品数量n ，物品重量数组w[]，物品价值数组p[]。 ● 动态数据结构：当前背包重量bagw ，当前背包总价bagp ，当前最优解x[]，当前最优总价值maxp ，最优解maxx[]，可用的物品价值r 。
（2） 迭代公式
{maxp =bagp ，maxx[]=x[] i >n 且nowc >maxc (1)bagw =bagw +w [i ],bagp =bagp +p [i ],x [i ]=1 bagw +w[i]<=m (2)bagw =bagw ?w [i ],bagp =bagp ?p [i ],x [i ]=0 bagp +r >maxp (3)
其中，式（1）表示装到最后一个物品后，若当前累加值nowc 大于上一次计算的最大值，则替换最大
值和最优解，此式可以作为递归的出口。式（2）表示若当前背包重量加上未装包的物品重量没超过背包的总装载量，则可以装包，它的判断条件即是评估函数。式（3）表示，若式（2）不满足且剩余物品重量r与已装包物品重量nowc的和大于现装最大重量，则可能还存在最优解，可以继续装，装载前要除去尝试装载的物品重量及选择值；若剩余物品重量r与已装包物品重量的和小于现装最大重量，则要进行剪枝。
输出：最优总价值maxp和最优解maxx[]
6.2.4旅行商问题
【例6-5】旅行商问题(Traveling Salesman Problem，简称TSP)是威廉.哈密尔顿爵士于19世纪初提出的一个数学问题：有若干个城市，任何两个城市之间的距离都是确定的，现要求一旅行商从某城市出发必须经过每一个城市且只能在每个城市逗留一次，最后回到原出发城市，问如何事先确定好一条最短的路线使其旅行的费用最少。
?问题分析
以具体实例来对这一问题进行分析。假设城市数量n=4，V={A,B,C,D}，城市间的距离如图6-9所示的图结构。设出发城市为A ，根据题意，问题的解空间为{A →{B ，C ，D 三者的全排列}→A}，即{{A →B →C →D →A},{A →B →D →C →A},{A →C →B →D →A},{A →C →D →B →A},{A →D →B →C →A},{A →D →C →B →A}}，解的数量6，其解空间树如图6-7所示，这棵树有且只有一个叶子结点A 。从图中很快可以选出一条总距离最短的路线，即问题的解是{A->B->D->C->A}，最短总距离为14。
图6-6 TSP 问题的图 图6-7 TSP 问题的解空间树
针对于图6-6的TSP 问题，可进行图6-7的回溯搜索，其过程如下： (1)从根结点A 出发，搜索至B ，C ，D ，A ，在叶节点A 处记录可行解为A →B →C →D →A ，长度为15。并且记为当前最优路线。
(2)从叶子结点A 回溯到最近结点D ，发现D 没有可扩展结点（除了A 点之外，其余全部用在行驶线路上），又回溯到C 处，C 依旧没有可扩展结点（除A 点外，只有D 点未用，而D 点在上次尝试的线路中已被使用，即C →D ），继续向上回溯到结点B 。结点B 可扩展结点D （上一次尝试的结点是C →D ），D 再到结点C ，由C 到A ，得到一个新的可行解A →B →D →C →A ，长度为14。这个路线比当前最优路线小，所以修正当前最优路线。
(3)在(2)的基础上又依次回溯到根结点A ，A 继续扩展到C ，C 扩展到B ，B 扩展到D ，又由D 到A ，得到可行解A →C →B →D →A ，长度为21。这个路线不比当前最优路线小，所以舍弃。
(4) 重复上述回溯过程，又得到另外3条可行解A →C →D →B →A ，A →D →B →C →A ，A →D →C →B →A ，最终回溯到根结点A ，A 再无可扩展结点，回溯结束。输出最终的最优路线为A →B →D →C →A ，长度为14。
根据上述分析，假设有n 个城市，记为V={v 1,v 2,…v n }，任意两个城市（v i , v j ）∈V 之间的距离为d vivj ，且d vivj =d vjvi ，则问题的解是寻找城市的一个访问顺序X={x 1,x 2,…, x i ,…, x n ,x 1}，其中x i ∈V ，使得在一次性遍历所有结点并回到起点（哈密尔顿环）的环路集中，X 是最短的，它的数学模型为：
目标函数：min (∑d x i x i+1+d x n x 1n?1i=1)
约束条件：s.t. {x i ≠x j x i ,x j ∈V
d x i x i+1>0
? 计算模型
（1） 数据结构
● 静态数据结构：城市数量n ，距离矩阵d[][]，城市名称city[]。
● 动态数据结构：当前路径距离nowd ，当前路径nowx[]，最短距离mind ，最优路径x[]。 （2） 迭代公式 （公式需要调整）
A
B
D
C
2
7
644
2
{nowd=nowd+d[t][1],mind=nowd,x[]=nowx[] i>n 且nowd nowd=nowd?d[t][j],nowx[i]="",nowd=nowd?d[t][1] (3)其中，式（1）表示访问到最后一个城市后，若当前累加值nowd小于上一次计算的最小值，则替换最大值和最优解，nowd=nowd+d[t][1]是从最后一个城市返回出发地。式（2）表示若当前城市未被访问过，则访问这个城市，增加访问的路程长度。式（3）表示访问完一个城市后，回溯到上一层，恢复到上级状态。 ?算法设计与描述 输入：城市数量n，距离矩阵d[][]，城市名称city[] ?算法分析 旅行商问题的解决方法显然与前几道题不同，它所生成的解空间树不是一棵选择树，而是一棵排序树，即父结点与子结点的顺序不同，则结果不同。由图6-7可知，对于由4个城市形 成的全排列树来说，第一层1个结点，第二层3个结点（n-1），第三层6个结点（n-1）*（n- 2），第四层为叶子结点等于第三层。按此规律，对由n个城市形成的全排列树来说，所含的结 点数目为： T(n) =1+(n-1)+(n-1)(n-2)+ (n-1)(n-2) (n-3) +……+((n-1)(n-2)……2)+(n-1)! =1 + (n-1)!×(1 (n?2)!+1 (n?3)! +?+1 2 +1) ≤1 + (n-1)!×(1 2n?3+1 2n?4 +?+1 2 +1)//依据斯特林公式有log2(n!)=θ(log22n)≥log22n?1 ≤1 + (n-1)!×1 1?1 2 = 1+2(n-1)!=O((n-1)!) 由上述4个实例可以看出回溯算法的一些共同特征： （1）可求解搜索问题和优化问题。 （2）解空间是一棵搜索树，每个结点对应了部分向量，满足约束条件（或评估函数）的树叶对应了可行解，在优化问题中不一定是最优解。 （3）搜索过程一般采用深度优先、宽度优先、函数优先或宽深结合等策略隐含遍历搜索树，所谓隐含遍历是指：不是真正访问到每个结点，需要从搜索树中进行裁减。 （4）满足约束条件（或评估函数）则分支扩张解向量；不满足约束条件回溯到该结点的父结点。6.3分支限界法的设计技术 考察6.2小节中所介绍的背包问题和旅行商问题，不难发现使用回溯法所得到的算法复杂度与第4章4.2小节用穷举法所得到的是一样的。但是，在6.2小节的分析中，我们也强调了若以当前结点为根的子树不能满足评估函数（目标函数）的要求时，算法将剪去这个子树，回溯到上一层重新选择，而不是像穷举法一样继续向下搜索。也就是说，通过约束条件进行剪枝操作使得算法效率提高，是回溯法不同于穷举法的关键点。按照这个思路，如果能够增加约束条件，过虑掉更多的结点，剪掉更多分支，就能更好地加快算法的执行速度。由此，分支限界法应运而生。其算法思想如下： 为了能够剪掉更多的分支，可以尝试增加以下约束： （1）上界函数，用来求得以当前结点为根的可行性解可能达到的极值，即当搜索进行到此结点时，以后无论怎么选择此结点的后代，目标函数所能达到的最大值都不会超过这个值。它是以当前结点为根的子树的所有可行解（由此子树参与的整个问题的解）的一个上界。由此定义可知，对于极大化组合优化问题，上界函数在父结点的值大于或等于在子结点的值。而对于极小化组合优化问题则与引正好相反，它的上界函数是用来求下界的。 （2）限界值，搜索到某一结点时，已经得到的可行解的最优值。 上界与限界值不同，上界是对当前分支的一种预测，是选择当前分支后可能达到的最大值，不一定是可行性解的值，选择此分支后所得到的可行性解（如果有的话）值不大于上界。限界是已找到可行性解当中最优解的值。若某分支的上界小于限界，说明在分支当中不可能找到小于该限界的可行性解，则应当停止对此分支的继续搜索。由于对于上界的预测是在搜索该分支之前，因而提高了效率。 在回溯法中，剪枝主要是因为不满足评价函数，而本算法除了评价函数外，还增加了上界函数与界限值的约束，通常可以剪掉更多的分支，也因此而被称为分支限界法。不难看出，它是回溯法的改进或升级。 一般来说，对于一个分支界限算法的解空间树来说，只要符合下面三种中的一种原因，则终止它在当前结点上的查找路径，进行剪枝： （1）该结点的上界小于界限值，即再往下搜索也不可能有更优的值。 （2）该结点无法代表任何可行解，因为它已经违反了问题的约束，不能满足评价函数。 （3）该节点代表的可行解的子集只包含一个单独的点，因此无法给出更多的选择。在这种情况下，将这个可行解在目标函数上的值和当前求得的界限值进行比较，如果新值更好一些，就用前者替换后者（界限值）。 经过上述讨论，可知设计分支限界算法的基本步聚如下： （1）建立上界函数，函数值是以该结点为根的搜索树中的所有可行解在目标函数上求得值的上（下）界。 （2）求得限界值，即当前巳经得到的可行解的目标函数的最大值。 （3）依据剪枝条件，停止分支的搜索，向上回溯到父结点。 （4）限界值的更新：如果目标函数值为正数，初值可以设为0，在搜索中如得到一个可行解，计算可行解的目标函数值，如果这个值大于当时的限界值，就将这个值作为新的限界。 6.4 分支限界的经典例题 6.4.1 装载问题 【例6-6】有n 个集装箱要装上一艘载重量为c 的轮船，其中集装箱i 的重量为w i 。找出一种最优装载方案，将轮船尽可能地装满，即在装载体积不受限制的情况下，将尽可能重的集装箱装上轮船。 ? 问题分析 本例题与【例6-2】一样，装载时同样要满足条件∑w i n i=1≤c ，即所装货物重量必须小于船的载重量。以4个集装箱为例，船的载重量c=10，集装箱的重量W={7，4，2，6}。如图6-8所示，这个问题的解空间是一棵选择树，结点代表集装箱装载的次序，边代表选择，左分支为选择（x i =1）,右分支为不选择（x i =0）。使用分支限界法求解，不需要遍历解空间，它有两个特点：（1）分支限界法的解空间是边求解边生成的；（2）在生成过程中剪去那些不符合要求的分支。 对于特点（1），分支限界法是按层进行子树生成的，需要借助一个队列来完成这一任务，入队和出队时，要对结点进行筛选。没有入队的结点，将不能对其进行扩展，也就不能生成以此结点为根的子树；入队的结点则可以进一步地扩展。这步操作即为剪支操作。 对于特点（2），有以下两种办法进行剪支：（1）预装入集装箱的重量加上船上已有集装箱的重量超过船的最大载重量，则此集装箱将不被装入；（2）在右分支的选择（即不装入当前集装箱）中，若船上已有集装箱的重量加上剩余所有尚未进行选择的集装箱的重量都不能超过当前已有的最优装载方案（注意，不同的分支就是不同的装载方案），则不用再扩展该结点了。 为了能够比较清晰地展示分支限界算法在本例题中的应用，先设定以下几个变量： ● C ：表示船的载重量。 ● w[]：表示集装箱重量。 ● x ：左儿子标识。 ● s ：表示当前未装船的集装箱总重量。 ● lw ：表示当前已装船的集装箱总重量。 ●bestw：表示当前船上装载的集装箱的最优值。 ●pw：表示预装船集装箱重量与当前已装船集装箱重量之和。在准备装载某个集装箱时，要先测试其重量加上已装船集装箱的重量后是否超出船的承载量。若pw 图6-9 分支限界法生成的选择树 尽管结点表示集装箱的重量，但是只有经过选择边后才能确定该集装箱是否能被装船，例如由结点1到结点2处，确定集装箱1可以被装船，且到结点2时，船上装载了集装箱1。因而在建造选择树时，并不让结点1入队。所以，第一层是由结点2和结点3组成的，这一层确定了集装箱1是否被装船：如经过8结点1的左分支到达结点2，则集装箱1被装船；如经过结点1的右分支到达结点3，则集装箱1未装船。现在就从结点1开始，借助辅助队列逐层生成选择树，并确定最优解和最优值。见图6-9和图6-10，其执行步骤如下： Step1：分层标志0入队列，如图6-10（1）所示。初始化各计算变量，c=10；w[]={0, 7, 4, 2, 6}。当前没有集装箱装船，lw=0，bestw=0。测试从集装箱1开始，剩余集装箱总重s= w[2]+ w[3]+w[4]=12。 Step2：尝试装载集装箱1。船当前载重量lw加集装箱1的重量w[1]，与船的总装载量c相比较，测得pw=lw+w[1]=7，pw Step3：结点3入队，如图6-10（1）的“2-3入队”所示。任意结点的右子树都表示不选择该集装箱，一般来说，可以将其放入队列，以便参与后面的最优化选择。但是，如果剩余尚未经过选择的未装船集装箱的重量加上已装船集装箱的重量之和仍小于等于最优值，则说明沿此结点再扩展，也不可能再生成一个更优的值，因此剪掉它，这样可以减少计算量。此处不装集装箱1，lw=0，便仍然有lw+s=12>bestw，说明剩余未经选择的集装箱重量仍有可能构成最优解，因此，结点3入队。结点3对应结点1左子树x=false的情况，同结点2一样parent=0。 13-10入队lw=pw=914-11入队lw=716-12入队lw=6bestw=pw=9 lw=pw=1017-13入队19-14入队lw=pw=2bestw=pw=10 4-分层标 lw=7lw=pw=4lw=0 10-0出队 11-分层标 12-5出队lw=pw=9lw=7 15-6出队lw=6bestw=pw=9 lw=4 18-7出队19-14入队lw=pw=2 3-0出队 lw=pw=7分层标志 4-分层标 lw=0 lw=0 5-2出队 lw=76-5入队 lw=pw=4lw=0 8-6入队9-7入队bestw=pw=711-分层标执行操作 1-0出队 执行次序 结点编号 (1)解空间一、二层所用队列片段(2)解空间二、三层所用队列片段 (3)解空间三、四层所用队列片段 21-分层标 图6-10 辅助队列协助分支限界法的运算过程 Step4：结点0出队，如图6-10（1）的“3-0出队”所示。当结点0出队时，表示本层结点测试完毕，满足条件的结点均已进入队列，下一层的分层标志结点0入队，如图6-10（1）的“4-分层标志入队”所示。 Step5：结点2出队，如图6-10（1）的“5-2出队”所示。此时，需要测试它的两个分支，首先是左子树，装载集装箱2，船上已装载的重量（结点2的lw 值）加上集装箱2的重量w[2]，与船的载重量c 相比较，即pw=lw+w[2]=7+4=11>c ，超出船的载重，结点4不能入队（图6-10（1）中没有结点4），同时剪掉以结点4为根的子树，见图6-9。 Step6：再测算结点2的右子树，不装载集装箱2，剩余集装箱重量s=s-w[2]=12-4=8。船上已装载的重量（结点2的lw 值）加上未装船的集装箱总重量与当前最优的载重量相比较，即lw+s=7+8=15>bestw=7，右子树仍有可能产生更优解，结点5入队，如图6-10（1）的“6-5入队”和图6-9所示。 Step7：结点3出队，如图6-10（1）的“7-3出队”所示。测试它的两个分支，首先是左子树，装载集装箱2，船上未装载任何集装箱（lw=0），因此有pw=lw+w[2]=0+4=4 Step6：测算结点3的右子树，不装载集装箱2，剩余集装箱重量s=s-w[2]=8。船上未装载任何集装箱（lw=0）时，也不装载集装箱2，仍有lw+s=0+8=8>bestw=7，右子树仍有可能产生更优解，结点7入队，如图6-10（1）的“9-7入队”和图6-9所示。 Step7：结点0出队，如图6-10（2）的“10-0出队”所示。表示本层结点测试完毕，满足条件的结点均已进入队列，下一层的分层标志结点0入队，如图6-10（2）的“11-分层标志入队”所示。 Step8：结点5出队，见图6-10（2）中的“12-5出队”。需要测试它的两个分支。首先是左子树，装载集装箱3。船上已装载的重量（结点5的lw=7）加上集装箱3的重量w[3]，与船的载重量c 相比较，即pw=lw+w[3]=7+2=9 Step9：测试结点5的右子树。不装载集装箱3，剩余集装箱重量s=s-w[3]=6，船上已装载的重量（结点5的lw=7），两者相加与当前最优的载重量作比较，lw+s=7+6=13>bestw ，结点11入队，如图6-10（2）的“14-11入队”和图6-9所示。 Step10：结点6出队，如图中6-10（2）的“15-6出队”所示。测试它的左子树，装载集装箱3，船上装载集装箱重量（lw=4）。因此有pw=lw+w[3]=4+2=6 Step11：测试结点6的右子树，不装载集装箱3，剩余集装箱重量s=6，船上装载集装箱重量（lw=4）， 此时有lw+s=4+6=10>bestw，结点13入队，如图6-10（2）的“17-12入队”和图6-9所示。 Step12：结点7出队，见图6-10（2）中的“18-7出队”。测试它的左子树，装载集装箱3，船上装载集装箱重量（lw=0），因此有pw=lw+w[3]=0+2 Step13：测试结点7的右子树，不装载集装箱3，剩余集装箱重量s=6，船上装载集装箱重量（lw=0），此时有lw+s=0+6=6 Step14：结点0出队，见图6-10（2）中的“20-0出队”。表示本层结点测试完毕，满足条件的结点均已进入队列，下一层的分层标志结点0入队，如图6-10（3）的“21-分层标志入队”所示。 Step15：结点10出队，见图6-10（3）中的“22-10出队”。测试它的左子树，装载集装箱4，船上装载集装箱重量（lw=9），因此有pw=lw+w[4]=9+6>c，结点20不入队，如图6-9所示。 Step16：测试结点10的右子树，不装载集装箱4，剩余集装箱重量s=6-w[4]=0，船上装载集装箱重量（lw=7），此时有lw+s=7+0=7 Step17：结点11出队，见图6-10（3）中的“23-11出队”。测试它的左子树，装载集装箱4，船上装载集装箱重量（lw=7），因此有pw=lw+w[4]=7+6>c，结点22不入队，如图6-9所示。 Step18：测试结点11的右子树，不装载集装箱4，剩余集装箱重量s=0，船上装载集装箱重量（lw=7），此时有lw+s=7+0=7 Step19：结点12出队，见图6-10（3）中的“24-12出队”。测试它的左子树，装载集装箱4，船上装载集装箱重量（lw=6），因此有pw=lw+w[4]=6+6>c，结点24不入队，如图6-9所示。 Step20：测试结点12的右子树，不装载集装箱4，剩余集装箱重量s=0，船上装载集装箱重量（lw=6），此时有lw+s=6+0=6 Step21：结点13出队，见图6-10（3）中的“25-13出队”。测试它的左子树，装载集装箱4，船上装载集装箱重量（lw=4），因此有pw=lw+w[4]=4+6=c，结点26不入队。但是请注意，这里已到达选择树的最底部，最后一个货物已装完，且恰好达到船的最大载重，是最优解，如果只要求得到最优解，则求解工作完成，如图6-9所示。但有些题目要求输出全部最优解，则需要继续运算下去。另外，本例到这里产生最优解是一个巧合。下面的过程与上面雷同，不再进行讨论。 计算模型 （1）数据结构 大部分数据结构在问题分析中已经介绍过了，除此之外，结点的构造如下： class QNode { template friend int EnQueue(Queue T bestw, QNode template friend Type MaxLoading(Type w[],Type c, int n, int bestx[]); public: QNode *parent; //父结点 bool LChild; //左孩子标志，是左孩子值为真，否则为右孩子。 Type weight;//结点权值 }; 为了使队列具有更大的灵活性，这里使用了C++中的模板编程。在结点类中加入了对其进行操作的友元函数EnQueue和MaxLoading，其中EnQueue是入队函数，MaxLoading是求解最优解函数。为了得到最优解，设置了父结点指针parent和左孩子标志LChild，其中通过parent把各个结点串连起来，LChild对应着集装箱的选择情况，标志为真就选择，为假就不选择。 bestv[]用来记录集装箱的选择情况，选择了是1，不选择为0，它是在搜寻父结点时，通过判断LChild 值来确定的。 （2）计算公式 依据问题分析，可知最优解是通过构造搜索空间得到的，而搜索的次序是由队列来控制的，即按次序分层进入队列，出队列生孩子结点，再入队列，循环这两种操作，直至找到最优解或搜索不到最优解（只要一个集装箱能装船就有最优解），而运算过程基本是：通过判定父结点权值（代表船上已装集装箱的重量）+当前预装集装箱的重量是否大于船的最大载重量，确定有无左孩子，即能否装船。剩余未装船的集装箱重量+父结点权值与当前已知的最优值作比较，来确定：如果不装载当前预装集装箱，是否仍能够达到最优值，它们的公式如下： pw=lw +w[i];//预装重量 bestw=pw pw<=c且pw>bestw //更新最大值 w[i]→Q pw<=c//选择左子树，装船 输出：最优值maxc和最优解maxx[] 分支限界法的研究与应用 摘要： 分支限界法与回溯法的不同:首先,回溯法的求解目标是找出解空间树中满足约束条件的所有解,而分支限界法的求解目标则是找出满足约束条件的一个解,或是在满足约束条件的解中找出在某种意义下的最优解。其次，回溯法以深度优先的方式搜索解空间树，而分支限界法则一般以广度优先或以最小耗费优先的方式搜索解空间树。再者，回溯法空间效率高；分支限界法往往更“快”。 分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。 常见的分支限界法有：队列式分支限界法，按照队列先进先出原则选取下一个结点为扩展结点。栈式分支限界法，按照栈后进先出原则选取下一个结点为扩展结点。优先队列式分支限界法，按照规定的结点费用最小原则选取下一个结点为扩展结点（最采用优先队列实现）。 分支搜索法是一种在问题解空间上进行搜索尝试的算法。所谓分支是采用广度优先的策略国,依次搜索E-结点的所有分支,也就是所有的相邻结点。和回溯法一样,在生成的结点中,抛弃那些不满足约束条件的结点,其余结点加入活结点表。然后从表中选择一个结点作为下一个E-结点,断续搜索。 关键词： 分支限界法回溯法广度优先分支搜索法 目录 第1章绪论 (3) 1.1 分支限界法的背景知识 (3) 1.2 分支限界法的前景意义 (3) 第2章分支限界法的理论知识.................. 错误!未定义书签。 2.1 问题的解空间树 ............................................... 错误!未定义书签。 2.2 分支限界法的一般性描述 (6) 第3章作业分配问题 (7) 3.1 问题描述 (7) 3.2 问题分析 (7) 3.3 算法设计 (8) 3.4 算法实现 (10) 3.5 测试结果与分析 (12) 第4章结论 (13) 参考文献 (14) TSP问题算法实验报告 指导教师：季晓慧 姓名：辛瑞乾 学号：1004131114 提交日期：2015年11月 目录 总述 (2) 动态规划法 (3) 算法问题分析 (3) 算法设计 (3) 实现代码 (3) 输入输出截图 (6) OJ提交截图 (6) 算法优化分析 (6) 回溯法 (6) 算法问题分析 (6) 算法设计 (7) 实现代码 (7) 输入输出截图 (9) OJ提交截图 (9) 算法优化分析 (10) 分支限界法 (10) 算法问题分析 (10) 算法设计 (10) 实现代码 (10) 输入输出截图 (15) OJ提交截图 (15) 算法优化分析 (15) 总结 (16) 总述 TSP问题又称为旅行商问题，是指一个旅行商要历经所有城市一次最后又回到原来的城 市，求最短路程或最小花费，解决TSP可以用好多算法，比如蛮力法，动态规划法…具体的时间复杂的也各有差异，本次实验报告包含动态规划法，回溯法以及分支限界法。 动态规划法 算法问题分析 假设n个顶点分别用0~n-1的数字编号，顶点之间的代价存放在数组mp[n][n]中，下面考虑从顶点0出发求解TSP问题的填表形式。首先，按个数为1、2、…、n-1的顺序生成1~n-1个元素的子集存放在数组x[2^n-1]中，例如当n=4时，x[1]={1},x[2]={2},x[3]={3},x[4]={1,2},x[5]={1,3},x[6]={2,3},x[7]={1,2,3}。设数组dp[n][2^n-1]存放迭代结果，其中dp[i][j]表示从顶点i经过子集x[j]中的顶点一次且一次，最后回到出发点0的最短路径长度，动态规划法求解TSP问题的算法如下。 算法设计 输入：图的代价矩阵mp[n][n] 输出：从顶点0出发经过所有顶点一次且仅一次再回到顶点0的最短路径长度 1.初始化第0列（动态规划的边界问题） for(i=1;i 回溯法与分支限界法的分析与比较 摘要：通过对回溯法与分支限界法的简要介绍，进一步分析和比较这两种算法在求解问题时的差异，并通过具体的应用来说明两种算法的应用场景及侧重点。 关键词：回溯法分支限界法n后问题布线问题 1、引言 1.1回溯法 回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。这种以深度优先方式系统搜索问题解的算法称为回溯法。 1.2分支限界法 分支限界法是以广度优先或以最小耗费优先的方式搜索解空间树，在每一个活结点处，计算一个函数值，并根据函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间上有最优解的分支推进，以便尽快地找出一个最优解，这种方法称为分支限界法。 2、回溯法的基本思想 用回溯法解问题时，应明确定义问题的解空间。问题的解空间至少应包含问题的一个解。之后还应将解空间很好的组织起来，使得能用回溯法方便的搜索整个解空间。在组织解空间时常用到两种典型的解空间树，即子集树和排列树。确定了解空间的组织结构后，回溯法从开始结点出发，以深度优先方式搜索整个解空间。这个开始结点成为活结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为新的活结点，并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点。此时，应往回移动至最近的一个活结点处，并使这个活结点成为当前的扩展结点。回溯法以这种工作方式递归的在解空间中搜索，直至找到所要求的解或解空间中已无活结点时为止。 3、分支限界法的基本思想 用分支限界法解问题时，同样也应明确定义问题的解空间。之后还应将解空间很好的组织起来。分支限界法也有两种组织解空间的方法，即队列式分支限界法和优先队列式分支限界法。两者的区别在于：队列式分支限界法按照队列先进先出的原则选取下一个节点为扩展节点，而优先队列式分支限界法按照优先队列 0-1背包问题 计科1班朱润华 32 方法1：回溯法 一、回溯法描述： 用回溯法解问题时，应明确定义问题的解空间。问题的解空间至少包含问题的一个（最优）解。对于0-1背包问题，解空间由长度为n的0-1向量组成。该解空间包含对变量的所有0-1赋值。例如n=3时，解空间为：｛（0，0，0），（0，1，0），（0，0，1），（1，0，0），（0，1，1），（1，0，1），（1，1，0），（1，1，1）｝然后可将解空间组织成树或图的形式，0-1背包则可用完全二叉树表示其解空间给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问:应如何选择装入背包的物品，使得装入背包中物品的总价值最大 形式化描述：给定c >0, wi >0, vi >0 , 1≤i≤n.要求找一n元向量(x1,x2,…,xn,), xi∈{0,1}, ∑ wi xi≤c,且∑ vi xi达最大.即一个特殊的整数规划问题。 二、回溯法步骤思想描述： 0-1背包问题是子集选取问题。0-1 背包问题的解空间可以用子集树表示。在搜索解空间树时，只要其左儿子节点是一个可行节点，搜索就进入左子树。当右子树中有可能含有最优解时，才进入右子树搜索。否则，将右子树剪去。设r是当前剩余物品价值总和，cp是当前价值；bestp是当前最优价值。当cp+r<=bestp时，可剪去右子树。计算右子树上界的更好的方法是将剩余物品依次按其单位价值排序，然后依次装入物品，直至 装不下时，再装入物品一部分而装满背包。 例如：对于0-1背包问题的一个实例， n=4,c=7,p=[9,10,7,4],w=[3,5,2,1]。这4个物品的单位重量价值分别为[3,2,3,5,4]。以物品单位重量价值的递减序装入物品。先装入物品4，然后装入物品3和1.装入这3个物品后，剩余的背包容量为1，只能装的物品2。由此得一个解为[1,,1,1]，其相应价值为22。尽管这不是一个可行解，但可以证明其价值是最优值的上界。因此，对于这个实例，最优值不超过22。 在实现时，由Bound计算当前节点处的上界。类Knap的数据成员记录解空间树中的节点信息，以减少参数传递调用所需要的栈空间。在解空间树的当前扩展节点处，仅要进入右子树时才计算上界Bound,以判断是否可将右子树剪去。进入左子树时不需要计算上界，因为上界预期父节点的上界相同。 三、回溯法实现代码： #include "" #include 实验五分支限界法实现单源最短路径 一实验题目：分支限界法实现单源最短路径问题 二实验要求：区分分支限界算法与回溯算法的区别，加深对分支限界法的理解。 三实验内容：解单源最短路径问题的优先队列式分支限界法用一极小堆来存储活结点表。其优先级是结点所对应的当前路长。算法从图G的源顶点s和空优先队列开始。 结点s被扩展后，它的儿子结点被依次插入堆中。此后，算法从堆中取出具有最小当前路长的结点作为当前扩展结点，并依次检查与当前扩展结点相邻的所有顶点。如果从当前扩展结点i到顶点j有边可达，且从源出发，途经顶点i再到顶点j的所相应的路径的长度小于当前最优路径长度，则将该顶点作为活结点插入到活结点优先队列中。这个结点的扩展过程一直继续到活结点优先队列为空时为止。 四实验代码 #include 0-1背包问题 计科1班朱润华2012040732 方法1:回溯法 一、回溯法描述： 用回溯法解问题时， 应明确定义问题的解空间。 问题的解空间至少包含问题的一个 (最 优)解。对于0-1背包问题，解空间由长度为 n 的0-1向量组成。该解空间包含对变量的所 有 0-1 赋值。例如 n=3 时，解空间为： {(0, 0, 0), (0, 1, 0), (0, 0, 1) , (1, 0, 0), (0, 1, 1), (1, 0, 1), (1, 1, 0), (1 , 1, 1) 然后可将解空间组织成树或图的形式， 0-1背包则可用完全二叉树表示其解空间给定 n 种物品和一背包。物品i 的重量是wi ,其价 值为vi ,背包的容量为 C 。问：应如何选择装入背包的物品，使得装入背包中物品的总价值 最大？ 形式化描述：给定 c >0, wi >0, vi >0 , 1 w i < n.要求找一 n 元向量(x1,x2,…,xn,), xi € {0,1}, ? 刀wi xi w c,且刀vi xi 达最大.即一个特殊的整数规划问题。 二、回溯法步骤思想描述： 0-1背包问题是子集选取问题。0-1背包问题的解空间可以用子集树表示。在搜索解空 间树时，只要其 左儿子节点是一个可行节点， 搜索就进入左子树。当右子树中有可能含有最 优解时，才进入右子树搜索。否则，将右子树剪去。设 r 是当前剩余物品价值总和， cp 是 当前价值；bestp 是当前最优价值。当 cp+r<=bestp 时，可剪去右子树。计算右子树上界的 更好的方法是将剩余物品依次按其单位价值排序， 然后依次装入物品， 直至装不下时，再装 入物品一部分而装满背包。 例如：对于 0-1 背包问题的一个实例，n=4,c=7,p=[9,10,7,4],w=[3,5,2,1] 品的单位重量价值分别为[3,2,3,5,4]。以物品单位重量价值的递减序装入物品。 品4,然后装入物品3和1.装入这3个物品后，剩余的背包容量为1,只能装 由此得一个解为[1,0.2,1,1]，其相应价值为22。尽管这不是一个可行解，但可以证明其价 值是最优值的上界。因此，对于这个实例，最优值不超过 在实现时，由 Bound 计算当前节点处的上界。类 Knap 的数据成员记录解空间树中的节 点信息，以减少参数传递调用所需要的栈空间。 在解空间树的当前扩展节点处， 仅要进入右 子树时才计算上界 Bound,以判断是否可将右子树剪去。进入左子树时不需要计算上界，因 为上界预期父节点的上界相同。 三、回溯法实现代码： #i nclude "stdafx.h" #in clude 问题描述 给定无向图G=(V, E)，其中V是非空集合，称为顶点集；E 是V中元素构成的无序二元组的集合，称为边集，无向图中的边均是顶点的无序对，无序对常用圆括号“( )”表示。如果U∈V，且对任意两个顶点u，v∈U有(u, v)∈E，则称U是G的完全子图(完全图G就是指图G的每个顶点之间都有连边)。G的完全子图U是G的团当且仅当U不包含在G的更大的完全子图中。G的最大团是指G中所含顶点数最多的团。 如果U∈V且对任意u，v∈U有(u, v)不属于E，则称U是G 的空子图。G的空子图U是G的独立集当且仅当U不包含在G的更大的空子图中。G的最大独立集是G中所含顶点数最多的独立集。 对于任一无向图G=(V, E)，其补图G'=(V', E')定义为：V'=V，且(u, v)∈E'当且仅当(u, v)∈E。 如果U是G的完全子图，则它也是G'的空子图，反之亦然。因此，G的团与G'的独立集之间存在一一对应的关系。特殊地，U是G的最大团当且仅当U是G'的最大独立集。 例：如图所示，给定无向图G={V, E}，其中V={1,2,3,4,5}，E={(1,2), (1,4), (1,5),(2,3), (2,5), (3,5), (4,5)}。根据最大团(MCP)定义，子集{1,2}是图G的一个大小为2的完全子图，但不是一个团，因为它包含于G的更大的完全子图{1,2,5}之中。{1,2,5}是G的一个最大团。{1,4,5}和{2,3,5}也是G的最大团。右侧图是无向图G的补 图G'。根据最大独立集定义，{2,4}是G的一个空子图，同时也是G的一个最大独立集。虽然{1,2}也是G'的空子图，但它不是G'的独立集，因为它包含在G'的空子图{1,2,5}中。{1,2,5}是G'的最大独立集。{1,4,5}和{2,3,5}也是G'的最大独立集。 算法设计 最大团问题的解空间树也是一棵子集树。子集树的根结点是初始扩展结点，对于这个特殊的扩展结点，其cliqueSize的值为0。算法在扩展内部结点时，首先考察其左儿子结点。在左儿子结点处，将顶点i加入到当前团中，并检查该顶点与当前团中其它顶点之间是否有边相连。当顶点i与当前团中所有顶点之间都有边相连，则相应的左儿子结点是可行结点，将它加入到子集树中并插入活结点优先队列，否则就不是可行结点。 接着继续考察当前扩展结点的右儿子结点。当 upperSize>bestn时，右子树中可能含有最优解，此时将右儿子结点加入到子集树中并插入到活结点优先队列中。算法的while循环的终止条件是遇到子集树中的一个叶结点(即n+1层结点)成为当前扩展结点。 华北水利水电学院数据结构与算法分析实验报告2009 ～2010 学年第 1 学期2009 级计算机专业 班级：200915326 学号：200915326 姓名：郜莉洁 一、实验题目： 分别用回溯法和分支限界法求解0-1背包问题 二、实验内容： 0-1背包问题：给定n种物品和一个背包。物品i的重量是Wi，其价值为Vi，背包的容量为C。应如何选择装入背包的物品，使得装入背包中物品的总价值最大? 在选择装入背包的物品时，对每种物品i只有2种选择，即装入背包或不装入背包。不能将物品i装入背包多次，也不能只装入部分的物品i。 三、程序源代码： A:回溯法： // bag1.cpp : Defines the entry point for the console application. // #include "stdafx.h" #include 算法分析与设计实验报告第八次附加实验 for(int i=1;i 完整代码（分支限界法） //分支限界法求最优装载 #include 算法设计与分析 目录 算法设计与分析 (1) 第6章回溯与分支限界 (3) 6.1回溯法的设计技术 (3) 6.2用回溯法求解装载问题 (7) 6.3用回溯法求解n皇后问题 (9) 6.4用回溯法求解0-1背包问题 (11) 6.5用回溯法求解旅行商问题 (13) 6.6 分支限界法的设计技术 (15) 6.7 用分支限界法求问题的解 (15) 本章小结 (15) 参考文献 (16) 第6章回溯与分支限界 内容导读 回溯法(Back Tracking Algorithm)与分支限界法（Branch and Bound Algorithm）都是基本的算法设计策略，属于树的搜索技术的范畴。在使用这两种算法求解问题前，均需要把解空间规划成一棵解空间树，并且在求解过程中使用剪枝策略来提高搜索效率。 回溯法也称试探法，可以把它看成是一个在约束条件下对解空间树进行深度优先搜索的过程，并在搜索过程中剪去那些不满足条件的分支。当用回溯法搜索到解空间树的某个结点时，如果发现当前路径不满足约束条件或不是历史最优时，则放弃对该结点的子树的搜索，并逐层向其祖先结点返回。否则，进入该结点的子树，继续进行深度优先搜索。实质上，这是一个先根遍历解空间树的过程，只是这个棵树不是遍历前预先建立的，而是隐含在遍历过程当中的。 分支限界法则是以最小代价优先的方式在解空间树上进行搜索，它可以找出满足问题约束的一个可行解，或者是从满足约束条件的可行解中找出一个使得目标函数达到极值的最优解。这里的可行解在搜索树中表现为一条由根到叶子结点的路径，这条路径上权值的和为可行解的值。其中，最优解就是使可行解的值达到最优的那条路径。分支限界算法的核心思想就是增加更多的约束条件，剪掉更多的分支，当对当前的树结点进行扩展时，一次性产生其所有儿子结点，并抛弃那些不可能产生可行解或最优解的结点，即剪枝；对于留下的儿子结点，计算一个函数值（限界），然后选取一个最有利的结点继续进行扩展，使得搜索朝着最优解的分支推进。重复这个过程直到找到最优解或没有可扩展的结点。 0-1背包问题 计科1班朱润华 2012040732 方法1：回溯法 一、回溯法描述： 用回溯法解问题时，应明确定义问题的解空间。问题的解空间至少包含问题的一个（最优）解。对于0-1背包问题，解空间由长度为n的0-1向量组成。该解空间包含对变量的所有0-1赋值。例如n=3时，解空间为：｛（0，0，0），（0，1，0），（0，0，1），（1，0，0），（0，1，1），（1，0，1），（1，1，0），（1，1，1）｝然后可将解空间组织成树或图的形式，0-1背包则可用完全二叉树表示其解空间给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问:应如何选择装入背包的物品，使得装入背包中物品的总价值最大? 形式化描述：给定c >0, wi >0, vi >0 , 1≤i≤n.要求找一n元向量(x1,x2,…,xn,), xi∈{0,1}, ? ∑ wi xi≤c,且∑ vi xi达最大.即一个特殊的整数规划问题。 二、回溯法步骤思想描述： 0-1背包问题是子集选取问题。0-1 背包问题的解空间可以用子集树表示。在搜索解空间树时，只要其左儿子节点是一个可行节点，搜索就进入左子树。当右子树中有可能含有最优解时，才进入右子树搜索。否则，将右子树剪去。设r是当前剩余物品价值总和，cp是当前价值；bestp是当前最优价值。当cp+r<=bestp时，可剪去右子树。计算右子树上界的更好的方法是将剩余物品依次按其单位价值排序，然后依次装入物品，直至装不下时，再装入物品一部分而装满背包。 例如：对于0-1背包问题的一个实例，n=4,c=7,p=[9,10,7,4],w=[3,5,2,1]。这4个物品的单位重量价值分别为[3,2,3,5,4]。以物品单位重量价值的递减序装入物品。先装入物品4，然后装入物品3和1.装入这3个物品后，剩余的背包容量为1，只能装0.2的物品2。由此得一个解为[1,0.2,1,1]，其相应价值为22。尽管这不是一个可行解，但可以证明其价值是最优值的上界。因此，对于这个实例，最优值不超过22。 在实现时，由Bound计算当前节点处的上界。类Knap的数据成员记录解空间树中的节点信息，以减少参数传递调用所需要的栈空间。在解空间树的当前扩展节点处，仅要进入右子树时才计算上界Bound,以判断是否可将右子树剪去。进入左子树时不需要计算上界，因为上界预期父节点的上界相同。 三、回溯法实现代码： #include "stdafx.h" #include 分治法 1、二分搜索算法是利用（分治策略）实现的算法。 9. 实现循环赛日程表利用的算法是（分治策略） 27、Strassen矩阵乘法是利用（分治策略）实现的算法。 34．实现合并排序利用的算法是（分治策略）。 实现大整数的乘法是利用的算法（分治策略）。 17．实现棋盘覆盖算法利用的算法是（分治法）。 29、使用分治法求解不需要满足的条件是（子问题必须是一样的）。 不可以使用分治法求解的是（0/1背包问题）。 动态规划 下列不是动态规划算法基本步骤的是（构造最优解） 下列是动态规划算法基本要素的是（子问题重叠性质）。 下列算法中通常以自底向上的方式求解最优解的是（动态规划法） 备忘录方法是那种算法的变形。（动态规划法） 最长公共子序列算法利用的算法是（动态规划法）。 矩阵连乘问题的算法可由（动态规划算法B）设计实现。 实现最大子段和利用的算法是（动态规划法）。 贪心算法 能解决的问题：单源最短路径问题，最小花费生成树问题，背包问题，活动安排问题， 不能解决的问题：N皇后问题，0/1背包问题 是贪心算法的基本要素的是（贪心选择性质和最优子结构性质）。 回溯法 回溯法解旅行售货员问题时的解空间树是（排列树）。 剪枝函数是回溯法中为避免无效搜索采取的策略 回溯法的效率不依赖于下列哪些因素（确定解空间的时间） 分支限界法 最大效益优先是（分支界限法）的一搜索方式。 分支限界法解最大团问题时，活结点表的组织形式是（最大堆）。 分支限界法解旅行售货员问题时，活结点表的组织形式是（最小堆） 优先队列式分支限界法选取扩展结点的原则是（结点的优先级） 在对问题的解空间树进行搜索的方法中,一个活结点最多有一次机会成为活结点的是( 分支限界法). 从活结点表中选择下一个扩展结点的不同方式将导致不同的分支限界法,以下除( 栈式分支限界法)之外都是最常见的方式. （1）队列式(FIFO)分支限界法：按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。 （2）优先队列式分支限界法：按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。 （最优子结构性质）是贪心算法与动态规划算法的共同点。 贪心算法与动态规划算法的主要区别是（贪心选择性质）。 回溯算法和分支限界法的问题的解空间树不会是( 无序树). 14．哈弗曼编码的贪心算法所需的计算时间为（ B ）。 A、O（n2n） B、O（nlogn） C、O（2n） D、O（n） 21、下面关于NP问题说法正确的是（B ） A NP问题都是不可能解决的问题 B P类问题包含在NP类问题中 C NP完全问题是P类问题的子集 D NP类问题包含在P类问题中 40、背包问题的贪心算法所需的计算时间为（ B ） [汇总]蛮力法、动态规划法、回溯法和分支限界法求解01 背包问题 一、实验内容: 分别用蛮力法、动态规划法、回溯法和分支限界法求解0/1背包问题。 C注:0/1背包问题:给定种物品和一个容量为的背包，物品的重量ni 是，其价值为，背包问题是如何使选择装入背包内的物品，使得装入背wvii 包中的物品的总价值最大。其中，每种物品只有全部装入背包或不装入背包两种选择。 二、所用算法的基本思想及复杂度分析: 1.蛮力法求解0/1背包问题: 1)基本思想: 对于有n种可选物品的0/1背包问题，其解空间由长度为n的0-1向量组成,可用子集数表示。在搜索解空间树时，深度优先遍历，搜索每一个结点，无论是否可能产生最优解，都遍历至叶子结点，记录每次得到的装入总价值，然后记录遍历过的最大价值。 2)代码: #include }a[N]; bool m(goods a,goods b) { return (a.p/a.w)>(b.p/b.w); } int max(int a,int b) { return a 2.设计动态规划算法的主要步骤为： （1）找出最优解的性质，并刻划其结构特征。 （2）递归地定义最优值。 （3）以自底向上的方式计算出最优值。 根据计算最优值时得到的信息，构造最优解。 3.分支限界法与回溯法的相同点与不同点 相同点： （1）都是一种在问题的解空间树T中搜索问题解的算法。 不同点： （1）求解目标不同； （2）搜索方式不同； （3）对扩展结点的扩展方式不同； （4）存储空间的要求不同。 4.分治法所能解决的问题一般具有的几个特征是： （1）该问题的规模缩小到一定的程度就可以容易地解决； （2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质; （3）利用该问题分解出的子问题的解可以合并为该问题的解； （4）原问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。 5.用分支限界法设计算法的步骤是： (1)针对所给问题，定义问题的解空间（对解进行编码） (2)确定易于搜索的解空间结构（按树或图组织解） (3)以广度优先或以最小耗费（最大收益）优先的方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。 6. 分支限界法的搜索策略是： 在扩展结点处，先生成其所有的儿子结点（分支），然后再从当前的活结点表中选择下一个扩展结点。为了有效地选择下一扩展结点，加速搜索的进程，在每一个活结点处，计算一个函数值（限界），并根据函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间上有最优解的分支推进，以便尽快地找出一个最优解。 7.算法的要特性是什么？ （1）确定性 （2）可实现性 （3）输入 （4）输出 （5）有穷性 8.算法分析的目的是什么？ 分析算法占用计算机资源的情况，对算法做出比较和评价，设计出更好的算法。 9.算法设计中常用的算法设计策略？ （1）蛮力法； （2）倒推法； （3）循环与递归； （4）分治法； （5）动态规划法； （6）贪心法； （7）回溯法； 0-1背包问题 计科1班朱润华2012040732 方法1：回溯法 一、回溯法描述： 用回溯法解问题时，应明确定义问题的解空间。问题的解空间至少包含问题的一个（最优）解。对于0-1背包问题，解空间由长度为n的0-1向量组成。该解空间包含对变量的所有0-1赋值。例如n=3时，解空间为：｛（0，0，0），（0，1，0），（0，0，1），（1，0，0），（0，1，1），（1，0，1），（1，1，0），（1，1，1）｝然后可将解空间组织成树或图的形式，0-1背包则可用完全二叉树表示其解空间给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问:应如何选择装入背包的物品，使得装入背包中物品的总价值最大? 形式化描述：给定c >0, wi >0, vi >0 , 1≤i≤n.要求找一n元向量(x1,x2,…,xn,), xi∈{0,1}, ? ∑wi xi≤c,且∑vi xi达最大.即一个特殊的整数规划问题。 二、回溯法步骤思想描述： 0-1背包问题是子集选取问题。0-1 背包问题的解空间可以用子集树表示。在搜索解空间树时，只要其左儿子节点是一个可行节点，搜索就进入左子树。当右子树中有可能含有最优解时，才进入右子树搜索。否则，将右子树剪去。设r是当前剩余物品价值总和，cp是当前价值；bestp是当前最优价值。当cp+r<=bestp时，可剪去右子树。计算右子树上界的更好的方法是将剩余物品依次按其单位价值排序，然后依次装入物品，直至装不下时，再装入物品一部分而装满背包。 例如：对于0-1背包问题的一个实例，n=4,c=7,p=[9,10,7,4],w=[3,5,2,1]。这4个物品的单位重量价值分别为[3,2,3,5,4]。以物品单位重量价值的递减序装入物品。先装入物品4，然后装入物品3和1.装入这3个物品后，剩余的背包容量为1，只能装0.2的物品2。由此得一个解为[1,0.2,1,1]，其相应价值为22。尽管这不是一个可行解，但可以证明其价值是最优值的上界。因此，对于这个实例，最优值不超过22。 在实现时，由Bound计算当前节点处的上界。类Knap的数据成员记录解空间树中的节点信息，以减少参数传递调用所需要的栈空间。在解空间树的当前扩展节点处，仅要进入右子树时才计算上界Bound,以判断是否可将右子树剪去。进入左子树时不需要计算上界，因为上界预期父节点的上界相同。 三、回溯法实现代码： #include "stdafx.h" #include 《算法设计与分析》作业 作业四+五回溯法+分支限界法 1. 二元最大连通块搜索 因为下了场大雨，青蛙王子高兴坏了，它有机会重新划定自己的王国范围。在下图中，空白区域表示积水的地方，青蛙王子需要找到一块最大的连续积水区域（上下或左右相连）作为自己的新领地。 2. 三元最大连通块搜索 小明在玩一种消除游戏。游戏中有一个长方形的区域，被RGB(红绿蓝)三种颜色的小球充满。要求每次找出当前最大连通区域（上下左右相邻同种颜色即可算作连通），进行消除。 ####.### ###.#### ##.##### the ans is 7 12 8 ..#..... .##....# .#....#. .###.#.. ....#... ..##.#.. .#....#. .##..#.# ###..#.. ....#... ...#.... ..#..... the ans is 18 1.3 程序运行情况 1.4 程序源码（含注释） #include"bits/stdc++.h" using namespace std; #define inf 999 //代码下标从0始，输入时.为可走，#为不可走 int n,m;//行、列 int ans,now;//最大连通数，当前搜索时连通数 char e[inf][inf];//地图 int book[inf][inf];//标记地图 int pos[4][2]={-1,0,1,0,0,1,0,-1};//方位，上下右左 void read()//输入数据 { printf("input the row and the column of the map:"); scanf("%d%d",&n,&m); printf("now input the map:\n"); for(int i=0;i 常用算法之：分支限界法 一、基本描述 类似于回溯法，也是一种在问题的解空间树T上搜索问题解的算法。但在一般情况下，分支限界法与回溯法的求解目标不同。回溯法的求解目标是找出T中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。 （1）分支搜索算法 所谓“分支”就是采用广度优先的策略，依次搜索E-结点的所有分支，也就是所有相邻结点，抛弃不满足约束条件的结点，其余结点加入活结点表。然后从表中选择一个结点作为下一个E-结点，继续搜索。 选择下一个E-结点的方式不同，则会有几种不同的分支搜索方式。 1）FIFO搜索 2）LIFO搜索 3）优先队列式搜索 （2）分支限界搜索算法 二、分支限界法的一般过程 由于求解目标不同，导致分支限界法与回溯法在解空间树T上的搜索方式也不相同。回溯法以深度优先的方式搜索解空间树T，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树T。 分支限界法的搜索策略是：在扩展结点处，先生成其所有的儿子结点（分支），然后再从当前的活结点表中选择下一个扩展对点。为了有效地选择下一扩展结点， 以加速搜索的进程，在每一活结点处，计算一个函数值（限界），并根据这些已计算出的函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间树上有最优解的分支推进，以便尽快地找出一个最优解。 分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。问题的解空间树是表示问题解空间的一棵有序树，常见的有子集树和排列树。在搜索问题的解空间树时，分支限界法与回溯法对当前扩展结点所使用的扩展方式不同。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，那些导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被子加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所求的解或活结点表为空时为止。 三、回溯法和分支限界法的一些区别 有一些问题其实无论用回溯法还是分支限界法都可以得到很好的解决，但是另外一些则不然。也许我们需要具体一些的分析——到底何时使用分支限界而何时使用回溯呢？ 回溯法和分支限界法的一些区别： 方法对解空间树的搜索方式存储结点的常用数据结构结点存储特性常用应用 回溯法深度优先搜索堆栈活结点的所有可行子结点被遍历后才被从栈中弹出找出满足约束条件的所有解 分支限界法广度优先或最小消耗优先搜索队列、优先队列每个结点只有一次成为活结点的机会找出满足约束条件的一个解或特定意义下的最优解 动态规划法回溯法分支限界法求解T S P问题实 验报告 文档编制序号：[KKIDT-LLE0828-LLETD298-POI08] TSP问题算法实验报告指导教师：季晓慧 姓名：辛瑞乾 学号： 提交日期： 2015年11月 目录 总述 TSP问题又称为旅行商问题，是指一个旅行商要历经所有城市一次最后又回到原来的城市，求最短路程或最小花费，解决TSP可以用好多算法，比如蛮力法，动态规划法…具体的时间复杂的也各有差异，本次实验报告包含动态规划法，回溯法以及分支限界法。 动态规划法 算法问题分析 假设n个顶点分别用0~n-1的数字编号，顶点之间的代价存放在数组mp[n][n]中，下面考虑从顶点0出发求解TSP问题的填表形式。首先，按个数为1、2、…、n-1的顺序生成1~n-1个元素的子集存放在数组x[2^n-1]中，例如当n=4时， x[1]={1},x[2]={2},x[3]={3},x[4]={1,2},x[5]={1,3},x[6]={2,3},x[7]={1,2,3}。设数组 dp[n][2^n-1]存放迭代结果，其中dp[i][j]表示从顶点i经过子集x[j]中的顶点一次且一次，最后回到出发点0的最短路径长度，动态规划法求解TSP问题的算法如下。 算法设计 输入：图的代价矩阵mp[n][n] 输出：从顶点0出发经过所有顶点一次且仅一次再回到顶点0的最短路径长度 1.初始化第0列（动态规划的边界问题） for(i=1;i(完整版)分支限界算法作业分配问题
动态规划法,回溯法,分支限界法求解TSP问题实验报告
回溯法与分支限界法的分析与比较
回溯法和分支限界法解决背包题
分支限界法实现单源最短路径问题
回溯法和分支限界法解决0-1背包题
0037算法笔记——【分支限界法】最大团问题
用回溯法和队列式分支限界算法求解0-1背包问题
分支限界法实验(最优装载问题)
算法设计与分析第6章回溯与分支限界
回溯法和分支限界法解决0-1背包题
算法设计与分析复习题目及答案 (3)
[汇总]蛮力法、动态规划法、回溯法和分支限界法求解01背包问题
算法简答题
回溯法和分支限界法解决0-1背包题
算法设计与分析---回溯+分支限界法实验报告
常用算法之：分支限界法
动态规划法回溯法分支限界法求解TSP问题实验报告
#include
相关主题
文本预览