算法笔记之分支限界法(1)

广度优先

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

算法思想

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

算法步骤

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

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

1.相同点:

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

2.不同点

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

0-1背包问题

问题分析

前面有,不再重述,

w[] 1 2 3 4
2 5 4 2
v[] 1 2 3 4
6 3 5 4

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

struct Goods
{
    int weight;
    int value;
} goods[N];
weight 2 5 4 2
value 6 3 5 4

算法设计

  1. 定义问题的解空间。问题解空间为{x1,x2,…,xi,…,xn},显约束为:xi=0或者1。
  2. 确定解空间的组织结构:子集树。
  3. 搜索解空间:
    • 约束条件为:wixi≤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
    }
};
  1. 扩展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表示为空
B X X X
B X X X
B C X X
B C X X
  1. 扩展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队列。如下表所示。
C D E X
C D E X
  1. 扩展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队列。如下表所示。
D E F G
D E F G
  1. 扩展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队列。如下表所示。
E F G H
E F G H
  1. 扩展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,所以不满足限界条件,舍弃。
  2. 扩展F结点。同理得到左分支,cp=8,rp=4,rw=1,t=4,x[3]=1,解向量为x[]=(0,1,1,0),生成左孩子J,加入q队列。扩展右分支,cp+rp<11,舍弃。
  3. 扩展G结点。该结点cp+rp<bestp=11,不满足限界条件,不再扩展。
  4. 扩展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。右分支不满足限界条件舍弃。
  5. 扩展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。右分支不满足限界条件舍弃。
  6. 队头元素J出队,该结点cp+rp=12<15,不满足限界条件,不再扩展。
  7. 队头元素K出队,扩展K结点:t=5,已经处理完毕,cp<bestp,不是最优解。
  8. 队头元素K出队,扩展K结点:t=5,已经处理完毕,cp=bestp,是最优解,输出该向量(1,0,1,1)。
  9. 队列为空,算法结束。

代码实现

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(2n+1),空间复杂度O(n*2n+1)。

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

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

weight 2 2 4 5
value 6 4 5 3

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;//返回最优值。
}

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注