算法基础之分支限界

梦里梦外; 2022-09-09 13:53 226阅读 0赞

### 算法基础之分支限界（C++示例） ###

分支限界（branch and bound）法与回溯法类似，但是回溯法是求解目标中所有满足约束条件的解，而分支限界法是找出满足约束条件的一个解，最优。

所谓“分支”是采用广度优先的策略，依次生成扩展结点的所有分支（即：儿子结点）。

所谓“限界”是在结点扩展过程中，计算结点的上界（或下界），边搜索边减掉搜索树的某些分支，从而提高搜索效率。

回溯法和分支限界法的一些区别

回溯法深度优先搜索堆栈活结点的所有可行子节点被遍历后，才被从栈中弹出找出满足约束条件的所有解。

分支限界法广度优先或最小消耗优先搜索队列，优先队列每个结点只有一次成为活结点的机会找出满足约束条件的一个解或特定意义下的最优解。

常见的两种分支界限法

1）队列式（FIFO）分支界限法（广度优先）：按照队列先进先出原则选取下一个结点为扩展结点。

2）优先队列式分支限界法（最小损耗优先）：按照优先队列规定的优先级选取优先级最高的结点成为当前扩展结点。

**例1、现在看一个简化版本的装载问题：一艘轮船装载问题**。是否有一个合理的装载方案，可将这n个集装箱装上这2艘轮船？将第一艘轮船尽可能装满等价于选取全体集装箱的一个子集，使该子集中集装箱重量之和最接近载重量。

★**队列式分支限界法**

解装载问题的队列式分支限界法仅求出所要求的最优值，稍后进一步构造最优解。

首先检测当前扩展结点的左儿子结点是否为可行结点。如果是，则将其加入到活结点队列Q中。

然后，将其右儿子结点加入到活结点队列中(右儿子结点一定是可行结点)。2个儿子结点都产生后，当前扩展结点被舍弃。

活结点队列中，队首元素被取出作为当前扩展结点。

活结点队列已空，算法终止。

源码如下：

//#include <bits/stdc++.h>
    #include <queue>
    #include <iostream>
    using namespace std;
    typedef struct QNode
    {
        QNode *parent;
        int lchild;
        int weight;
    }QNode;
    int n;
    int c;
    int bestw;
    int w[100];
    int bestx[100];
    void InPut()
    {
        printf("集装箱数和轮船载重量:");
    	scanf("%d %d", &n, &c);
    	printf("%d 个集装箱的重量:",n);
        for(int i = 1; i <= n; ++i) //w[i]的i从1开始的 
            scanf("%d", &w[i]);
    }
    //QNode *&bestE 的原因是 首先bestE是个地址， 其次引用为了赋值使用, 后边for循环中用到
    void EnQueue(queue<QNode *> &q, int wt, int i, QNode *E, QNode *&bestE, int ch)
    {
        if(i == n)
        {
            if(wt == bestw)
            {
                bestE = E;
                bestx[n] = ch;
                return;
            }
        }
        QNode *b;
        b = new QNode;
        b->weight = wt;
        b->lchild = ch;
        b->parent = E;
        q.push(b);
    }
    int MaxLoading()
    {
        queue<QNode *>q;
        q.push(0);
        int i = 1;
        int Ew = 0, r = 0;
        bestw = 0;
        for(int j = 2; j <= n; ++j)
            r += w[j];
        QNode *E, *bestE; //bestE的作用是：结束while循环后，bestE指向最优解的叶子节点，然后通过bestE->parent找到装入了哪些物品。
        E = new QNode; //E这里作为一个中间量，连接parent和child
        E = 0;         //赋0是因为树的根的值是0，while刚开始的时候其代表root
        while(true)
        {
            int wt = Ew + w[i];
            if(wt <= c)
            {
                if(wt > bestw)   //提前更新bestW,注意更新条件
                    bestw = wt;
                EnQueue(q, wt, i, E, bestE, 1);
            }
            if(Ew + r >= bestw)   //右儿子剪枝
            {
                EnQueue(q, Ew, i, E, bestE, 0);    
            }
            E = q.front();
            q.pop();
            if(!E)    //如果取得的数是0，代表该处理下一层
            {
                if(q.empty())   //如果队列为空，表示该循环结束了
                    break;
                q.push(0);     //如果队列中还有数据，表示循环还没结束。在该层的末尾加一个0标识符
                E = q.front();
                q.pop();
                i++;     //下一层走起
                r -= w[i];   //计算剩余的重量
            }
            Ew = E->weight; //不要忘记更新最新节点的值
        }
        for(int j = n - 1; j > 0; --j)
        {
            bestx[j] = bestE->lchild;
            bestE = bestE->parent;
        }
    }
    void OutPut()
    {
        printf("最优装载量为 %d\n", bestw);
        printf("装载的物品为 \n");
        for(int i = 1; i <= n; ++i)
            if(bestx[i] == 1)
              printf("%d ", i); // i 是 w[i]的 序号;  w[i]的i从1开始的 
    }
    int main()
    {
        InPut();
    
        MaxLoading();
        OutPut();
    }

