【算法设计与分析】实验三贪心法 - 最短路径问题TSP目录一、实验目的与要求1. 实验目的2. 实验要求二、实验内容三、实验方法四、详细的算法设计及运行结果1. 贪心法基本原理贪心法的核心步骤贪心法的适用条件2. TSP问题的贪心法求解问题描述贪心策略最近邻点法算法流程详解实验数据实验代码运行结果结果分析3. 算法效率分析时间复杂度分析空间复杂度分析4. 算法的特色与局限性算法特色算法局限性五、实验感想贪心法的核心思想总结贪心法的优缺点贪心法 vs 动态规划 vs 回溯法贪心法的经典应用场景一、实验目的与要求1. 实验目的理解并掌握贪心法的基本原理与核心思想深刻认识局部最优导向全局最优的算法策略。能够灵活运用贪心法解决最短路径及TSP旅行商等经典问题。通过与动态规划、回溯法的对比深入理解贪心法的适用条件与局限性。2. 实验要求准确理解最短路径问题和TSP问题的含义掌握多种求解策略。掌握贪心法的贪心选择性质和最优子结构性质判断问题是否适合使用贪心法。能编写出正确实现贪心法解决最短路径问题的代码并添加详细注释。分析程序的运行结果进行多组测试数据的对比验证。对算法的时间复杂度和空间复杂度进行理论分析。二、实验内容在本实验中需要理解并实现贪心法的基本原理并将其运用在最短路径问题中。具体包括TSP旅行商问题使用贪心法的最近邻点策略求解从某一城市出发经过所有城市恰好一次最后回到出发城市的最短路径。算法分析对贪心法的正确性、复杂度和局限性进行系统分析。三、实验方法学习并深入理解最短路径问题的基本概念和应用背景物流规划、电路布线等。学习并理解贪心法的基本理论掌握贪心法的两个核心性质贪心选择性质每一步都做出当前最优的选择。最优子结构性质问题的最优解包含子问题的最优解。按照贪心法的理论用 C 编写实现贪心法解决 TSP 问题的代码。运行程序记录程序的运行结果分析不同起点对结果的影响并反思解决方案的效果以及可能存在的局限性。四、详细的算法设计及运行结果1. 贪心法基本原理贪心算法Greedy Algorithm是一种在每一步选择中都采取当前状态下最优即最有利的选择从而希望导致结果是全局最优的算法策略。贪心法的核心步骤步骤描述① 选择初始状态确定算法的起点初始化相关数据结构② 应用贪心选择在当前状态下选择一个局部最优的动作③ 可行性检查判断当前选择是否满足问题的约束条件④ 更新状态根据贪心选择的结果更新当前状态⑤ 结束条件检查是否达到算法的结束条件若未结束则回到步骤②贪心法的适用条件关键定理一个问题能用贪心法求得最优解必须同时满足以下两个性质贪心选择性质问题的整体最优解可以通过一系列局部最优的选择来达到。最优子结构性质问题的最优解包含其子问题的最优解。2. TSP问题的贪心法求解问题描述给定 n 个城市及它们之间的距离矩阵从某个城市出发经过每个城市恰好一次后返回出发城市要求总路径长度最短。TSP精确求解的时间复杂度为 O(n!)在城市数量较大时不可行。贪心法通过牺牲最优性来换取较低的计算复杂度。贪心策略最近邻点法核心思想从起点出发每次选择距离当前城市最近且未被访问过的城市作为下一个访问目标直到所有城市都被访问最后返回起点。算法流程详解┌────────────────────────────────┐ │ 开始选择起点s │ │ 标记s为已访问 │ │ 当前城市 u s │ │ 总距离 sum 0 │ └──────────────┬─────────────────┘ ↓ ┌──────────────────────────────────┐ │ 遍历所有城市j (j 0 to n-1) │ │ 找到未访问且距离u最近的城市v │ │ min_dist min(A[u][j]) │ └──────────────┬───────────────────┘ ↓ ┌───────┴───────┐ │ 是否找到城市v │ └───────┬───────┘ 是 ↓ 否 ↓ ┌───────────────┐ ┌──────────────────┐ │ sum min_dist│ │ 所有城市已访问 │ │ 标记v为已访问 │ │ sum A[u][s] │ │ u v │ │ 输出路径和总长度 │ │ 返回上方循环 │ │ 结束 │ └───────────────┘ └──────────────────┘实验数据使用 5 个城市的距离矩阵进行测试城市0城市1城市2城市3城市4城市0∞3326城市13∞732城市237∞25城市3232∞3城市46253∞实验代码#includeiostreamusingnamespacestd;constintinf10000;// 用一个大数表示不可达即无穷大constintn5;// 城市的数量/** 算法思想 1. 从起点出发标记为已访问 2. 每次在未访问的城市中选择距离当前城市最近的城市 3. 移动到该城市标记为已访问 4. 重复步骤2-3直到所有城市都被访问 5. 最后从最后一个城市返回起点 */voidfindTSP(intA[n][n],intstart){boolvisited[n]{false};// 记录每个城市是否被访问过intsum0;// 记录路径总长度intustart;// 当前所在的城市visited[u]true;// 标记起点为已访问cout路径u;// 需要再访问 n-1 个城市for(inti0;in-1;i){intmininf;// 记录到未访问城市的最短距离intv-1;// 记录最近的未访问城市编号// 遍历所有城市查找距离当前城市最近的未访问城市for(intj0;jn;j){if(!visited[j]A[u][j]min){minA[u][j];// 更新最短距离vj;// 更新最近城市编号}}// 贪心选择移动到最近的未访问城市summin;// 累加路径长度visited[v]true;// 标记该城市为已访问cout-v;uv;// 更新当前城市}// 从最后一个城市返回起点形成回路sumA[u][start];cout-start\n;cout总长度sumendl;}intmain(){// 5个城市的对称距离矩阵intdist[n][n]{{inf,3,3,2,6},// 城市0到各城市的距离{3,inf,7,3,2},// 城市1到各城市的距离{3,7,inf,2,5},// 城市2到各城市的距离{2,3,2,inf,3},// 城市3到各城市的距离{6,2,5,3,inf}// 城市4到各城市的距离};for(inti0;in;i){cout起点 i: ;findTSP(dist,i);coutendl;}return0;}运行结果 不同起点的贪心法TSP结果 起点 0: 路径0-3-2-4-1-0 总长度14 起点 1: 路径1-4-3-2-0-1 总长度14 起点 2: 路径2-3-0-1-4-2 总长度13 起点 3: 路径3-0-1-4-2-3 总长度14 起点 4: 路径4-1-0-3-2-4 总长度14结果分析起点路径总长度是否最优00→3→2→4→1→014近似最优11→4→3→2→0→114近似最优22→3→0→1→4→213✅ 本组最优33→0→1→4→2→314近似最优44→1→0→3→2→414近似最优⚠️关键发现不同的起点会导致不同的贪心路径和总长度。起点2得到的路径总长度为13优于其他起点的14。这充分说明了贪心法得到的解依赖于初始条件不一定能获得全局最优解。3. 算法效率分析时间复杂度分析操作时间复杂度说明外层循环O(n)遍历 n-1 个城市内层查找最近邻点O(n)在 n 个城市中查找最小距离总时间复杂度O(n²)两层循环嵌套 与精确求解 TSP 的 O(n!) 相比贪心法的 O(n²) 复杂度有巨大优势。对于 n20 的情况精确算法需要约 2.4×10¹⁸ 次运算而贪心法仅需 400 次。空间复杂度分析存储项空间复杂度说明距离矩阵 AO(n²)存储 n×n 的邻接矩阵访问标记数组 visitedO(n)记录每个城市是否被访问辅助变量O(1)sum、u、v、min 等总空间复杂度O(n²)主要由距离矩阵决定4. 算法的特色与局限性算法特色思路直观最近邻点策略模拟了人类直觉——“先去最近的地方”算法实现简单清晰。效率极高O(n²) 的时间复杂度使其可以处理大规模城市集合数千个城市而精确算法在几十个城市时就已不可行。贪心选择明确每一步的选择标准唯一且易于实现——选择距离最小的未访问城市。可作为启发式初始解贪心法的结果常作为其他优化算法如模拟退火、遗传算法的初始解。算法局限性不保证最优解贪心法只关注局部最优可能在前期选择了较短的边导致后期被迫选择很长的边尤其是返回起点的那条边。起点敏感性不同起点会得到不同结果如上表所示需要遍历所有起点取最优。无法应用于非对称TSP的改进对于非对称距离矩阵A[i][j] ≠ A[j][i]贪心法的近似比可能更差。理论分析对于满足三角不等式的对称 TSP 问题最近邻点贪心法的近似比上界为 O(log n)即贪心解不超过最优解的 O(log n) 倍。五、实验感想贪心法的核心思想总结贪心法是一种在每一步选择中都采取当前最优解的算法策略通过局部最优期望获得全局最优或近似最优解。它的基本步骤可以归纳为建立数学模型将问题抽象为可量化的形式明确目标函数和约束条件。确定贪心策略找到一个局部最优选择的准则如最近邻、最小权重、最早结束等。逐步构建解按贪心策略逐步选择每一步不可撤回。验证可行性确保每一步的选择满足约束条件。贪心法的优缺点维度优点缺点简单性算法思路直观代码简洁正确性证明往往较复杂效率时间复杂度通常较低多项式级—最优性在满足贪心选择性质的问题中可得最优解不满足条件时只能得到近似解回溯无需回溯决策过程单向一旦做出错误选择无法纠正适用性适用于活动选择、哈夫曼编码、Dijkstra等不适用于0-1背包、TSP精确求解等贪心法 vs 动态规划 vs 回溯法特性贪心法动态规划回溯法决策序列只产生一个决策序列产生多个决策序列产生多个决策序列求解方向自顶向下求解自底向上求解深度优先搜索最优性保证不一定全局最优✅ 保证全局最优✅ 保证全局最优时间复杂度通常最低中等通常最高空间复杂度通常最低需要存储子问题的解需要递归栈空间是否回溯❌ 不回溯❌ 不回溯✅ 需要回溯贪心法的经典应用场景问题贪心策略是否最优活动选择问题按结束时间排序选不冲突的✅ 最优哈夫曼编码每次合并频率最小的两个节点✅ 最优Dijkstra最短路径每次选距离最小的未确定节点✅ 最优非负权Kruskal最小生成树每次选权重最小的不成环的边✅ 最优Prim最小生成树每次选权重最小的跨割边✅ 最优TSP旅行商问题最近邻点策略❌ 近似解0-1背包问题按单位价值排序选择❌ 不一定最优提示贪心法不能盲目使用。在应用之前必须分析问题是否满足贪心选择性质和最优子结构性质。对于 TSP 问题由于不满足贪心选择性质局部最优不能保证全局最优因此贪心法只能给出近似解。