回溯算法

什么是回溯

根据度娘的解读，我们不难理解回溯法就是与人类正常思维相契合的枚举搜索方法，对于每一个交叉十字路口都是尝试所有可能的理想情况，当都尝试完后再回到上一个交叉口进行试，所以回溯法也常常与深度优先搜索dfs相关，但是我们要注意并不是要尝试所有情况，而是可能产生更好结果的情况，对于已知不理想的情况则直接避开，所以这也是回溯法相较于直接暴力枚举有所优化时间复杂度的不同之处。

典型例题精讲

8皇后问题

在8×8的棋盘上放置8个皇后，使得这8个皇后不在同一行、同一列以及同一斜角线上，如下图

这是一道典型的dfs题，这里我们主要是讨论对齐优化，即回溯减少时间开销。在解题之前我们先看几个概念：

什么是解空间？

8皇后问题的解可以表示为一个8-(x1,x2,…x8)的元组，其中xi是放在第i行的皇后所在的列号，则8皇后为题就可以形式化为在8^8个8元组解中找到满足题干条件的解，这8^8个8元组解构成的集合就成为8皇后问题的解空间即搜索范围。如果我们将约数条件之一即任意两个皇后不能再同一列上时，则解空间大幅缩小到8!个元组。不同的算法设计会产生不同的解空间，但是我们的目的永远是用尽可能少的约束条件来大幅缩减解空间从而加快搜索，这里我们使用xi时就已经限制了皇后不可能在同一行或同一列了，所以唯一可能不符合的情况只会是由于出现了同一斜角线产生，这样我们就大幅缩小了解空间。

什么是状态空间树？

任何算法都可以用建立在解空间上的状态空间树加以描述。状态空间树是我们尝试选择元组的各个分量时产生的结构，及每一个从根节点出发直至叶子节点的树枝都代表一种情况，每一个中间节点都会对应几个选择即代表对于不同情况的选择。搜索算法并不是事先将状态空间树存储在计算机内在进行遍历，而是通过不断的尝试来展开状态空间树找到所求的解，而回溯法，分支-限界法等就是利用一种启发式的限界条件剪掉状态空间树上的某些没必要的分枝即不用走就知道不可能得到更好解的情况，使得搜索算法在展开时只展开空间树的一部分，从而降低了搜索算法的时间和空间复杂度。

接下来我们就来分析一下8皇后问题，这里为了普适性，我们推广为n皇后问题，所以解空间为n元组啦，并且有n!个情况，状态空间互有两种，一种是每次只讨论本节点是否选取的二叉树结构（即0-1结构），还有一种就是符合人类思维，每次分叉点代表写一个可以选取的节点，即m叉树。如下：

第一种：

第二种：

其中无好坏之分，只是后者空间复杂度会略小，但是同时也不好构建代码逻辑，树上节点的数字代表执行的顺序。下面我们在定义一下不同节点的术语：

什么是状态空间树术语？

状态空间树的每个节点代表问题求解过程中达到的一个状态，根节点到他的路径代表对一些分量已作出的选择，状态空间树的所有节点构成的集合称为求解该问题的状态空间。

• 每一个中间节点X都代表一个面临选择的问题，所以称为问题节点
• 对于叶子节点S，若从根节点出发到节点S可以确定为解空间的一个元组解，则S节点称为解节点
• 如果解节点S(实际上代表的是一个从根节点到S的元组解)满足约束条件，则为答案节点
• 若已展开了空间树部分子节点，但是还没有将子节点完全展开，即中间节点，则称为活结点
• 被限界无法在展开或者已全部展开的子节点称为死节点
• 当前正在展开子节点的活结点称为E-节点

