分治限界法

以下均转载于:五大常用算法-分支界限,加入了一些我自己的想法

1.基本描述

类似于回溯法,也是一种在问题的解空间树T上搜索问题解的算法。但在一般情况下,分支限界法与回溯法的求解目标不同。回溯法的求解目标是找出T中满足约束条件的所有解,而分支限界法的求解目标则是找出满足约束条件的一个解,或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解,即在某种意义下的最优解

分支搜索算法

所谓“分支”就是采用广度优先的策略,依次搜索E-结点的所有分支,也就是所有相邻结点,抛弃不满足约束条件的结点,其余结点加入活结点表。然后从表中选择一个结点作为下一个E-结点,继续搜索。
选择下一个E-结点的方式不同,则会有几种不同的分支搜索方式。
1.FIFO搜索
2.LIFO搜索
3.优先队列式搜索

2.分支限界法的一般过程

由于求解目标不同,导致分支限界法与回溯法在解空间树T上的搜索方式也不相同。回溯法以深度优先的方式搜索解空间树T,而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树T

1.分支限界法的搜索策略是:
在扩展结点处,先生成其所有的儿子结点(分支),然后再从当前的活结点表中选择下一个扩展对点。为了有效地选择下一扩展结点,以加速搜索的进程,在每一活结点处,计算一个函数值(限界),并根据这些已计算出的函数值,从当前活结点表中选择一个最有利的结点作为扩展结点,使搜索朝着解空间树上有最优解的分支推进,以便尽快地找出一个最优解

2.分支限界法常以广度优先或以最小耗费(最大效益)优先的方式搜索问题的解空间树。
问题的解空间树是表示问题解空间的一棵有序树,常见的有子集树和排列树。在搜索问题的解空间树时,分支限界法与回溯法对当前扩展结点所使用的扩展方式不同。在分支限界法中,每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点,就一次性产生其所有儿子结点。在这些儿子结点中,那些导致不可行解或导致非最优解的儿子结点被舍弃,其余儿子结点被子加入活结点表中。此后,从活结点表中取下一结点成为当前扩展结点,并重复上述结点扩展过程。这个过程一直持续到找到所求的解或活结点表为空时为止。

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

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

  1. 方法对解空间树的搜索方式
  2. 存储结点的常用数据结构
  3. 结点存储特性常用应用
  4. 回溯法深度优先搜索堆栈活结点的所有可行子结点被遍历后才被从栈中弹出找出满足约束条件的所有解
  5. 分支限界法广度优先或最小消耗优先搜索队列、优先队列每个结点只有一次成为活结点的机会找出满足约束条件的一个解或特定意义下的最优解

4.举个例子

还是上文回溯算法中的例子,给定一组数组nums,再给定一个目标值target,找出集合nums的所有子集使其之和刚好为目标值,nums中的数只能使用一次。不过我们稍作修改,现在只需要找到一个子集即可。虽然这个例子不算优化问题,但是却很好的展示了只要满足条件即可。

下面按照思路进行求解。

4.1构造解空间树

这里和回溯算法中解空间树其实相同,我们采用子集树

4.2确定搜索方式

这里我使用的FIFO的队列形式,使用该队列维护一张活节点表,队首为扩展节点。

4.3利用剪枝函数进行界限分割

假定我们给出的数组为nums = {1,1,2,3,4,5,6},target=9,那么现在有一种情况是1+1+2=4,当前节点为第3层(从第0层开始),那么其左子树则为1+1+2+3=7满足条件,那么需不需要进入其右子树呢?其右子树表示为1+1+2+0+xxx,即不加入第3层,下面还有3层为4,5,6。计算上界为1+1+2+4+5+6>9的,这样说明第3层的右子树可能存在解,我们需要遍历,但是考虑另一种情况,如果我把nums改为{1,1,2,3,1,1,1},则右子树上界为1+1+2+0+1+1+1=7<9,显然就算下面所有都加完,都不能达到9,不需要搜索右子树。

