1. 从“最优旅行”到算法竞赛一道经典图论题的实战拆解最近在整理历年算法竞赛的真题时我又翻到了第十届蓝桥杯Java B组国赛的这道“最优旅行”。题目名字听起来挺生活化但内核却是一个经典的图论优化问题。很多刚接触算法竞赛的同学一看到“最优”、“旅行”这类字眼可能会下意识地想到动态规划或者贪心但实际一上手往往会在数据规模、状态定义和路径搜索上栽跟头。这道题就是一个很好的例子它考察的不仅仅是你会不会某个算法更是考察你能否在复杂的约束条件下正确地建模、选择算法并高效实现。今天我就结合自己带学生备赛和打比赛的经验把这题的“里子”和“面子”都拆开来讲讲手把手带你走一遍从理解题意到ACAccepted的全过程。这道题本质上是一个带约束的最短路径问题。旅行者需要在多个城市间移动每个城市有“游览价值”路径有“通行成本”目标很可能是在总成本如时间、花费有限的前提下最大化总游览价值或者是在收集一定价值的前提下最小化总成本。这立刻就把我们带入了图论建模的领域城市是顶点路径是边成本和价值是边的权重或顶点的属性。而“最优”二字则引入了最优化的目标。处理这类问题单纯的Dijkstra或Floyd可能就不够用了往往需要结合状态压缩、动态规划DP或者搜索剪枝。接下来我们就一步步拆解。2. 题目场景还原与核心问题抽象虽然原题的具体描述需要查阅官方赛题但根据“最优旅行”这个标题和蓝桥杯国赛的难度定位我们可以合理还原出一个典型的赛题场景。这有助于我们脱离具体数字先把握问题的本质结构。通常这类题目会给出以下要素N个城市编号从0到N-1或者从1到N。起点和终点可能固定比如总是从0号城市出发也可能需要计算。城市属性每个城市有一个“游览价值”或“评分”记为value[i]。城市间的连接通过一个矩阵或边列表给出表示城市之间是否有直接通路以及通行的“成本”记为cost[i][j]。成本可能是时间、距离或金钱。约束条件这是关键。常见的有两种预算成本约束总旅行成本不能超过一个上限MAX_COST。价值目标约束必须收集至少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需要包含至少两个信息当前位于哪个城市current_city。目前已经获得的总价值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 关键细节与陷阱时间与价值的取舍我们的dfs函数返回的是“未来价值”所以在主函数中需要加上起点的价值。务必理清这个逻辑。状态压缩的表示1 city是得到只有该城市位为1的掩码。visited mask用于检查visited | mask用于添加。记忆化数组的维度memo[i][visited]的大小是N * 2^N。当N20时2^20 ≈ 1e6N * 2^N ≈ 2e7这个数组在内存上假设是int类型大约80MB在Java中可能接近极限或导致OutOfMemoryError。这是此类题目的一个经典陷阱蓝桥杯的题目通常会将N限制在15左右2^1532768使得状态数在可接受范围内约50万。如果N真的到20可能需要更优的DP写法或剪枝。不可达与溢出将INF设置为Integer.MAX_VALUE/2是一个好习惯防止在cost[a][b] cost[b][c]时加法溢出变成负数。访问顺序我们的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的顺序尝试。可以按照某种启发式顺序比如优先尝试价值高、或者距离成本低的城市。这样更有机会快速找到一个较好的解从而让最优性剪枝更早生效。// 预处理将未访问的城市按照价值降序排序需要额外数组存储索引 ListInteger 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[1N][N]; for (int[] row : dp) Arrays.fill(row, INF); dp[1start][start] 0; // 初始化在起点只访问了起点成本0 // 遍历所有状态mask for (int mask 0; mask (1N); mask) { for (int i 0; i N; i) { if (dp[mask][i] INF) continue; // 状态不可达 if ((mask (1i)) 0) continue; // 当前城市i必须在mask中 // 尝试从i走到下一个未访问的城市j for (int j 0; j N; j) { if ((mask (1j)) ! 0) continue; // j未访问 if (cost[i][j] INF) continue; // 有通路 int newMask mask | (1j); dp[newMask][j] Math.min(dp[newMask][j], dp[mask][i] cost[i][j]); } } } // 最终答案在所有城市都访问过的状态中找即mask (1N)-1这种DP写法避免了递归的开销和栈深度的限制思维上更直接但需要仔细设计循环顺序和状态转移。对于“最优旅行”这类问题DP写法往往是标准解法。6. 常见变种与举一反三“最优旅行”模型非常灵活这里列举几个常见变种帮助你巩固对这个模型的理解变种一必须访问所有城市TSP变种题目可能要求访问所有城市每个城市价值为1并回到起点在最小化总成本的同时可能还有一个额外的价值目标。这时状态(city, visited)中的visited会逐渐变为全1。我们的目标可能是min(dp[(1N)-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. 调试技巧与赛场策略在竞赛中实现这类题目调试是关键。以下是一些实用技巧小数据验证自己构造一个N3或4的样例手工计算出答案然后用你的程序跑看结果是否一致。这是检验算法逻辑最直接的方法。打印中间状态在DFS或DP的关键步骤打印出状态变量如curCity,visited,remainingTime,currentValue观察状态转移是否符合预期。对于记忆化搜索可以打印memo数组被填充的情况。边界条件测试测试M0无法移动、N1只有一个城市、所有城市价值为0、成本矩阵全为INF不连通等情况确保程序不会崩溃或输出错误结果。复杂度估算在编码前估算一下状态数量和时间复杂度。例如状态压缩DP的复杂度通常是O(2^N * N^2)。如果N202^20 * 400 ≈ 4e8在2秒的时限内可能很悬。这时就要考虑是否有优化空间或者题目数据是否保证N较小。赛场策略看到这类题不要急于编码。先花5-10分钟在草稿纸上完成问题抽象、状态定义和转移方程。如果思路清晰DP的代码框架其实很固定。如果思路卡壳先写一个暴力搜索DFS版本确保能过小数据点再逐步加入记忆化或优化成DP。在蓝桥杯的系统中有时暴力搜索也能拿到一部分分数。这道“最优旅行”题浓缩了图论、状态压缩、动态规划/记忆化搜索等多个核心算法知识点。它不像单纯的模板题需要你根据具体描述灵活地建模和设计状态。通过这道题的深入剖析我希望你掌握的不仅仅是一道题的解法而是应对一整类“带约束的图优化问题”的思考框架。下次再遇到“在XX限制下找YY最优路径”的问题不妨先想想状态该怎么定义维度有哪些是搜索剪枝还是直接DP多练习几次这种思维就会成为你的本能。