回溯法

回溯法的思想是：能进则进，进不了换，换不了退。
隐约束指对能否得到问题的可行解和最优解做出的约束。隐约束包括约束函数和限界函数。
关键步骤是：

1. 定义解空间；
2. 确定解空间的组织结构（子集树、排列数、m叉树等）；
3. 搜索解空间。

回溯法阶梯的关键是设计有效的显约束和隐约束。

大卖场购物（0-1背包问题）

问题举例

每个物品重量w和价值v如下表所示，购物车容量为W，求不超过购物车重量的最大价值。

w[]	1	2	3	4
	2	5	4	2

w[]	1	2	3	4
	6	3	5	4

问题分析

1. 解空间={x₁,x₂,…,x_i,…,x_n}的所有子集（包括{0,0,0}这种子集），你像这里面就是{0,0,0,0},{0,0,0,1},{0,0,1,0},{0,0,1,1},…{1,1,1,1}。显约束为x_i=0或1。
2. 确定解空间的组织结构。由于显约束的缘故，可以看出解空间为子集树。
3. 搜索解空间

• 约束条件为：w_ix_i≤W（i=1~n）
• 限界条件：cp+rp>bestp（cp为当前已经装入购物车的物品的总价值，rp为第t+1~第n种物品的总价值，bestp为最大价值）

4. 搜索过程见问题求解。

问题求解

（1）首先初始化。w[]={2,5,4,2}，v[]={6,3,5,4}，sumw=2+5+4+2=13，sumv=6+3+5+4=18，因为sumw>W，所以不能装完，所以需要进行后续的操作。此时定义一个cp=rp=bestp=0，x[i]=0，cw=0。
注意：在这里w[]和v[]的下标都是从1开始。并且以左子树为x_i=1，右子树x_i=0。

