蓝桥杯国赛“最优旅行”题解：图论约束优化与状态压缩DP实战

1. 从“最优旅行”到算法竞赛：一道经典图论题的实战拆解

最近在整理历年算法竞赛的真题时，我又翻到了第十届蓝桥杯Java B组国赛的这道“最优旅行”。题目名字听起来挺生活化，但内核却是一个经典的图论优化问题。很多刚接触算法竞赛的同学，一看到“最优”、“旅行”这类字眼，可能会下意识地想到动态规划或者贪心，但实际一上手，往往会在数据规模、状态定义和路径搜索上栽跟头。这道题就是一个很好的例子，它考察的不仅仅是你会不会某个算法，更是考察你能否在复杂的约束条件下，正确地建模、选择算法并高效实现。今天，我就结合自己带学生备赛和打比赛的经验，把这题的“里子”和“面子”都拆开来讲讲，手把手带你走一遍从理解题意到AC（Accepted）的全过程。

这道题本质上是一个带约束的最短路径问题。旅行者需要在多个城市间移动，每个城市有“游览价值”，路径有“通行成本”，目标很可能是在总成本（如时间、花费）有限的前提下，最大化总游览价值，或者是在收集一定价值的前提下，最小化总成本。这立刻就把我们带入了图论建模的领域：城市是顶点，路径是边，成本和价值是边的权重或顶点的属性。而“最优”二字，则引入了最优化的目标。处理这类问题，单纯的Dijkstra或Floyd可能就不够用了，往往需要结合状态压缩、动态规划（DP）或者搜索剪枝。接下来，我们就一步步拆解。

2. 题目场景还原与核心问题抽象

虽然原题的具体描述需要查阅官方赛题，但根据“最优旅行”这个标题和蓝桥杯国赛的难度定位，我们可以合理还原出一个典型的赛题场景。这有助于我们脱离具体数字，先把握问题的本质结构。

通常，这类题目会给出以下要素：

• N个城市：编号从0到N-1，或者从1到N。起点和终点可能固定（比如总是从0号城市出发），也可能需要计算。
• 城市属性：每个城市有一个“游览价值”或“评分”，记为value[i]。
• 城市间的连接：通过一个矩阵或边列表给出，表示城市之间是否有直接通路，以及通行的“成本”，记为cost[i][j]。成本可能是时间、距离或金钱。
• 约束条件：这是关键。常见的有两种：
  1. 预算（成本）约束：总旅行成本不能超过一个上限MAX_COST。
  2. 价值（目标）约束：必须收集至少TARGET_VALUE的总游览价值。
• 优化目标：在满足约束的前提下，最大化总游览价值，或者最小化总旅行成本。

例如，一个可能的抽象描述是：“旅行者从城市0出发，希望访问若干城市（可重复访问？通常不允许，除非特别说明），最终回到城市0。每个城市i有一个评分S[i]，城市i到j需要耗时T[i][j]。计划总时间不超过M天。求在不超过M天的前提下，能够获得的最大总评分之和。”

为什么这样抽象很重要？因为算法竞赛题千变万化，但核心模型就那么几十个。看到“最优旅行”，你脑子里应该立刻弹出几个备选模型：**旅行商问题（TSP）**的变种、背包问题与图论的结合（常称为“图背包”）、带权图上的搜索。准确的抽象是选择正确算法的第一步。

注意：蓝桥杯的题目有时会强调“B组”，这意味着相比A组（更偏重算法设计与优化），B组可能更注重基础数据结构、逻辑实现和小心审题。但国赛级别，对B组的要求也绝对不低，图论DP是常客。

3. 算法选型分析：为什么不是简单的最短路径？

面对“旅行”和“最优”，新手最容易犯的错误就是直接套用标准最短路径算法。我们来分析一下为什么这通常行不通。

