算法学习——分支限界法_分支限界算法经典例题

实质

回溯法的改进版本

与回溯法的比较

不同：回溯法为“盲目搜索”（DFS），分支限界法为最“好”优先，智能搜索。

共同：统称为树搜索技术，都在搜索解空间树，并剪枝。

缺陷

只适用于组合优化问题

程序框架

    // 以求最大值为例
    public void branchbound(){
 
        // 初始化
        max = 0;
        bestx = [x0,....,xn-1]; // 保存每层的最优结果
        PriorityQueue queue = new PriorityQueue();
        queue.add(root);
 
        // 循环
        while(!queue.isEmpty()){
            node = queue.poll();
 
            if(node.up <= max){
                break;
            }
 
            // 依次遍历子节点
            for(each of subNode){
                if(!consttraint(subNode)){
                    continue;
                }
 
                // 若子节点非叶节点
                if(subNode.layer < n){
                    queue.add(subNode);
                }else {
                    max = subNode.v;
                    bestx = subNode.x;
                }
 
            }
        }