以图的形式再次说明


image.png

下面是整体代码

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    /**
     * 分支限界法
     */
    static int[] nums = {1,1,2,3,4,5,6};
    static int target = 9;
    static int n = nums.length;
    public static void main(String[] args) {
        solve();
    }

    private static void solve() {
        boolean[] currentX = new boolean[n];
        //这里采用FIFO队列存储活节点
        Queue<Node> queue = new LinkedList<Node>();
        int i = 0;
        int currentValue = 0;
        int up;

        do {
            //检查左子树可行性
            if(currentValue+nums[i] < target) {
                //进入左子树
                currentX[i] = true;
                queue.add(new Node(currentX.clone(),currentValue+nums[i] ,i+1));
            }else if (currentValue+nums[i]  == target) {
                //如果产生可行解
                currentX[i] = true;
                System.out.println(Arrays.toString(currentX));
                break;
            }
            up = bound(i);
            if(currentValue+up >= target) {
                //进入右子树
                currentX[i] = false;
                queue.add(new Node(currentX.clone(),currentValue,i+1));
            }
            //取得扩展节点
            Node currentNode = queue.poll();

            currentX = currentNode.x;
            currentValue = currentNode.vlaue;
            i = currentNode.level;
        }while(!queue.isEmpty());
    }

    private static class Node{
        boolean[] x;//用于恢复现场,记录其父节点及其以上加入情况
        int vlaue;//当前累加值
        int level;//当前是第几层
        public Node(boolean x[],int vlaue, int level) {
            super();
            this.x = x;
            this.vlaue = vlaue;
            this.level = level;
        }

    }

    //剪枝函数
    private static int bound(int i) {
        int sum = 0;
        i++;
        for(;i<n;i++) {
            sum+=nums[i];
        }
        return sum;
    }
}

运行结果如下:

[true, true, false, true, true, false, false]

即:1+1+3+4=9

下面在给出0-1背包问题的分支限界解法。
0-1背包问题:给定一些物品,每个物品均有其价格和重量,现有一个有限容量的背包,问如何选择物品才能使得所获价值最大,物品不能分块装。

物品:
weight = {2, 2, 6, 5, 4};
value = {6, 3, 5, 4, 6};
容量:
c = 10;

