算法笔记之分支限界法（1）

广度优先

广度优先搜索，其实就是层次遍历，程序采用队列来实现。

算法思想

从根开始，常以BF或以最小耗费（即最大收益）优先的方式搜索问题的解空间树。首先将根结点加入活结点表，接着从活结点表中取出根结点，使其成为当前扩展结点，一次性生成其所有孩子结点，判断孩子结点是舍弃还是保留，舍弃哪些导致不可行解或导致非最优解的孩子结点，其余的被保留在活结点表中。再从活结点表中取出一个活结点作为当前扩展结点，重复上述扩展过程，直到找到所需的解或活结点表为空时为止。每一个活结点最多只有一次机会成为扩展结点。

算法步骤

算法解题步骤为：
1. 定义问题的解空间。
2. 确定问题的解空间组织结构。
3. 搜索解空间。搜索前要定义判断标准（约束函数或限界函数），如果选优优先队列式分支限界法，则必须确定优先级。

回溯法与分支限界法的异同

1.相同点：

• 均需要先定义问题的解空间，确定的解空间组织结构一般都是树和图；
• 在问题的解空间树上搜索问题解。
• 搜索前均需要确定判断条件，该判断条件用于判断扩展生成的结点是否为可行结点。
• 搜索过程中必须判断扩展生成的结点是否满足判断条件，如果满足则保留该扩展结点，否则舍弃。

2.不同点

• 搜索目标不同：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支界限法的求解目标则是找出满足约束条件的一个解，或者是在满足约束条件的解中找出在某种意义下的最优解。
• 搜索的方式不同：回溯法以深度优先搜索方法搜索空间树，分支限界法采用广度优先法或者最小消耗优先搜索解空间树。
• 扩展方式不同：回溯法搜索，扩展结点一次只生成一个孩子结点，而分支限界法则一次生成所有孩子结点。

0-1背包问题

问题分析

前面有，不再重述，

购物车重量W=10。
商品的结构体定义为：

struct Goods
{
    int weight;
    int value;
} goods[N];

算法设计

1. 定义问题的解空间。问题解空间为{x₁,x₂,...,x_i,...,x_n}，显约束为：x_i=0或者1。
2. 确定解空间的组织结构：子集树。
3. 搜索解空间：
   • 约束条件为：w_ix_i≤W（i=1~n）
   • 限界条件：cp+rp>bestp（cp为当前已经装入购物车的物品的总价值，rp为第t+1~第n种物品的总价值，bestp为最大价值）
4. 搜索过程：从根节点开始，以BFS方式进行搜索。根节点首先成为活结点，也是当前的扩展结点。一次性生成所有孩子结点，由于子集树中约定左分支上的值为“1”，因此沿着扩展结点的左分支扩展，则代表装入物品；右分支的值为“0”，代表不装入物品。此时判断是否满足约束条件和限界条件，如果满足，则将其加入队列中；反之舍弃。然后再从队列中取出一个元素，作为当前扩展结点，搜索过程队列为空时结束。

步骤解释

1. 初始化。sumw=2+5+4+2=13，sumv=6+3+5+4=18，因为sumw>W，所以不能装完，所以需要进行后续的操作。初始化cp=0,rp=sumv，当前剩余重量rw=W；当前处理物品序号为1；当前最优值bestp=0.解向量为x[]=(0,0,0,0)，创建一个根结点Node(cp,rp,rw,id)，标记为A，加入先进先出队列q中。cp为装入购物车的物品价值，rp为剩余物品的总价值，rw为剩余容量，id为物品号，x[]为当前解向量。

//定义结点。每个节点来记录当前的解。
struct Node

{
    int cp, rp; //cp背包的物品总价值，rp剩余物品的总价值
    int rw; //剩余容量
    int id; //物品号
    bool x[N];//解向量
    Node() {}
    Node(int _cp, int _rp, int _rw, int _id){
        cp = _cp;
        rp = _rp;
        rw = _rw;
        id = _id;
        memset(x, 0, sizeof(x));//解向量初始化为0
    }
};

