分枝限界

什么是分枝-限界

分枝限界法是一个用途十分广泛的算法，运用这种算法的技巧性很强，不同类型的问题解法也各不相同。分枝限界法的基本思想是对有约束条件的最优化问题的所有可行解（数目有限）空间进行搜索。该算法在具体执行时，把全部可行的解空间不断分割为越来越小的子集（称为分支），并为每个子集内的解的值计算一个下界或上界（称为限界）。对凡是界限超出已知可行解值那些子集不再做进一步分支。

看完度娘的介绍，我们发现其实分枝-限界和回溯法很相似，都是加上限界条件进行剪枝从而加快搜索速度，但是仔细观察，发现分枝-限界对于子问题的求解与回溯法又有所差异，他是每次对一个子节点进行全部打开并分别对每次进行一个限界值得计算，然后每次都选择而最理想的值进行展开，这是与回溯法最大的区别，所以分支-限界一般是与bfs相关的题进行联系。

概念介绍

分枝

顾名思义，就是在一个节点称为E-节点以后（又叫做展开节点），要一次性展开他的所有子节点，并将这些子节点放在一个称为活结点表的数据结构中，从活结点表中的节点可以展开所有状态空间树的节点（说白了就是存储某一层的节点，然后在进行展开），即为广度优先搜索状态空间树。每次我们都是从这个活结点表中取出一个节点作为E节点进行展开，活结点表可以使用FIFO(First Input First Output，先进先出队列），LIFO（Last Input First Output,后进先出队列）或者优先级队列（设计权重的队列）进行表示。当使用优先级队列时必须对活结点表中的节点赋以一个权值。本次结合求解问题介绍使用优先级队列我分支-限界法。

任意节点的成本函数

定义状态空间树上任一节点x的成本函数c(x):如果x是可行的叶子节点，那么c(x)=cost(x)，如果x是中间可行节点，那么c(x)=从x展开状态空间树能得到的最小成本值（即以x为根节点的状态空间树展开后所能得到的最理想值，跟回溯法背包问题中的bound,回溯法最大团cn+n-i,回溯法旅行商中未走过的城市最短路径长度之和bestn的定义其实一样）。如果其子树无可行解，即没有解能满足条件，那么c(x)=∞。

LC-检索

LC-检索其实就是分支-限界法中具体实现每次选择最优节点进行展开的实现方法。即如果活结点表中每个节点都以c(x)为权值，则每次都从活结点表中取最小权值节点（即优先级最高的节点或者情况最理想的节点）作为E-节点，则算法就能够很快找到最优解。虽然可能展开x前我们不知道c(x)的值，但是有可能从历史信息中获得c(x)的某一个下界c*(x)，即c(x)随着具体的展开是会变化的，逐渐趋近于真实值，从回溯法背包问题中bound逐渐变小趋近于具体解所对应的效益值情况是类似的。每次以c(x)的下界c*(x)作为活结点表中节点的权值，每次都去有最小c*(x)的节点（即拥有最理想情况解）的节点作为E-节点进行展开。特殊地，根据这种检索方法，对于可行叶子节点z，会有c*(z)=c(z)=cost(z),即此时成本函数值=成本函数值下界=真实值。

限界方法

那么什么时候会触发限界函数切换E-节点呢，此时我们需要设计一个限界函数来判断此时的节点不再是具有最优成本函数值的节点，从而根据活结点表切换E-节点，这个判断方法如下：每次我们都根据活结点表中记录最优成本值为U，对于正在展开的节点E-节点，当其展开某个子节点x时，如果该子节点x的c(x)>=U,我们就停止展开此子节点，即不将其放入活节点表（因此我们也不难看出，新加入活结点表的值一定是更优的相较于之前的节点），然后此时我们并不是一定要回溯到父节点，这里适合回溯法最大的区别，而是切换到U所对应的节点进行展开，如果展开的新子节点的c(x)<U,则更新U且将这个节点加入活结点表中，并且此时不是立刻切换E-节点为此新子节点，而是继续展开当前的E-节点直至其为一个死节点然后从活结点表中移除该E-节点，然后在切换至U所对应的节点。所以每一次都有U=min{U,cost(x)}。

伪代码

E=T，U=∞
    //将活结点表初始化为空
    while(true){
        for E的每个子节点x注意检验
        //得到一组可行解
        if(x是叶子节点){
            //更新U，此时cost(x)=c(x)
            U=min{U,cost(x)};
        }
        if(c*(x)<U){
            //加入活节点表
            Add(x);
            //此时继续展开其父节点
            parent(x)=E;
        }
        if(E=NULL){
            //活节点表为空，算法结束
            //能尝试展开的都尝试完了
            return;
        }
        delete(E);
        if(c*(E)>=U){
            //剩下的所有活结点表的最优值都大于已知的最优值U
            //算法结束
            return;
        }
    }

在上面的伪代码中，算法结束时，如果c*(E)>=U,即活结点表中其他节点x的下界也满足c*(x)>=c*(E)>=U,则展开这些活结点也不能产生更好的解了，所以算法结束时U就是优化值。（c*(x)表示x节点成本值得下界，c*(E)是活结点表中的所有点中成本值的下界，U就是已知的最优值，很好理解上面我的不等式，对于一个新的子节点x，他的可能最优值可能比活结点表中的下界值还要大，但是如果此时他就是产生最优值的节点，那么此时他进入或节点表后活节点表的成本值下界就会和他的成本值下界相等，所以c*(x)>=c*(E)，又因为U是在已知活结点表中的成本值中选取最小值为其自身值，所以c*(E)>=U)。

