分支限界通常是将一个完全形态的搜索树（树的叶子结点可能是可行/最优解）通过限界技术在一些不可能得到正确答案的分支上进行剪枝，从而达到减小搜索空间的目的。
解 与解空间 通常，解是一个/组向量： < x 1 , x 2 , x 3 , x 4 , . . . , x n > <x_1, x_2, x_3, x_4,..., x_n> <x1,x2,x3,x4,...,xn>。 并且解具有多米诺性质：若部分解 < x 1 , x 2 , x 3 , . . . , x k > <x_1, x_2, x_3, ..., x_k> <x1,x2,x3,...,xk>是一个最优解，则 部分解 < x 1 , x 2 , x 3 , . . . , x k − 1 > <x_1, x_2, x_3, ..., x_{k-1}> <x1,x2,x3,...,xk−1>也一定是最优的。 逆否命题： 如果解 < x 1 , x 2 , x 3 , . . . , x k − 1 > <x_1, x_2, x_3, ..., x_{k-1}> <x1,x2,x3,...,xk−1>不是最优的部分解，则 < x 1 , x 2 , x 3 , . . . , x k > <x_1, x_2, x_3, ..., x_k> <x1,x2,x3,...,xk>也绝不可能是一个合格的解的一部分了，因此这时就可以剪去该分支了。 解空间通常是一个棵树，或许是子集树，或许是排列树，也有可能是多叉树，具体问题具体分析。
搜索方法 一般采用深度优先加回溯的方法，在搜到叶子结点或者搜到某个不可能的分支以后，就回溯到父亲结点继续搜。也可以采用广度优先搜索，但是比较少见。
约束条件 约束条件一般在题目中会给出，要求我们的解应该满足一定的条件。例如对于背包问题，要求放入物品的总重量不能超过背包的容量；对于最大团问题，新加入的点要与已得团中的所有结点都有边相连；对于八皇后问题，要求皇后不能在同一横线竖线和斜线上；对于货郎担（旅行者）问题，要求每个城市只能走一次，所以已经走过的城市不能再走，于是解空间是一个排列树。
界 界就是我们当前得到的最优解。初值一般为0（对于求最大极大的问题）或者正无穷（对于求极小最小值的问题）。
代价函数 代价函数是用来供我们剪枝用的，好的代价函数能够极大的降低搜索空间，并且计算简单，否则如果计算起来很复杂，需要花费的资源比不剪枝搜完整个子树空间还大，那就得不偿失了。 代价函数是计算当前结点如果继续往下搜到最终的叶子结点得到的解所能取得的最优值。 如果从结点 x k x_k xk出发，遍历整个以 x k x_k xk为根的子树所能得到的最优值都还不如界，那显然就没有必要继续搜这个子树了。 因此可知代价函数一般由两部分组成：已有价值 + 未来可能的最优价值。已有价值就是搜到结点 x k x_k xk时取得的部分解的值，未来可能的最优价值是需要好好设计的，这个是最重要的部分了。本质上这一部分就是一个估计上界（当求最大极大时）的过程，所以需要恰当的放缩，在数学的不等式中也是极难的。当然你可以将上界估到最大，但是这就失去了剪枝的能力，因此这个上界估计的越小越好，但是这是极难的，并且另一方面这个估计出来的上界不能太难算，否则也失去剪枝的本来目的。 代价函数的用法：每当遍历到一个结点，就计算该结点的代价，然后与界比较，如果优于界，就继续搜以该结点为根的子树；否则就将该子树分支剪掉。
剪枝条件
该结点的代价不优于界；该结点不满足约束条件。解向量： < x 1 , x 2 , x 3 , x 4 > <x_1, x_2, x_3, x_4> <x1,x2,x3,x4>， x i x_i xi的取值范围是自然数，所以这是一个无穷叉树？哈哈哈，当然不是，考虑到实际，每种物品最多只能装10/wi个（下取整）。 约束条件：装入物品的总重量不超过背包容量。 界：当前所得到的可行解中的最优解。 代价函数：如果背包剩余的重量小于后面尚未被考虑过（标号大于k的物品）的所有的物品的重量，那肯定是没法再往里装物品了，因此代价就是当前背包里的已有价值；否则我们就假定剩余的容量全部用来装第k+1件物品（因为已经按照性价比降序排了，所以第k+1件物品是性价比最高的，这也是我们能够得到的最大价值，是一个估计的上界）。 剪枝：每当搜索到一个结点时，都计算是否满足约束条件，再计算代价函数是否优于界，如果不满足约束条件或者不优于界，则将该分支剪掉。 什么是组合优化问题？ 组合（最）优化问题是最优化问题的一类。最优化问题似乎自然地分成两类：
一类是连续变量的问题，另一类是离散变量的问题。 具有离散变量的问题，我们称它为组合的。在连续变量的问题里，一般地是求一组实数，或者一个函数；在组合问题里，是从一个有限集或者可数无限集里寻找一个对象——典型地是一个整数，一个集合，一个排列，或者一个图。一般地，这两类问题有相当不同的特色，并且求解它们的方法也是很不同的。组合优化（Combinatorial Optimization）问题的目标是从组合问题的可行解集中求出最优解。
在讲这个问题之前先介绍几个概念。
子图：子图就是某个图取出一部分点，及这部分点所拥有的边的一部分组成的。因为边不能脱离点单独存在，所以点可以是原图点集的任何子集，但是边不能是原图边集的任何子集。 补图：因为补集是要相对于一个全集来说的，对于不同的全集同一个集合得到的补集是不一样的。例如对于自然数集来说，如果全集是整数集合，补集就是负整数集，如果全集是有理数集，那补集就是全部的负有理数和正有理数中除了整数的那些数的集合。这里的全集或者全图指的是一个图对应的完全图，即保留其所有的点，并给任意两点间都加一条边得到的图。补图的补 补的是原图相对于其完全图的边。即补图和原图的点还有对应完全图的点集是相同的，补图的边集和原图的边集是相对于完全图的边集互补的。 从上图可以很清晰的看到，原图与补图是互为补图的。 团：图的完全子图。注意与连通图的区别，连通图只要任意两结点间有路径即可，而完全图要求的是任意两结点间有边。 最大团：顾名思义，就是结点数最多的团。 点独立集：由图中的点子集构成，这些点之间没有任何的边相连，注意这里只是子集内的任意两点之间都没有边，并不是说子集内的点不能与子集外的点有边相连。独立不是指与外部独立，而是指独立集内部是互相独立的。 最大点独立集：点最多的独立集。 在上图左边的那个图中，点独立集有 { v 1 , v 4 } 、 { v 1 , v 5 } 、 { v 2 , v 3 } 、 { v 2 , v 5 } 、 { v 3 , v 4 } 、 { v 1 , v 4 , v 5 } 等 \{v_1, v_4\}、\{v_1, v_5\}、\{v_2, v_3\}、\{v_2, v_5\}、\{v_3, v_4\}、\{v_1, v_4, v_5\}等 {v1,v4}、{v1,v5}、{v2,v3}、{v2,v5}、{v3,v4}、{v1,v4,v5}等，最大点独立集为 { v 1 , v 4 , v 5 } \{v_1, v_4, v_5\} {v1,v4,v5}。 命题： U是G的最大团当且仅当U是 G ‾ \overline{G} G(G的补图)的最大点独立集。验证一下，上面说了 { v 1 , v 4 , v 5 } \{v_1, v_4, v_5\} {v1,v4,v5}是左边的最大点独立集，那么它应该是右边那个补图的最大团，显然是的。 这个命题可以这么理解，U是 G ‾ \overline{G} G的最大点独立集，说明首先它里面包含的点最多，其次它里面的任意两点之间都没有任何的边相连。对应在G里面，这些点就是任意两个之间都有边相连，那么这只能说明U在G里是一个团，是否是最大呢？ 可以用反证法来说明一下，假设U在G里面不是最大的团，那么必然还有一个比U更大的团，设为T，这个最大团T对应到 G ‾ \overline{G} G中，其任意两点之间的边都将不再存在，此时T成了 G ‾ \overline{G} G中的一个点独立集，而且其点的个数比U还多，这与U是 G ‾ \overline{G} G中的最大点独立集矛盾。 这说明了，如果人家U是一个最大团，那么即使它跑到对手那里也照样能得到一个最大点独立集的称号，告诉我们如果你是优秀的人到哪里都会秀起来的。 混淆图：由有穷字符集构成图的顶点集，互相易混淆的字符之间连上一条边所构成的图。 这里的代价函数比较粗糙，就是说这个上界放的太大了，但是这也没办法，因为未考察的点可能最终都是团中的点，所以必须要这么放大。代价函数不够精确的结果就是其剪枝能力差，对搜索空间的减小帮助能力差。
代价函数的意义：代价函数分为两大部分，前一项是已走过路径长度，后一项是剩余路径长度的下界，这是一个估计值。这个估计值又由两部分组成，前面是从点ik开始前往其它相邻城市的最短距离，后面的部分是剩余所有未去过城市去其相邻城市最短距离的和。 这里可以看到，从某个城市出发的最短距离是可以去已经到达过的市的情况下，得出的最短距离。 这里说了代价函数的计算为常数时间，而上面的代价函数里面是要累加从每个城市到其相邻城市的距离的最小值的，因此需要遍历所有未达的城市并且求所有未达城市的最短出发路径，这两个计算都需要遍历，即使每个城市都存储了其最短出发路径，那也还是要遍历所有的未达城市，不知道这里为什么说是常数时间。 仔细想想，其实是这么做的，因为这是深度优先，我们可以在初始时就将所有的城市的最短出发距离累加和保存起来，然后每遍历到一个城市，就将该城市的最短出发路径从这个和里面减掉就行了，而不用重新计算。
代价函数的估计下界是将剩余未排列的圆都看作是与它们（剩余未排）之间最小的那个圆相同的大小，得到的排列长度。这是一个合理的估计下界，剩余的圆无论怎么排都不可能小于这个值。在遍历树中每个结点的过程中计算代价函数值，并与界比较，如果比界大那就剪掉该分支。 这是一棵排列树，因此叶结点总数为n!，从根结点到叶节点的路径有n个结点，每个结点要计算当前的解得到的值，以及代价函数的值。 假如我们已经求得了前k个圆的排列长度( l k = r 1 + x k + r k l_k=r_1+x_k+r_k lk=r1+xk+rk)，现在要求第k+1个圆放过去得到的排列长度 l k + 1 l_{k+1} lk+1。因为 x k x_k xk已知，则我们可以很容易计算得到 x k + 1 = x k + 2 r k ∗ r k + 1 x_{k+1}=x_k+2\sqrt{r_k*r_{k+1}} xk+1=xk+2rk∗rk+1 ，并由 x k + 1 x_{k+1} xk+1得到 l k + 1 = r 1 + x k + 1 + r k + 1 l_{k+1}=r_1+x_{k+1}+r_{k+1} lk+1=r1+xk+1+rk+1。时间复杂度为O(1)。 要计算代价函数，我们就要得到剩余圆的最小半径，这需要一趟遍历，时间复杂度为O(n)。 所以似乎每条路径上代价函数的计算不是O(n)而是O(n2)。
由于要求从1开始得到最大的连续邮资，显然必须得有一种面额为1的邮票，并且之后的面额肯定是递增的。 约束条件：下一种邮票面值肯定要比前一种大，所以 x i + 1 > x i x_{i+1} > x_i xi+1>xi，并且 x i + 1 x_{i+1} xi+1的值不能超过 r i + 1 r_i+1 ri+1,否则 r i + 1 r_i+1 ri+1的邮票没法支付，因为前i种邮票能贴出的最大面额是ri。因此xi+1的取值范围是：[xi+1, ri+1]。 y i ( j ) y_i(j) yi(j)表示的是使用至少一张面值为 x i x_i xi的邮票贴出值为j的邮资时所需要的最少邮票数。这句话有点绕，它的意思是你要用提供的邮票面值贴出邮资j，这样一般都有多种贴法，但是加了两个限制条件，一个是你必须使用至少一个面值为 x i x_i xi的邮票，另一个是你必须使用的邮票数最少。就好比要凑够100块钱你可以有很多种不同的钱币组合得到。但是现在要求用最少的钱币数目，那你大可直接掏出一张红色毛爷爷。但是现在又加了一个限制条件，你的钱款当中必须至少有一张10块的，这样的话，最少的钱币数就应该是10+20+20+50一共四张了。 设你在使用至少一张面值为 x i x_i xi的邮票贴邮资j时实际使用的面值为 x i x_i xi的邮票数为t，又因为你最多只能使用m张邮票，因此t的取值范围为1≤t≤m，当 x i x_i xi使用t张以后，剩余的邮资为 j − t ∗ x i j-t*x_i j−t∗xi，需要的最少邮票数为min_t，则 y i ( j ) = m i n { t + m i n _ t } y_i(j)=min\{t+min\_t\} yi(j)=min{t+min_t}，这里我有一个疑问，这个min_t为什么非得使用 x i − 1 x_{i-1} xi−1呢，按照我的理解这个式子不应该是这样的吗？ 剩余的邮资为什么一定还要用至少一个 x i − 1 x_{i-1} xi−1去凑呢，在某些情况下使用 x i − 1 x_{i-1} xi−1邮资根本就凑不出来。或者说有办法可以证明 y i − 2 , i − 3 , . . ( j − t ∗ x i ) y_{i-2,i-3,..}(j-t*x_i) yi−2,i−3,..(j−t∗xi)就一定会比 y i − 1 ( j − t ∗ x i ) y_{i-1}(j-t*x_i) yi−1(j−t∗xi)大呢？就是说如果使用了更大的面值去凑 j − t ∗ x i j-t*x_i j−t∗xi一定可以使用更少的邮票，这里似乎没有说明直接带过了。 这里接下一篇：分支限界算法2.