代码如下:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    /**
     * 分支界限法,解决0-1背包问题
     */

    static int bestValue = 0;
    static int[] weight = {2, 2, 6, 5, 4};
    static int[] value = {6, 3, 5, 4, 6};
    static int c = 10;
    static int n = weight.length;
    static boolean[] bestX = new boolean[n];

    public static void main(String[] args) {
        //对物品进行按照性价比预排序,因为总是期望性价比高的先存放(当然也可以自定义规则)
        int[] oldIndex = selSort();
        solve();
        //恢复原序列
        boolean[] realX = new boolean[n];
        int valueS =0;
        for (int i = 0; i < bestX.length; i++) {
            realX[oldIndex[i]] = bestX[i];
            if(bestX[i]){
                valueS+=value[i];
            }
        }
        System.out.println(Arrays.toString(realX));
        System.out.println("vlaue:"+valueS);
    }

    /*
     * 使用简单选择排序,数据量大时可选择快速排序,堆排,归并排序等高效排序算法
     */
    private static int[] selSort() {
        float[] p = new float[weight.length];
        int[] oldeIndex = new int[p.length];
        for (int i = 0; i < p.length; i++) {
            p[i] = (float) value[i] / weight[i];
            oldeIndex[i] = i;
        }
        //用来存储排序后,元素在原来数组中的位置,方便后续恢复信息,不要求按原数组输出可不用这一步

        for (int i = 0; i < p.length - 1; i++) {
            for (int j = i + 1; j < p.length; j++) {
                if (p[i] < p[j]) {
                    float tempP = p[i];
                    p[i] = p[j];
                    p[j] = tempP;

                    int tempW = weight[i];
                    weight[i] = weight[j];
                    weight[j] = tempW;

                    int tempV = value[i];
                    value[i] = value[j];
                    value[j] = tempV;

                    int tempI = oldeIndex[i];
                    oldeIndex[i] = oldeIndex[j];
                    oldeIndex[j] = tempI;
                }
            }
        }
        return oldeIndex;
    }

    private static void solve() {
        int i = 0;
        int currentValue = 0;
        int currentWeight = 0;
        boolean[] currentX = new boolean[weight.length];
        //申请活节点FIFO队列
        Queue<Node> queue = new LinkedList<Node>();

        do {
            //判定左子树可行性
            if (currentWeight + weight[i] <= c) {
                currentX[i] = true;
                queue.add(new Node(currentX.clone(), currentValue + value[i], currentWeight + weight[i], i + 1));
                //判断是否需要更新最优解
                if (currentValue + value[i] > bestValue) {
                    bestValue = currentValue + value[i];
                    bestX = currentX.clone();
                }
            }
            //计算上界
            if (currentValue + bound(i, currentWeight) >= bestValue) {
                //可以进入右子树
                currentX[i] = false;
                queue.add(new Node(currentX.clone(), currentValue, currentWeight, i + 1));
            }
            //更新扩展节点
            Node currrentNode = queue.poll();
            currentValue = currrentNode.currentValue;
            currentWeight = currrentNode.currentWeight;
            currentX = currrentNode.x;
            i = currrentNode.level;
        } while (!queue.isEmpty() && i != n);
    }

    private static float bound(int i, int currentWeight) {
        i++;
        float p = 0;
        while (currentWeight <= c && i < n) {
            p += value[i];
            currentWeight += weight[i];
        }
        if (i < n) {
            //删除多装的一个
            p -= value[i];
            currentWeight -= weight[i];
            p += (c - currentWeight) * ((float) (value[i]) / (weight[i]));
        }
        return p;
    }

    private static class Node {
        boolean[] x;//保存背包中以存放的物品信息
        int currentValue;
        int currentWeight;
        int level;

        public Node(boolean[] x, int currentValue, int currentWeight, int level) {
            this.x = x;
            this.currentValue = currentValue;
            this.currentWeight = currentWeight;
            this.level = level;
        }
    }
}


执行结果:

[true, true, false, false, true]
vlaue:15
即:第1,2,5个物品,价值6+3+6=15,重量2+2+4 = 8
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 206,723评论 6 481
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 88,485评论 2 382
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 152,998评论 0 344
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 55,323评论 1 279
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 64,355评论 5 374
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 49,079评论 1 285
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 38,389评论 3 400
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 37,019评论 0 259
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 43,519评论 1 300
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,971评论 2 325
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,100评论 1 333
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,738评论 4 324
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 39,293评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,289评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,517评论 1 262
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 45,547评论 2 354
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,834评论 2 345

推荐阅读更多精彩内容

  • 回溯法与分支限界法 时间 2016-03-24 标签 搜索 回溯法 1、概念 回溯算法实际上一个类似枚举的搜索尝...
    wangchuang2017阅读 2,317评论 0 4
  • 五大常用算法之一:分治算法 基本概念: 把一个复杂的问题分成两个或更多的相同的或相似的子问题。再把子问题分成更小的...
    親愛的破小孩阅读 4,860评论 0 1
  • B树的定义 一棵m阶的B树满足下列条件: 树中每个结点至多有m个孩子。 除根结点和叶子结点外,其它每个结点至少有m...
    文档随手记阅读 13,183评论 0 25
  • 可能你自己也没意识到,你来回的重复和比较无意中给了我莫大的推荐。终于在深夜,看完滚蛋吧,肿瘤君。 你说,你现在的心...
    她爱写故事阅读 390评论 0 1
  • 不阿绝唱阅读 337评论 0 0