假设我们直接使用Dijkstra算法求从起点到所有点的最短路径（最小成本）。它只能告诉我们“从起点到某个城市i的最小成本是多少”。但我们的目标很可能不是仅仅到达某个城市，而是要在途中积累价值。Dijkstra算法在扩展状态时，只记录到达每个顶点的最小成本这一个维度，而丢弃了其他可能成本稍高但积累了更多价值的路径。然而，这些“成本稍高”的路径可能在后续访问其他城市时，因为提前积累了价值，反而能在总成本约束下达成更优的总价值。因此，单一维度的状态（最小成本）不足以表征问题的全部信息。

Floyd算法计算所有点对之间的最短路径，但它同样只关心成本，不关心价值积累的过程。它无法处理“访问顺序影响结果”这类需要记录路径历史的问题。

那么，什么算法可以处理这种多维度约束的优化问题呢？核心思路是：我们需要扩展状态的定义。

状态（State）需要包含至少两个信息：

1. 当前位于哪个城市（current_city）。
2. 目前已经获得的总价值（current_value）或者已经花费的总成本（current_cost）。

这样，我们的问题就变成了：在这个扩展的状态空间里，找到一条从初始状态（起点，价值0或成本0）到某个目标状态（如任意城市，价值>=目标 或 成本<=预算）的“最优”路径。

这引出了两种主流的解法思路：

思路一：动态规划（DP）我们可以定义dp[i][j]：表示当前在城市i，并且已经获得的总价值为j时，所花费的最小成本。或者定义dp[i][c]：表示当前在城市i，已经花费成本为c时，所能获得的最大价值。具体哪个作为维度，取决于约束条件和数据范围。如果价值总和V不大，就用价值作为一维；如果成本上限C不大，就用成本作为一维。然后进行状态转移：dp[next_city][new_value] = min(dp[next_city][new_value], dp[current_city][current_value] + cost[current][next])。这本质上是一个在图上进行的DP，类似于“分层图”的思想。

思路二：搜索与剪枝（DFS/BFS）直接进行深度优先搜索（DFS），状态就是(当前城市，当前价值，当前成本)。通过递归遍历所有可能的路径。但纯搜索的复杂度是指数级的，必须进行强力剪枝：

• 最优性剪枝：如果当前成本已经超过历史最优解的成本（或当前价值已经低于历史最优解的价值），则放弃该分支。
• 可行性剪枝：如果当前成本已经超过总预算MAX_COST，则放弃。
• 记忆化搜索（Memoization）：这是将搜索和DP结合的关键。我们可以用一个数组memo[i][v]记录“在城市i、已获得价值v时的最小成本”。如果在搜索中再次遇到相同的(i, v)状态，且当前成本已经不小于记录中的成本，就可以直接剪枝，因为继续走下去不可能更优。

对于蓝桥杯国赛的数据规模（N通常在15-20，价值或成本总和在几百到几千），记忆化搜索通常是更直观且不易出错的选择，它思维难度低于直接推导DP方程，但通过缓存状态同样达到了DP的效率。

4. 基于记忆化搜索的详细实现与代码剖析

我们以“在总成本限制下最大化价值”为例，采用记忆化搜索（DFS + Memo）来实现。假设题目规定：从城市0出发，最终可以不回到起点，在总时间M内，访问每个城市最多一次（获得其价值S[i]），求最大总价值。

4.1 状态定义与数据结构设计

int N; // 城市数量 int[][] cost; // cost[i][j] 表示从i到j的耗时，INF表示不通 int[] value; // value[i] 表示城市i的评分 int M; // 总时间上限 int[][] memo; // 记忆化数组 // memo[i][visited]：当前在城市i，已访问城市的集合为visited（状态压缩）时，剩余时间还能获得的最大价值。 // 注意：这里用“剩余时间”和“已访问集合”作为状态维度。