举例来看，上图中的2节点，他有三个选择可选(即3,8,13），所以2节点是一个问题节点，1->2->3已经走完了，所以3就是一个解节点，如果还刚好满足条件约束则3就是一个答案节点，在看如果此时2只是展开了3，接下来该展开8了，所以2是一个活结点因为他还可以继续展开，再看此时正在展开8(即8有两个选择)，所以此时8既是问题节点又是E-节点，当8节点走完9,11两种情况后发现没有可展开的了，则8就成为了死节点。接下来返回到2,2继续展开13，所以此时13又变成了E-节点，此时2变成了死节点。

仔细回想我们发现上面这种展开方法其实就是深度优先搜索，即: 一个E-结点展开自己的一个子结点后, 就让该子结点成为E-结点的展开方法(相当于对状态空间树做深度优先搜索), 称为深度优先展开方法。而回溯法也通常就是在深度优先搜索方法上加上限制条件来加快搜索速度，那么分支-限界则刚好相反，他是经常伴随广度优先搜索出现，即一个结点一旦成为E-结点则它将展开其全部子节点, 之后自己变成死结点. 这样的展开状态空间树的方法成为广度优先搜索，而分支-限界就是加上了限制条件从而加快搜索速度。

什么是限制条件（限界）？

综上所述，我们无论是回溯还是分支限界都是要在dfs或者bfs上加以限界，这个限界函数就是在每次展开这个子节点之前先进行预估计算判断是否可以得到一个比已知答案解更好的答案节点，当不能得到是就返回true，此时就会停止展开这个子节点(即限界或者"kill子节点")。从而加快了搜索，此时面对限界函数返还的true信息两种不同的放法进行不同的策略，回溯法就是一直回退到还可以进行展开的父节点处，而分支-限界就是回退到已知可能还会得到更好解的节点进行展开（本章不细讲此方法）。

解题思路

对于n皇后问题我们采用此种策略，即每次先对第i行的皇后分配列数然后将不可能的取值点进行标记，然后在选下一行的皇后i+1的列数，入过此时发现无法放置，则说明上一个皇后放置的位置不妥当，此时我们回退到第i个皇后放置的问题上，选择放置其他列数位置，如果没有可选的了，则继续回退到第i-1个皇后更改，按照此方法即可快速搜索。具体实现参考本视频：N皇后问题

子集和数的问题

给定n个正数w(i)和另一个正数M，找出{w(i)，i=1,2,3…,n}中所有使得和数等于M的子集。

这里我们可以思考每次展开这个子节点前先思考对于这个节点K是否有前面所有已选择的数的和+k节点后面所有数的总和值是否能够>=M，如果不能，则Kill掉次子节点不再展开，因为已知最大和值都已经不可能等于M了，则就没有必要展开了，限界函数表达如下:其中X(i)表示取1表示选择，取0表示不选择

$$if\sum_{i=1}^{k}{W(i)X(i)}+\sum_{i=k+1}^{n}{W(i)}<M$$

后面一项没有乘X(i)是因为默认就是全部选择所以全部乘1，就没必要写了，然后表达式设置为小于是因为只有满足次条件是才应该返还true值从而Kill子节点。符合限界函数的定义要求。

最大子集和数的问题

找到不超过M的和数最大的子集。

最大子集和数的问题其实可以看做是效益值等于质量的特殊0/1背包问题，这里我们讨论一种更特殊的情况，即如果已知数是以一种非降序的方式排列给出的，那么我们进一步可以限界条件强化为当已选数的和值小于M且再加上下面一个数就超过了M值，则就不用了展开次子节点了，限界条件如下：

$$if(\sum_{i=1}^{k}{W(i)X(i)}<M\&\&\sum_{i=1}^{k}{W(i)X(i)}+W(i+1)>M)$$

此时如果返回true就限界kill此子节点，因为W(i+1)必定是后面的数中最小的了，加上都大于M了，则此时后面无论再选什么数W，都一定超过M了。

0/1背包问题

0/1背包问题此时我们也需要找到一个限界条件，此时我们先对背包的物品和效益值计算效益密度，按照效益密度重新排列，然后注意，此时我们这里要做的不是逐一尝试，而是将其看成连续背包问题来计算最大效益值，即即使装不下我们也要拿效益密度最大的进行填充来计算出最理想效益密度值bestp，而限界条件就是拿每次的最大贪心解bound来和bestp相比较，如果bound<=bestp,就不展开，一句话就是每次我都尽量多拿，如果大了我们在回退考虑不拿某个物体的情况，所以回溯虽然可以省略某些不必要的情况，但是我们还是计算出来了所有可能取得答案解的情况。

下面我们举一道例题来进行对比：考察一个背包例子，n=4,c=7,p=[9,10,7,4],w=[3,5,2,1]，按密度排列为(4,3,1,2)，w=[1,2,3,5],p=[4,7,9,10]

我们用回溯法求解，首先先进行效益密度重排列，题干已完成，然后我们直接求解最理想效益值bound=4+7+9+2*(7-1-2-3)=22,所以最理想效益值为22。接下来开始展开空间树，其中节点序号代表执行顺序，则回溯法展开时如下：(bound为可能取得的最大贪心效益值，bestp为已知取得的最大贪心效益值)，图中的判断式去掉等于号

我们仔细观察上图，发现对于第一个效益密度值最大的物体(即物体4)（来到了节点1），我们假设拿，则此时在已经拿了物体4以后的最大贪心效益值为bestp=4+7+9+2*(7-1-2-3)还是22，所以没有大于bound继续展开左子树，即继续假设拿（来到了节点2），此时第二大效益密度值得物体3，我们发现可以拿，则拿此时再重新计算最大贪心效益值，还是22，所以继续展开左子树，来到节点3讨论是否拿第三大效益密度值得物体1，发现可以拿，则继续拿，此时最大贪心效益密度还是22，所以继续展开左子树，来到了节点4，此时讨论是否拿第四大效益密度值物体2（其实就是最好一个拿不拿），按照bound和bestp的计算，我们都是假设拿不了了就尽量填充，但是实际上只能选择拿或者不拿，所以此时不足以放下物体2，所以就不拿了，此时就来到了5节点（因为4左子树不能展开，所以就只能展开右子树），此时bestp=20，更新bestp=20，所以我们回溯到上一个父节点4，发现也展开完了，继续回溯至节点3，发现此时可以展开右子树，即讨论拿不拿物体1，此时我们假设不拿，则最大贪心效益值bound为4+7+0+2*（7-1-2)=19发现不拿物体1时，最大贪心效益值为bound=19<bestp=20，所以不再展开子节点6（因为已知不拿物品1的话最大效益值都已经到不了已知最大效益值20了,触发限界函数），而是继续回溯到了节点2，发现可以尝试展开右子树，即不拿物品3，此时做大贪心效益值bound=4+0+9+2*(7-1-3)=19<bestp=20,所以不再展开节点7（因为已知不可能得到比已知最大效益值20更好的结果了,触发限界函数），在回溯至节点1展开右子树，发现bound=0+7+9+2*(7-2-3)=20（来到了节点8)。