经典例题精讲

带截止期的作业调度问题

n个作业，1台处理机，每个作业i对应一个三元组（pi,di,ti)。pi是罚款额即不做的罚款值，di是截止日期，ti是需要的处理机时间。求可行的作业子集J，使得罚款额Σpj最小，其中j为不在J中的作业。

我们定义元组表示作业子集：(x1,x2,…,xn)，表示第i个任务是否做，1表示做，0表示不做。下界c*(x)可表示为展开到x时已得到的罚款额。

例如4个作业的三元组{(5,1,1),(10,3,2),(6,2,1),(3,1,1)}对于每个E-节点x都快速计算一个可行解，并以该可行解的成本值，记为u(x)，修改U的值，如下：

是题的状态空间树展开过程，接下来我们就具体分析一下，首先节点1代表讨论第一个任务是否做，此时相当于还没有不做的，所以此时罚款额为0，然后对1进行全扩展，即一直把1展开到死节点位置，这里有两个选择做或者不做1，所以2节点是做，3节点是不做，但是3节点不做作业1时罚款额为5，此时比较发现2节点罚款额小，所以优先2节点，2节点同样展开为4和5，此时5节点的罚款额为10,4节点罚款额还是最小的为0，继续展开4节点，但是此时，发现选择了作业1和作业2后，不能选择作业3了，放不下了，所以只能扩展右子树的节点6，此时6罚款额为6，此时，很重，活结点表中有{3,5,6}三个活结点，LC-检索每次都会优先展开最优的节点，此时6不是最优节点了而3是最右节点了，所以跳转开始展开3节点，此时对3进行展开，左右全都可以展开得到7和8，然后3成为死节点，从活结点表中移除，是7节点罚款额为5,8节点罚款额为15，所以继续展开7节点为9和10,9节点罚款额仍是最小的，所以继续展开节点9，但是选择了作业2和作业3后，作业4放不下了，所以9节点只能展开右子树，得节点11，罚款额为8，此时到达了叶子节点，得到了一组解为[0,1,1,0]，罚款额为8，但是此时活结点表中还有{6,8,10}发现8,10两个节点不用继续展开罚款额都已经大过U=8了，所以不展开8,10,而6罚款额为6，比8小，此时对节点6进行展开，但是发现作业1和作业2选择以后作业4放不下了，所以只能展开右子树得节点12，罚款额为9>U,然后将节点6从活结点表中移除，此时活结点表中还有{8,10}，但是此时都已知比U大了，所以此时处于伪代码中的最后一种情况了，算法结束，得到了最优解就是[0,1,1,0]。

思考：分支-限界法是怎样加快搜索速度的？