运行之，如下图所示：

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6L2v5Lu25oqA5pyv5a2m5Lmg5byA5Y-R54ix5aW96ICF_size_14_color_FFFFFF_t_70_g_se_x_16][]

**★优先队列式分支限界法**

解装载问题的优先队列式分支限界法用最大优先队列存储活结点表。

活结点x在优先队列中的优先级定义为从根结点到结点x的路径所相应的载重量Ew(即：当前扩展结点船的载重量Ew)再加上剩余集装箱的重量r之和（即：将上界Ew+r定义为结点优先级）。

优先队列中优先级最大的活结点成为下一个扩展结点。

子集树中叶结点所相应的载重量与其优先级（上界值）相同，即：该叶子结点的上界值等于当前叶子结点处船的重量Ew。

在优先队列式分支限界法中，一旦有一个叶结点成为当前扩展结点，则可以断言该叶结点所相应的解即为最优解。此时可终止算法。

源码如下：

//#include <bits/stdc++.h>
    #include <queue>
    #include <iostream>
    using namespace std;
    class MaxHeapQNode
    {
    public:
        MaxHeapQNode *parent;  //父节点
        int lchild;    //左节点:1; 右节点"0
        int weight;    //总重量
        int lev;       //层次
    };
    struct cmp
    {
        bool operator()(MaxHeapQNode *&a, MaxHeapQNode *&b) const
        {
            return a->weight < b->weight;
        }
    };
    int n;
    int c;
    int bestw;
    int w[100];
    int bestx[100];
    void InPut()
    {
        printf("集装箱数和轮船载重量:");
    	scanf("%d %d", &n, &c);
    	printf("%d 个集装箱的重量:",n);
        for(int i = 1; i <= n; ++i) //w[i]的i从1开始的  
            scanf("%d", &w[i]);
    }
    void AddAliveNode(priority_queue<MaxHeapQNode *, vector<MaxHeapQNode *>, cmp> &q, MaxHeapQNode *E,  int wt, int i, int ch)
    {
        MaxHeapQNode *p = new MaxHeapQNode;
        p->parent = E;
        p->lchild = ch;
        p->weight = wt;
        p->lev = i + 1;
        q.push(p);
    }
    void MaxLoading()
    {
        priority_queue<MaxHeapQNode *, vector<MaxHeapQNode *>, cmp > q; // 大顶堆
        //定义剩余重量数组r
        int r[n + 1];
        r[n] = 0;
        for(int j = n - 1; j > 0; --j)
            r[j] = r[j + 1] + w[j + 1];
        int i = 1;
        MaxHeapQNode *E;
        int Ew = 0;
        while(i != n + 1)
        {
            if(Ew + w[i] <= c)
            {
                AddAliveNode(q, E, Ew + w[i] + r[i], i, 1);
            }
            AddAliveNode(q, E, Ew + r[i], i, 0);
    
            //取下一节点
            E = q.top();
            q.pop();
            i = E->lev;
            Ew = E->weight - r[i - 1];
        }
        bestw = Ew;
        for(int j = n; j > 0; --j)
        {
            bestx[j] = E->lchild;
            E = E->parent;
        }
    }
    void OutPut()
    {
        printf("最优装载量为 %d\n", bestw);
        printf("装载的物品为 \n");
        for(int i = 1; i <= n; ++i)
            if(bestx[i] == 1)
              printf("%d ", i);  // i 是 w[i]的 序号; w[i]的i从1开始的 
    }
    int main()
    {
        InPut();
        MaxLoading();
        OutPut();
    }

运行之，如下图所示：

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6L2v5Lu25oqA5pyv5a2m5Lmg5byA5Y-R54ix5aW96ICF_size_15_color_FFFFFF_t_70_g_se_x_16][]

**例2**、背包问题：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。

假设有n个物品和1个背包，每个物品的重量为wi,价值为vi,每个物品只有1件，要么装入，要么不装，不可拆分，背包载重量一定，如何装使背包装入的物品价值最高？

例如有 n = 6 个物品，背包最大可装载 M = 100 Kg，物品重量和价值分别如下：

W=\{92,4,43,83,84,68\}

V=\{44,46,90,72,91,40\}

求最优背包价值。

源码如下：