2. 扩展A结点。队头元素A出队，该结点的cp+rp≥bestp，满足限界条件，可以扩展。rw=10>goods[1].weight=2，剩余容量大于1号物品，满足约束条件，可以放入购物车，cp=0+6=6。rp=18-6=12，rw=10-2=8，t=2，x[1]=1，解向量更新为x[]=(1,0,0,0)，生成左孩子B，加入q队列，更新bestp=6。再扩展右分支，cp=0,rp=18-6=12,cp+rp>=bestp=6，满足限界条件，不放入1号物品，cp=0,rp=12,rw=10,t=2,x[1]=0，解向量为x[]=(0,0,0,0)，创建新结点C，加入q队列。如下表所示，X表示为空。

3. 扩展B结点。队头元素B出队，该结点cp+rp>=bestp，满足限界条件，可以扩展。rw=8>goods[2].weight=5，剩余容量大于2号物品重量，满足约束条件，可以放入购物车，cp=6+3=9。rp=12-3=9，rw=8-5=3，t=3，x[2]=1，解向量更新为x[]=(1,1,0,0)，生成左孩子D，加入q队列，更新bestp=9。再扩展右分支，cp=6,rp=12-3=9,cp+rp>=bestp=9，满足限界条件，不放入2号物品，cp=6,rp=9,rw=8,t=3,x[2]=0，解向量为x[]=(1,0,0,0)，创建新结点E，加入q队列。如下表所示。

4. 扩展C结点。队头元素C出队，该结点cp+rp>=bestp，满足限界条件，可以扩展。rw=10>goods[2].weight=5，剩余容量大于2号物品重量，满足约束条件，可以放入购物车，cp=0+3=3。rp=12-3=9，rw=10-5=5，t=3，x[2]=1，解向量更新为x[]=(0,1,0,0)，生成左孩子F，加入q队列。再扩展右分支，cp=0,rp=12-3=9,cp+rp>=bestp=9，满足限界条件，不放入2号物品，cp=6,rp=9,rw=10,t=3,x[2]=0，解向量为x[]=(0,0,0,0)，创建新结点G，加入q队列。如下表所示。

5. 扩展D结点。队头元素D出队，该结点cp+rp>=bestp，满足限界条件，可以扩展。但是rw=3>goods[3].weight=4，所以不满足约束条件，舍弃左分支。扩展右分支，cp=9,rp=9-5=4,cp+rp>=bestp=9，满足限界条件，不放入3号物品，cp=9,rp=4,rw=3,t=4,x[3]=0，解向量为x[]=(1,1,0,0)，创建新结点H，加入q队列。如下表所示。

6. 扩展E结点。同理可得cp=11,rp=4,rw=4,t=4,x[3]=1，更新解向量为x[]=(1,0,1,0)，生成左孩子I，加入q队列，更新bestp=11。扩展右分支，cp=6,rp=9-5=4,cp+rp=10<bestp=11，所以不满足限界条件，舍弃。
7. 扩展F结点。同理得到左分支，cp=8,rp=4,rw=1,t=4,x[3]=1，解向量为x[]=(0,1,1,0)，生成左孩子J，加入q队列。扩展右分支，cp+rp<11，舍弃。
8. 扩展G结点。该结点cp+rp<bestp=11，不满足限界条件，不再扩展。
9. 扩展H结点。队头H结点出队，该结点cp+rp>=bestp，满足限界条件，rw=3>goods[4].weight=2，满足约束条件，令cp=9+4=13,rp=4-4=0,rw=3-2=1,t=5,x[4]=1，解向量更新为x[]=(1,1,0,1)，生成孩子K，加入q队列，更新bestp=13。右分支不满足限界条件舍弃。
10. 扩展I结点。 队头I结点出队，该结点cp+rp>=bestp，满足限界条件，rw=4>goods[4].weight=2，满足约束条件，令cp=11+4=15,rp=4-4=0,rw=4-2=2,t=5,x[4]=1，解向量更新为x[]=(1,0,1,1)，生成孩子L，加入q队列，更新bestp=15。右分支不满足限界条件舍弃。
11. 队头元素J出队，该结点cp+rp=12<15，不满足限界条件，不再扩展。
12. 队头元素K出队，扩展K结点：t=5，已经处理完毕，cp<bestp，不是最优解。
13. 队头元素K出队，扩展K结点：t=5，已经处理完毕，cp=bestp，是最优解，输出该向量(1,0,1,1)。
14. 队列为空，算法结束。

