算法设计与分析4：回溯法 - 0-1背包问题和TSP问题

【算法设计与分析】实验四回溯法 - 0-1背包问题和TSP问题一、实验目的与要求目录一、实验目的与要求二、实验内容三、实验方法四、详细的算法设计及运行结果五、实验感想1. 实验目的理解并掌握回溯法的基本原理深刻认识系统搜索 剪枝优化的算法思想。理解解空间树的概念掌握子集树和排列树两种解空间树的构造方法。能够设计有效的约束函数和限界函数进行剪枝减少不必要的搜索。能应用回溯法解决 0-1 背包问题和 TSP 问题两类经典组合优化问题。2. 实验要求准确理解 0-1 背包问题和 TSP 问题的含义以及解决方法。掌握回溯法的基本原理能灵活运用在上述问题上。能编写出实现回溯法解决 0-1 背包问题和 TSP 问题的代码添加详细注释。对比有无剪枝对搜索效率的影响。分析程序的运行结果并以回溯法的思想解释结果。二、实验内容掌握并能解释 0-1 背包问题和 TSP 问题的含义应用回溯法解决这两个问题。具体包括TSP 旅行商问题在完全图中找到最短的哈密顿回路排列树搜索。0-1 背包问题在容量约束下选择物品使总价值最大化子集树搜索。算法分析对回溯法的搜索策略、剪枝策略和复杂度进行系统分析。三、实验方法学习并深入理解 0-1 背包问题和 TSP 问题的基本概念和应用背景。学习并理解回溯法的基本理论掌握以下核心概念解空间问题所有可能解的集合。解空间树将解空间组织成树形结构便于系统搜索。约束函数Constraint判断当前部分解是否满足问题的约束条件。限界函数Bound判断当前部分解是否有可能优于已知最优解。按照回溯法的理论用 C 编写实现回溯法解决这两个问题的代码。运行程序记录程序的运行结果并反思解决方案的效果以及可能存在的局限性。四、详细的算法设计及运行结果回溯法基本原理核心思想回溯算法的基本思想是从一条路往前走能进则进不能进则退回来换一条路再试。回溯法本质上是一种带有剪枝优化的深度优先搜索DFS。它在解空间树中从根结点出发深度优先搜索当探索到某一结点时若该结点满足约束条件且有可能产生更优解通过限界函数判断则继续向下搜索若该结点不满足约束条件或不可能产生更优解则剪枝Pruning回溯到父结点换一条路径继续搜索。回溯法的一般步骤步骤操作说明①定义解空间明确问题的所有可能解②组织解空间树构建子集树或排列树③深度优先搜索从根结点开始DFS遍历④约束剪枝不满足约束条件的分支直接剪掉⑤限界剪枝不可能优于已知最优解的分支直接剪掉⑥记录最优解到达叶结点时更新最优解两种解空间树类型适用问题树的结构叶结点数典型应用子集树从 n 个元素中选择子集每个结点有2个子结点选/不选2ⁿ0-1背包问题排列树求 n 个元素的排列第i层结点有**(n-i)个**子结点n!TSP问题Part 1利用回溯法编程求解TSP问题问题描述给定 n 个城市和一个 n×n 的代价矩阵cost[i][j]表示从城市 i 到城市 j 的距离求从城市 1 出发经过所有城市恰好一次后返回城市 1 的最短回路。解空间树分析对于n4的 TSP 问题从城市 0 出发其解空间树为排列树城市0(起点) / | \ 1 2 3 ← 第1层选择 / \ / \ / \ 2 3 1 3 1 2 ← 第2层选择 | | | | | | 3 2 3 1 2 1 ← 第3层叶结点 ↓ ↓ ↓ ↓ ↓ ↓ →0 →0 →0 →0 →0 →0 ← 返回起点 路径示例: 0→1→2→3→0 0→1→3→2→0 ... 可能解数: (n-1)! 3! 6 种树中的6 个叶子结点分别代表该问题的 6 个可能解。算法搜索至任一结点时先判断该结点是否有可能包含最优解当前路径长度 已知最优长度若当前路径已经超过最优解则剪枝无需继续往下搜索。剪枝策略剪枝条件当前路径长度 c cost[u][i] ≥ 当前最优解 best 含义如果从起点走到当前城市u再走到下一个城市i的累计距离 已经 ≥ 已找到的最短回路长度则这条路不可能产生更优解 直接剪掉该分支。实验数据使用 4 个城市的非对称距离矩阵城市0城市1城市2城市3城市0∞367城市15∞23城市264∞2城市3375∞实验代码#includebits/stdc.husingnamespacestd;constintinf1e9;// 表示不可达constintN4;// 矩阵intcost[N][N]{{inf,3,6,7},{5,inf,2,3},{6,4,inf,2},{3,7,5,inf}};intbestinf;vectorintbest_p;vectorintcurr_p;vectorboolvis(N);intpruneCount0;voiddfs(intu,intcnt,intc){// 递归终止if(cntNcost[u][0]!inf){// 如果最后一个城市能返回起点且总代价更小if(ccost[u][0]best){bestccost[u][0];// 更新最优值best_pcurr_p;// 保存当前路径best_p.push_back(0);// 添加返回起点}return;}// 尝试访问每一个未被访问的城市for(inti0;iN;i){if(!vis[i]cost[u][i]!inf){// 【关键剪枝】如果当前累计代价加上到城市i的代价已经 ≥ 最优解// 则这条路不可能产生更优解直接跳过if(ccost[u][i]best){vis[i]true;// 标记城市i为已访问curr_p.push_back(i);// 将城市i加入当前路径dfs(i,cnt1,ccost[u][i]);// 递归搜索vis[i]false;curr_p.pop_back();}else{pruneCount;// 统计剪枝次数}}}}intmain(){vis[0]true;// 标记起点为已访问curr_p.push_back(0);// 将起点加入路径dfs(0,1,0);// 开始搜索// 输出结果cout最小路径代价bestendl;cout最优路径;for(inti0;ibest_p.size();i){cout(best_p[i]1);// 城市编号从1开始显示if(ibest_p.size()-1)cout - ;}coutendl;cout剪枝次数pruneCountendl;return0;}运行结果#### 搜索过程详解 以下展示回溯法的完整搜索过程从城市0出发第1步从城市0出发尝试去城市1代价3第2步从城市1出发尝试去城市2代价2累计5第3步从城市2出发尝试去城市3代价2累计7到达叶结点0→1→2→3→0总代价 7 cost[3][0] 7 3 10更新最优解 best 10 ✅回溯到城市2回溯到城市1第2步从城市1出发尝试去城市3代价3累计6第3步从城市3出发尝试去城市2代价5累计1111 ≥ best(10)剪枝❌回溯到城市3回溯到城市1回溯到城市0第1步从城市0出发尝试去城市2代价6第2步从城市2出发尝试去城市1代价4累计1010 ≥ best(10)剪枝❌第2步从城市2出发尝试去城市3代价2累计8第3步从城市3出发尝试去城市1代价7累计1515 ≥ best(10)剪枝❌回溯回溯… 通过剪枝原本需要搜索 (4-1)! 6 条完整路径实际只完整搜索了部分路径大幅提高了效率。Part 2利用回溯法解决0-1背包问题问题描述给定 n 个物品和一个容量为 C 的背包。第 i 个物品的重量为w[i]价值为v[i]。每个物品只能选择装入或不装入不能分割要求在不超过背包容量的前提下使得装入物品的总价值最大。解空间树分析对于 n5 的 0-1 背包问题解空间树为子集树每一层代表一个物品的决策选(1) 或 不选(0)叶结点总数 2⁵ 32 种可能的组合每个叶结点对应一个解向量 x (x[0], x[1], …, x[4])剪枝策略详解回溯法在0-1背包问题中采用两种剪枝策略剪枝类型条件含义约束剪枝左子树cur_w w[i] C装入物品i后超重不能选择限界剪枝右子树cur_v remain_v ≤ best_v即使剩余物品全选也不如已知最优解实验数据实验代码#includebits/stdc.husingnamespacestd;constintn5;intbag_v0;intbag_w10;intbag[n],x[n];intw[n]{2,2,6,5,4};intval[n]{6,3,5,4,6};voidsearch(intcur,intcur_v,intcur_w){if(curn){if(cur_vbag_v){bag_vcur_v;for(inti0;in;i){bag[i]x[i];}}return;}if(cur_ww[cur]bag_w){cur_ww[cur];cur_vval[cur];x[cur]1;search(cur1,cur_v,cur_w);// 回溯cur_w-w[cur];cur_v-val[cur];}x[cur]0;search(cur1,cur_v,cur_w);}intmain(){search(0,0,0);cout最大价值为:endl;coutbag_vendl;cout解空间为endl;for(inti0;in;i){coutbag[i] ;}return0;}运行结果5. 算法效率分析TSP问题排列树项目分析最坏时间复杂度O(n!) — 需要遍历排列树的所有叶结点平均时间复杂度通过剪枝显著优于 O(n!)具体取决于数据空间复杂度O(n) — 递归栈深度为 n加上路径数组剪枝效果早期找到较优解后剪枝效果越来越好0-1背包问题子集树项目分析最坏时间复杂度O(2ⁿ) — 需要遍历子集树的所有叶结点平均时间复杂度通过限界剪枝和约束剪枝远优于 O(2ⁿ)空间复杂度O(n) — 递归栈深度为 n加上解向量限界剪枝优化将物品按单位价值降序排列后剪枝效果更佳剪枝效率对比问题无剪枝搜索结点数有剪枝搜索结点数剪枝效率TSP (n4)16约 10~37.5%0-1背包 (n5)631773%结论好的剪枝函数可以将指数级的搜索空间大幅缩减使回溯法在实际应用中具有可行性。6. 回溯法 vs 贪心法 vs 动态规划维度回溯法贪心法动态规划搜索策略DFS 剪枝逐步贪心选择自底向上递推最优性✅ 保证全局最优❌ 不一定最优✅ 保证全局最优时间复杂度指数级O(2ⁿ) 或 O(n!)多项式级伪多项式级空间复杂度O(n) 递归栈O(1) ~ O(n)O(nW)适用场景组合优化、约束满足满足贪心性质的问题具有最优子结构和重叠子问题核心技术剪枝函数贪心选择策略状态转移方程是否回溯✅ 是❌ 否❌ 否同一问题的不同算法对比以0-1背包为例算法时间复杂度空间复杂度是否最优特点暴力枚举O(2ⁿ)O(n)✅遍历所有子集效率最低回溯法O(2ⁿ)最坏O(n)✅通过剪枝大幅优化动态规划O(nW)O(nW)✅伪多项式W大时效率低贪心法O(n log n)O(n)❌适用于分数背包0-1背包不保证最优五、实验感想在本次实验中通过回溯法实现0-1背包与TSP旅行商问题的求解我掌握了回溯法中深度优先搜索和剪枝优化的核心思想。相较于暴力枚举回溯法通过约束条件剔除无效解降低时间复杂度。实验中我发现0-1背包是子集树时间复杂度为O2nTSP是排列树时间复杂度为On。本次实验中我掌握了深度优先搜索算法以及剪枝函数的确立。回溯法的精髓 回溯法的精髓在于“试探与回退”——沿着一条路深入搜索遇到不满足条件的分支及时剪枝回退避免无效计算。