回溯算法：从八皇后到TSP的思维跃迁

回溯算法，说白了就是一种「试错」的思维。你想想看，生活中我们做决策时，不也经常是走一步看一步吗？这条路走不通，退回来换一条。回溯算法干的就是这件事——它把问题的所有可能解空间想象成一棵树，从根节点出发，沿着一条路径往下走，走到某个节点发现不对劲，就掉头回去，换条路再试。

我个人习惯把回溯算法叫做「有智慧的暴力」。为什么这么说？因为它本质上还是穷举，但比纯粹的暴力搜索聪明得多——它会在搜索过程中剪掉那些明显不可能的分支。嗯，这里要注意，剪枝的好坏直接决定了回溯算法的效率。

回溯算法的基本框架

我在项目中用过不少回溯算法，总结下来，它的代码结构其实非常固定。你只要记住这个模板，大部分回溯问题都能往里套：

void backtrack(路径, 选择列表) {
    if (满足结束条件) {
        记录结果;
        return;
    }
    
    for (选择 : 选择列表) {
        // 做选择
        路径.add(选择);
        // 进入下一层决策树
        backtrack(路径, 选择列表);
        // 撤销选择（回溯的核心）
        路径.remove(选择);
    }
}

这个模板里，最关键的就是「做选择」和「撤销选择」这两步。我曾经见过不少新手写回溯时，只记得做选择，忘了撤销，结果路径越走越长，永远找不到解。说白了，回溯的精髓就在于「能进能退」。

八皇后问题：回溯的经典入门

八皇后问题，你应该听说过。在一个8×8的棋盘上放8个皇后，要求任意两个皇后都不能在同一行、同一列或同一对角线上。我第一次看到这个问题时，觉得挺简单的，结果自己动手写代码才发现——嗯，坑不少。

先来看代码实现：

#include <stdio.h>
#include <stdbool.h>

#define N 8

int count = 0;  // 解的总数

// 检查位置 (row, col) 是否安全
bool isSafe(int board[N][N], int row, int col) {
    int i, j;
    
    // 检查当前列的上方
    for (i = 0; i < row; i++) {
        if (board[i][col] == 1)
            return false;
    }
    
    // 检查左上对角线
    for (i = row, j = col; i >= 0 && j >= 0; i--, j--) {
        if (board[i][j] == 1)
            return false;
    }
    
    // 检查右上对角线
    for (i = row, j = col; i >= 0 && j < N; i--, j++) {
        if (board[i][j] == 1)
            return false;
    }
    
    return true;
}

void solveNQueens(int board[N][N], int row) {
    // 所有行都放完了，找到一个解
    if (row == N) {
        count++;
        printf("解法 %d:\n", count);
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                printf("%c ", board[i][j] ? 'Q' : '.');
            }
            printf("\n");
        }
        printf("\n");
        return;
    }
    
    // 尝试在当前行的每一列放置皇后
    for (int col = 0; col < N; col++) {
        if (isSafe(board, row, col)) {
            board[row][col] = 1;  // 放置皇后
            solveNQueens(board, row + 1);  // 递归处理下一行
            board[row][col] = 0;  // 撤销皇后（回溯）
        }
    }
}

int main() {
    int board[N][N] = {0};
    solveNQueens(board, 0);
    printf("八皇后问题共有 %d 种解法\n", count);
    return 0;
}

运行这段代码，你会发现八皇后问题一共有92种解法。你想想看，如果不用回溯，纯暴力枚举8^8种可能，那得算到什么时候？回溯通过剪枝，把搜索空间大大缩小了。

图的着色问题：给地图涂颜色

图的着色问题，说白了就是：给定一个无向图，用m种颜色给每个顶点涂色，要求相邻顶点颜色不同。这个问题在实际中很有用，比如地图染色、寄存器分配、排课表等等。

我记得有一次做嵌入式系统的任务调度，多个任务共享一些硬件资源，不能同时访问。我当时就把这个问题建模成了图的着色问题——每个任务是一个顶点，冲突的任务之间连一条边，然后用回溯算法找一种可行的调度方案。

#include <stdio.h>
#include <stdbool.h>

#define V 4  // 顶点数

// 检查顶点v是否可以涂颜色c
bool isSafe(int graph[V][V], int color[], int v, int c) {
    for (int i = 0; i < V; i++) {
        if (graph[v][i] && color[i] == c)
            return false;
    }
    return true;
}