代码实现

int bestp, W, n, sumw, sumv;
/*
bestp 用来记录最优解。
W为购物车最大容量。
n为物品的个数。
sumw 为所有物品的总重量。
sumv 为所有物品的总价值。
*/
//bfs 来进行子集树的搜索。
int bfs()
{
    int t, tcp, trp, trw;
    queue<Node> q; //创建一个普通队列(先进先出)
    q.push(Node(0, sumv, W, 1)); //压入一个初始结点
    while (!q.empty()) //如果队列不空
    {
        Node livenode, lchild, rchild;//定义三个结点型变量
        livenode = q.front();//取出队头元素作为当前扩展结点livenode
        q.pop(); //队头元素出队
                 //cp+rp>bestp当前装入的价值+剩余物品价值小于当前最优值时，不再扩展。
        cout << "当前结点的id值:" << livenode.id << "当前结点的cp值:" << livenode.cp << endl;
        cout << "当前结点的解向量:";
        for (int i = 1; i <= n; i++)
        {
            cout << livenode.x[i];
        }
        cout << endl;
        t = livenode.id;//当前处理的物品序号
                        // 搜到最后一个物品的时候不需要往下搜索。
                        // 如果当前的购物车没有剩余容量(已经装满)了，不再扩展。
        if (t>n || livenode.rw == 0)
        {
            if (livenode.cp >= bestp)//更新最优解和最优值
            {
                for (int i = 1; i <= n; i++)
                {
                    bestx[i] = livenode.x[i];
                }
                bestp = livenode.cp;
            }
            continue;
        }
        if (livenode.cp + livenode.rp<bestp)//判断当前结点是否满足限界条件，如果不满足不再扩展
            continue;
        //扩展左孩子
        tcp = livenode.cp; //当前购物车中的价值
        trp = livenode.rp - goods[t].value; //不管当前物品装入与否，剩余价值都会减少。
        trw = livenode.rw; //购物车剩余容量
        if (trw >= goods[t].weight) //满足约束条件，可以放入购物车
        {
            lchild.rw = trw - goods[t].weight;
            lchild.cp = tcp + goods[t].value;
            lchild = Node(lchild.cp, trp, lchild.rw, t + 1);//传递参数
            for (int i = 1; i<t; i++)
            {
                lchild.x[i] = livenode.x[i];//复制以前的解向量
            }
            lchild.x[t] = true;
            if (lchild.cp>bestp)//比最优值大才更新
                bestp = lchild.cp;
            q.push(lchild);//左孩子入队
        }
        //扩展右孩子
        if (tcp + trp >= bestp)//满足限界条件，不放入购物车
        {
            rchild = Node(tcp, trp, trw, t + 1);//传递参数
            for (int i = 1; i<t; i++)
            {
                rchild.x[i] = livenode.x[i];//复制以前的解向量
            }
            rchild.x[t] = false;
            q.push(rchild);//右孩子入队
        }
    }
    return bestp;//返回最优值。
}

算法分析

时间复杂度为O(2ⁿ⁺¹)，空间复杂度O(n*2ⁿ⁺¹)。

算法优化拓展——优先队列式分支限界法

优先队列优化，简单来说就是以当前结点的上界为优先值，把普通队列改成优先队列。
1. 算法设计。约束条件没有改变。优先级定义为活结点代表的部分解锁描述的装入物品价值的上界，该价值上界越大，优先级越高。活结点的价值上界up=活结点的cp+剩余物品装满购物车剩余容量的最大价值rp'。限界条件变为up=cp+rp'>=bestp。
2. 解题步骤（简略版）
- 初始化。sumw和sumv分别用来统计所有物品的总重量和总价值。sumw=13,sumv=18,sumw>W，所以不能全部装完，需要搜索求解。
- 按价值重量比非递增排序。排序结果如下表所示。
- 后续不再详细叙述。

3.代码实现

//定义辅助物品结构体，包含物品序号和单位重量价值,用于按单位重量价值(价值/重量比)排序、
struct Object
 {
        int id; //物品序号
        double d;//单位重量价值
    }S[N];