哎嘿😆，此时发现出现了两个情况最大贪心解都是20：

你说巧不巧，难不成这两种情况都可以吗？有这种可能，但是记住一般做题是不可能滴，仔细想一想这两个20的意义一样吗？其实我们发现这两个20可是意义不一样滴！左下角的20仔细回想一下是用bound=22推出来的，最后推出来具体的元组解效益值为20，也就是具体可以理解为这个bound的意思是可能取得的最最最好的情况也，但是可能具体解出来后会小于这个值，而现在左下角的20就是根据最好的情况为22最终推出来了效益值为20的解，那么现在右上角的那个bound=20就说明元组解的效益值一定为20吗？那可不一定，只是代表不拿物品4，最最好的情况是20，此时bestp不大于bound=20所以可以展开，我们要接着展开节点8继续讨论最终的具体元组解效益值能不能得20，我们再回想一下，这个bound=20是怎么得来的，是bound=0+7+9+2*(7-2-3)=20，也就是不拿物品4，拿了物品3,1，最后的物品2没有全拿，而是只拿了一部分来尽量填充背包才取得的20，但是物品2具体看要么不拿要么拿，所以c=2的情况下不能容纳下物体2，所以最终展开节点8的结果就是具体解的效益值根本就取不到20，而是16，所以最终的解只有一个，就是左下角这种情况了，即取物品4,3,1,不区物品2，最大效益值就是20，元组解为[1,0,1,1]。那么仔细回想一下：我们到底在哪里省略了展开从而加快了搜索呢？