这里引入了一个关键技巧：状态压缩。因为N不大（比如<=20），我们可以用一个整数的二进制位来表示城市是否被访问过。例如，visited = 5（二进制101）表示城市0和城市2被访问过。memo[i][visited]的含义是：当我们已经访问了visited集合中的城市，并且当前站在城市i时，从此刻开始，在剩余的时间里，还能获得的最大价值。这样定义有利于递归。

4.2 深度优先搜索（DFS）函数设计

/** * @param curCity 当前所在城市 * @param visited 已访问城市集合（状态压缩） * @param remainingTime 剩余时间 * @return 从当前状态出发，能获得的最大价值 */ private int dfs(int curCity, int visited, int remainingTime) { // 记忆化查询：如果这个状态已经计算过，直接返回 if (memo[curCity][visited] != -1) { return memo[curCity][visited]; } int maxFutureValue = 0; // 记录从当前状态出发，后续能获得的最大价值 // 尝试访问每一个未访问过的城市next for (int nextCity = 0; nextCity < N; nextCity++) { // 检查：1. 是否未访问过？ 2. 是否有通路？ 3. 时间去得到吗？ if ((visited & (1 << nextCity)) == 0 // nextCity未访问 && cost[curCity][nextCity] != INF // 有通路 && cost[curCity][nextCity] <= remainingTime) { // 时间够去 // 访问nextCity int newVisited = visited | (1 << nextCity); int timeSpent = cost[curCity][nextCity]; // 获得nextCity的价值，并继续搜索 int futureValue = value[nextCity] + dfs(nextCity, newVisited, remainingTime - timeSpent); maxFutureValue = Math.max(maxFutureValue, futureValue); } } // 记录当前状态的结果 memo[curCity][visited] = maxFutureValue; return maxFutureValue; }

递归的终止条件隐含在循环中：如果当前状态下，没有下一个城市可以访问（要么都访问过了，要么时间不够去任何未访问城市），那么maxFutureValue将保持为0，递归自然结束。

4.3 初始化与启动

// 初始化记忆化数组为-1，表示未计算 memo = new int[N][1 << N]; // 状态数：N * 2^N for (int i = 0; i < N; i++) { Arrays.fill(memo[i], -1); } // 初始化cost矩阵，自身到自身为0，不可达为INF(例如Integer.MAX_VALUE/2防止加法溢出) // 赋值value数组和总时间M // 开始搜索，从城市0出发，已访问集合只包含城市0（如果城市0有价值，需预先加上），剩余时间为M int startVisited = 1 << 0; // 二进制第0位设为1 // 注意：如果起点城市0的价值也算，则初始价值为value[0]，然后搜索剩余部分。 // 这里假设dfs返回的是“从当前状态开始能获得的价值”，则总价值 = value[0] + dfs(0, startVisited, M); int totalValue = value[0] + dfs(0, startVisited, M - 0); // 假设从0出发不需要时间，如果需要则减去 System.out.println(totalValue);

4.4 关键细节与陷阱

1. 时间与价值的取舍：我们的dfs函数返回的是“未来价值”，所以在主函数中需要加上起点的价值。务必理清这个逻辑。
2. 状态压缩的表示：1 << city是得到只有该城市位为1的掩码。visited & mask用于检查，visited | mask用于添加。
3. 记忆化数组的维度：memo[i][visited]的大小是N * 2^N。当N=20时，2^20 ≈ 1e6，N * 2^N ≈ 2e7，这个数组在内存上（假设是int类型）大约80MB，在Java中可能接近极限或导致OutOfMemoryError。这是此类题目的一个经典陷阱！蓝桥杯的题目通常会将N限制在15左右（2^15=32768），使得状态数在可接受范围内（约50万）。如果N真的到20，可能需要更优的DP写法或剪枝。
4. 不可达与溢出：将INF设置为Integer.MAX_VALUE/2是一个好习惯，防止在cost[a][b] + cost[b][c]时加法溢出变成负数。
5. 访问顺序：我们的DFS隐含了访问顺序。题目如果允许重复访问，状态定义中就不能用visited集合，而需要用“剩余时间”和“当前城市”作为状态，可能还需要考虑重复访问的价值获取规则（通常重复访问不重复获得价值），这会更复杂，可能需要用dp[time][city]来表示在某个时间点位于某个城市获得的最大价值。

5. 性能优化与剪枝策略实战

当N较大或者约束条件更复杂时，朴素的记忆化搜索可能依然会超时。我们需要额外的剪枝策略来提前终止无效分支。

5.1 最优性剪枝的强化在DFS递归前，我们可以先计算一个“乐观估计”。例如，计算所有未访问城市的价值之和。如果当前已获价值 + 所有未访问城市价值之和 <= 当前记录的历史最优价值，那么即使后面完美实现，也不可能超越最优解，可以立即剪枝。这需要预处理城市价值并按降序排序，以便快速计算剩余最大可能价值。

5.2 状态表示的优化如果题目要求最终回到起点，那么状态(city, visited)可能是不够的。因为从A点到B点，和从B点回到A点，即使visited集合相同，后续的可行性也不同（例如，从B可能无法回到起点）。但通常蓝桥杯的题目会简化，不要求回起点，或者将问题转化为从起点出发访问所有点再回来的TSP问题（此时状态是(city, visited)，目标是求visited为全1时，回到起点的最小成本，价值可能作为另一个维度或目标）。

5.3 搜索顺序的优化在for循环尝试下一个城市nextCity时，不要简单地按0到N-1的顺序尝试。可以按照某种启发式顺序，比如优先尝试价值高、或者距离（成本）低的城市。这样更有机会快速找到一个较好的解，从而让最优性剪枝更早生效。

// 预处理，将未访问的城市按照价值降序排序（需要额外数组存储索引） List<Integer> candidates = new ArrayList<>(); for (int i = 0; i < N; i++) { if ((visited & (1 << i)) == 0) candidates.add(i); } candidates.sort((a, b) -> Integer.compare(value[b], value[a])); // 降序 for (int nextCity : candidates) { // ... 尝试访问nextCity }

5.4 记忆化与DP的等价思考我们的记忆化搜索dfs(curCity, visited)，其实等价于填充一个DP表dp[visited][curCity]。dfs是自顶向下的递归填充，而我们可以用循环自底向上地填充这个DP表。通常，对于状态压缩DP，我们按照visited集合的大小（即已访问城市数量）进行递推会更自然。例如：

// dp[mask][i] 表示已访问城市集合为mask，当前在城市i，所花费的最小成本（或获得的最大价值） int[][] dp = new int[1<<N][N]; for (int[] row : dp) Arrays.fill(row, INF); dp[1<<start][start] = 0; // 初始化，在起点，只访问了起点，成本0 // 遍历所有状态mask for (int mask = 0; mask < (1<<N); mask++) { for (int i = 0; i < N; i++) { if (dp[mask][i] == INF) continue; // 状态不可达 if ((mask & (1<<i)) == 0) continue; // 当前城市i必须在mask中 // 尝试从i走到下一个未访问的城市j for (int j = 0; j < N; j++) { if ((mask & (1<<j)) != 0) continue; // j未访问 if (cost[i][j] == INF) continue; // 有通路 int newMask = mask | (1<<j); dp[newMask][j] = Math.min(dp[newMask][j], dp[mask][i] + cost[i][j]); } } } // 最终答案在所有城市都访问过的状态中找，即mask = (1<<N)-1

这种DP写法避免了递归的开销和栈深度的限制，思维上更直接，但需要仔细设计循环顺序和状态转移。对于“最优旅行”这类问题，DP写法往往是标准解法。

6. 常见变种与举一反三

“最优旅行”模型非常灵活，这里列举几个常见变种，帮助你巩固对这个模型的理解：

变种一：必须访问所有城市（TSP变种）题目可能要求访问所有城市（每个城市价值为1），并回到起点，在最小化总成本的同时，可能还有一个额外的价值目标。这时状态(city, visited)中的visited会逐渐变为全1。我们的目标可能是min(dp[(1<<N)-1][i] + cost[i][start])，即在所有城市都访问完后，从任意城市i回到起点的最小总成本。如果还有价值维度，就需要三维DPdp[mask][i][v]。

变种二：资源收集（图背包问题）每个城市有价值value[i]和“访问成本”time[i]（停留在城市的时间），城市间移动有成本cost[i][j]。总预算为M。求最大化总价值。这更像一个背包问题，但物品（城市）的获取有顺序依赖（移动成本）。此时状态可以设计为dp[i][c]：当前在城市i，总花费成本为c时获得的最大价值。转移时，既可以考虑从城市i移动到j（花费移动成本），也可以考虑停留在i收集价值（花费停留成本，可能允许多次停留？需看题意）。这通常需要更复杂的状态定义和转移。

变种三：多目标优化题目可能要求同时优化两个目标，比如“在时间不超过M的前提下，最大化价值；如果价值相同，则最小化时间”。这需要在状态中同时维护价值和成本，并在比较解时制定优先级规则。或者使用分数规划或二分答案的思路，将多目标转化为单目标。例如，我们二分一个“性价比”比值λ，检查是否存在一条路径，使得总价值 - λ * 总成本 >= 0，从而将问题转化为判断是否存在满足条件的路径。

如何应对未知变种？核心永远是：仔细审题，明确状态维度。问自己几个问题：1. 什么信息决定了后续的选择？（当前城市、已获价值、已花成本、已访问集合…）2. 决策是什么？（下一步去哪里？是否在当前城市停留？）3. 目标是什么？（最大/最小化什么？）把答案抽象出来，状态的定义就出来了。

7. 调试技巧与赛场策略

在竞赛中实现这类题目，调试是关键。以下是一些实用技巧：

1. 小数据验证：自己构造一个N=3或4的样例，手工计算出答案，然后用你的程序跑，看结果是否一致。这是检验算法逻辑最直接的方法。
2. 打印中间状态：在DFS或DP的关键步骤，打印出状态变量（如curCity,visited,remainingTime,currentValue），观察状态转移是否符合预期。对于记忆化搜索，可以打印memo数组被填充的情况。
3. 边界条件测试：测试M=0（无法移动）、N=1（只有一个城市）、所有城市价值为0、成本矩阵全为INF（不连通）等情况，确保程序不会崩溃或输出错误结果。
4. 复杂度估算：在编码前，估算一下状态数量和时间复杂度。例如，状态压缩DP的复杂度通常是O(2^N * N^2)。如果N=20，2^20 * 400 ≈ 4e8，在2秒的时限内可能很悬。这时就要考虑是否有优化空间，或者题目数据是否保证N较小。
5. 赛场策略：看到这类题，不要急于编码。先花5-10分钟在草稿纸上完成问题抽象、状态定义和转移方程。如果思路清晰，DP的代码框架其实很固定。如果思路卡壳，先写一个暴力搜索（DFS）版本，确保能过小数据点，再逐步加入记忆化或优化成DP。在蓝桥杯的系统中，有时暴力搜索也能拿到一部分分数。

这道“最优旅行”题，浓缩了图论、状态压缩、动态规划/记忆化搜索等多个核心算法知识点。它不像单纯的模板题，需要你根据具体描述灵活地建模和设计状态。通过这道题的深入剖析，我希望你掌握的不仅仅是一道题的解法，而是应对一整类“带约束的图优化问题”的思考框架。下次再遇到“在XX限制下找YY最优路径”的问题，不妨先想想：状态该怎么定义？维度有哪些？是搜索+剪枝还是直接DP？多练习几次，这种思维就会成为你的本能。