我们发现在分支限界法中，虽然没有向回溯法一样回到父节点，但是他这种每次都跳跃到最理想的节点继续展开，最终就会实现得到最优解且上图中3个节点处都进行了剪枝，从此加快了搜索速度

思考：回溯法和分支-限界法有什么思路上的区别吗？

有，我们可以两种方法看成是两种人，回溯法就像是一位着眼全局谨慎的人，做任何事（展开子树）前都会先顾后（查看后面是否会出现比已知更好的结果来进行限界判断)来避免进行一些不必要的扩展。而分支-限界更像是一位着眼于现在和已知的历史信息的人，他在每次做事情后都会记录下相应的信息，以便在进行后面的事情（展开子树）时根据现在的情况和历史信息进行对比判断（瞻前），一旦发现自己不再处于最优解的扩展路径上，就马上离开着手于更好的情况。但是归根结底两者都是进行了剪枝策略，避免了没有必要的扩展，从而加快了搜索速度，并且注意，两者无优劣之分，只是对于不同的问题各有偏向（dfs/bfs)。

当然，空间扩展书我们也可以使用M叉树实现，如下：

两个树都可以，但是后者虽然省略了层数，但是不同节点分分枝数不太好进行统计判断。对于上面这种数展开，方法类似，我只给出数据请自行推理：

最大团问题

最大团的有关概念就不介绍了，请查看本篇博客：《回溯算法》这里我们在采用分支限界的方法进行求解。在分枝-限界法中，通常是使用广度优先搜索并且以最小消耗优先的方式解状态空间树。对于下图：

我们在使用分枝-限界法解决上面G的最大团问题之前，先考虑一下具体怎么实现，我们知道分枝-限界主要的限界方法就是设立几个条件，只有符合条件的节点才能进入活结点表，然后每次展开时都是展开活结点表的最优节点，这样不满条件即无法进入活结点表的节点也就被剪枝了，这就是分枝-限界的策略，所以我们需要寻找几个条件进行剪枝，首先我们可以很容易知道一个条件即想展开左子树需要左子节点和已知的团中所有节点相连，而对于所有节点只有满足cn+un>bestn(cn是当前已经选择的节点数，un是当前cn和n-t的和，n-t是剩余所有未选择节点的数，所以un即为可能产生的最大贪心效益团，bestn是当前已知的最大团的最优团数)，un=cn+n-t，所以只有满足已经选择的节点数和所有未选节点数之和比bestn大的才有可能继续产生更大团，所以只有满足cn+n-t的节点才能进入活结点表，接下来就是每次展开时都选择活结点表中的最优节点进行展开，我们知道对于0/1背包问题中我们每次选择的都是具有最大贪心效益值的节点进行展开，而对于最大团问题我们每次都选取活结点表中un最大的节点，但是难免会产生un相等的活结点表节点，此时根据不同的方法我们对状态空间树进行展开并对比两个策略的优劣。为了方便起见，我们将上图中G中的1,2,3,4,5用A,B,C,D,E代替：

策略1：un>bestn&&FIFO队列

此时活结点表使用FIFO队列即先进先出，所以当面对un相同的节点，我们选择最先到的节点，当然节点还是要满足un从大到小排列的。那么状态空间树如下：

我们来一步步推导一下，其中括号包裹的是按顺序排列的活结点表，每次都选取队首节点（因为队首节点就是最优节点）,并且我们可以看出n-t表示的就是剩余节点数量且每一层都讨论的是某一个节点在不同情况下的选取情况，例如第一层表示的就是A的选取情况，第4层表示的就是D的选取情况。第零层根节点表示还没有选择节点，所以第零层的cn=0,un=5,此时还没有选择节点，所以已知最有团大小就是bestn=0。