反思：具体加快搜索怎样实现的？

我们对比一下dfs的步骤，你就会发现在节点6,7处我们都没有再次展开，这里可是省略了许多步骤呢😲！而我们付出的代价仅仅是每次计算一下最大贪心解执行一下限界判断而已，为此我们可是少进行了以下8个节点（即8中情况）的讨论呢！这就是加快搜索的原理。

反思：能否进一步再优化

其实看一下我们发现我们只是先得到了一种最优效益值解bestp，然后拿着这个解又与其他的情况bound逐一判断来寻找可能更好的解，将其他情况bound全部比较认定为不是比已知刚好的情况后pass掉了其他可能情况最后间接的就证明了bestp这个是最好的解了，那么我们有没有一种不用讨论其他最好情况bound，就只求出一组解就直接可以断定他是最优解的方法呢？当然有，那就是分支-限界的核心所在，具体参考：《手撕算法日记–分枝-限界法》

反思：注意讨论bound=bestp的情况

一定要注意上面讨论的这种5和8相同的情况，千万不要默认5就一定是最好情况了，可能会出现这种8和5的具体解最终效益值相同的情况（即存在两组最优解的罕见情况)甚至更多组相同最优解亦或者是甚至存在比5更好的情况，一定要记得讨论😒！

总结

就是拿bestp和bound进行比较，bestp>bound时就触发限界函数，bestp<=bound就继续展开。如在结点5处得到bestp=20，结点6处bound=19,故限界掉,类似,结点7,8也被限界掉。

最大集团问题

就是寻找一个图的也叫最大集团，所以重在理解概念。所以首先我们要理解子图，最大集团等概念：

概念

• 完全图：如果无向图中的任何一对顶点之间都有一条边，这种无向图称为完全图。
• 完全子图：给定无向图G=（V,E），如果点集U⊆V，且对任意U中的两个点u,v都有（u,v)⊆E,则成U是G的完全子图。
• 团（最大完全子图）：U是G的团当且仅当U不包含在G的更大的完全子图中。
• 最大团：G的最大团是指G中所含顶点数最多的团。
• 独立集：对于给定无向图G=（V,E），如果顶点集合V*⊆V，若V*中任何两个顶点均不相连，则称V*为G的独立集。
• 最大独立集：G中所含顶点数最多的独立集。

例如：

对于图

有

a,b都是完全子图，因为点和边都是图的子集，且任意点之间都相连，但是c,d是团，a,b都不是团，团就是最大完全子图，a,b都可以被更大的完全子图包含，所以a,b不是最大完全子图，所以也就不是最大团，d是最大团，所以c,d都是最大完全子图，但是只有d是最大团。

所以对于

a是一个无向图，b,c,d都是a的最大团。

• 补图：完全图中未相连的边和无向图的所有点所构成的图就成为补图

b就是a的一个补图，因为（1,3）（2,4）没有在无向图中存在，所以他是补图的边，而且有如下关系：无向图G的团和G补图的独立集之间存在一一对应的关系，特别地，U是G的最大团当且仅当U是G补图的最大独立集。如{1,2,5}是G的最大团，同时{1,2,5}也是G补图的最大独立集。