//定义排序优先级按照物品单位重量价值由大到小排序
bool cmp(Object a1,Object a2)
{
    return a1.d>a2.d;
}

//定义队列的优先级。 以up为优先，up值越大，也就越优先
bool operator <(const Node &a, const Node &b)
{
    return a.up<b.up;
}

int bestp,W,n,sumw,sumv;
/*
  bestv 用来记录最优解。
  W为背包的最大容量。
  n为物品的个数。
  sumw 为所有物品的总重量。
  sumv 为所有物品的总价值。
*/

double Bound(Node tnode)
{
    double maxvalue=tnode.cp;//已装入购物车物品价值
    int t=tnode.id;//排序后序号
    //cout<<"t="<<t<<endl;
    double left=tnode.rw;//剩余容量
    while(t<=n&&w[t]<=left)
    {
        maxvalue+=v[t];
       // cout<<"malvalue="<<maxvalue<<endl;
        left-=w[t];
        t++;
    }
    if(t<=n)
        maxvalue+=double(v[t])/w[t]*left;
    //cout<<"malvalue="<<maxvalue<<endl;
    return maxvalue;
}
//priorbfs 为优先队列式分支限界法搜索。
int priorbfs()
{
     int t,tcp,trw;
     double tup; //当前处理的物品序号t，当前装入购物车物品价值tcp，
    //当前装入购物车物品价值上界tup，当前剩余容量trw
    priority_queue<Node> q; //创建一个优先队列,优先级为装入购物车的物品价值上界up
    q.push(Node(0, sumv, W, 1));//初始化,根结点加入优先队列
    while(!q.empty())
    {
        Node livenode, lchild, rchild;//定义三个结点型变量
        livenode=q.top();//取出队头元素作为当前扩展结点livenode
        q.pop(); //队头元素出队
        cout<<"当前结点的id值:"<<livenode.id<<"当前结点的up值:"<<livenode.up<<endl;
        cout<<"当前结点的解向量:";
        for(int i=1; i<=n; i++)
        {
            cout<<livenode.x[i];
        }
        cout<<endl;
        t=livenode.id;//当前处理的物品序号
        // 搜到最后一个物品的时候不需要往下搜索。
        // 如果当前的购物车没有剩余容量(已经装满)了，不再扩展。
        if(t>n||livenode.rw==0)
        {
            if(livenode.cp>=bestp)//更新最优解和最优值
            {
              cout<<"更新最优解向量:";
              for(int i=1; i<=n; i++)
              {
                bestx[i]=livenode.x[i];
                cout<<bestx[i];
              }
              cout<<endl;
              bestp=livenode.cp;
            }
            continue;
        }
        //判断当前结点是否满足限界条件，如果不满足不再扩展
        if(livenode.up<bestp)
          continue;
        //扩展左孩子
        tcp=livenode.cp; //当前购物车中的价值
        trw=livenode.rw; //购物车剩余容量
        if(trw>=w[t]) //满足约束条件，可以放入购物车
        {
            lchild.cp=tcp+v[t];
            lchild.rw=trw-w[t];
            lchild.id=t+1;
            tup=Bound(lchild); //计算左孩子上界
            lchild=Node(lchild.cp,tup,lchild.rw,lchild.id);//传递参数
            for(int i=1;i<=n;i++)
            {
              lchild.x[i]=livenode.x[i];//复制以前的解向量
            }
            lchild.x[t]=true;
            if(lchild.cp>bestp)//比最优值大才更新
               bestp=lchild.cp;
            q.push(lchild);//左孩子入队
        }
        //扩展右孩子
         rchild.cp=tcp;
         rchild.rw=trw;
         rchild.id=t+1;
         tup=Bound(rchild); //右孩子计算上界
         if(tup>=bestp)//满足限界条件，不放入购物车
         {
            rchild=Node(tcp,tup,trw,t+1);//传递参数
            for(int i=1;i<=n;i++)
            {
              rchild.x[i]=livenode.x[i];//复制以前的解向量
            }
            rchild.x[t]=false;
            q.push(rchild);//右孩子入队
          }
    }
    return bestp;//返回最优值。
}