首先根节点表示还没选择节点呢，所以bestn=0，此时左右分别讨论是否选择A得到两个节点1,2并且1此时的un=5不变，cn=1，2的un=4,cn=0，都满足cn>bestn,所以都插入节点表，并且此时更新bestn=1,虽然我们知道此时还没有形成团（但是可以特殊地看成是1个团大小为1的团），活结点表为（1,2）
取1(此时1一定被展开成死节点，所以就不在活结点表中了），发现选A以后B可选可不选，所以同样左右展开的3和4,3的cn=2,un=5,4的cn=1,un=4,bestn=2,都可以插入活结点表，活结点表为(3,2,4)，虽然3比2来的晚，但是3的un更大，所以排在2前面，而4和2的un相同此时采取FIFO策略，2来的早所以2在前面。
取3(此时3一定被展开成死节点，所以就不在活结点表中了），发现此时选取了A,B不能选C，因为C和A不相连，所以3只能右展开得5，此时cn=2,un=4满足un>bestn5加入活结点表，此时活结点表为(2,4,5)
取2(此时2一定被展开成死节点，所以就不在活结点表中了），2左右展开均可以得节点节点6,7，6的cn=1,un=4,7的cn=0,un=3，均可以进活结点表，活结点表为(4,5,6,7)
取4(此时4一定被展开成死节点，所以就不在活结点表中了），只能右展得节点8,cn=1,un=3，活结点表为(5,6,7,8)
取5(此时5一定被展开成死节点，所以就不在活结点表中了），只能右展得9加入活结点表，活结点表为(6,7,8,9)
取6(此时6一定被展开成死节点，所以就不在活结点表中了），6左右展均可以，得到10,11,10的cn=2,un=4,11的cn=1,un=3，所以加入活结点表，活结点表为(10,6,7,8,9,11),10在最前面是由于un最大。
取10(此时10一定被展开成死节点，所以就不在活结点表中了）,10只能右展得到12，cn=2,un=3此时加入活结点表,活结点表为(7,8,9,11,12)
取7(此时7一定被展开成死节点，所以就不在活结点表中了），7左右展均可以，得到13和14,13的cn=1,un=3,14的cn=2,un=2，所以此时只有13加入活节点表，因为14的un=2==bestn=2，不大于所以剪枝不用再加入活结点表中讨论了。活结点表为(8,9,11,12,13)
取8(此时8一定被展开成死节点，所以就不在活结点表中了），8左右展均可以，得到15,16,15的cn=2,un=3,16的cn=1,un=2,所以只有15加入活结点表，活结点表为(9,11,12,13,15)
取9(此时9一定被展开成死节点，所以就不在活结点表中了），9左右展开均可以得到17和18，17的cn3,un=3,18的un=2,cn=2,此时发现已经到达叶节点了即当cn=un时就是叶子节点了，所以已经找到了最优解，及时在展开其他情况也只是得到不大于此时解的情况，所以此时的解就是一组最优解了，最大团数为bestn=cn=3,之所以不是18节点是因为17的情况更好，所以算法结束啦，最终就是最大团数为3，最优解为[1,1,0,0,1]即{A,B,E}，当然如果你继续展开要全部展开的话也可以，最终还会得到两组解为{B,C,E}和{A,D,E}但是并不会改变bestn的值了，所以剩下的活结点表节点销毁即可。

思考：有没有可以优化的地方？

仔细观察，我们会发现在出现类似于2,5这种un相同的情况时采取的是FIFO策略存储，所以接下来是展开来的更早的节点，但是按照正常思维来说，我们考虑一下2和5,2节点表示此事还一个节点没选但是最好的可能情况为4，而节点5表示的是在已经选择了两个节点情况下最好的可能情况为4即5节点最好情况和2相同的情况下还保证了最差的情况为至少能得到大小为2的团，而节点2不排除得到大小为1或者0的团，所以按常理来说5比2更好，所以应该是展开5，所以在活结点表中我们应该将5放在2前面，所以我们采取一种大顶堆策略来实现活结点表存储，即每次都按照un从大到小排列的同时，当un相同时cn更大的排在前面。这样就得到了策略2

策略2：un>bestn&&大顶堆

此时就是在un从大到小排序的同时，un相等的情况使用cn更大的节点排在前面的策略来存储，确实步数更少了所以也就优化了搜索效率，具体步骤如下：

首先根节点表示还没选择节点呢，所以bestn=0，此时左右分别讨论是否选择A得到两个节点1,2并且1此时的un=5不变，cn=1，2的un=4,cn=0，都满足cn>bestn,所以都插入节点表，并且此时更新bestn=1,虽然我们知道此时还没有形成团（但是可以特殊地看成是1个团大小为1的团），活结点表为（1,2）
取1(此时1一定被展开成死节点，所以就不在活结点表中了），发现选A以后B可选可不选，所以同样左右展开的3和4,3的cn=2,un=5,4的cn=1,un=4,bestn=2,都可以插入活结点表，活结点表为(3,2,4)，虽然3比2来的晚，但是3的un更大，所以排在2前面，而4和2的un相等，此时cn大的排在前面，所以活节点表为(3,4,2)
取3(此时3一定被展开成死节点，所以就不在活结点表中了），只能右展得节点5,cn=2,un=4,所以5放入活节点表并且因为5比4更好，所以5直接插入到4前面，活节点表为(5,4,2)
取5(此时5一定被展开成死节点，所以就不在活结点表中了），只能右展得到节点6，cn=2,un=3,所以放入活节点表中，活结点表为(4,2,6)
取4(此时4一定被展开成死节点，所以就不在活结点表中了），只能右展得到节点7，cn=1,un=3，所以放入活结点表且7放在6的后面此时活结点表为(2,6,7)
取2(此时2一定被展开成死节点，所以就不在活结点表中了），左右均可展开得到8,9，8的cn=1，un=4,9的cn=0,un=3,所以8放入活结点表头因为他的un最大，而9在最末端因为un=3且cn=0最小，所以活结点表为(8,6,7,9)
取8(此时8一定被展开成死节点，所以就不在活结点表中了），8左右均可展开，所以得到10和11,10的cn=2,un=4,11的cn=1,un=3,所以10放在最前面因为un最大，而11放在7前面，我们发现此时出现了更为特殊地情况即11和7的cn和un均相等，此时可以采取两种策略，第一种就是FIFO，先到先出，这样可以，但是还有一种策略就是将11插入到7前面因为既然11和7的情况完全相同那么我们就继续选择最近完成的情况11进行展开。活结点表为(10,6,11,7,9)
取10(此时10一定被展开成死节点，所以就不在活结点表中了），10只能右展得到12，此时发现又出现特殊情况12和6的情况完全相同，我们还是采取不切换的策略所以活结点表为(12,6,11,7,9)
取12(此时12一定被展开成死节点，所以就不在活结点表中了），左右展开得到13和14并且此时13和14是cn=un所以到达了叶子节点，所以13就是最优解，最大团数为3,解为[0,1,1,0,1]即为{B,C,E},此时也是继续展开肯能还会得到其他团为3的解，但是总体看来最大团数不会再发生改变就是3，所以活结点表中剩余节点销毁即可，算法结束。

思考：对于cn和un都相等的情况使用FIFO是否更好？

事实是使用FIFO策略更好，因为这样好实现功能，所以我们对上面的进行小更改，此时按照FIFO策略

取8(此时8一定被展开成死节点，所以就不在活结点表中了），8左右均可展开，所以得到10和11,10的cn=2,un=4,11的cn=1,un=3,所以10放在最前面因为un最大，而11放在7前面，我们发现此时出现了更为特殊地情况即11和7的cn和un均相等，此时可以采取两种策略，第一种就是FIFO，先到先出，此时我们就采取FIFO策略，所以11在7的后面9的前面，所以活结点表为(10,6,7,11,9)
取10(此时10一定被展开成死节点，所以就不在活结点表中了），10只能右展得到12，此时发现又出现特殊情况12和6的情况完全相同，我们采取FIFO策略所以活结点表为(6,12,11,7,9)
取6(此时6一定被展开成死节点，所以就不在活结点表中了），左右展开得到13和14并且此时13和14是cn=un所以到达了叶子节点，所以13就是最优解，最大团数为3,解为[1,1,0,0,1]即为{A,B,E},此时也是继续展开肯能还会得到其他团为3的解，但是总体看来最大团数不会再发生改变就是3，所以活结点表中剩余节点销毁即可，算法结束。

所以按照上面的步骤并没有产生对速度的影响而功能实现起来更简单了，最终空间树如下：

所以最终我们发现最好的策略就是un>best&&使用大顶堆&&对于cn，un相等的情况采用FIFO的搜索效率最快且实现也较为简单。

思考：分枝-限界和回溯的区别？

其实我们在回溯法里已经做过对比了，这里在温习一下，回溯法就是每次都尽量走能取得更好情况的左展（这里有一个左展限界），用时也要进行回溯讨论能否右展（右展限界）最终是得到许多可能产生最优情况的解再对比这多组解得到最优解。而分枝-限界就是一次性左右展都展开（如果有特别需要左右展有限界条件）同时对于每一个节点（无论是左展还是右展）都要用一个限界条件来判断是否可以加入活结点表，只有能够满足条件进入活结点表的节点才有被展开的资格，然后每次展开时都是选取活结点表队首元素即当下能产生最好情况的节点进行展开，最终得到的解就是最优解。无优劣之分，不一定每次分枝-限界都比回溯法搜索效率高。

货担郎问题（旅行商问题TSP）

就是卖货郎要每个城市只能路过一边且最终回到出发城市的最短路径。这里我们也可以使用分枝-限界的方法，进行计算，但是这里使用的是一种无向图权重题求成本函数特有的方法求得成本函数值下界的方法，叫做归约矩阵和归约数的东西。我知道他不太好理解，你一定会问为什么这样算，有没有什么依据，答案肯定是有依据的，只是很难理解，我不会😅。这里有一句话说得好呀：

别试着理解它，感受它 --《信条》by诺兰

所以这里我只介绍方法，反正能解题就行了，如果你也像本博主一样菜鸡，不想知道为什么，那就一来看看求解方法吧！

我们已经归约矩阵和归约数来求解c(x)，首先我们看一下定义：

什么是归约矩阵？

每行每列均含有0的矩阵就是归约矩阵，简单来说，就是无论是以行的视角去看矩阵，还是以列的视角去看矩阵，我们都要保证这个矩阵在每一行或每一列都含有0。但是特殊地，如果某一行或者某一列全是∞也可以。

什么是行归约矩阵，什么是列归约矩阵？

顾名思义，只满足行条件的就是行归约矩阵，只满足列的就是列归约矩阵。

怎样将一个矩阵变为归约矩阵？

对于一个矩阵，如果某一行没有或者某一列没有0，则就对这一行或者这一列减去最小的数（并且这个数肯定是非零的且不是∞,否则这一行就满足了归约条件）。

什么是矩阵行归约数，什么是矩阵列归约数？

对于每一行，将进行过归约的行所减去的数求和就是行归约数。对于每一列，将进行过归约的列所减去的数求和就是列归约数。

什么是矩阵归约数？

矩阵归约数就是矩阵行归约数+矩阵列归约数。

什么是节点归约矩阵

就是对于归约矩阵，如果是节点i到节点j的归约矩阵，则将第i行和第j列全部数值改为∞，还要将(j,i)改为∞，如果此时还满足是一个归约矩阵的话，那么他就是从i到j的归约矩阵。如果不是我们暂称为节点矩阵。

什么是节点行归约数，什么是节点列归约数？

对于节点矩阵，如果变换以后不满足是一个归约矩阵的条件了，那么需要对它进行规约化，那么相应的行归约数和列归约数就叫做节点行归约数，节点列归约数。

什么是节点归约数

就是节点行归约数+节点列归约数。

然后我们在看一下c(x)和归约数以及归约矩阵的关系。对于某个节点S如果其父节点为R，则就是从R到S的一条路径，那么c(S)=c®+A(i,j)+r,其中c®就是其父节点R的成本函数值，A（i,j)就是其父节点R的节点归约矩阵中从R到S的数值（R,S）,r就是S节点归约矩阵的节点归约数。特殊地，要记住，节点1即根节点的节点归约矩阵就是归约矩阵，其节点归约数就是归约数。

可能你已经看蒙了，没事，我们以一道例题来讲解。

例题

这是城市之间的关系，因为无论从哪里出发最终都是绕一圈回来，所以起点不影响最终结果，所以我们就以1位起点城市开始。

那么首先我们写出城市间的邻接矩阵如下：

不直接相连的城市距离设置为∞，然后发现并不是归约矩阵，所以先归约化。首线先进行行归约化：

因为每一行都不满足行归约条件，所以每一行都要进行归约化，即都要减去最小的数，则每行分别减去了{10,2,2,3,4}，所以行归约数就是10+2+2+3+4=21。然后发现第一列和第三列不满足列归约条件，所以这两列进行规约化，分别减去{1,3}，如下图;

此时已经变成了归约矩阵（同时也是1节点归约矩阵），所以归约数为21+4=25，并且特殊地根节点即1节点的节点归约矩阵也是这个，且节点1即根节点的节点归约数=归约数=25。所以c(1)=25。此时我们展开状态空间树节点1，按照分枝-限界的思路，先将1节点全部打开直至为死节点，所以1节点（代表从1出发，那么肯定已经过了城市1了）展开出2,3,4，5三个节点分别代表出发去这四个城市。那么我们也要分别计算c(2),c(3),c(4),c(5)并将节点2,3,4,5加入到活结点表中。我们先计算c(2),首先按照前面的定义，先写出从1到2的节点矩阵，即将第一行和第二列全部置为∞，然后还要讲(2,1)改为∞，此时矩阵变成：

啊哈，好巧不巧，他直接就是一个归约矩阵，太nice了😋，省去了归约化得过程，那么我们接下来就求解以下c(2),首先c(2)=c(1)+A(1,2)+r(2),此时c(1)=1节点归约数=归约数=25，A(1,2)表示为1的归约矩阵中从1到2的数值查表为10，且此时因为2节点矩阵直接就是节点归约矩阵了，不需要归约化，所以此时r(2)=0。所以c(2)=25+10+0=35。然后我们在计算一个没有那么巧合的c(3)，此时我们需要将归约矩阵的第一行和第三列置为∞，且把(3,1)改为∞，此时变成了3节点矩阵：

我们发现他并不是恰好为一个节点归约矩阵，所以我们先要对它进行归约化，所以发现行全部满足归约条件，对于列第一列不满足，所以第一列归约化，减去11，所以列归约化以后：

此时变成了3节点归约矩阵了，且节点归约数为11，所以此时c(3)=c(1)+A(1,3)+r(3)=25+17+11=53。c(4)也是类似，这样算，所以空间展开书就是如下：

c(4)=25，c(5)=31,根据分支-限界思路，我们选择最优情况进行展开，所以展开节点4有6,7,8三个点代表去{2,3,5}三个城市，同样我们需要计算c(6),c(7),c(8)，但是这里要尤为注意，此时计算时c(6)=c(4)+A(4,6)+r(6),表示的是用城市4的节点归约数11，和A(4,6)为在城市4的节点归约矩阵上查找(4,6)的值，并且还需要计算r(6)的值，这个就需要计算6的节点归约矩阵了，此时需要在归约矩阵上将第4行和第2列置为∞和(2,4)置为∞，在归约求解归约数。最终一直算下去就得到了节点11，此时为28意味着具体额优化开销为28，所以最优解就是1->4->2->5->3->1,开销只需要28，图貌似有点不太对，忘了标出5城市了，没关系，反正我们知道怎么计算就好了。如果没明白，可以多看看或者留言哦~

小作业

Questions

对以下最小罚款额调度问题的实例：(10,3,2),(3,4,2),(8,2,1),(6,3,1)利用分枝-限界法求解，要求：写出限界条件，划出展开的部分状态空间树
对以下0/1背包问题的实例：n=4,c=7,w=[3,5,2,1],p=[9,10,7,4]利用分枝-限界法求解，要求：写出限界条件，划出展开的部分状态空间树

Answers

总结

那么本次分枝-限界方法我们了解到了他总是伴随bfs出现，并且每次都要计算c(x)来记录随时切换到最理想的情况进行求解，最终即可同时得到最优值和最优解，所以其根本难点在于计算c(x)，对于罚款额，背包等一般问题我们按照正常思维（每次寻找最少罚款额，每次选取效益值大的情况）即可写出c(x）计算式，对于这种货担郎复杂的图论问题，则需要归约矩阵进行计算c(x)了，那么本次分享就到此为止啦，希望你能有所收获😎！