无向图G的最大子团和最大独立子集问题实际上是一种题型，两者之间可以互相转换，并且使用回溯法可以将时间复杂度控制在O(n*2^n)以内解决。因为最大团和最大独立子集问题都可以看做是图G顶点集V的子集选取问题，因此，都可以选择使用状态空间树展开求解，解空间就是n元组。解决思想是，设当前的E-节点（又称为扩展节点)Z处于解空间的第i层，在进入左子树，即代表1状态，加入Z之前，我们需要先进行判断他是否和已选择的所有团节点都连接，如果没有，则不能进入，在进入右子树即0状态不选取Z选取除Z以外的其他点之前判断是否还有足够多个点可以供我们选择来使得有可能在右子树（即选择Z以外剩余点）形成比已知最大团更大的团。再具体实现时，使用邻接矩阵表示图G，以一个整数型数组向量返回找到最大团的解，v[i]=1表示顶点i属于最大团的顶点。

所以接下来我们的任务是首先判断这个点能否加入，若不能加入则kill掉左子树，然后在判断能否进入右子树，即还有没有足够多个点来使得右子树产生比已知最大团更大团，如果可以进入左子树，则还需要考虑加入该顶点和舍弃两种情况。这样执行剪枝策略可以有效提高搜索速度。那么我们怎么解决判断是否能够还有足够多个点使得右子树产生比已知最大团更大团？

思考：右子树限界函数怎么实现？

这里我们可以考虑执行一种特殊的扩展方式，我们先假设所有节点都是相连的，所以每次扩展时不是挑选节点，而是枚举节点，按照从小到大的顺序枚举节点，然后在判断是否相连，即从i=1开始，然后2,3,4，…,n这样对每一个节点进行判断，这样还有一个好处是相同情况的点会在数的同一层，这样我们就可以轻松知道假设节点Z在t层，总结点数为n个，已选的节点数为cn，那么剩余的除Z以外的节点数就是n-t个，若

$$(已选节点数)cn+(所有除Z以外剩余的节点数)n-t<已知最大团的节点数bestn$$

那么就出发限界函数不进入此右子树，那么已选节点数可以通过每次选中某个节点时参数cn++来进行统计，自此核心判断公式就写完了，我们可以写出伪代码了。

伪代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

void AdjacencyGraph::maxClique(int i){
    //计算最大团的回溯代码
    if(i>n){//到到达了叶子节点
        //找到了一个最大团的元组解，更新
        for(int j=1;j<=n;j++){
            //记录这组解
            bextx[j]=x[j];
            //最大团的节点数就是此时解的节点数
            bextn=cn;
            return;//退出
        }
    }
    //如果没到叶子节点则还是中间节点，首先判断能否进入左子树
    //即顶点i是否与其他所有的已选顶点相连
    int ok=1//默认是相连的
    for(int j=1;j<i;j+=){
        //j节点在已选最大团组里&&i和j不相连，找到一组即可
        if(x[j]&&a[i][j]==NoEdge){
            ok=0;//不相连
            break;
        }
    }
    if(ok)//符合全部相连
    {
        //将i加入最大团组中
        x[i]=1;
        //已选顶点数加一
        cn++;
        //检验i+1能否进入，递归调用
        //并计算bestn
        maxClique(i+1);
        //很重要！！！
        //还要回溯到i进入右子树检验不放回的情况
        x[i]=0;
        cn--;
    }
    //检验有没有必要进入右子树
    //即除i节点以外选取全部剩余节点后能否形成更大团
    if(cn+n-i>bextn){
        //有必要进入&&不选i节点
        x[i]=0;
        //检验i+1能否进入，递归调用
        //并计算bestn
        maxClique(i+1)
    }
}
//初始化和返还bestn
int AdjacencyGraph::MaxClique(int v[]){
    x=new int [n+1]//存元组解
    cn=0;//已选顶点数为0
    bestn=0;//
    bestx=v;
    //从1开始注意检验顶点
    maxClique(1);
    return bestn;
}

状态空间树展开过程

