计算机算法设计与分析（第6版）-课件 ch0607旅行售货员问题

旅行售货员问题的分支限界法01问题与模型旅行售货员问题定义与数学模型问题通俗描述数学模型形式化旅行售货员问题描述了一位售货员从驻地出发，需要遍访所有城市恰好一次后返回起点，目标是找到总路程最短的回路。这是经典的组合优化问题，广泛应用于物流、交通等领域。从图论角度形式化TSP问题：给定带权有向图G=(V,E)，寻找一条哈密顿回路，使得边权之和最小。解空间是所有顶点的排列，对应排列树搜索结构，为后续分支限界法提供基础。暴力枚举的复杂度暴力枚举所有城市排列需要O(n!)时间，当城市数量n≥20时，计算量已不可承受。排列树中每条根到叶的路径对应一个完整的回路，内部结点代表部分路径。剪枝的必要性仅当部分路径已显劣时才可剪枝。引入“代价下界”概念，为分支限界法提供必要性论证。通过剪枝避免无效搜索，提高算法效率。分支限界的优势分支限界法通过优先队列维护活结点，利用下界剪枝，避免了暴力搜索的低效性，能够在合理时间内找到最优解，是解决TSP问题的有效方法。排列树搜索空间与复杂度02分支限界算法框架优先队列式分支限界法优先队列式分支限界法用最小堆维护活结点，每次扩展下界最小者。若下界已不优于当前最优，则整棵子树被剪去。算法输出为最小费用及对应回路序列，效率高且结果精确。算法骨架概述活结点数据结构MinHeapNode拆解MinHeapNode中的x数组保存当前排列的前缀，记录已确定的部分路径，为后续路径的生成提供基础，确保路径的连贯性和完整性。x数组的作用01cc表示当前已付费用，随着路径的扩展而累加。rcost是剩余顶点最小出边和，用于估计后续路径的最小可能费用，为下界计算提供依据。cc与rcost的计算03lcost=cc+rcost作为优先级，用于在最小堆中排序活结点。它保证了下界的有效性，使堆顶始终是最有希望的结点，奠定了后续剪枝的正确性。lcost的重要性04s记录已固定的顶点数，表示当前路径的长度。随着算法的推进，s逐渐增加，直至找到完整的回路，是路径生成的关键指标。s的含义0203预处理与初始化最小出边预处理与回路存在性判定最小出边费用计算第一步扫描邻接矩阵，对每个顶点i求最小出边费用MinOut[i]。若发现某个顶点无出边，则立即返回NoEdge，表明图不存在回路，算法提前终止。MinSum的作用累加MinOut得到MinSum，作为后续rcost的初值。MinSum为算法提供了全局的下界信息，有助于在后续搜索中快速剪枝，提高算法效率。创建根结点与优先队列初始化01将顶点1置为起点，x[0]=1，剩余城市顺序填入x[1..n-1]。设置s=0、cc=0、rcost=MinSum，生成首个活结点并入堆，为算法的启动做好准备。根结点的初始化02同时初始化bestc为NoEdge，表示尚未找到可行解。bestc用于记录当前最优解的费用，随着算法的推进不断更新，确保最终找到全局最优解。bestc的初始化03优先队列用于存储活结点，按照下界lcost进行排序。每次从队列中取出下界最小的结点进行扩展，保证了搜索的高效性和正确性。优先队列的作用04结点扩展与剪枝结点处理与完整回路判定01结点的扩展当s=n-2时，仅剩一条边即可闭合回路。检查x[n-2]→x[n-1]与x[n-1]→1是否存在。若可行且新费用小于bestc，则更新bestc并将该叶结点入堆，否则丢弃。02完整回路的判定这是算法唯一产生完整解的地方，保证最优性及时更新。一旦找到更优的完整回路，立即更新bestc，确保算法能够找到全局最优解。内部结点儿子生成与下界过滤01020304儿子结点的生成下界过滤的作用rcost的递减剪枝的重要性当s<n-2时，循环剩余顶点x[i]，若边(x[s],x[i])存在，则计算cc、rcost与b=cc+rcost。生成新的儿子结点，为后续路径的扩展提供候选。--01----02----03----04--当b<bestc时，创建新结点并交换位置以维护排列，否则剪枝。下界过滤能够有效去除不可能产生更优解的路径，提高算法效率。rcost逐层递减MinOut[x[s]]，保持下界紧致。紧致的下界能够更准确地估计后续路径的费用，使剪枝更加高效。剪枝是分支限界法的核心，通过去除不可能产生更优解的路径，避免了无效的搜索，大大提高了算法的效率，是解决TSP问题的关键。05算法终止与输出堆空终止条件与最优解提取终止条件while循环持续至堆空或叶结点成为扩展结点。由于lcost单调不降，一旦叶被扩展即获全局最小费用，算法终止条件明确且合理。最优解的提取随后把E.x复制到输出数组v[1..n]，完成解的对外交付。提取最优解的过程简单高效，确保了算法的完整性和实用性。算法结束的依据任何剩余活结点均不可能提供更优解，故算法可安全结束。这一结论基于分支限界法的剪枝机制，确保了算法的正确性。内存清理与复杂度最后用循环逐个释放堆中结点内存，防止动态数组泄漏。总结时间复杂度最坏仍为O(n!)，但下界剪枝使平均情况远优于暴力；空间复杂度取决于堆内活结点数，通常可处理n≤50规模。内存清理与复杂度06小结算法要点回顾与对比总结算法要点分支限界法用优先队列驱动，下界全局排序。TSP分支限界适合边权非负且需要精确解的场景，若规模再大则需转向近似算法或启发式搜索。算法比较用对照表形式重申分支限界与回溯、动态规划差异：前者用优先队列驱动，下界全局排序；后者深度优先或阶段递推。对比总结有助于理解不同算法的特点和适用场景。延伸思考提出可拓展方向：对称/非对称TSP、时间窗口约束、多目标优化。这些可提供进一步研究的方向，拓宽对TSP问题的理解。延伸思考了解Con