#include<iostream>
    #include<queue>
    #include<cstring>
    using namespace std;
    const int maxn=10;
    
    struct node
    {
        int cv,lv;//当前价值，剩余价值
        int lw;//剩余容量
        int id;//物品序号
        int x[maxn];//解向量
        node()
        {
            memset(x,0,sizeof(x));
        }
        node(int cvv,int lvv,int lww,int idd)//有参构造函数
        {
            memset(x,0,sizeof(x));
            cv=cvv;
            lv=lvv;
            lw=lww;
            id=idd;
        }
    };//结点结构体
    
    int n,W;//物品种数，背包容量
    int w[maxn],v[maxn];//重量和价值
    int bestx[maxn];//最优解
    int bestv;//最优价值
    
    void init()
    {
        memset(w,0,sizeof(w));
        memset(v,0,sizeof(v));
        memset(bestx,0,sizeof(bestx));
        bestv=0;
    }
    
    void bfs()
    {
        queue<node> q;
        int sumv=0;
        int i;
        for(i=1; i<=n; ++i)
            sumv+=v[i];
        q.push(node(0,sumv,W,1));
        while(!q.empty())
        {
            node live;
            live=q.front();
            q.pop();
            int t=live.id;//当前处理物品的序号
            if(t>n||live.lw==0)//到达叶子结点或者没有容量了
            {
                if(live.cv>=bestv)//更新最优解,不加等号的话，第一次计算得到的值不会更新
                {
                    for(int i=1; i<=n; ++i)
                        bestx[i]=live.x[i];
                    bestv=live.cv;
                }
                continue;
            }
            if(live.cv+live.lv<bestv)//不满足限界条件
                continue;
            if(live.lw>=w[t])//满足约束条件，可以生成左孩子
            {
                node lchild(live.cv+v[t],live.lv-v[t],live.lw-w[t],t+1);
                for(int i=1; i<=n; ++i)
                    lchild.x[i]=live.x[i];
                lchild.x[t]=1;
                if(lchild.cv>bestv)//注意要更新最优值
                    bestv=lchild.cv;
                q.push(lchild);
            }
            if(live.cv+live.lv-v[t]>=bestv)//满足限界条件，可以生成右孩子
            {
                node rchild(live.cv,live.lv-v[t],live.lw,t+1);
                for(int i=1; i<=n; ++i)
                    rchild.x[i]=live.x[i];
                rchild.x[t]=0;
                q.push(rchild);
            }
        }
    }
    
    void output()
    {
        cout<<"可装载物品的最大价值为："<<bestv<<endl;
        cout<<"装入的物品为：";
        for(int i=1; i<=n; ++i)
            if(bestx[i])
                cout<<i<<" ";
        cout<<endl;
        return ;
    }
    
    int main()
    {
        init();
        
        cout<<"请输入物品个数：";
        cin>>n;
        cout<<"请输入背包容量：";
        cin>>W;
        cout<<"请依次输入物品的重量：";
        for(int i=1; i<=n; ++i) //w[i]的i从1开始的 
            cin>>w[i];
        cout<<"请依次输入物品的价值：";
        for(int i=1; i<=n; ++i) //v[i]的i从1开始的 
            cin>>v[i];
    	    
        bfs();
        
        output();
        
        return 0;
    }

运行之，如下图所示：

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6L2v5Lu25oqA5pyv5a2m5Lmg5byA5Y-R54ix5aW96ICF_size_16_color_FFFFFF_t_70_g_se_x_16][]

[https://blog.csdn.net/weixin\_45591044/article/details/111089127][https_blog.csdn.net_weixin_45591044_article_details_111089127]

[https://blog.csdn.net/wwj\_748/article/details/9163211][https_blog.csdn.net_wwj_748_article_details_9163211]

[https://blog.csdn.net/Luoxiaobaia/article/details/109725604][https_blog.csdn.net_Luoxiaobaia_article_details_109725604]

[https://www.freesion.com/article/9394920015/][https_www.freesion.com_article_9394920015]

[https://cloud.tencent.com/developer/article/1616376][https_cloud.tencent.com_developer_article_1616376]

[https://blog.csdn.net/vxiao\_shen\_longv/article/details/98481660][https_blog.csdn.net_vxiao_shen_longv_article_details_98481660]

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6L2v5Lu25oqA5pyv5a2m5Lmg5byA5Y-R54ix5aW96ICF_size_14_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/ac57fa1d660f4dd78cce5ceb54fdc7f6.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6L2v5Lu25oqA5pyv5a2m5Lmg5byA5Y-R54ix5aW96ICF_size_15_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/5d6dfddfada047929ad597f284e82f8b.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6L2v5Lu25oqA5pyv5a2m5Lmg5byA5Y-R54ix5aW96ICF_size_16_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/65e67a4bd8494f5d8333a1eb13713353.png
[https_blog.csdn.net_weixin_45591044_article_details_111089127]: https://blog.csdn.net/weixin_45591044/article/details/111089127
[https_blog.csdn.net_wwj_748_article_details_9163211]: https://blog.csdn.net/wwj_748/article/details/9163211
[https_blog.csdn.net_Luoxiaobaia_article_details_109725604]: https://blog.csdn.net/Luoxiaobaia/article/details/109725604
[https_www.freesion.com_article_9394920015]: https://www.freesion.com/article/9394920015/
[https_cloud.tencent.com_developer_article_1616376]: https://cloud.tencent.com/developer/article/1616376
[https_blog.csdn.net_vxiao_shen_longv_article_details_98481660]: https://blog.csdn.net/vxiao_shen_longv/article/details/98481660