上图是对无向图G寻找最大团时状态空间树展开过程的图解，我们从R开始，逐一对顶点进行检验，首先R节点处相当于初始化，此时没有选点，cn=0,bestn=0。我们首先选节点1（因为默认单调递增检验顶点），然后进入1的左子树，检验2发现和1相连，可以加入，所以此时cn=2,bestn=0（记得吗，此时是a情况，虽然是一个完全子图，但是不是团，因为不是最大完全子图),然后检验节点3，发现3虽然和2相连，但是和1不相连，所以2不能展开左子树即不能选择3，此时判断能否进入右子树，此时已选节点数为2，剩余节点数为5-3=2（这里的图是显示3节点在第4层，但是代码由于默认从节点1位根节点出发，所以与这里的图略有出入，在代码里此时节点3就是在第三层），所以cn+n-i=4>bestn=0,即如果将4,5默认全选上还是有可能产生更大的团的，由于此时还没有形成团，所以bestn=0，所以可以对2进行右子树展开即放弃3，然后判断顶点4，发现4和2不相连，所以无法展开3的左子树即不能选择节点4，判断3能否右子树扩展，发现是可以的，所以判断5，发现5和1,2都相连，所以可以选5，此时对于4来说进行了左展开，此时到达了叶子节点，最大团产生了一个为{1,2,5},并且bestn=cn=3，然后注意对于可以加入的顶点，不要忘记还要回溯判断不选的情况，即回溯到了节点4，判断能够右子树扩展，发现此时cn=2(因为此时只选了1,2),出来5剩余的顶点数为5-5=0，所以cn+n-i=2<bestn=3，即展开右子树也不可能得到比已知最大团{1,2,5}更大的团了，所以不展开右子树，继续回溯到了1节点，然后如图，虽然1节点可以右展开到黄色的2节点，但是黄色的2节点无法左右展开，继续回溯到了R节点进行右展开的判断，此时cn+n-i=5>bestn所以右展开，以此类推即完成了空间树的展开。

货箱装船问题

给定载重量c的货船，找一种装船的办法，使得装载的货箱数目最多(0-1背包问题，没有效益值，直接贪心就行)，现在对问题进行了改动，有两艘船和n个货箱，第一艘船的载重量为c1,第二艘船的载重量为c2,w(i)是货箱i的重量，且w(1)+…+w(n)<=c1+c2,问是否有一种可以将n个货箱全部装走的办法（可行解）？

思路就是极大化第一只船的装箱重量，如果剩余的货箱能够被第二只船装载，则有可行解，否则就没有。我们不要枚举所有情况，太过复杂，可以用某些限界方法进行剪枝，如设cw为船1已装的重量，则如果cw+w(i)>c1,就杀死左子树，不再展开，如果已知的最优装箱重量为bestw，如果r为剩余的未装货的重量，如果cw+r<=bestw，则不用在展开此节点。两种限界方法同时使用即可加快搜索速度。

所以展开左子节点：

• 如果cw+w(i)>c1，停止展开左子节点，r=r-w[i]，并展开右子树即不放入i物品的情况
• 如果cw+w(i)<=c1,x[i]=1,cw=cw+w[i],r=r-w[i]并继续检验w[i+1]同时回溯讨论不要i物品的情况即展开右子树的情况

展开右子节点：

• 如果cw+r<=bestw，停止展开右子树，并回溯到最近的活父节点
• 如果cw+r>bestw，x[i]=0，展开右子树即讨论不要物品i的情况。

回溯时如果x[i]=1说明只讨论了展开左子树的情况，还可以尝试展开右子树，如果x[i]=0，说明已经节点I已经是个死节点了，继续向上回溯。

旅行商问题

售货员要到若干城市去推销商品，已知各个城市之间的路程，他要选定一条从驻地出发，经过每个城市一次，最后回到驻地的路线，使得总的路程（或者总旅行费）最小。

我们假设城市之间的图如下：