bool graphColoringUtil(int graph[V][V], int m, int color[], int v) {
    // 所有顶点都涂色完毕
    if (v == V)
        return true;
    
    // 尝试给顶点v涂上各种颜色
    for (int c = 1; c <= m; c++) {
        if (isSafe(graph, color, v, c)) {
            color[v] = c;  // 涂色
            if (graphColoringUtil(graph, m, color, v + 1))
                return true;
            color[v] = 0;  // 撤销涂色（回溯）
        }
    }
    
    return false;  // 没有可用的颜色
}

void graphColoring(int graph[V][V], int m) {
    int color[V] = {0};  // 初始化为0，表示未涂色
    
    if (graphColoringUtil(graph, m, color, 0)) {
        printf("找到可行着色方案:\n");
        for (int i = 0; i < V; i++)
            printf("顶点 %d -> 颜色 %d\n", i, color[i]);
    } else {
        printf("无法用 %d 种颜色完成着色\n", m);
    }
}

int main() {
    int graph[V][V] = {
        {0, 1, 1, 1},
        {1, 0, 1, 0},
        {1, 1, 0, 1},
        {1, 0, 1, 0}
    };
    
    int m = 3;  // 3种颜色
    graphColoring(graph, m);
    return 0;
}

旅行商问题（TSP）：最短路线的穷举

旅行商问题，简称TSP。问题是这样的：一个商人要拜访n个城市，每个城市只去一次，最后回到出发城市，求最短的路径。这个问题看起来简单，但它是著名的NP-hard问题——随着城市数量增加，计算量呈阶乘级增长。

回溯算法解决TSP的思路很直接：从起点出发，尝试所有可能的路径，记录最短的那条。当然，我们可以加一些剪枝策略来加速——比如当前路径长度已经超过已知最短路径时，直接剪掉。

#include <stdio.h>
#include <limits.h>

#define N 4  // 城市数量

int graph[N][N] = {
    {0, 10, 15, 20},
    {10, 0, 35, 25},
    {15, 35, 0, 30},
    {20, 25, 30, 0}
};

int visited[N];
int bestPath[N];
int bestCost = INT_MAX;

void tsp(int currPos, int count, int cost, int path[]) {
    // 所有城市都访问过了，回到起点
    if (count == N && graph[currPos][0]) {
        int totalCost = cost + graph[currPos][0];
        if (totalCost < bestCost) {
            bestCost = totalCost;
            for (int i = 0; i < N; i++)
                bestPath[i] = path[i];
            bestPath[N] = 0;  // 最后回到起点
        }
        return;
    }
    
    // 尝试访问下一个城市
    for (int i = 0; i < N; i++) {
        if (!visited[i] && graph[currPos][i]) {
            // 剪枝：如果当前成本已经超过已知最优解，跳过
            if (cost + graph[currPos][i] >= bestCost)
                continue;
            
            visited[i] = 1;
            path[count] = i;
            tsp(i, count + 1, cost + graph[currPos][i], path);
            visited[i] = 0;  // 回溯
        }
    }
}

int main() {
    int path[N];
    
    visited[0] = 1;  // 从城市0出发
    path[0] = 0;
    tsp(0, 1, 0, path);
    
    printf("最短路径长度: %d\n", bestCost);
    printf("路径: ");
    for (int i = 0; i <= N; i++)
        printf("%d ", bestPath[i]);
    printf("\n");
    
    return 0;
}

回溯算法的知识体系

说了这么多，我们来梳理一下回溯算法的知识结构。下面这张图可以帮你快速建立整体认知：

回溯算法的适用场景与局限

回溯算法不是万能的。我根据实际经验总结了一下，它最适合解决以下几类问题：

• 组合优化问题：比如从n个物品中选k个，求最大价值。典型的0-1背包问题就可以用回溯。
• 约束满足问题：比如数独、八皇后、图的着色。这类问题的特点是有一堆约束条件，需要找到满足所有条件的解。
• 路径规划问题：比如TSP、迷宫寻路。这类问题需要找到一条满足条件的路径。

但回溯算法也有明显的局限。说白了，它本质上还是穷举，虽然加了剪枝，但最坏情况下的时间复杂度仍然是指数级的。对于规模较大的问题（比如n>30的TSP），回溯算法基本跑不动。

好了，关于回溯算法就聊到这里。代码示例我都贴出来了，建议你亲手跑一跑，改一改参数，看看效果。嗯，动手实践才是最好的学习方式。

公众号:蓝海资料掘金营，微信deep3321