查看“︁分支定界”︁的源代码

{{NoteTA
|G1= IT
}}
{{图搜索算法}}
'''分支定界'''（{{lang-en|Branch and bound}}，'''BB'''）是用于[[离散优化]]、[[组合优化]]以及[[数学优化]]问题的算法设计范式。分支定界算法可以视为一种对可行解进行穷举的算法，但是和[[穷举法]]所不同的是，分支定界算法在对某一分支进行检索之前会先算出该分支的上界或下界，如果界限不比目前最佳解更好，那么该分支就会被舍弃，从而节约了大量的时间。分支定界算法非常依赖合适的上界或下界，如果无法找到合适的界限，该算法将会退化为穷举法。

该方法最初是由阿尔萨·兰德和艾莉森·哈考特在1960年由[[英国石油公司]]赞助的[[倫敦政治經濟學院|伦敦经济学院]]进行离散规划研究时提出的，<ref name=land_doig>{{cite journal |last1=Land |first1=A. H. |last2=Doig |first2=A. G. |title=An Automatic Method of Solving Discrete Programming Problems |journal=Econometrica |date=1960 |volume=28 |issue=3 |pages=497–520 |doi=10.2307/1910129 |url=https://www.jstor.org/stable/1910129?origin=crossref#metadata_info_tab_contents |accessdate=2022-10-16 |issn=0012-9682 |archive-date=2022-12-01 |archive-url=https://web.archive.org/web/20221201123545/https://www.jstor.org/stable/1910129?origin=crossref#metadata_info_tab_contents |dead-url=no }}</ref>目前已成为解决[[NP困难]]优化问题最常用的工具。<ref name="clausen99">{{cite techreport |first=Jens |last=Clausen |title=Branch and Bound Algorithms—Principles and Examples |year=1999 |publisher=[[University of Copenhagen]] |url=http://www.diku.dk/OLD/undervisning/2003e/datV-optimer/JensClausenNoter.pdf |access-date=2014-08-13 |archive-url=https://web.archive.org/web/20150923214803/http://www.diku.dk/OLD/undervisning/2003e/datV-optimer/JensClausenNoter.pdf |archive-date=2015-09-23 |url-status=dead }}</ref>“分支定界”一词最早出现在解决[[旅行推销员问题]]的时候。<ref name="little">{{cite journal |last1=Little |first1=John D. C. |last2=Murty |first2=Katta G. |last3=Sweeney |first3=Dura W. |last4=Karel |first4=Caroline |title=An algorithm for the traveling salesman problem |journal=Operations Research |volume=11 |issue=6 |year=1963 |pages=972–989 |doi=10.1287/opre.11.6.972 |url=http://dspace.mit.edu/bitstream/handle/1721.1/46828/algorithmfortrav00litt.pdf |hdl=1721.1/46828 |hdl-access=free |access-date=2022-03-03 |archive-date=2022-01-20 |archive-url=https://web.archive.org/web/20220120114331/https://dspace.mit.edu/bitstream/handle/1721.1/46828/algorithmfortrav00litt.pdf |dead-url=no }}</ref><ref>{{cite journal |last1=Balas |first1=Egon |last2=Toth |first2=Paolo |title=Branch and Bound Methods for the Traveling Salesman Problem: |date=1983-03-01 |doi=10.21236/ada126957 |url=https://www.semanticscholar.org/paper/Branch-and-Bound-Methods-for-the-Traveling-Salesman-Balas-Toth/3446fc85faacecd1ef6ad5d1a3f85cb6fff8cb36 |accessdate=2022-10-16 |archive-date=2022-10-17 |archive-url=https://web.archive.org/web/20221017142055/https://www.semanticscholar.org/paper/Branch-and-Bound-Methods-for-the-Traveling-Salesman-Balas-Toth/3446fc85faacecd1ef6ad5d1a3f85cb6fff8cb36 |dead-url=no }}</ref>
==概述==
分支定界法的目的是从可行解集合<math>S</math>中选出一个解<math>x</math>，使得目标函数<math>f(x)</math>最大化或最小化。其中集合<math>S</math>被称为搜寻空间或可行区域。本节所有的最佳化问题均可视为对<math>f(x)</math>进行最小化，因为对<math>f(x)</math>进行最大化问题本质上还是对<math>g(x)=-f(x)</math>进行最小化。分支定界法需要遵循以下两个原则：
*先是将搜寻空间通过递归的手段分成多个子空间，在每个子空间对<math>f(x)</math>进行最小化，这种分割方式就是分支。
*如果只有分支那么这种方法就成为了[[暴力搜索]]法，运算量将会非常庞大。为了提升算法的性能，需要对每个分支进行下界计算，对于那些下界已经超过目前最佳解的分支，需要进行[[决策树剪枝|剪枝]]操作。
为了将这些原则转化为问题的具体算法，我们需要将这些候选解转化为合适的[[数据结构]]，这样的表示方式被称为问题的[[实例]]。我们用<math>S_I</math>表示实例<math>I</math>的候选解集，实例表示必须有如下三个操作:
*<math>branch(I)</math>：产生两个或多个实例，每个实例为<math>S_I</math>的一个子集。（通常来讲，每个子集都是[[不交集|互不相交]]的，这是为了避免每个候选解被多次访问从而浪费时间，但有时也会有例外。<math>S_I</math>的最优解必然会出现在它的一个或多个子集中。<ref name="bader">{{cite encyclopedia |first1=David A. |last1=Bader |first2=William E. |last2=Hart |first3=Cynthia A. |last3=Phillips |author3-link=Cynthia A. Phillips |title=Parallel Algorithm Design for Branch and Bound |editor-first=H. J. |editor-last=Greenberg |encyclopedia=Tutorials on Emerging Methodologies and Applications in Operations Research |publisher=Kluwer Academic Press |year=2004 |url=http://www.cc.gatech.edu/~bader/papers/ParallelBranchBound.pdf |access-date=2015-09-16 |archive-url=https://web.archive.org/web/20170813145917/http://www.cc.gatech.edu/~bader/papers/ParallelBranchBound.pdf |archive-date=2017-08-13 |url-status=dead }}</ref>）
*<math>bound(I)</math>：计算实例<math>I</math>中所有候选解所对应的目标函数值的下界，满足对于任意<math>x \in S_I</math>，<math>bound(I) \leq f(x)</math>。
*<math>solution(I)</math>：确定<math>I</math>是否表示单个候选解。（如果不是，接下来可以从<math>S_I</math>中回传一些可行的解再进一步进行分支定界的操作。{{r|bader}}）如果<math>solution(I)</math>回传了一个解，那么<math>f(solution(I))</math>提供了整个可行解空间中最优目标函数的上界。
通过使用这些操作，分支定界算法在分支操作形成的实例[[树 (数据结构)|树]]中执行自顶向下递归搜索。在访问实例<math>I</math>时，我们不妨先检查<math>bound(I)</math>，如果<math>bound(I)</math>已经大于目前所找到的上界，我们就直接丢弃该实例。为了实现这一步骤，我们需要设定一个[[全局变量]]，用于记录目前为止所检查的所有实例中看到的最小上界。
===通用格式===
下面是最小化任意目标函数<math>f</math>的通用分支定界算法框架。<ref name="clausen99"/>要从中得到一个算法，我们需要一个边界函数，用来计算函数<math>f</math>在搜索树节点上的下界，以及一个基于特定问题的分支规则。本文提出的通用算法是一个[[高阶函数]]。
#首先使用[[启发法]]找出一个优化问题的解<math>x_h</math>,并存储数值<math>B=f(x_h)</math>。（如果无法通过启发法找到解，则设B的值为无穷大）B表示到目前为止找到的最佳解，并把它作为候选解的上界。
#初始化一个[[队列]]，用于存储在不进行变量分配时所得到的局部解。
#执行如下[[循环 (控制流程)|循环]]直至队列被清空：
##从队列中取出节点<math>N</math>
##如果节点<math>N</math>代表单一的候选解<math>x</math>且满足<math>f(x)<B</math>，那么我们就可以说<math>x</math>为目前所找到的最佳解，令<math>B</math>←<math>f(x)</math>。
##反之，节点<math>N</math>产生新的分支节点<math>N_i</math>，对于这些新产生的节点：
###如果<math>bound(N_i) > B</math>，则舍弃该节点，因为最优解不可能出现在这个节点里。
###反之，将节点<math>N_i</math>存入队列。
在这一算法中，队列也可以替换为其他的数据结构。在使用遵循[[先进先出算法|先进先出]]原则的队列时，该算法属于[[广度优先搜索]]。反之如果使用遵循先进后出的[[堆栈]]储存节点，该算法就成为了[[深度优先搜索]]。当然，也可以使用[[优先队列]]对所有的节点的下界进行排序，进一步提升效率。<ref name="clausen99"/>采用这种算法的例子是[[戴克斯特拉算法]]及其衍生的[[A*搜索算法]]。当无法通过启发法生成初始解时，建议使用深度优先算法的变体，因为它可以快速生成完整解，从而得到整个问题的上界。<ref>{{cite book |last1=Mehlhorn |first1=Kurt |author-link1=Kurt Mehlhorn |first2=Peter |last2=Sanders |author2-link=Peter Sanders (computer scientist) |title=Algorithms and Data Structures: The Basic Toolbox |publisher=Springer |year=2008 |page=249 |url=http://people.mpi-inf.mpg.de/~mehlhorn/ftp/Toolbox/GenericMethods.pdf |access-date=2022-03-04 |archive-date=2018-06-19 |archive-url=https://web.archive.org/web/20180619111231/http://people.mpi-inf.mpg.de/~mehlhorn/ftp/Toolbox/GenericMethods.pdf |dead-url=no }}</ref>
==== 伪代码 ====
和C++语言相似的伪代码如下：
<syntaxhighlight lang="c++" line="1">
// C++-like implementation of branch and bound, 
// assuming the objective function f is to be minimized
CombinatorialSolution branch_and_bound_solve(
    CombinatorialProblem problem, 
    ObjectiveFunction objective_function /*f*/,
    BoundingFunction lower_bound_function /*bound*/) 
{
    // Step 1 above
    double problem_upper_bound = std::numeric_limits<double>::infinity; // = B
    CombinatorialSolution heuristic_solution = heuristic_solve(problem); // x_h
    problem_upper_bound = objective_function(heuristic_solution); // B = f(x_h)
    CombinatorialSolution current_optimum = heuristic_solution;
    // Step 2 above
    queue<CandidateSolutionTree> candidate_queue;
    // problem-specific queue initialization
    candidate_queue = populate_candidates(problem);
    while (!candidate_queue.empty()) { // Step 3 above
        // Step 3.1
        CandidateSolutionTree node = candidate_queue.pop();
        // "node" represents N above
        if (node.represents_single_candidate()) { // Step 3.2
            if (objective_function(node.candidate()) < problem_upper_bound) {
                current_optimum = node.candidate();
                problem_upper_bound = objective_function(current_optimum);
            }
            // else, node is a single candidate which is not optimum
        }
        else { // Step 3.3: node represents a branch of candidate solutions
            // "child_branch" represents N_i above
            for (auto&& child_branch : node.candidate_nodes) {
                if (lower_bound_function(child_branch) <= problem_upper_bound) {
                    candidate_queue.enqueue(child_branch); // Step 3.3.2
                }
                // otherwise, bound(N_i) > B so we prune the branch; step 3.3.1
            }
        }
    }
    return current_optimum;
}
</syntaxhighlight>
在上述伪代码中，函数<code>heuristic_solve</code>和<code>populate_candidates</code>为[[子程序]]，必须基于具体问题进行设计。
===改进===
当<math>\mathbf{x}</math>为空间处于<math>\mathbb{R}^n</math>的向量时，分支定界算法可以与区间分析<ref>{{cite book|last1=Moore|first1=R. E.|
title=Interval Analysis|
year=1966|publisher=Prentice-Hall|
location=Englewood Cliff, New Jersey|isbn=0-13-476853-1}}
</ref>和间隔承包商技术相结合，以提供全局最小包络值的保证。<ref>
{{cite book|last1=Jaulin|first1=L.|last2=Kieffer|first2=M.|last3=Didrit|first3=O.|last4=Walter|first4=E.|
title=Applied Interval Analysis|url=https://archive.org/details/appliedintervala0000unse|year=2001|publisher=Springer|location=Berlin|isbn=1-85233-219-0}}
</ref><ref>
{{cite book|last=Hansen|first=E.R.|
title=Global Optimization using Interval Analysis|year=1992|
publisher=Marcel Dekker|location=New York}}
</ref>

==参考文献==
{{reflist}}

[[Category:最优化算法]]