我们发现某些城市之间是没有直接相连接的路径的，且每条路的开销各不相同，我们的目的就是寻找一个使线段权值之和最小的连接所有城市的路。并且不能逐一枚举尝试，复杂度过高，这里可以加上某些限界函数来进行剪枝加快搜索。我们构建一个元组解{x1,…xn}，分量xi表示第i个要去的城市编号，因为只有去一次，所以前面走过的城市{x1,x2,…,xk-1}，后面的取值为S-{x1,x2,…,xk-1}，我们仍然可以使用状态空间树进行展开，这里也要加上限界条件，其中展开左子树需要满足两个节点即两座城市是相连的且从起点到这个检验节点即选择的要去的城市的路径长度（即已经走过的城市所用的路径长度之和）要小于已知的最短路径长度，对于右子树其实我们也可以加上限界条件：

$$已经选中的城市路径长度之和+未走过的所有城市的最短到达路径长度<已知的走遍全部城市的最短路径长度$$

但是由于未走过的所有城市最短距离之和不好计算，所以对于右子树展开不加限界条件了，但是只有左子树限界方法也已经大幅加快了搜索速度了。

伪代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

template<class T>
T AdjacencyWDigraph<T>::Tsp(int v[]){
    //回溯算法解决旅行商问题
    //预处理程序函数，用来返还最优旅游路径的耗费
    //最优路径存入v[1:n]
    //初始化
    x= new int [n+1]
    //x是排列
    //初始化为第i次走城市i
    for(int i=1;i<=n;i+=){
        x[i]=i;
    }
    //两城市最短路径默认为正无穷
    bestc=NoEdge;
    //最优可行元组解
    bestx=v;
    cc=0;//已经走过的城市路径长度
    tsp(2);
    delete x;
    return bestc;
}

void AdjacencyWDigraph<T>::tsp(int i){
    //旅行商回溯算法
    if(i==n){
        //位于一个叶子节点的父节点
        //找到了一个最优路径可行解
        //a二维数组是城市无向图G的邻接矩阵
        //如果n-1和n有路且1和城市有路（注意他还得回去）
        //之所以这样比较是因为回去的路长度会影响总长度
        if(a[x[n-1][x[n]]]!=NoEdge&&a[x[n][1]]!=NoEdge
          &&(cc+a[x[n-1]x[n]]+a[x[n][1]]<bestc||bestc==NoEdge)
          ){
            //找到了更优的旅行路径
            for(int j=1;j<=n;j++){
                bestx[j]=x[j];//记录这组解
            }
            bestc=cc+a[x[n-1][x[n]]]+a[x[n][1]];//记录最优路径长度
        }
    }
    else{
        //还没走完所有城市
        //尝试展开子树
        for(int j=i;j<=n;j++){
            //判断是否相连即能否展开左子树
            //以及是否此时是比已知对短路径更短的情况
            if(a[x[i-1]x[j]]!=Noedge&&(cc+a[x[i-1]x[i]]<bestc||bestc==NoEdge)){
                //能走
                //搜索该子树
                Swap(x[i],x[j]);
                cc+=a[x[i-1]x[i]];
                //递归调用检验下一个城市
                tsp(i+1)
                //同时千万不要忘记回溯检验不走这个城市的情况
                cc-=a[x[i-1]x[i]];
                Swap(x[i],x[j]);
            }
        }
    }
}

小测验

Questions

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

Answers

总结

通过这次回溯法的学习，我们了解到回溯法实际上就是在dfs基础上加以限界函数来加快搜索速度，其中无论是哪种题型，其核心思想都是一样的，设置元组解，对利用限界条件对状态空间树展开加以剪枝，其中，我们都是在能否展开，能够左子树展开，能否右子树展开这三处关键点进行限界条件添加，当然如果特别复杂的限界判断可以适当不加，一定要注意对于这种dfs回溯永远都是能左子树展开，优先一直展开左子树，即E-节点优先一直向下延伸，同时对于左子树展开的同时也要回溯进行右子树展开，这样问题才能讨论完全，直至每次到达叶子节点得到一组可行解，记住要更新限界条件等，然后在所有可行接中最终得到最优解，那么这次分享就告于段落啦，有兴趣的小伙伴可以提前思考一下分支-限界和回溯又有什么本质区别呢，我们下次再见😋~