（2）开始搜索第一层（t=1）。cw=cw+w[1]=2<W，所以令x[1]=1，
cp=cp+v[1]=6，将2号结点加入左子树。(2号结点是第一个商品）

（3）拓展2号结点。考虑cw+w[2]=7<W，所以令x[2]=1，cp=cp+v[2]=9，将3号结点加入左子树。（3号结点是第2个商品）

（4）拓展3号结点。考虑cw+w[3]=11>W，所以x[3]=0，然后计算cp+rp=9+4=13>bestp（此时bestp还是0），所以将4号结点加入右子树。（4号结点是第3个商品）

（5）拓展4号结点。考虑cw+w[4]=9<W，所以x[4]=1，然后计算cp=cp+v[4]=13，所以将5号结点加入左子树。（5号结点是第4个商品）

（6）拓展5号结点。由于此时t>n，故已经找到了一个当前的最优解，令bestp=cp（值为13），5号结点成为死结点。返回到上一结点。

（7）回溯拓展4号。此时cp=9，若将5号结点加入右子树，cp+rp=9<bestp，故该结点不满足限界条件，成为死结点，继续回溯到3号结点。由于3号结点已经研究过，左子树不可行，所以回溯到2号结点。

（8）扩展2号结点（t=2）。之前扩展了左子树，所以现在考虑右子树。此时cp=6，bound(t+1)=cp+rp=15>bestp，因此满足限界条件，扩展右子树，令x[2]=0，生成6号结点。（也就是第2个商品不要了）

（9）扩展6号结点（t=3）。cw+w[3]=6<W，满足约束条件，扩展左分支，令x[3]=1，cw=cw+w[3]=6，cp=cp+v[3]=11，生成7号结点加入左子树。（7号结点是第3件商品）。

（10）拓展7号结点（t=4）
cw+w[4]=8<W，满足约束条件，扩展到左子树。令x[4]=1，cw=cw+w[4]=8，cp=cp+v[4]=15。（8号结点是第4件商品）

（11）拓展8号结点（t=5）。由于此时t>n，故已经找到了一个当前的最优解，令bestp=cp（值为15），8号结点成为死结点。返回到上一结点。

（12）拓展7号结点（t=4）。考察bound(t+1)=cp+rp=11<15，成为死结点。

（13）拓展6号结点（t=3）。bound(t+1)=cp+rp=10<15，成为死结点。

（14）拓展1号结点（t=1），bound(t+1)=12<15，成为死结点。算法结束。

代码实现

double Bound(int i)//计算上界
{
    int rp=0;//剩余重量
    while (i <= n)
    {
        rp += v[i];
        i++;
    }
    return rp+cp;
}

void Backtrack(int t)//t当前在第t层
{
    if (t > n)
    {
        for (i = 1; i <= n; i++)
        {
            bestx[i] = x[i];
        }
        bestp = cp;
        return;
    }
    if (cw + w[t] <= W)//还未到重量，可以搜索左子树
    {
        x[t] = true;
        cw += w[t];
        cp += v[t];
        Backtrack(t + 1);
        cw -= w[t];//回溯
        cp -= v[t];//回溯
    }
    //若左子树不满足，然后看右子树，判断限界条件
    if (Bound(t + 1) > bestp)
    {
        x[t] = false;
        Backtrack(t + 1);
    }
}
void initial_parameter(double W, int n)
{
    cw = 0;//初始化当前重量为0
    cp = 0;//初始化当前价值为0
    bestp = 0;//初始化当前最好价值为0
    int sumw = 0;//统计所有物品的总重量
    int sumv = 0;//统计所有物品价值
    //这里上面两个参数可以根据具体情况确定为int或者double等
    for (i = 1; i <= n; i++)
    {
        sumw += w[i];
        sumv += v[i];
    }
    if (sumw <= W)
    {
        bestp = sumv;
        cout << "所有物品均放入购物车";
        cout << "放入购物车的最大价值为" << bestp << "元。" << endl;
        return;
    }
    Backtrack(1);
    cout << "放入购物车的最大价值为" << bestp << "元。" << endl;
    cout << "放入购物车的物品序号为：";
    for (i = 1; i <= n; i++)
    {
        if (bestx[i] == true)
            cout << i << " ";
    }
    cout << endl;
}

算法复杂度和改进

1.算法复杂度
（1）时间复杂度：O(12ⁿ+n 2ⁿ)=O(n 2ⁿ)。
（2）空间复杂度：O(n)。
2.算法优化
实际上，经常我们在计算bound()函数的时候对于rp多算太多了，因为很有可能rp到某一步就超过了购物车的中梁，所以我们可以缩小上界，从而加快剪枝速度，提高搜索效率。
上界函数bound()：当前价值cp+剩余容量可容纳的剩余物品的最大价值brp（为了能装最大价值，所以在计算上界函数的时候可以对商品分割，*但实际的时候不允许），即修改为

double bound(int i)
{
    //剩余物品为第i~n种物品
    double cleft=W-cw;//剩余容量
    while(i<=n && w[i]<cleft)
    {
        cleft-=w[i];
        brp+=v[i];
        i++
    }
    //下面是采用切割的方式装满背包，这里是求上界，
    //所以可以这样做。实际是不允许的
    if(i<=n)
    {
        brp+=v[i]/w[i]*cleft;
    }
    return cp+brp;
}

为了更好地计算和运用上界函数剪枝，先将物品按照其单位重量价值（价值/重量）从大到小排序，然后按照排序后的顺序考察各个物品。即定义这样一个结构体：

struct Object
{
    int id;//物品序号
    double ;//单位重量价值
};

bool cmp(Object a1, Object a2)
{
    return a1.d>a2.d;
}

然后将 initial_parameter(double W, int n)的if(sumw<=W)这个语段后面加入：

sort(Q,Q+n,cmp);
for(i=1;i<=n;i++)
{
    a[i]=w[Q[i-1].id];//把排序后的数据传递给辅助数组
    b[i]=v[Q[i-1].id];
}
for(i=1;i<=n;i++)
{
    w[i]=a[i];
    v[i]=b[i];
}

然后将

 for (i = 1; i <= n; i++)
{
    if (bestx[i] == true)
        cout << i << " ";
}

修改为

    for (i = 1; i <= n; i++)
{
    if (bestx[i] == true)
        cout << Q[i-1].id << " ";
}

最大团

问题描述

部落酋长希望组织一支保卫部落的卫队，要在居民中选出最多的居民加入，并保证卫队中任何两个人都不是仇敌。编程计算构建部落护卫队的最佳方案。

问题分析

• 完全子图：给定无向图G(V,E)，其中V是结点集，E是边集。G’=(V’,E’)。如果结点集V’⊆V，E’⊆E，且G’*中的任意两个结点都有边相连，则成G’是G的完全子图。
• 当且仅当G’不包含在G的更大的完全子图中时，G的完全子图G’ 是 G的团，就是说G’ 是 G的极大完全子图。
• 最大团：G的最大团是指G所有团中，含结点数最多的团。

算法设计

1. 定义问题的解空间。问题的解空间为 {x₁,x₂,…,x_i,…,x_n}的所有子集（包括{0,0,0}这种子集），你像这里面就是{0,0,0,0},{0,0,0,1},{0,0,1,0},{0,0,1,1},…{1,1,1,1}。显约束为x_i=0或1。
2. 解空间的组织结构：子集树，深度为n。
3. 搜索解空间：
   • 约束条件：假设当前扩展结点位于解空间树的第t层，那么从第1到第t-1层的结点情况都已经确定，接下来是按照扩展结点的左分支进行扩展，此时需要判断是否将第t个结点放到团里，只要第t和结点和前面t-1个结点中被选中的结点都有边连接，那么就能放到团里，即x[i]=1，否则不能放到团里，即x[i]=0。
   • 限界条件：根据前t个结点的状态确定当前已经放入团中的结点个数（用cn表示），假想t+1个结点到第n结点全部放入团内，放入的节点个数（fn表示），fn=n-t，则cn+fn是所有从根出发的路径中经过中间结点z的可行解所包含结点个数的上界。若cn+fn>bestn，则需要向子孙结点搜索，否则不需要。所以限界条件为cn+fn>bestn。

代码实现

bool isPlace(int t)
{
    bool status = true;
    for (int j = 1; j < t; j++)
    {
        if (x[j] && a[t][j] == 0)
        {
            status = false;
            break;
        }
    }
    return status;
}

//回溯法主体
void backtrack(int t)
{
    //到达叶结点
    if (t > n)
    {
        for (int i = 1; i <= n; i++)
            bestx[i] = x[i];
        bestn = cn;
        return;
    }

    if (isPlace(t))
    {
        x[t] = 1;
        cn++;
        backtrack(t + 1);
        cn--;
    }
    if (cn + n - t > bestn)//这里可以进行优化
    {
        x[t] = 0;
        backtrack(t + 1);
    }
}

算法复杂度分析

1.时间复杂度：O(n* 2ⁿ)，空间复杂度为O(n)。

着色问题

问题分析

假设地图共有7个区域，分别是A/B/C/D/E/F/G，对上面顺序进行编号，每个区域用一个结点表示，相邻的区域有连线，那么地图就转化成一个无向连接图。

算法设计

1. 定义问题的解空间。图的m着色问题解空间形式为n元组{x₁,x₂,…,x_i,…,x_n}，每个分量取值为1,2,3,…,m，即问题的解是一个n元向量。由此可得，问题的解空间为{x₁,x₂,…,x_i,…,x_n}，其中显约束为x_i=1,2,…,m。
2. 确定解空间的组织结构：一颗满m叉树，树的深度为n。
3. 搜索解空间
   • 约束条件：假设当前扩展结点位于解空间树的第t层，那么从第1到第t-1层的结点情况都已经确定，接下来是按照扩展结点的第一个分支进行扩展，此时需要判断是否将第t个结点着色情况。第t个结点的色号要与前t-1个结点中与其有边相连的结点颜色不同，如果有颜色相同的，则第t个结点不能用这个色号，换下一个色号尝试。
   • 限界条件：无。
   • 搜索过程：扩展结点沿着第一个分支扩展，判断约束条件，满足则进入深一层继续搜索；如果不满足，则扩展生成的结点被剪掉，换下一个色号尝试。如果所有色号都尝试完毕，该结点变成死结点，向上回溯到距离其最近的活结点，继续搜索。搜索到叶子结点时，找到一种着色方案，搜索过程直到全部活结点变成死结点为止。

解题过程

地图7个区域，3种颜色。

1. 开始搜索第1层（t=1）。扩展A结点第一个分支，首先判断是否满足约束条件，因为之前还未着色任何结点，所以满足约束条件，扩展该分支，令1号结点着1号色，即x[1]=1，生成B。
2. 拓展B结点（t=2）。扩展第一个分支x[2]=1，首先判断2号结点是否和前面已经确定色号的结点（1号）有边相连且色号相同，不满足约束条件，剪掉该分支，然后沿着x[2]=2扩展，2号结点和前面已经确定色号的结点（1号）有边相连，但色号不同，满足约束条件，扩展该分支，令x[2]=2。
3. 扩展C结点（t=3）。扩展第一个分支x[3]=1，首先判断3号结点是否和前面已经确定色号的结点（1、2号）有边相连且色号相同，不满足约束条件，剪掉该分支；同理剪掉x[3]=2分支。然后沿着x[3]=3扩展，3号结点和前面已经确定色号的结点（1、2号）有边相连，但色号不同，满足约束条件，扩展该分支，令x[3]=3。生成D。
4. 扩展D结点（t=4）。扩展第一个分支x[4]=1，首先判断4号结点是否和前面已经确定色号的结点（1、2、3号）有边相连且色号相同，不满足约束条件（4余1相连），剪掉该分支；然后令x[4]=2，符合条件，生成E。
5. 扩展E结点（t=5）。扩展第一个分支x[5]=1，首先判断4号结点是否和前面已经确定色号的结点（1、2、3号）有边相连且色号相同，确定5与2、3、4相连但色号不同，满足约束条件，扩展该分支，生成F。
6. 扩展F结点（t=6）。扩展第一个分支x[6]=1，同理不满足，剪掉分支；然后沿着x[6]=2扩展，6与5号有边相连但色号不同，故满足约束条件，扩展该分支，令x[6]=2，生成G。
7. 扩展G结点（t=7）。扩展第一个分支x[7]=1，剪掉x[7]=1和x[7]=2的分支，然后令x[7]=3，符合要求，生成H。
8. 扩展H结点（t=8）。t>n，找到一个可行解，输出该可行解{1,2,3,2,1,2,3}，回溯到最近的活结点G。
9. 重新扩展G结点（t=7）。G已经考察完毕，成为死结点，回溯到最近的活结点F。
10. 继续搜索，又找到第二种着色方案，输出可行解{1,3,2,3,1,3,2}。
11. 继续搜索，又找到4个可行解。

代码实现

//约束条件
bool isRight(int t)
{
    for (int j = 1; j < t; j++)
    {
        if (map[t][j])
        {
            if (x[j] == x[t])
                return false;
        }
    }
    return true;
}

//回溯方法函数
void Backtrack(int t)
{
    if (t > n)
    {
        sum++;
        cout << "第" << sum << "种方案：";
        for (int i = 1; i <= n; i++)//输出该着色方案
        {
            cout << x[i] << " ";
        }
        cout << endl;
    }
    else {
        for (int i = 1; i <= m; i++)
        {
            x[t] = i;
            if (isRight(t))
                Backtrack(t + 1);
        }
    }
}

算法复杂度分析

1. 时间复杂度：O(nmⁿ)。
2. 空间复杂度：O(n)。

n皇后问题

问题介绍

在n×n的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋规则，皇后可以攻击与之在同一行、同一列、同一斜线上的棋子。现在在n*n的棋盘上放置n个皇后，使其不受攻击。

问题分析

求解策略：
以行为主导：

• 在第1行第1列放置第一个皇后。
• 在第2行放置第2个皇后。第2个皇后的位置不能和前面的皇后同列、同斜线，不用再判断同行了，因为每行我们本来就只放一个。
• 在第3行放置第3个皇后。第3个皇后的位置不能和前面的皇后同列、同斜线。
• ……
• 在第t行放置第t个皇后。第t个皇后的位置不能和前面的皇后同列、同斜线。
• ……
• 在第n行放置第n个皇后。第n个皇后的位置不能和前面的皇后同列、同斜线。

算法设计

（1）定义问题的解空间。n皇后问题解的形式为n元组：{x₁,x₂,…,x_i,…,x_n}，分量x_i表示第i个皇后放置在第i行第x_i列，x_i取值为1,2,3,…,n。显约束为不同行。

（2）解空间的组织结构：一颗m(m=n)叉树，树深度为n。

（3）搜索解空间。
约束条件：在第t行放置第t个皇后时，第t个皇后的位置不能和前t-1个皇后同列、同斜线。第i个皇后和第j个皇后不同列，即x_i!=x_j。

限界条件：不需要设置。

搜索过程：

从根开始，以DFS的方式进行搜索。根节点是活结点，并且是当前的扩展结点。在搜索过程中，当前的扩展结点沿纵深方向移向一个新结点，判断该新结点是否满足隐约束。如果满足，则该新结点成为活结点，并且成为当前的扩展结点，继续深一层的搜索；如果不满足，则换到该新结点的兄弟结点继续搜索；如果新结点没有兄弟结点，或其兄弟结点已全部搜索完毕，则扩展结点成为死结点，搜索回溯到其父结点处继续进行。搜索过程直到找到问题的根结点变成死结点为止。

代码实现

bool isPlace(int t)
{
    bool place = true;
    for (int j = 1; j < t; j++)
    {
        if (x[t] == x[j] || t - j == fabs(x[t] - x[j]))//判断列、对角线是否冲突
        {
            place = false;
            break;
        }
    }
    return place;
}

void backtrack(int t)
{
    if (t > n)
    {
        countn++;
        for (int i = 1; i <= n; i++)
        {
            cout << x[i] << " ";
        }
        cout << endl;
        cout << "---------" << endl;
    }
    else
    {//分别判断n个分支，特别注意i不要定义为全局变量，否则递归调用有问题
        for (int i = 1; i <= n; i++)
        {
            x[t] = i;
            if (isPlace(t))
                backtrack(t + 1);
            //上面说的是不冲突就进行下一行搜索
        }
    }
}

算法复杂度分析

1. 时间复杂度：O(nⁿ⁺¹）。
2. 空间复杂度：O(n)。

最优加工顺序

问题描述

现在有3个机器零件{J₁,J₂,J₃}，在第一台机器上的加工时间分别为2、5、4，在第二台机器上的加工时间分别为3、1、6.如何安排零件加工顺序，使第一个零件从机器1上加工开始到最后一个零件在机器2上加工完成，所需的总加工时间最短？

问题分析

我们通过分析可以发现，第一台机器可以连续加工，而第二台机器开始加工的时间是当前第一台机器的下线时间和第二台机器下线时间的最大值。
实际上就是找到n个机器零件的一个排列，使总的加工时间最短。

算法设计

1. 定义问题的解空间。解的形式为n元组：{x₁,x₂,…,x_i,…,x_n}，分量x_i表示第i个加工的零件号，n个零件组成的集合为S={1,2,…,n}，x_i取值为S-{x₁,x₂,…,x_i-1}。
2. 解空间的组织形式为一颗排列数，深度为n。
3. 搜索解空间。
   • 约束条件：无约束条件。
   • 限界条件：用f₂表示当前已完成的零件在第二台机器加工结束所用的时间，用bestf表示当前找到的最优加工方案的完成时间。显然，继续向深处搜索时，f₂不会减少，只会增加。因此，当f₂≥bestf时，没有继续向深处搜索的必要。限界条件可以描述为：f₂<bestf。f₂初值为0，bestf的初值为无穷大。
4. 搜索过程。扩展结点沿着某个分支扩展时需要判断限界条件，如果满足，则进入深一层继续搜索；如果不满足，则剪掉该分支。搜索到叶子结点的时候，即找到当前最优解。搜索直到全部活结变成死结点为止。

代码实现

1.数据结构

struct node
{
    //机器零件在第一台机器上的加工时间x和第二胎机器上的加工时间y
    int x,y;
}T[MAX];

2.按限界条件进行搜索求解：t表示当前扩展结点在第t层，f₁表示当前第一台机器上加工的完成时间，f₂表示当前第二台机器上加工的完成时间。如果t>n表示已经到达叶子结点，记录最优值和最优解，返回。否则，分别判断每个分支是否满足约束条件，若满足则进入下一层backtrack(t+1)；如果不满足则反操作复位，考察下一个分支（兄弟结点）。

void Backtrack(int t)
{
    if(t>n)
    {
        for(int i=1;i<=n;i++)
            bestx[i]=x[i];//记录最优队列
        bestf=f2;//更新最优值
        return ;
    }
    for(int i=t;i<=n;i++)
    {
        f1+=T[x[i].x;
        int temp=f2;
        f2=max(f1,f2)+T[x[i]].y;
        if(f2<bestf)//满足限界条件
        {
            swap(x[t],x[i]);//交换
            Backtrack(t+1);//继续搜索
            swap(x[t],x[i]);//复位，反操作
        }
        f1-=T[x[i]].x;//复位，反操作
        f2=temp;//复位，反操作
    }
}

算法复杂度分析

时间复杂度为O(nn!)≈O((n+1)!)，空间复杂度为O(n)。

算法优化改进

新的算法的时间复杂度为O(nlogn)，空间复杂度为O(n)。利用贝尔曼规则，代码如下：

#include<iostream>
#include<algorithm>
using namespace std ;
const int MX=10000+5 ;
int n;
struct node
{
    int id;
    int x,y;
}T[MX] ;
bool cmp(node a,node b)
{
    return min(b.x,a.y)>=min(b.y,a.x);//按照贝尔曼规则排序
}
int main()
{
    cout<<"请输入机器零件的个数 n:";
    cin>>n;
    cout<<"请依次输入每个机器零件在第一台机器上的加工时间x和第二台机器上的加工时间y:";
    for(int i=0;i<n;i++)
    {
        cin>>T[i].x>>T[i].y;
        T[i].id=i+1;
    }
    sort(T,T+n,cmp);   //排序
    int f1=0,f2=0;
    for(int i=0;i<n;i++)  //计算总时间
    {
       f1+=T[i].x;
       f2=max(f1,f2)+T[i].y;
     }
    cout<<"最优的机器零件加工顺序为:";
     for(int i=0;i<n;i++) //输出最优加工顺序
       cout<<T[i].id<<" ";
    cout<<endl;
    cout<<"最优的机器零件加工的时间为:";
    cout<<f2<<endl;
    return 0 ;
}

旅行商问题

问题描述

假设有5个点，这五个点之间是用无向边来连接的，但是每一个边是有权重的，这实际上是一个无向带权图。我们希望在最小权重的情况下走过这5个点，且不重复，那应该怎样来实现呢？

算法设计

1. 定义问题的解空间：问题解的形式为n元组{x₁,x₂,…,x_i,…,x_n}，分量x_i表示第i个要去的旅游景点编号，景点的集合为S={1,2,…,N}。因为景点不可重复走，因此在确定x_i时，前面走过的景点{x₁,x₂,…,x_i,…,x_i-1}不能再走。x_i的取值为S-{x₁,x₂,…,x_i,…,x_i-1}。
2. 解空间的组织形式：解空间是一颗排列树，树的深度为n=5。除了开始结点1之外，一共有24种排列方式。
3. 搜索解空间：约束条件：用二维数组g[][]储存无向带权图的邻接矩阵，如果g[i][j]≠无穷表示城市i和城市j又边相连，能走通。限界条件：cl<bestl。cl的初始值为0，表示当前已经走过的城市所用的路径长度；bestl初始值为无穷，表示当前找到的最短路径的路径长度。
4. 搜索过程：扩展结点沿着某个分支扩展时需要判断约束条件和限界条件，如果满足，则进入深一层继续搜索，如果不满足，则剪掉该分支。搜索到叶子结点时，即找到了当前最优解。搜索直到全部的活结点变成死结点为止。

完美图解

（1）数据结构：如下表所示的邻接矩阵。

	3		8	9
3		3	10	5
	3		4	3
8	10	4		20
9	5	3	20

（图中未填的就是无穷）

（2）初始化：cl=0,bestl=无穷，解分量x[i]和最优解bestx[i]初始化为：

i	1	2	3	4	5
x[i]	1	2	3	4	5

i	1	2	3	4	5
bestx[i]	0	0	0	0	0

（3）开始搜索第一层（t=1）

扩展A₀结点，因为我们是从1号结点出发，所以x[1]=1，生成A结点。

（4）扩展A结点（t=2）
沿着x[2]=2分支扩展，因为1号结点和2号结点有边相连，且cl+g[1][2]=0+3<bestl，满足限界条件，生成B结点。

（5）扩展B结点（t=3）
沿着x[3]=3分支扩展，因为2号结点和3号结点有边相连，且cl+g[2][3]=3+3=6<bestl，满足限界条件，生成C结点。

（6）扩展C结点（t=4）
沿着x[4]=4分支扩展，因为3号结点和4号结点有边相连，且cl+g[3][4]=6+4=10<bestl，满足限界条件，生成D结点。

（7）扩展D结点（t=5）
沿着x[5]=5分支扩展，因为4号结点和5号结点有边相连，且cl+g[3][4]=10+20=30<bestl，满足限界条件，生成E结点。

（8）扩展E结点（t=6）
t>n，判断5号结点是否和1号结点相连，确认有，且cl+g[5][1]=30+9=39<bestl，找到一个当前最优解（1,2,3,4,5,1），更新bestl=39。

（9）向上回溯到D，D的孩子已经生成完毕，成为死结点，继续回溯到C，C结点还有一个孩子未生成。
（10）重新扩展C结点（t=4）。沿着x[4]=5分支扩展，因为3号结点和5号结点有边相连，且cl+g[3][5]=6+3=9<bestl=39，满足限界条件，生成F结点。

（11）扩展F结点（t=5）。
沿着x[5]=4分支扩展，因为5号结点和4号结点有边相连，且cl+g[5][4]=9+20=29<bestl=39，满足限界条件，生成G结点。

（12）扩展G结点（t=6）。t>n，判断4号结点是否和1号结点相连，确认有，且cl+g[4][1]=29+8=37<bestl=39，找到一个当前最优解（1,2,3,5,4,1），更新bestl=37。

不断搜索下去，到最后有以下组合和其值。

i	1	2	3	4	5	权值
结点组合	1	2	3	4	5	39
结点组合	1	2	3	5	4	37
结点组合	1	2	4	3	5	29
结点组合	1	2	5	3	4	23
结点组合	1	4	3	2	5	29
结点组合	1	4	3	5	2	23
结点组合	1	5	2	3	4	29

综上所述，bestl=23，路径为1-2-5-3-4-1。

代码实现

//初始化
void init()
{
    bestl = INF;
    cl = 0;
    for (int i = 1; i <= n; i++)
        for (int j = i; j <= n; j++)
            g[i][j] = g[j][i] = INF;
    for (int i = 0; i <= n; i++)
    {
        x[i] = i;
        bestx[i] = 0;
    }
}
//邻接矩阵赋值
void createMatrix()
{
    int u, v, w;//结点u和v，权值w
    cout << "请依次输入两个结点u和v之间的权值w。" << endl;
    cout << "格式：结点u 结点v 距离w" << endl;
    for (int i = 1; i <= m; i++)
    {
        cin >> u >> v >> w;
        g[u][v] = g[v][u] = w;
    }
}
//回溯法核心
void backTrack(int t)
{
    if (t > n)
        //到达叶子结点
        //最后一个结点与第一个结点有边相连且路径长度比当前最优值最小
        //说明找到了一条更优路径，记录相关信息
    {
        if (g[n][1] != INF && (cl + g[x[n]][1] < bestl))
        {
            for (int j = 1; j <= n; j++)
                bestx[j] = x[j];
            bestl = cl + g[x[n]][1];
        }

    }
    else
    {
        //没有到达叶子结点
        for (int j = t; j <= n; j++)
        {
            //搜索扩展结点的所有分支
            //如果第t-1个结点与第t个结点有边相连且可以得到更短路径
            if (g[x[t - 1]][x[j]] != INF && (cl + g[x[t - 1]][x[j]] < bestl))
            {
                //保存第t个结点到x[t]中，进入第t+1个
                swap(x[t], x[j]);//交换两个元素的值
                cl = cl + g[x[t - 1]][x[t]];
                backTrack(t + 1);
                cl = cl - g[x[t - 1]][x[t]];
                swap(x[t], x[j]);
            }
        }
    }
}

//打印路径
void print()
{
    cout << "最短路径：" << endl;
    for (int i = 1; i <= n; i++)
        cout << bestx[i] << "--->";
    cout << "1" << endl;
    cout << "最短路径长度：" << bestl << endl;
}

算法复杂度分析

1. 时间复杂度：除了最后一层外，有1+(n-1)+…+(n-1)(n-2)…2<=n(n-1)!个结点需要判断约束函数和限界函数，判断两个函数需要O(1)的时间，因此耗时O(n!)。在叶子节点处记录当前最优解需要耗时O(n)，在最坏情况下回搜索到每一个叶子结点，叶子数为(n-1)!，所以时间复杂度为O（n!）。
2. 空间复杂度：O(n)。