首页 > 代码库 > 回溯法与分支限界
回溯法与分支限界
回溯法
1、有许多问题，当需要找出它的解集或者要求回答什么解是满足某些约束条件的最佳解时，往往要使用回溯法。
2、回溯法的基本做法是搜索，或是一种组织得井井有条的，能避免不必要搜索的穷举式搜索法。这种方法适用于解一些组合数相当大的问题。
3、回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含（剪枝过程），则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。
问题的解空间
问题的解向量：回溯法希望一个问题的解能够表示成一个n元式(x1,x2,…,xn)的形式。
显约束：对分量xi的取值限定。
隐约束：为满足问题的解而对不同分量之间施加的约束。
解空间：对于问题的一个实例，解向量满足显式约束条件的所有多元组，构成了该实例的一个解空间。
注意：同一个问题可以有多种表示，有些表示方法更简单，所需表示的状态空间更小（存储量少，搜索方法简单）。
下面是n=3时的0-1背包问题用完全二叉树表示的解空间：
生成问题状态的基本方法
扩展结点:一个正在产生儿子的结点称为扩展结点
活结点:一个自身已生成但其儿子还没有全部生成的节点称做活结点
死结点:一个所有儿子已经产生的结点称做死结点
深度优先的问题状态生成法：如果对一个扩展结点R，一旦产生了它的一个儿子C，就把C当做新的扩展结点。在完成对子树C（以C为根的子树）的穷尽搜索之后，将R重新变成扩展结点，继续生成R的下一个儿子（如果存在）
宽度优先的问题状态生成法：在一个扩展结点变成死结点之前，它一直是扩展结点
回溯法：为了避免生成那些不可能产生最佳解的问题状态，要不断地利用限界函数(bounding function)来处死(剪枝)那些实际上不可能产生所需解的活结点，以减少问题的计算量。具有限界函数的深度优先生成法称为回溯法。（回溯法 = 穷举 + 剪枝）
回溯法的基本思想
(1)针对所给问题，定义问题的解空间；
(2)确定易于搜索的解空间结构；
(3)以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。
两个常用的剪枝函数：
- (1)约束函数：在扩展结点处减去不满足约束的子数
- (2)限界函数：减去得不到最优解的子树
用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。在任何时刻，算法只保存从根结点到当前扩展结点的路径。如果解空间树中从根结点到叶结点的最长路径的长度为h(n)，则回溯法所需的计算空间通常为O(h(n))。而显式地存储整个解空间则需要
回溯算法的设计步骤
回溯算法的递归实现和迭代实现
递归回溯
回溯法对解空间作深度优先搜索，因此，在一般情况下用递归方法实现回溯法。
// 针对N叉树的递归回溯方法
void backtrack (int t)
{
if (t > n) {
// 到达叶子结点，将结果输出
output (x);
}
else {
// 遍历结点t的所有子结点
for (int i = f(n,t); i <= g(n,t); i ++ ) {
x[t] = h[i];
// 如果不满足剪枝条件，则继续遍历
if (constraint (t) && bound (t))
backtrack (t + 1);
}
}
}迭代回溯
采用树的非递归深度优先遍历算法，可将回溯法表示为一个非递归迭代过程。
// 针对N叉树的迭代回溯方法
void iterativeBacktrack ()
{
int t = 1;
while (t > 0) {
if (f(n,t) <= g(n,t)) {
// 遍历结点t的所有子结点
for (int i = f(n,t); i <= g(n,t); i ++) {
x[t] = h(i);
// 剪枝
if (constraint(t) && bound(t)) {
// 找到问题的解，输出结果
if (solution(t)) {
output(x);
}
else // 未找到，向更深层次遍历
t ++;
}
}
}
else {
t--;
}
}
}回溯法一般依赖的两种数据结构：子集树和排列树
子集树（遍历子集树需
void backtrack (int t)
{
if (t > n)
// 到达叶子结点
output (x);
else
for (int i = 0;i <= 1;i ++) {
x[t] = i;
// 约束函数
if ( legal(t) )
backtrack( t+1 );
}
}排列树（遍历排列树需要O(n!)计算时间）
void backtrack (int t)
{
if (t > n)
output(x);
else
for (int i = t;i <= n;i++) {
// 完成全排列
swap(x[t], x[i]);
if (legal(t))
backtrack(t+1);
swap(x[t], x[i]);
}
}几个典型的例子
装载问题
问题表述：有一批共n个集装箱要装上2艘载重量分别为c1和c2的轮船，其中集装箱i的重量为wi，且
装载问题要求确定是否有一个合理的装载方案可将这个集装箱装上这2艘轮船。如果有，找出一种装载方案。
解决方案：
容易证明，如果一个给定装载问题有解，则采用下面的策略可得到最优装载方案。
(1)首先将第一艘轮船尽可能装满；
(2)将剩余的集装箱装上第二艘轮船。
将第一艘轮船尽可能装满等价于选取全体集装箱的一个子集，使该子集中集装箱重量之和最接近。由此可知，装载问题等价于以下特殊的0-1背包问题。
解空间：
子集树可行性约束函数(选择当前元素)：
上界函数(不选择当前元素)：
void backtrack (int i)
{
// 搜索第i层结点
if (i > n) // 到达叶结点
更新最优解bestx,bestw;return;
r -= w[i];
if (cw + w[i] <= c) {
// 搜索左子树
x[i] = 1;
cw += w[i];
backtrack (i + 1);
cw -= w[i];
}
if (cw + r > bestw) {
x[i] = 0; // 搜索右子树
backtrack(i + 1);
}
r += w[i];
}变量解释：
r: 剩余重量
w: 各个集装箱重
cw:当前总重量
x: 每个集装箱是否被选取标志
bestx: 最佳选取方案
bestw: 最优载重量
实现：
#include <iostream>
#include <vector>
#include <iterator>
using namespace std;
/* 装载问题子函数
* layers: 搜索到第layers层结点
* layers_size: layers_size总层数
* current_w: 当前承载量
* best_w: 最优载重量
* flag_x: 选取方案
* best_x: 最佳选取方案
* remainder_w:剩余重量
* container_w:每个集装箱的重量
* total_w: 总承载量
*/
void __backtrack (int layers,const int layers_size,
int current_w,int& best_w,
vector<int>& flag_x,vector<int>&
best_x,
int remainder_w,
const vector<int>& container_w,
int total_w)
{
if (layers > layers_size - 1) {
// 到达叶子结点，更新最优载重量
if (current_w < best_w || best_w == -1) {
copy(flag_x.begin(),flag_x.end
(),best_x.begin());
// copy(best_x.begin(),best_x.end
(),flag_x.begin());
best_w = current_w;
}
return;
}
remainder_w -= container_w[layers];
if (current_w + container_w[layers] <= total_w) {
// 搜索左子树
flag_x[layers] = 1;
current_w += container_w[layers];
__backtrack(layers + 1,layers_size,current_w,
best_w,flag_x,best_x,remainder_w,container_w,
total_w);
current_w -= container_w[layers];
}
if (current_w + remainder_w > best_w || best_w == -
1) {
flag_x[layers] = 0;
__backtrack(layers + 1,layers_size,current_w,
best_w,flag_x,best_x,remainder_w,container_w,
total_w);
}
remainder_w += container_w[layers];
}
/* 装载问题
* container_w: 各个集装箱重量
* total_w: 总承载量
*/
void loading_backtrack (int total_w, vector<int>&
container_w)
{
int layers_size = container_w.size(); // 层数
int current_w = 0; // 当前装载重量
int remainder_w = total_w; // 剩余重量
int best_w = -1; // 最优载重量
vector<int> flag_x(layers_size); // 是否被选取标
志
vector<int> best_x(layers_size); // 最佳选取方案
__backtrack(0,layers_size,current_w,
best_w,flag_x,best_x,remainder_w,container_w,
total_w);
cout << "path : " ;
copy(best_x.begin(),best_x.end
(),ostream_iterator<int>(cout," "));
cout << endl;
cout << "best_w = " << best_w
<< "( ";
// 将结果输出
for (size_t i = 0;i < best_x.size(); ++ i) {
if (best_x[i] == 1) {
cout << container_w[i] << " ";
}
}
cout << ")" << endl;
}
int main()
{
const int total_w = 30;
vector<int> container_w;
container_w.push_back(40);
container_w.push_back(1);
container_w.push_back(40);
container_w.push_back(9);
container_w.push_back(1);
container_w.push_back(8);
container_w.push_back(5);
container_w.push_back(50);
container_w.push_back(6);
loading_backtrack(total_w,container_w);
return 0;
}批处理作业调度
问题表述：给定n个作业的集合
批处理作业调度问题要求对于给定的n个作业，制定最佳作业调度方案，使其完成时间和达到最小。
显然，1,3,2是最佳调度方案。
解空间：排列树（将作业顺序进行全排列，分别算出各种情况的完成时间和，取最佳调度方案）
实现：
#include <iostream>
#include <vector>
using namespace std;
class flowshop
{
public:
flowshop(vector<vector<int> >& rhs) {
task_count = rhs.size() ;
each_t = rhs ;
best_t.resize (task_count) ;
machine2_t.resize (task_count,0) ;
machine1_t = 0 ;
total_t = 0 ;
best_total_t = 0 ;
current_t.resize (task_count,0) ;
for (int i = 0 ;i < task_count; ++ i) {
current_t[i] = i; // 为了实现全排列
}
}
void backtrack () {
__backtrack (0);
// 显示最佳调度方案和最优完成时间和
cout << "the best flowshop scheme is : ";
copy (best_t.begin(),best_t.end(),ostream_iterator<int> (cout, " "));
cout << endl;
cout << "the best total time is : " << best_total_t << endl;
}
private:
void __backtrack (int i) {
if (i >= task_count) {
if (total_t < best_total_t || best_total_t == 0) {
// 存储当前最优调度方式
copy (current_t.begin(),current_t.end(),best_t.begin()) ;
best_total_t = total_t;
}
return ;
}
for (int j = i; j < task_count; ++ j) {
// 机器1上结束的时间
machine1_t += each_t[current_t[j]][0] ;
if (i == 0) {
machine2_t[i] = machine1_t + each_t[current_t[j]][1] ;
}
else {
// 机器2上结束的时间
machine2_t[i] =
((machine2_t[i - 1] > machine1_t) ? machine2_t[i - 1] : machine1_t)
+ each_t[current_t[j]][1] ;
}
total_t += machine2_t[i];
// 剪枝
if (total_t < best_total_t || best_total_t == 0) {
// 全排列
swap (current_t[i],current_t[j]) ;
__backtrack (i + 1) ;
swap (current_t[i],current_t[j]) ;
}
machine1_t -= each_t[current_t[j]][0] ;
total_t -= machine2_t[i] ;
}
}
public :
int task_count ; // 作业数
vector<vector<int> > each_t ; // 各作业所需的处理时间
vector<int> current_t ; // 当前作业调度
vector<int> best_t ; // 当前最优时间调度
vector<int> machine2_t ; // 机器2完成处理的时间
int machine1_t ; // 机器1完成处理的时间
int total_t ; // 完成时间和
int best_total_t ; // 当前最优完成时间和
};
int main()
{
// const int task_count = 4;
const int task_count = 3 ;
vector<vector<int> > each_t(task_count) ;
for (int i = 0;i < task_count; ++ i) {
each_t[i].resize (2) ;
}
each_t[0][0] = 2 ;
each_t[0][1] = 1 ;
each_t[1][0] = 3 ;
each_t[1][1] = 1 ;
each_t[2][0] = 2 ;
each_t[2][1] = 3 ;
// each_t[3][0] = 1 ;
// each_t[3][1] = 1 ;
flowshop fs(each_t) ;
fs.backtrack () ;
}N后问题
问题表述：在
解向量：(x1, x2, … , xn)
显约束：xi = 1,2, … ,n
隐约束：
1)不同列：xi != xj
2)不处于同一正、反对角线：|i-j| != |x(i)-x(j)|
解空间：满N叉树
实现：
#include <iostream>
#include <vector>
using namespace std;
class queen
{
// 皇后在棋盘上的位置
struct q_place {
int x;
int y;
q_place ()
: x(0),y(0)
{}
};
public:
queen(int qc)
: q_count (qc), sum_solution (0) {
curr_solution.resize (q_count);
}
void backtrack () {
__backtrack (0);
}
private:
void __backtrack (int t) {
if (t >= q_count) {
// 找到一个解决方案
++ sum_solution ;
for (size_t i = 0;i < curr_solution.size(); ++ i) {
cout << "x = " << curr_solution[i].x
<< " y = " << curr_solution[i].y << endl;
}
cout << "sum_solution = " << sum_solution << endl;
}
else {
for (int i = 0;i < q_count; ++ i) {
curr_solution[t].x = i;
curr_solution[t].y = t;
if (__place(t)) {
__backtrack (t + 1);
}
}
}
}
// 判断第k个皇后的位置是否与前面的皇后相冲突
bool __place (int k) {
for (int i = 0; i < k; ++ i) {
if ((abs(curr_solution[i].x - curr_solution[k].x)
== abs(curr_solution[i].y - curr_solution[k].y))
|| curr_solution[i].x == curr_solution[k].x) {
return false;
}
}
return true;
}
private:
vector<q_place> curr_solution; // 当前解决方案
const int q_count; // 皇后个数
int sum_solution; // 当前找到的解决方案的个数
};
int main()
{
queen q(5);
q.backtrack ();
return 0;
}旅行售货员问题
问题表述：在图中找到一个权最小的周游路线
解空间：排列树
剪枝策略：
当前路径的权重＋下一个路径的权重 < 当前的最小权重，则搜索该路径
实现：
#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>
using namespace std;
class traveling
{
public:
static const int NOEDGE = -1 ;
public:
traveling (const vector<vector<int> >& ug)
: curr_cost (0), best_cost (-1) {
node_count = ug.size ();
undigraph = ug;
curr_solution.resize (node_count);
for (int i = 0; i < node_count; ++ i) {
curr_solution[i] = i;
}
best_solution.resize (node_count);
}
void backtrack () {
__backtrack (1);
cout << best_cost << endl;
}
private:
void __backtrack (int layers) {
if (layers >= node_count) {
if (undigraph[curr_solution[node_count - 1]][curr_solution[0]] == NOEDGE){
return ;
}
int total_cost = curr_cost +
undigraph[curr_solution[node_count - 1]][curr_solution[0]] ;
if (total_cost < best_cost || best_cost == -1) {
// 更新最优费用和最优路径
best_cost = total_cost;
copy (curr_solution.begin(),
curr_solution.end(),
best_solution.begin());
}
return ;
}
for (int i = layers; i < node_count; ++ i) {
// 剪枝
if (undigraph[curr_solution[layers - 1]][curr_solution[i]] != NOEDGE &&
( curr_cost + undigraph[curr_solution[layers - 1]][curr_solution[i]]
< best_cost || best_cost == -1 )) {
// 搜索子树
swap (curr_solution[layers],curr_solution[i]);
curr_cost +=
undigraph[curr_solution[layers - 1]][curr_solution[layers]];
__backtrack (layers + 1);
curr_cost -=
undigraph[curr_solution[layers - 1]][curr_solution[layers]];
swap (curr_solution[layers],curr_solution[i]);
}
}
}
int node_count; // 结点个数
int curr_cost; // 当前费用
int best_cost; // 当前
vector<int> curr_solution; // 当前解决方案
vector<int> best_solution; // 最优解决方案
vector<vector<int> > undigraph; // 无向图(采用矩阵存储)
};
int main()
{
int size = 4;
vector<vector<int> > ug(size);
for (int i = 0;i < size; ++ i) {
ug[i].resize (size);
}
ug[0][0] = -1;
ug[0][1] = 30;
ug[0][2] = 6;
ug[0][3] = 4;
ug[1][0] = 30;
ug[1][1] = -1;
ug[1][2] = 5;
ug[1][3] = 10;
ug[2][0] = 6;
ug[2][1] = 5;
ug[2][2] = -1;
ug[2][3] = 20;
ug[3][0] = 4;
ug[3][1] = 10;
ug[3][2] = 20;
ug[3][3] = -1;
traveling t(ug);
t.backtrack();
return 0;
}0-1背包问题
问题表述：给定n种物品和一背包。物品i的重量是wi，其价值为pi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?
0-1背包问题是一个特殊的整数规划问题。
解空间：
可行性约束函数：
上界函数：
考虑一个右子树的时候，设
r：是当前未考虑的剩余物品的总价值(remainder)
cp：是当前的价值(current price)
bestp：是当前得到的最优价值(best price)
那么，满足：
但是，上界r太松。
一个更加紧的上界：
将剩余物品按照单位重量价值排序，然后依次装入物品，直到装不下，再将剩余物品的一部分放入背包。(r_n <= r)
实现
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;
class goods {
public:
int weight; // 重量
int price; // 价格
goods() : weight(0),price(0)
{}
};
bool goods_greater(const goods& lhs,const goods& rhs)
{
return (lhs.price / lhs.weight) > (rhs.price / rhs.weight);
}
class knapsack
{
public:
knapsack (int c,const vector<goods>& gl)
: capacity (c), curr_price(0), best_price (0), curr_weight(0){
goods_list = gl;
total_layers = gl.size();
curr_path.resize (total_layers);
best_path.resize (total_layers);
}
void backtrack () {
__backtrack (0);
cout << "path: " ;
copy (best_path.begin(),best_path.end(),ostream_iterator<int> (cout, " "));
cout << endl;
cout << "best_price: " << best_price << endl;
}
private:
// 计算上界
int __bound (int layers) {
int cleft = capacity - curr_weight;
int result = curr_price;
// 将layer之后的物品进行按单位价格降序排序
vector<goods> tmp = goods_list;
sort (tmp.begin() + layers, tmp.end(),goods_greater);
// 以物品单位重量价值递减序装入物品
while (layers < total_layers && tmp[layers].weight <= cleft) {
cleft -= tmp[layers].weight;
result += tmp[layers].price;
++ layers;
}
// 装满背包
if (layers < total_layers) {
result += (tmp[layers].price / tmp[layers].weight) * cleft;
}
return result;
}
void __backtrack (int layers) {
// 到达叶子结点，更新最优价值
if (layers >= total_layers) {
if (curr_price > best_price || best_price == 0) {
best_price = curr_price;
copy (curr_path.begin(), curr_path.end(), best_path.begin());
}
return ;
}
// 左剪枝（能放的下）
if (curr_weight + goods_list[layers].weight <= capacity) {
curr_path[layers] = 1;
curr_weight += goods_list[layers].weight;
curr_price += goods_list[layers].price;
__backtrack (layers + 1);
curr_weight -= goods_list[layers].weight;
curr_price -= goods_list[layers].price;
}
// 右剪枝
if (__bound (layers + 1) > best_price || best_price == 0 ) {
curr_path[layers] = 0;
__backtrack (layers + 1);
}
/*curr_path[layers] = 0;
__backtrack (layers + 1);*/
}
private:
vector<goods> goods_list; // 货物信息列表
int capacity; // 背包承载量
int curr_price; // 当前价格
int curr_weight; // 当前重量
int best_price; // 当前得到的最优价值
int total_layers; // 总层数
vector<int> curr_path; // 当前路径
vector<int> best_path; // 最优价值下的路径
};
int main()
{
const int size = 3;
vector<goods> gl(size);
gl[0].weight = 10;
gl[0].price = 1;
gl[1].weight = 8;
gl[1].price = 4;
gl[2].weight = 5;
gl[2].price = 5;
knapsack ks(16, gl);
ks.backtrack ();
return 0;
}分支限界法
分支限界法与回溯法
（1）求解目标：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。
（2）搜索方式的不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。
分支限界法的基本思想
分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。
在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。
此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。
常见的两种分支限界法
（1）队列式(FIFO)分支限界法
按照队列先进先出（FIFO）原则选取下一个结点为扩展结点。
（2）优先队列式分支限界法
按照优先队列中规定的优先级选取优先级最高的结点成为当前扩展结点。
单源最短路径问题
问题描述 :在下图所给的有向图G中，每一边都有一个非负边权。要求图G的从源顶点s到目标顶点t之间的最短路径。
下图是用优先队列式分支限界法解有向图G的单源最短路径问题产生的解空间树。其中，每一个结点旁边的数字表示该结点所对应的当前路长。
找到一条路径：
目前的最短路径是8，一旦发现某个结点的下界不小于这个最短路进，则剪枝：
同一个结点选择最短的到达路径：
2.剪枝策略
在算法扩展结点的过程中，一旦发现一个结点的下界不小于当前找到的最短路长，则算法剪去以该结点为根的子树。
在算法中，利用结点间的控制关系进行剪枝。从源顶点s出发，2条不同路径到达图G的同一顶点。由于两条路径的路长不同，因此可以将路长长的路径所对应的树中的结点为根的子树剪去。
3.算法思想
解单源最短路径问题的优先队列式分支限界法用一极小堆来存储活结点表。其优先级是结点所对应的当前路长。
算法从图G的源顶点s和空优先队列开始。结点s被扩展后，它的儿子结点被依次插入堆中。此后，算法从堆中取出具有最小当前路长的结点作为当前扩展结点，并依次检查与当前扩展结点相邻的所有顶点。如果从当前扩展结点i到顶点j有边可达，且从源出发，途经顶点i再到顶点j的所相应的路径的长度小于当前最优路径长度，则将该顶点作为活结点插入到活结点优先队列中。这个结点的扩展过程一直继续到活结点优先队列为空时为止。
实现
#include <iostream>
#include <vector>
#include <queue>
#include <limits>
using namespace std;
struct node_info
{
public:
node_info (int i,int w)
: index (i), weight (w) {}
node_info ()
: index(0),weight(0) {}
node_info (const node_info & ni)
: index (ni.index), weight (ni.weight) {}
friend
bool operator < (const node_info& lth,const node_info& rth) {
return lth.weight > rth.weight ; // 为了实现从小到大的顺序
}
public:
int index; // 结点位置
int weight; // 权值
};
struct path_info
{
public:
path_info ()
: front_index(0), weight (numeric_limits<int>::max()) {}
public:
int front_index;
int weight;
};
// single source shortest paths
class ss_shortest_paths
{
public:
ss_shortest_paths (const vector<vector<int> >& g,int end_location)
:no_edge (-1), end_node (end_location), node_count (g.size()) , graph (g)
{}
// 打印最短路径
void print_spaths () const {
cout << "min weight : " << shortest_path << endl;
cout << "path: " ;
copy (s_path_index.rbegin(),s_path_index.rend(),
ostream_iterator<int> (cout, " "));
cout << endl;
}
// 求最短路径
void shortest_paths () {
vector<path_info> path(node_count);
priority_queue<node_info,vector<node_info> > min_heap;
min_heap.push (node_info(0,0)); // 将起始结点入队
while (true) {
node_info top = min_heap.top (); // 取出最大值
min_heap.pop ();
// 已到达目的结点
if (top.index == end_node) {
break ;
}
// 未到达则遍历
for (int i = 0; i < node_count; ++ i) {
// 顶点top.index和i间有边，且此路径长小于原先从原点到i的路径长
if (graph[top.index][i] != no_edge &&
(top.weight + graph[top.index][i]) < path[i].weight) {
min_heap.push (node_info (i,top.weight + graph[top.index][i]));
path[i].front_index = top.index;
path[i].weight = top.weight + graph[top.index][i];
}
}
if (min_heap.empty()) {
break ;
}
}
shortest_path = path[end_node].weight;
int index = end_node;
s_path_index.push_back(index) ;
while (true) {
index = path[index].front_index ;
s_path_index.push_back(index);
if (index == 0) {
break;
}
}
}
private:
vector<vector<int> > graph ; // 图的数组表示
int node_count; // 结点个数
const int no_edge; // 无通路
const int end_node; // 目的结点
vector<int> s_path_index; // 最短路径
int shortest_path; // 最短路径
};
int main()
{
const int size = 11;
vector<vector<int> > graph (size);
for (int i = 0;i < size; ++ i) {
graph[i].resize (size);
}
for (int i = 0;i < size; ++ i) {
for (int j = 0;j < size; ++ j) {
graph[i][j] = -1;
}
}
graph[0][1] = 2;
graph[0][2] = 3;
graph[0][3] = 4;
graph[1][2] = 3;
graph[1][5] = 2;
graph[1][4] = 7;
graph[2][5] = 9;
graph[2][6] = 2;
graph[3][6] = 2;
graph[4][7] = 3;
graph[4][8] = 3;
graph[5][6] = 1;
graph[5][8] = 3;
graph[6][9] = 1;
graph[6][8] = 5;
graph[7][10] = 3;
graph[8][10] = 2;
graph[9][8] = 2;
graph[9][10] = 2;
ss_shortest_paths ssp (graph, 10);
ssp.shortest_paths ();
ssp.print_spaths ();
return 0;
}测试数据（图）
测试结果
min weight : 8
path: 0 2 6 9 10 装载问题
问题描述
有一批共个集装箱要装上2艘载重量分别为
装载问题要求确定是否有一个合理的装载方案可将这个集装箱装上这2艘轮船。如果有，找出一种装载方案。
容易证明：如果一个给定装载问题有解，则采用下面的策略可得到最优装载方案。
(1)首先将第一艘轮船尽可能装满；
(2)将剩余的集装箱装上第二艘轮船。
将第一艘轮船尽可能装满等价于选取全体集装箱的一个子集，使该子集中集装箱重量之和最接近。由此可知，装载问题等价于以下特殊的0-1背包问题。
例如：W = <10,8,5> , C = 16
- 队列式分支限界法
在算法的while循环中，首先检测当前扩展结点的左儿子结点是否为可行结点。如果是则将其加入到活结点队列中。然后将其右儿子结点加入到活结点队列中(右儿子结点一定是可行结点)。2个儿子结点都产生后，当前扩展结点被舍弃。
活结点队列中的队首元素被取出作为当前扩展结点，由于队列中每一层结点之后都有一个尾部标记-1，故在取队首元素时，活结点队列一定不空。当取出的元素是-1时，再判断当前队列是否为空。如果队列非空，则将尾部标记-1加入活结点队列，算法开始处理下一层的活结点。
while (true) {
// 检查左儿子结点
if (Ew + w[i] <= c) //x[i] = 1
EnQueue(Q, Ew + w[i], bestw, i, n);
// 右儿子结点总是可行的
EnQueue(Q, Ew, bestw, i, n); //x[i] = 0
Q.Delete(Ew); // 取下一扩展结点
if (Ew == -1) { // 同层结点尾部
if (Q.IsEmpty())
return bestw;
Q.Add(-1); // 同层结点尾部标志
Q.Delete(Ew); // 取下一扩展结点
i++; // 进入下一层
}
}变量含义：
Ew: 扩展节点的载重量
W: 重量数组
Q: 活节点队列
bestw: 当前最优载重量
i: 当前处理到的层数
n: 总货物数
- 算法的改进
节点的左子树表示将此集装箱装上船，右子树表示不将此集装箱装上船。设bestw是当前最优解；ew是当前扩展结点所相应的重量；r是剩余集装箱的重量。则当ew + r ￡ bestw时，可将其右子树剪去，因为此时若要船装最多集装箱，就应该把此箱装上船。
另外，为了确保右子树成功剪枝，应该在算法每一次进入左子树的时候更新bestw的值。
// 检查左儿子结点
Type wt = Ew +w[i]; //左儿子结点的重量
if (wt <= c) { //可行结点
if (wt > bestw)
bestw = wt;
// 加入活结点队列
if (i < n)
Q.Add(wt);
}
// 检查右儿子结点
if (Ew + r > bestw&& i < n)
Q.Add(Ew); // 可能含最优解
Q.Delete(Ew); //取下一扩展结点构造最优解
为了在算法结束后能方便地构造出与最优值相应的最优解，算法必须存储相应子集树中从活结点到根结点的路径。为此目的，可在每个结点处设置指向其父结点的指针，并设置左、右儿子标志。
class QNode
{
QNode *parent ; // 指向父结点的指针
bool LChild ; // 左儿子标志
Type weight ; // 结点所相应的载重量
}找到最优值后，可以根据parent回溯到根节点，找到最优解。
// 构造当前最优解
for (int j = n – 1; j> 0; j–) {
bestx[j] = bestE->LChild;
bestE = bestE->parent;
}LChild是左子树标志，1表示左子树，0表示右子树；
bestx[i]取值为0/1，表示是否取该货物。
备注：下面仅是我个人的理解：
以W = <10,8,5> , C = 16 问题为例，
最后遍历路径队列找出路径（office学的不好，别见怪啊）。从分析可知如果集装箱数量为n，那么需要的存储空间为(2^n-1)，无疑是很费内存空间的，而且代码要复杂的多，所以在我的代码中没有实现。
优先队列式分支限界法
解装载问题的优先队列式分支限界法用最大优先队列存储活结点表。活结点x在优先队列中的优先级定义为从根结点到结点x的路径所相应的载重量再加上剩余集装箱的重量之和。
优先队列中优先级最大的活结点成为下一个扩展结点。以结点x为根的子树中所有结点相应的路径的载重量不超过它的优先级。子集树中叶结点所相应的载重量与其优先级相同。
在优先队列式分支限界法中，一旦有一个叶结点成为当前扩展结点，则可以断言该叶结点所相应的解即为最优解。此时可终止算法。
两种实现方式：
（1） 在结点优先队列的每一个活结点中保存从解空间树的根节点到该活结点的路径。 算法确定了达到最优值的叶结点时，在该叶结点处同时得到相同的最优解。
（2） 在算法的搜索进程中保存当前以构造出的部分解空间树。这样在算法确定了达到最优值的叶结点时，就可以在解空间树种该叶结点开始向根结点回溯，构造出相应的最优解。
实现：
#include <iostream>
#include <vector>
#include <queue>
#include <numeric>
using namespace std;
// BAB for "branch and bound method"
// FIFO队列式分支限界法
class load_BAB
{
public:
load_BAB (const vector<int>& w, int c)
: weight (w), capacity (c), c_count ((int)w.size()), best_w(0) {
}
int get_best_w () const {
return best_w ;
}
// 队列式分支限界法
int queue_BAB () {
live_node_q.push (-1); // 同层节点尾部标识
int i = 0;
int cw = 0;
while (true) {
// 检查左子结点
if (cw + weight[i] <= capacity) {
__en_queue (cw + weight[i], i) ;
/*if ((cw + weight[i]) > best_w) {
best_w = cw + weight[i];
}*/
}
// 检查右子节点(可能产生最优解)
int best_rest = accumulate (weight.begin() + i + 1, weight.end(), 0) ;
if (best_rest > best_w) {
__en_queue (cw, i) ;
}
// 取下一个结点
cw = live_node_q.front ();
live_node_q.pop ();
if (cw == -1) {
if (live_node_q.empty ()) {
return best_w ;
}
live_node_q.push (-1);
cw = live_node_q.front ();
live_node_q.pop ();
++ i ;
}
}
}
private:
void __en_queue (int cw, int i) {
// 将活结点加入到活结点队列Q中
if (i >= c_count - 1) {
if (cw > best_w) {
best_w = cw ;
}
}
else {
live_node_q.push (cw) ;
}
}
private:
vector<int> weight; // 集装箱重量
queue<int> live_node_q; // 活结点队列
int c_count; // 集装箱 (container) 个数
int capacity; // 轮船承载量
int best_w; // 最优载重量
};
// 子集空间树中结点
class BB_node
{
public:
BB_node (BB_node* par, bool lc) {
parent = par ;
left_child = lc ;
}
public:
BB_node* parent ; // 父结点
bool left_child ; // 左儿子结点标志
} ;
// 优先级队列结点
class heap_node
{
public:
heap_node (BB_node* node, int uw, int lev) {
live_node = node ;
upper_weight = uw ;
level = lev ;
}
friend
bool operator < (const heap_node& lth, const heap_node& rth) {
return lth.upper_weight < rth.upper_weight ;
}
friend
bool operator > (const heap_node& lth, const heap_node& rhs) {
return lth.upper_weight > rhs.upper_weight ;
}
public:
BB_node* live_node ; //
int upper_weight ; // 活结点优先级（上界）
int level ; // 活结点在子集树中所处的层序号
};
// 优先权队列式分支限界法
class load_PQBAB
{
public:
load_PQBAB (const vector<int>& w, int c)
: weight (w), capacity (c), c_count (static_cast<int>(w.size())) {
}
~load_PQBAB () {
}
void max_loading () {
BB_node* pbn = NULL ; // 当前扩展结点
int i = 0 ; // 当前扩展结点所处的层
int ew = 0 ; // 扩展结点所相应的载重量
vector<int> r (c_count, 0);// 剩余重量数组
for (int j = c_count - 2; j >= 0; -- j) {
r[j] = r[j + 1] + weight[j + 1] ;
}
/*copy (r.begin(), r.end(), ostream_iterator<int>(cout, " ")) ;
cout << endl; */
// 搜索子集空间树
while (i != c_count) {
// 非叶结点，检查当前扩展结点的儿子结点
if (ew + weight[i] <= capacity) {
// 左儿子为可行结点
__add_live_node (ew + weight[i] + r[i], i + 1, pbn, true) ;
}
// 右儿子结点为可行结点
__add_live_node (ew + r[i], i + 1, pbn, false) ;
// 释放内存
while (pbn != NULL) {
BB_node *p = pbn ;
pbn = pbn->parent ;
delete p ;
}
// 取下一扩展结点
heap_node node = pri_queue.top () ;
pri_queue.pop ();
// cout << node.upper_weight <<endl;
i = node.level ;
pbn = node.live_node ;
ew = node.upper_weight - r[i - 1] ;
}
// 释放内存
while (pri_queue.size() != 0) {
heap_node node = pri_queue.top () ;
pri_queue.pop () ;
while (node.live_node != NULL) {
BB_node* temp = node.live_node ;
node.live_node = node.live_node->parent ;
delete temp ;
}
}
// 构造最优解
cout << "best capacity: " << ew << endl ;
cout << "path: " ;
vector<bool> temp_path ;
while (pbn != NULL) {
temp_path.push_back (pbn->left_child) ;
BB_node *temp = pbn ;
pbn = pbn->parent ;
delete temp ;
}
copy (temp_path.rbegin(), temp_path.rend(), ostream_iterator<bool> (cout, " "));
cout << endl ;
}
private:
// 产生新的活结点，加入到子集树中
void __add_live_node (int uw, int lev, BB_node* par, bool lc) {
// 深拷贝
BB_node *first = NULL;
BB_node *end = NULL ;
while (par != NULL) {
BB_node* p = new BB_node(NULL, par->left_child) ;
if (first == NULL) {
first = p ;
end = p ;
}
else {
end->parent = p ;
end = end->parent ;
}
par = par->parent ;
}
BB_node* p = new BB_node (first, lc) ;
pri_queue.push (heap_node (p, uw, lev)) ;
}
private :
vector<int> weight; // 集装箱重量
int c_count; // 集装箱 (container) 个数
int capacity; // 轮船承载量
priority_queue<heap_node> pri_queue ; // 活结点优先级队列
} ;
int main()
{
const int capacity = 20 ;
vector<int> weight ;
weight.push_back (10);
weight.push_back (8);
weight.push_back (5);
weight.push_back (1);
weight.push_back (3);
load_PQBAB l (weight, capacity) ;
l.max_loading ();
/*load_BAB lb (weight, capacity) ;
lb.queue_BAB () ;
cout << lb.get_best_w() << endl ;*/
return 0;
}旅行售货员问题
- 问题描述
某售货员要到若干城市去推销商品，已知各城市之间的路程(或旅费)。他要选定一条从驻地出发，经过每个城市一次，最后回到驻地的路线，使总的路程(或总旅费)最小。
路线是一个带权图。图中各边的费用（权）为正数。图的一条周游路线是包括V中的每个顶点在内的一条回路。周游路线的费用是这条路线上所有边的费用之和。
旅行售货员问题的解空间可以组织成一棵树，从树的根结点到任一叶结点的路径定义了图的一条周游路线。旅行售货员问题要在图G中找出费用最小的周游路线（解空间：排列树）。
- 算法描述
算法开始时创建一个最小堆，用于表示活结点优先队列。堆中每个结点的子树费用的下界lcost值是优先队列的优先级。接着算法计算出图中每个顶点的最小费用出边并用minout记录。
如果所给的有向图中某个顶点没有出边，则该图不可能有回路，算法即告结束。如果每个顶点都有出边，则根据计算出的minout作算法初始化。
使用最小堆：
对树中的每个节点，定义以下成员变量：
优先级：lcost
当前节点的路径长度：cc
剩余节点的最小出边和：rcost
节点在树中的深度：s
长度为n的数组x[0:n-1]，用来存放从起点开始的路径。
我们定义：
对第n-2层以上的节点：lcost = cc + rcost
对第n-1，n-2层的节点：lcost = 该回路的长度
算法的while循环体完成对排列树内部结点的扩展。对于当前扩展结点，算法分2种情况进行处理：
1、首先考虑s = n-2的情形，此时当前扩展结点是排列树中某个叶结点的父结点。如果该叶结点相应一条可行回路且费用小于当前最小费用，即：lcost < bestc,则将该叶结点插入到优先队列中，否则舍去该叶结点。
2、当s < n-2时，算法依次产生当前扩展结点的所有儿子结点。由于当前扩展结点所相应的路径是x[0:s]，其可行儿子结点是从剩余顶点x[s+1:n-1]中选取的顶点x[i]，且(x[s]，x[i])是所给有向图G中的一条边。对于当前扩展结点的每一个可行儿子结点，计算出其前缀(x[0:s]，x[i])的费用cc和相应的下界lcost。当lcost
#include <iostream>
#include <vector>
#include <queue>
#include <limits>
using namespace std ;
class heap_node
{
public:
heap_node (float lc, float cc, float rc, int s, const vector<int>& p)
: lower_cost (lc), current_cost (cc), remainder_cost (rc), size(s)
{
path = p ;
}
friend
bool operator < (const heap_node& rhs, const heap_node& lhs) {
return rhs.lower_cost > lhs.lower_cost ;
}
public:
float lower_cost ; // 子树费用的下界
float current_cost ; // 当前费用
float remainder_cost ;// 剩余顶点的最小出边费用和
int size ; // 根节点到当前结点的路径为path [0 : s]
vector<int> path ; // 需要进一步搜索的顶点是path [s+1 : n-1]
} ;
class BBTSP
{
public:
static float MAX_VALUE;
static float NO_EDGE_VALUE;
typedef priority_queue<heap_node> min_heap ;
public:
// 构造函数
BBTSP (const vector<vector<float> >& g) {
graph = g ;
node_count = (int)g.size ();
best_p.resize (node_count) ;
}
void bb_TSP () {
int n = node_count;
min_heap mh ; // 最小堆
// min_out[i] = 顶点i最小出边费用
vector<float> min_out(node_count) ;
float min_sum = 0.0f ; // 最小出边费用和
for (int i = 0; i < node_count ; ++ i) {
float min = MAX_VALUE ;
for (int j = 0; j < node_count ; ++ j) {
if (graph[i][j] != NO_EDGE_VALUE && graph[i][j] < min) {
min = graph[i][j] ;
}
}
if (min == MAX_VALUE) {
cerr << " No cycle !" << endl;
return ;
}
min_out[i] = min ;
min_sum += min ;
}
for (int i = 0; i < node_count ; ++ i) {
cout << "结点" << i << "的最小出边费用和为: " << min_out[i] << endl ;
}
cout << "总出边费用为: " << min_sum << endl << endl ;
// 初始化
vector<int> path(n) ;
for (int i = 0; i < n; ++ i) {
path[i] = i;
}
heap_node hn(0, 0, min_sum, 0, path);
float best_c = MAX_VALUE ;
// 搜索排列空间树
while (hn.size < n - 1) {
// 非叶结点
path = hn.path ;
cout << "path: " ;
copy (path.begin(), path.end(), ostream_iterator<int>(cout,"")) ;
cout << endl ;
if (hn.size == n - 2) {
// 当前扩展结点是叶结点的父结点
// 再加条边构成回路
// 所构成的回路是否优于当前最优解
if (graph[path[n-2]][path[n-1]] != NO_EDGE_VALUE &&
graph[path[n-1]][1] != NO_EDGE_VALUE &&
hn.current_cost + graph[path[n-2]][path[n-1]] +
graph[path[n-1]][1] < best_c ) {
// 找到费用更小的回路
best_c = hn.current_cost + graph[path[n-2]][path[n-1]] +
graph[path[n-1]][1] ;
hn.current_cost = best_c ;
hn.lower_cost = best_c ;
hn.size ++ ;
mh.push (hn) ;
}
}
else {
// 产生当前扩展结点的儿子结点
for (int i = hn.size + 1; i < n; ++ i) {
if (graph[path[hn.size]][path[i]] != NO_EDGE_VALUE) {
// 可行的儿子结点
float cc = hn.current_cost + graph[path[hn.size]][path[i]] ;
float rcost = hn.remainder_cost - min_out[path[hn.size]] ;
// 优先级= 当前费用+ 剩余结点的最小费用和- 当前节点的最小费用
float b = cc + rcost ; // 下界
if (b < best_c) {
// 子树可能含最优解，结点插入最小堆
vector<int> p(n) ;
for (int j = 0; j < n; ++ j) {
p[j] = path[j] ;
}
//copy (p.begin(), p.end(), ostream_iterator<int> (cout, " ")) ;
//cout << ", " ;
p[hn.size + 1] = path[i] ;
p[i] = path[hn.size + 1] ;
//copy (p.begin(), p.end(), ostream_iterator<int> (cout, " ")) ;
//cout << endl;
heap_node in(b, cc, rcost, hn.size + 1, p) ;
mh.push (in) ;
}
}
}
}
// 取下一扩展结点
hn = mh.top () ;
mh.pop () ;
}
best_cost = best_c ;
for (int i = 0; i < node_count; ++ i) {
best_p[i] = path[i] ;
}
copy (best_p.begin(), best_p.end(), ostream_iterator<int> (cout, "")) ;
cout << endl ;
cout << "best cost : " << best_cost << endl ;
}
private:
vector<vector<float> > graph ; // 图的数组表示
int node_count ;// 结点个数
vector<int> best_p ; // 产生最优解的路径
float best_cost ; // 最优解
} ;
float BBTSP::MAX_VALUE = http://www.mamicode.com/numeric_limits<float>::max() ;
float BBTSP::NO_EDGE_VALUE = http://www.mamicode.com/-1.0f ;
int main()
{
// 图的初始化
const int size = 6 ;
vector<vector<float> > g(size) ;
for (int i = 0; i < size; ++ i) {
g[i].resize (size) ;
}
for (int i = 0;i < size; ++ i) {
g[i][i] = BBTSP::NO_EDGE_VALUE ;
}
g[0][1] = 30 ;
g[0][2] = 6 ;
g[0][3] = 4 ;
g[0][4] = 5 ;
g[0][5] = 6 ;
g[1][0] = 30 ;
g[1][2] = 4 ;
g[1][3] = 5 ;
g[1][4] = 2 ;
g[1][5] = 1 ;
g[2][0] = 6 ;
g[2][1] = 4 ;
g[2][3] = 7 ;
g[2][4] = 8 ;
g[2][5] = 9 ;
g[3][0] = 4 ;
g[3][1] = 5 ;
g[3][2] = 7 ;
g[3][4] = 10 ;
g[3][5] = 20 ;
g[4][0] = 5 ;
g[4][1] = 2 ;
g[4][2] = 8 ;
g[4][3] = 10 ;
g[4][5] = 3 ;
g[5][0] = 6 ;
g[5][1] = 1 ;
g[5][2] = 9 ;
g[5][3] = 20 ;
g[5][4] = 3 ;
BBTSP bt(g) ;
bt.bb_TSP () ;
return 0 ;
}运行结果：
结点 0的最小出边费用和为: 4
结点 1的最小出边费用和为: 1
结点 2的最小出边费用和为: 4
结点 3的最小出边费用和为: 4
结点 4的最小出边费用和为: 2
结点 5的最小出边费用和为: 1
总出边费用为: 16
path: 0 1 2 3 4 5
path: 0 3 2 1 4 5
path: 0 4 2 3 1 5
path: 0 3 1 2 4 5
path: 0 4 1 3 2 5
path: 0 3 1 5 4 2
path: 0 4 1 5 2 3
path: 0 2 1 3 4 5
path: 0 3 1 4 2 5
path: 0 5 2 3 4 1
path: 0 4 5 3 1 2
path: 0 5 1 3 4 2
path: 0 4 5 1 3 2
path: 0 2 1 3 4 5
path: 0 2 1 5 4 3
path: 0 3 1 5 4 2
path: 0 5 1 4 3 2
path: 0 2 1 4 3 5
path: 0 3 2 1 4 5
path: 0 3 1 4 5 2
path: 0 3 2 1 4 5
path: 0 3 2 1 5 4
path: 0 2 1 5 4 3
path: 0 2 1 4 5 3
path: 0 4 1 2 3 5
path: 0 5 4 3 2 1
path: 0 3 1 2 4 5
path: 0 5 4 1 2 3
path: 0 3 2 1 4 5
path: 0 5 1 2 4 3
0 5 1 2 4 3
best cost : 21回溯法与分支限界