《算法设计与分析》课件 第5-9章 贪心算法 -并行算法

贪心算法截至目前,我们已经学习了三种主要的算法设计策略:枚举法、分治法和动态规划。本章将介绍第四种算法设计策略——贪心算法(GreedyAlgorithm),也称为贪心策略。通过详细的案例讲解,读者将能够理解贪心策略的适用条件,并掌握如何利用贪心算法设计高效的算法来解决实际问题。基本思想:兑零钱问题问题描述给定硬币面值数组和目标金额n,每种硬币可重复使用且数量不限,求使用最少数量的硬币凑出金额n。例如:硬币面值为[1,2,5],兑换11元需要多少枚硬币?贪心策略每次选择当前可兑换的最大面额硬币。兑换11元:先选5元(剩6元),再选5元(剩1元),最后选1元。方案为{5,5,1},共3枚硬币。贪心策略的核心特征局部最优选择每次决策时仅考虑当前状态下的最优选择,不关注之前或之后的决策影响构造全局解试图通过一系列局部最优的选择构造出整体最优解直观易懂贪心算法通常直观且易于理解,只需尝试几个小规模示例即可发现求解方式旅行商问题的贪心策略旅行商问题(TSP)需要找到一条从某个城市出发、遍历所有城市且仅访问一次、最终回到起始城市的最短路径。01起始城市从起始城市开始,选择距离最近的未访问城市02迭代选择到达新城市后,在未访问的城市中再次选择距离最近的城市03完成遍历依此类推,直到遍历所有城市,最后回到起始城市TSP问题贪心解法贪心算法的求解步骤定义最优解结构明确问题目标及解的形式,确保问题适用于贪心策略构建贪心选择规则确定在当前状态下如何选择局部最优且可行的选项更新问题状态每次贪心选择后,更新当前状态以便继续应用贪心策略构建最终解不断重复贪心选择,逐步构造出最终的解背包问题:0-1背包

1定义最优解结构

2贪心选择规则

3更新状态每选择一个物品后,更新背包剩余容量W4构建解反复应用贪心选择规则,逐步构建物品选择序列0-1背包问题示例4个物品的重量和价值:重量w=[2,3,4,5]价值v=[3,4,5,6]背包容量W=8单位价值分别为:1.5,1.3,1.25,1.2按单位价值排序:物品1,2,3,4贪心算法求解选择物品1(重量2),剩余容量6选择物品2(重量3),剩余容量3物品3和4无法装入贪心解:{物品1,物品2},总价值7最优解:{物品2,物品4},总价值100-1背包的时间复杂度分析预处理阶段时间复杂度Θ(nlogn)物品选择阶段时间复杂度Θ(n)总体复杂度Θ(nlogn)+Θ(n)=Θ(nlogn)贪心算法的优点简单直观每一步都做出当前看起来最优的选择,易于理解和实现高效性通常具有较低的时间复杂度,适合处理大规模问题占用空间少不需要维护复杂的数据结构或记录大量中间状态适用于特定问题在某些情况下能够保证找到全局最优解提供近似解即使无法保证最优解,通常也能提供较为接近最优解的近似解贪心算法的缺点依赖问题特性适用性高度依赖于问题本身的结构,只有在特定类型的问题中才能有效工作局部最优导致全局次优每一步只关注局部最优选择,忽略整体影响,可能导致最终解在全局范围内并非最优局部最优与全局最优《庄子·齐物论》记载:养猴人每天早晨给猴子们发三颗栗子,傍晚发四颗。猴子们觉得早晨的栗子太少,不满意。于是,养猴人改为早晨发四颗,傍晚发三颗。猴子们立刻高兴起来。实际上,无论"朝三暮四"还是"朝四暮三",每天猴子们得到的栗子总数都是七颗,并未发生任何变化。这个故事反映了猴子们只关注眼前得失,被表面的数量变化所迷惑,忽略了整体利益并没有变化的事实。这种行为正是局部最优与全局最优之间的区别。贪心算法的必要条件贪心算法并不能保证一定找到全局最优解。只有在特定条件下,贪心算法才能确保其所得解为最优解。最优子结构性质问题的最优解包含其子问题的最优解。如果一个问题的最优解包含了某个子问题的最优解,那么整个问题就具有最优子结构性质。此性质也是动态规划的核心。贪心选择性质通过局部最优的选择,可以直接构造出全局最优解。换句话说,最优解可以通过一系列局部最优的选择逐步构建,而不需要回溯或调整之前的决策。部分背包问题部分背包问题与0-1背包问题类似,但存在关键区别:允许将物品拆分成任意比例后装入背包。问题描述

目标是找到一种装包方案,使得背包内物品的总价值最大化。贪心策略

直到背包无法容纳更多物品为止。部分背包问题示例背包最大承重W=50,有4个物品:物品编号重量价值单位价值11060622010053301204425753部分背包求解过程选择物品1单位价值6,重量10,剩余容量40,背包价值60选择物品2单位价值5,重量20,剩余容量20,背包价值160部分选择物品3单位价值4,部分装入20,剩余容量0,背包价值240最终选择:物品1、物品2和物品3的一部分,背包总价值为240。贪心选择性质的证明

因此，贪心算法的选择不会低于最优解的选择。这表明，通过每一步选择单位价值最高的物品部分，贪心算法的选择能够逐步构建出最优解，满足贪心选择性质。最优子结构性质的证明假设我们有一个最优解S选择了部分背包问题中的若干物品，其中按照单位价值从高到低的顺序依次选择。设第一个被选择的物品为物品i，其单位价值最高。

由此可见，部分背包问题满足最优子结构性质。部分背包问题的结论贪心算法保证最优解部分背包问题同时满足最优子结构性质和贪心选择性质。因此,贪心算法能够保证在该问题中找到全局最优解。0-1背包贪心算法不能保证最优解部分背包贪心算法能够保证最优解兑零钱问题的深入分析在某些硬币面额体系下,贪心算法能够保证找到最优解。例如,当硬币的面额为1元、2元和5元时,贪心算法始终能够找到兑换目标金额的最优解。反例:面额[1,3,4]目标金额:6元贪心策略:选择4元(剩2元),选择1元两次贪心解:3枚硬币最优解:两枚3元硬币,仅需2枚充分条件硬币面额满足递增倍数关系:

其中a是整数且a≥2这种情况下,使用最大面额的硬币总是最优的活动安排问题

活动安排问题示例1选择活动b结束时间最早,加入解集合2选择活动e从剩余活动中选择结束时间最早的3选择活动h继续选择,直到剩余活动集合为空最终,贪心算法求得的活动集合为{b,e,h},共3个活动。1定义最优解结构构建一个不冲突的最大活动集合2贪心选择规则选择结束时间最早的活动3更新状态更新当前时间,筛选剩余活动4构建最终解重复直到没有符合条件的活动活动安排的贪心策略对比选择结束时间最早的活动贪心算法得到:{b,e,h}活动数量:3个(最优)选择开始时间最早的活动贪心算法得到:{a,g}活动数量:2个(非最优)选择占用时间最少的活动贪心算法得到:{c,h}活动数量:2个(非最优)活动安排算法的时间复杂度O(nlogn)排序阶段对所有活动按照结束时间进行排序O(n)遍历阶段对活动进行遍历,需要执行n-1次循环O(nlogn)总体复杂度最小生成树问题一家电力公司计划在某个地区建立新的输电网络,以连接若干个城市和乡镇,确保电力能够输送到每个地方。由于建设输电线路的成本非常高,公司希望总的建设成本尽可能低。问题建模将此问题建模为一个带权无向图。图的顶点代表城市和乡镇,顶点之间的边代表可能建设的输电线路,边的权重代表建设成本。最优方案最优的输电线路是连接所有顶点的边集合,并且这些边的总权重(即总建设成本)最小。这对应一棵生成树。最小生成树的定义在一个带权连通无向图G=(V,E)中,V表示顶点集合,E表示边集合,每条边都赋予了一个权重(或称成本)。生成树包含图G中的所有顶点的无环的连通子图,即任意两个顶点之间只有唯一的一条路径最小生成树(MST)在所有可能的生成树中,边权重之和最小的那颗生成树

Kruskal算法的贪心策略Kruskal算法使用贪心策略来构造最小生成树:定义最优解结构找到一棵包含所有顶点的树,使得所有边的权重之和最小贪心选择规则每次选择权重最小且不会形成环路的边加入到树中更新状态将选择的边和相应的顶点加入到当前的树中构建最终解当树中包含了n个顶点和n-1条边时,生成树构建完成Kruskal算法示例以4个顶点的图为例,边的权重分别为:(A,D):1(B,C):2(A,C):3(A,B):4(C,D):5(B,D):601排序边按权重升序排序所有边02选择边(A,D)权重1,不形成环路,加入MST03选择边(B,C)权重2,不形成环路,加入MST04选择边(A,C)权重3,不形成环路,加入MSTMST构建完成,总建设成本为6(1+2+3=6)。假设使用基于比较的排序算法（如快速排序或归并排序），排序的时间复杂度为Θ(|E|log|E|)，其中|E|表示图中边的数量。算法的主体结构是第3-10行的循环，该循环遍历图中的每一条边。最坏情况下，需要遍历所有|E|条边。对每一条边都要进行环路检测，也就是时间复杂度为|E|Θ(环路检测)。算法总体时间复杂度为Θ(|E|log|E|)+|E|Θ(环路检测)。时间复杂度分析环路检测:深度优先遍历在遍历时,如果访问一个邻接顶点时发现该顶点已经被访问过,并且它不是当前顶点的父顶点,则说明存在环路。从顶点A开始进行深度优先遍历，将A标记为正在访问。深度优先遍历A的第一个邻接点B，将B标记为正在访问，B的相邻顶点是A,C，A已访问并且是B的父顶点，符合父子关系，不构成环。访问B的邻接点C，将C标记为正在访问。C的邻接点有A，B，D。发现A顶点已访问过，且不是C的父顶点，发现环路。上述算法在最坏情况下需要遍历图中的所有顶点和边，其时间复杂度为Θ(|V|+|E|)。并查集:更高效的环路检测并查集是一种用于管理不相交集合的数据结构,支持以下基本操作:初始化每个顶点自成一个集合查找操作find(x)查找元素x所对应集合的代表元素(根顶点)合并操作union(x,y)将包含x的集合和包含y的集合合并当处理一条边(u,v)时,如果find(u)=find(v),说明u和v已经属于同一个集合,此时再连接u与v会形成环路。基于并查集的Kruskal算法基于并查集的Kruskal算法：示例Kruskal算法的时间复杂度O(|E|log|E|)排序阶段对所有边按照权重进行升序排序O(|E|α(V))环路检测使用并查集,α(V)增长极其缓慢,可视为常数O(|E|log|E|)总体复杂度算法总体时间复杂度为Θ(|E|log|E|)Prim算法的核心思想Prim算法体现了"从内向外扩张"的思想。与Kruskal算法不同,Prim算法从图中的任意一个顶点出发,在每一步中选择一条将该子树与尚未加入树的顶点连接起来的最短边。从单个顶点开始最初只有一个顶点的"树"逐步扩张每次迭代子树中增加一个顶点完成构建直到所有顶点都加入树中Prim算法示例

Prim算法时间复杂度分析基于优先队列的Prim算法

优先队列的作用存储未加入MST的顶点按照顶点到子树的距离排序快速提取距离最小的顶点关键操作pop():提取距离最小的顶点decrease_key():更新顶点的距离parent[]:记录每个顶点的父顶点基于优先队列的Prim算法Prim算法的时间复杂度使用最小堆实现优先队列,算法时间复杂度分析如下:O(|V|)初始化将所有顶点加入优先队列O(|V|log|V|)pop操作while循环执行|V|次pop操作O(|E|log|V|)decrease_key操作对每条边最多执行一次decrease_keyO(|E|log|V|)总体复杂度由于连通图中|E|≥|V|-1,化简为O(|E|log|V|)最短路径问题一家物流公司计划为其货车车队确定从配送中心到各个客户网点的运输路线,目标是在满足配送需求的前提下,尽可能减少卡车在路上的行驶距离和时间。问题建模将问题建模为一个带权有向图。顶点代表配送中心或客户网点,有向边表示可行驶的道路,边的权重代表成本(路程、时间或油耗)求解目标从特定的起始点(配送中心)出发,求解到其他各个网点的最短路径,以便在运输过程中尽可能降低成本。最短路径问题的定义在一个带权有向图G=(V,E)中,给定起点s∈V,希望找到从s到其他任意顶点v∈V的最小权重路径,其中边的权重表示通过该边所消耗的代价。最短路径问题即为求出起点s与任意目标顶点v之间的代价最低的路径。随着顶点和边数的增加,一张图中的路径数量会迅速增长,因此尝试枚举所有路径并从中选出最优解的方法并不可行。观察从A出发有两条边：边AB的权重为2，边AC的权重为3，则从A到B的最短路径肯定是边AB？同时利用顶点A和B的信息，则可以确定A→C的最短路径为直接边AC？Dijkstra算法的贪心策略Dijkstra算法使用贪心思想求解最短路径问题(假设边权重非负):1定义最优解结构将顶点分为已确定最短路径的集合D和未确定的集合V\D2贪心选择规则在未确定顶点中,选择距离起点s最近的顶点u3更新状态根据顶点u的邻接边,更新其他顶点的距离估计值4构建最终解不断重复,直至D包含所有顶点Dijkstra算法示例Dijkstra算法的时间复杂度假设优先队列使用二叉堆实现:初始化初始化d[]和π[]数组,时间复杂度O(|V|)extract_min单次O(log|V|),共执行|V|次decrease_key单次O(log|V|),最多执行|E|次总体复杂度O((|E|+|V|)log|V|)=O(|E|log|V|)哈夫曼编码哈夫曼编码是一种用于无损数据压缩的贪心算法,其核心思想是构建哈夫曼树,为不同频率的字符分配不同长度的编码,从而使得整体编码长度达到最小。定长编码字符集合{A,B,C},A出现990次,B和C各出现5次每个字符使用2位编码总编码长度:2×990+2×5+2×5=2000位变长编码A用0表示,B用11表示,C用10表示总编码长度:1×990+2×5+2×5=1010位节省近50%的空间哈夫曼编码的前缀码性质哈夫曼编码需要确保编码方案满足前缀码的性质,即任何一个字符的编码都不是另一个字符编码的前缀,从而保证解码的唯一性。反例如果A、B、C分别用0、00、10来表示,那么对000的解码就会出现歧义,因为它可能代表AAA、AB或者BA。哈夫曼编码的保证哈夫曼编码通过构建哈夫曼树,确保每个字符对应一个叶子节点,从根节点到任意叶子节点的路径都是唯一的,因此必然是一种前缀码。哈夫曼算法的核心操作哈夫曼算法的核心操作是每次从优先队列中提取两个频率最小的节点,创建一个新的内部节点,其频率为这两个节点频率之和。提取最小节点从优先队列中提取两个频率最小的节点创建新节点创建新的内部节点频率为两节点之和插入队列将新节点重新插入优先队列重复迭代直到队列中只剩下一个节点(根节点)哈夫曼编码示例6个字符及其频率:A:5,B:9,C:12,D:13,E:16,F:45

哈夫曼算法的时间复杂度O(n)初始化将n个字符插入优先队列O(nlogn)构造哈夫曼树循环执行n-1次,每次两次extract_min操作O(n)生成编码遍历哈夫曼树,为每个字符分配编码O(nlogn)总体复杂度算法总体时间复杂度为O(nlogn)磁盘调度算法:SSTF在计算机系统中,磁盘调度问题旨在确定磁盘访问请求的服务顺序,从而在有限的磁盘寻道时间内提高整体性能。问题背景磁盘机械臂在磁盘表面移动需要时间,合理安排访问顺序可以显著减少磁头移动距离SSTF算法最短寻道时间优先算法,每次选择距离最近的磁道进行访问优化目标最小化总寻道长度或平均寻道时间,提升系统吞吐量和响应速度SSTF算法示例磁盘请求序列:98,183,37,122,14,124,65,67,磁头初始位置为53。1访问65距离53最近的磁道是652访问67从65出发,选择距离最近的673继续选择依次类推,直到所有请求完成算法的核心操作即是寻找与当前磁头位置最近的磁道。SSTF算法的时间复杂度朴素实现每次迭代都需要遍历所有剩余请求,寻找距离最近的磁道总比较次数:n+(n-1)+...+2时间复杂度:O(n²)优化方案首先将请求序列按照磁道号排序在左右两侧查找下一次最近的请求时间复杂度:O(nlogn)如果使用桶排序,可降至O(n)14,37,65,67,98,122,124,183贪心算法总结1核心思想每步做出局部最优选择,期望构造全局最优解2适用条件最优子结构性质和贪心选择性质3优点简单直观、高效、占用空间少4缺点依赖问题特性,局部最优可能导致全局次优5应用背包问题、最小生成树、最短路径、哈夫曼编码、调度算法等贪心算法的设计技巧明确目标清晰定义优化目标和解的形式设计贪心规则确定局部最优选择的标准验证性质检查是否满足最优子结构和贪心选择性质高效实现使用合适的数据结构优化算法测试验证通过示例验证算法的正确性回溯与分支限界法在算法设计与分析中,回溯算法和分支限界法是两种重要的策略,广泛应用于解决各种组合优化问题和决策问题。虽然这两种方法在基本原理和应用场景上有所不同,但它们都基于对解空间的系统性探索,以寻找满足特定条件的最优解或所有可行解。回溯法基本思想设想一个复杂的迷宫问题:迷宫的起点位于左上角,终点位于右下角。迷宫由若干个房间构成,各房间之间通过通道相连,而部分通道可能因墙壁阻挡而无法通行。问题要求找到一条从起点到终点的路径,保证路径上每一步均合法且畅通。走迷宫的思路面对走迷宫这一问题,常用的思路是:从起点出发,在每个房间可能有多个选择,例如向左、向右、向上或向下移动。在选择一条通道前进后,如果到达的房间发现所有通往未探索区域的通道均已堵塞而无法继续前行,则需要退回到上一个分叉点,重新选择另一条未曾尝试的通道,继续进行探索。这个过程可能需要重复多次,直至找到一条通往终点的有效路径。回溯法的核心特点做出选择在每个房间都需要做出选择,决定下一步的移动方向排除路线在不断地探索中,需要排除那些无法通往终点的路线回溯尝试当发现当前选择无法达到目标时,必须回溯到先前的决策点,尝试其他可能的选择回溯法的应用范围这些特点正是回溯法的核心思想。回溯法通过系统地尝试所有可能的选择,并逐步剔除不符合条件的路径,最终找到满足目标的解答。该方法不仅适用于解决迷宫问题,而且在组合优化、排列组合、图遍历等多个领域都有广泛应用。0-1背包问题回顾

之前,我们已使用枚举法、动态规划和贪心算法来求解此问题。在本章中,我们尝试使用回溯法进行求解。0-1背包问题示例问题参数以3个物品为例:

解空间特征对于每个物品,都有"装入背包"或"不装入背包"两种选择,因此整个搜索空间可以用一棵满二叉树表示,这棵树称为解空间树。解空间树结构根节点A对应起始状态,对于物品1有选择和不选择两种状态,分别对应树第二层的节点B和C。接下来,在节点B或C上,对物品2也有选择和不选择两种状态,产生第三层的4个节点。对于3个物品,解空间树共有8个叶节点,代表所有8种可能的方案。回溯法求解0-1背包问题就相当于对这棵解空间树的搜索过程。回溯搜索过程(1)01从根节点A开始按照深度优先的顺序搜索,从A到B,访问节点B。假设向左子树移动表示装入物品,而向右子树移动表示不装入物品,则节点B表示选择装入物品1。此时,背包剩余容量为14(即30-16),背包中物品总价值为45。当前搜索路径为:A→B。

回溯搜索过程(2)02

尝试装入物品2从节点B开始,按照深度优先的顺序搜索,访问节点D。由于物品2的重量大于背包剩余容量,无法装入物品2,因此这一分支无效,需回溯到其父节点B。回溯搜索过程(3)03

不装入物品2在节点B,搜索完D子树后,继续搜索E子树。在状态E下,决策为不装入物品2,此时背包剩余容量仍为14,物品总价值仍为45。当前搜索路径为:A→B→E。回溯搜索过程(4)

尝试装入物品3:

物品3的重量大于背包剩余容量,无法装入,故此分支无效,回溯至节点E找到第一个可行解:节点E的右子树尚未访问,接着访问节点K。此时得到一个可行解,背包总价值为45。当前搜索路径为:A→B→E→K。回溯到根节点:K访问完毕,回溯到其父节点E;E的子树均已访问,继续回溯到B,再回溯到节点A,此时发现节点A的右子树尚未访问。不装入物品1:A访问C。此时背包剩余容量为30,物品总价值为0。装入物品2:访问节点F。背包剩余容量为15(30-15),物品总价值为25。当前搜索路径为:A→C→F。回溯搜索过程(5)

找到最优解:从F出发,访问L,对应装入物品3。此时背包剩余容量为0,物品总价值增至50。继续探索:L为叶子节点,回溯至F。F的右子树尚未访问,随后访问M,得到一个可行解:仅装入物品2,背包总价值为25。搜索其他分支:M访问完毕后,回溯到F;回溯至C。此时C的右子树尚未访问,接着访问节点G。完成搜索：在节点G,首先访问其N,表示装入物品3,得到一个可行解:背包总价值为25。从节点N回溯到父节点G,再访问O,得到一个可行解:不装入物品3,背包总价值为0。0-1背包问题的回溯算法

回溯法的求解范式从初始状态出发,通过深度递归搜索在每一步中尝试所有可能的决策选项对每个选项进行合法性和可行性判断,不符合要求的立即剪枝,符合条件的则继续深入;当达到可行解或终止条件时回溯返回,最终收集所有解或最优解。n皇后问题接下来,我们再次思考如何求解n皇后问题。问题描述为:在一个n×n的棋盘上,摆放n个皇后,使得任意两个皇后不处于同一行、同一列以及同一对角线上,求共有多少种不同的摆放方法。此前,我们曾采用枚举法求解该问题,此方法需要枚举n!种可能的摆放方式,导致时间复杂度较高。为此,在本章中,我们尝试使用回溯法来求解n皇后问题。4皇后问题求解过程(1)以4皇后问题为例,对于第一个皇后(Q1),可以放在棋盘第一行的4个位置中的任意一个,共有4种选择。之后,对于第二个皇后(Q2),可以放在棋盘第二行的4个位置中的任意一个。依此类推,构成的解空间树是一棵深度为4的满4叉树。我们用Q1、Q2、Q3、Q4分别表示放在第一行、第二行、第三行和第四行的皇后,用(i,j)表示棋盘的第i行第j列。4皇后问题求解过程(2)放置Q1将Q1放在第1行的第一个位置(1,1)放置Q2对于Q2,尝试放在(2,1)或(2,2)均与Q1冲突,因此不可行;于是将Q2放置在不冲突的位置(2,3)Q3无法放置对于Q3,发现第三行的4个位置均与Q1或Q2冲突,因此无法放置Q3,需要回溯到Q2调整Q2位置在Q2已放在(2,3)的子树探索完毕后,尝试将Q2放在下一个位置,即(2,4)4皇后问题求解过程(3)继续放置Q3对于Q3,尝试将其放在(3,1)时,与Q1冲突,因此改尝试(3,2)Q4无法放置对于Q4,在第四行的4个位置均与前面的皇后冲突,因此Q4无法放置,需要回溯到Q3多次回溯由于Q3在(3,2)的情况已探索完毕,继续尝试Q3的其他摆放位置,但发现(3,3)或(3,4)均与Q2冲突,于是Q3需要回溯到Q2;而Q2在(2,4)的情况也已探索完毕,故回溯到Q14皇后问题求解过程(4)01调整Q1位置将Q1从(1,1)移到下一个位置,即(1,2)02放置Q2和Q3Q2只能放在(2,4)才能与Q1不冲突。将Q3放在(3,1)03找到第一个可行解对于Q4,在第四行(4,1)和(4,2)与Q3或Q1冲突,因此选择将Q4放在(4,3),此时得到一个可行的摆放方案04继续搜索尝试将Q4放在(4,4)时,与Q2冲突,因此回溯到Q3;而Q3在(3,2)、(3,3)和(3,4)均与前面的皇后冲突,故再次回溯到Q2;Q2已探索完毕,继续回溯到Q1。4皇后问题求解过程(5)将Q1移到下一个位置,即(1,3)。考虑到4×4的棋盘关于中线对称,Q1放在(1,3)的搜索路线与Q1放在(1,2)的情况对称,因此可根据Q1在(1,2)时获得的可行解直接推出一个新的可行解。最终,得到两个可行的摆放方案。n皇后问题的回溯算法回溯法遍历完整个解空间树的时间复杂度为O(n!)数独求解问题数独问题的目标是将一个9×9的网格填满数字1至9,使得每一行、每一列以及每个3×3的子网格中的数字均不重复。在本节中,我们尝试使用回溯法求解数独问题。我们将数独问题视为一个决策序列问题:从左到右、从上到下依次扫描每一个空格。数独求解的回溯策略决策过程当处理到某个空格时,尝试填入数字1至9中的某个数字(前提是不违反所在行、所在列以及所属3×3网格的约束条件)。如果存在可行的数字,则递归地填入下一个空格。回溯机制如果所有数字均不可行,则说明当前路径无效,需要回溯到上一个决策点,尝试其他数字。数独问题的解空间树通过这种深度优先搜索的过程,我们实际上在一棵隐含的解空间树上进行搜索。树的根节点对应初始状态,即给定的数独盘面;从根节点出发,当我们为第一个空格填入某个数字时,就相当于沿着树的一条分支向下走,形成一个新的状态。类似地,为下一个空格填数又会在该状态上拓展出若干子节点,每个子节点代表一次新的决策。最终,当搜索深入到树的叶子节点时,如果所有空格均已合法填满,则说明找到了一个完整的可行解;否则,在某个节点发现无法为当前空格填入合适的数字,该分支即被判定为死路,需要回溯到上一个节点,选择其他数字继续尝试。回溯法的一般性说明在本节中,我们将概括性地介绍回溯法。回溯法通常适用于一类通过搜索求解的决策问题和组合问题。这些问题的求解过程可以分解为一系列有序的决策步骤,每一步从有限的候选选项中选择其一。

回溯法的约束条件同时,这类问题通常伴随着一组约束条件,用以判断当前部分解是否满足要求。例如,n皇后问题要求所有皇后之间互不攻击;0-1背包问题要求选取的物品总重量不超过给定容量。此外,我们可以将问题的所有可能决策序列看作是一棵解空间树,其中每个节点对应一次决策或一个状态,每条边代表一次具体的选项选择。当搜索遍历到树的叶子节点时,如果该叶节点对应的解满足所有约束条件,则该解为一个可行解。回溯法的求解步骤状态定义与搜索起点从初始状态出发(例如:棋盘上尚未放置任何皇后,背包为空),确定搜索过程的起点。逐步决策与探索在每个决策点,尝试为下一个需要决策的元素选择一个可行的选项。如果所选选项与已选择的部分无冲突,则继续深入到下一个决策点;若发生冲突,则尝试其他选项。到达递归出口当所有决策点均已完成选择且满足所有约束条件时,即找到一个可行解。如果需要求得所有解,则继续搜索其他分支。回溯过程当在某个决策点无法找到合适的选项时,回溯到上一个决策点修改选择,探索另一条可能路径。回溯法算法框架回溯法的优化策略剪枝策略剪枝策略在搜索过程中起着至关重要的作用。具体来说,在发现当前部分解已经不可能产生最终的可行解或最优解时,我们立即停止沿该分支继续搜索。例如,在n皇后问题中,如果某一列已被占用,则无需在该列上重复尝试。高效数据结构借助更高效的数据结构也能显著提高状态检查的速度。通过使用额外的标记数组、位运算、散列表等手段,可以实现对某些约束条件的常量时间检查,从而减少不必要的计算开销。回溯法与穷举法的区别穷举法穷举法往往"盲目"地枚举所有排列组合,不论中途是否能提前判定失败,都需要生成所有可能的结果再进行检查。回溯法回溯法则是"按需搜索",在发现某条路径不可行时,立即剪枝,停止继续沿该路径搜索。回溯法明确地将问题映射为一棵解空间树,并采用深度优先策略有序地探索各个状态。分支限界法的基本思想在前面章节中,我们系统研究了回溯法的核心原理。回溯法通过构建解空间树并实施剪枝策略,为解决约束满足问题和组合优化问题提供了一种普适性框架。然而,其深度优先的搜索策略与保守的剪枝机制,可能导致在最坏情况下需要遍历指数级数量的节点。这促使我们思考:能否通过更精确的剪枝判断,在搜索早期识别并剪除无效分支?回溯法的工作机制解空间建模回溯法将问题的所有解映射为一棵解空间树,树的每一层代表一个决策步骤,每一条分支代表一次决策选项,每个节点表示部分解深度优先搜索沿树的分支纵向深入,直至发现完整解或不可行解时回溯可行性剪枝在搜索过程中,我们通过判断当前部分解是否违反约束条件来进行剪枝。一旦检测到无解或无望成为更优解的分支,立即回溯,省略对该分支下所有后续节点的访问分支限界法的核心思想那么,能否在回溯基础上进一步增强剪枝效率,使我们在搜索早期就能判定某个分支的未来潜力,从而尽早地"剪掉"更多分支,减少无谓的搜索?这便是"分支限界法"(BranchandBound)的核心思想所在。分支限界法与回溯法同样以解空间树为基本框架,对解空间进行有序、系统的搜索。分支限界法的基本要素分支(Branching)与回溯法类似,分支限界法在问题求解中也通过分解决策步骤,使解空间展现为一棵搜索树。每个节点对应一个部分解,每次决策产生新的分支节点。限界(Bounding)对于搜索树中的每个节点,利用限界函数为其部分解提供一个估计值(下界或上界),以预测在最理想情况下该分支能达到的最佳目标值。如果某分支的"最优潜力"低于当前已知的最优解,则可立即剪枝。搜索策略与分支选择分支限界法通常采用广度优先或优先队列来选择下一个扩展节点,而非简单的深度优先。通过灵活调整搜索策略和利用限界值判断,分支限界法有望在较早的时间点就发现高质量的可行解。分支限界法的优势总的来说,分支限界法本质上仍是对解空间树的搜索,但相比回溯法,"限界"这一机制使得剪枝更加高效。在解决0-1背包问题、旅行商问题和分配问题等组合优化问题时,分支限界法往往能够大幅减少实际访问的节点数量,从而提升求解效率。0-1背包问题的上界函数让我们再次回顾0-1背包问题。传统的回溯法主要依赖于超重剪枝(即当当前部分解的总重量超过容量时立即终止该分支)以及在到达叶子节点后更新最优解,从而减少搜索工作。然而,在最坏情况下,回溯法仍可能遍历大量无用分支。为了进一步提高搜索效率,我们希望在尚未遍历到叶子节点时,就能够判断当前分支的潜在最优性。如果当前分支的"最佳潜在结果"已经不可能超过当前已知的最优解,则继续搜索该分支便毫无意义。为此,我们为每个节点定义一个上界函数,该函数估计从当前节点继续向下搜索时能获得的最大装包价值。上界函数的设计

方式1假设剩余容量全部用来装入单位价值最高的物品,即全部装入物品1,则背包的价值上界为10×10=100。方式2按照价值密度依次装入物品。先装入物品1,使用4的容量,剩余6;然后用剩余容量全部装入物品2,其单位价值为6,上界为40+6×6=76。显然,方式1得到的100是一个比方式2更宽松的上界,但其计算更为简单。为了便于展示,我们默认采用方式1来计算上界。分支限界法求解0-1背包问题从根节点开始,生成左右两个节点,分别对应装入物品1和不装入物品1,并计算这两个节点的上界,分别为76和60。随后,选择上界较高的节点(根节点的左孩子)继续搜索,并生成其左右子节点。由于无法装入物品2,因此无需搜索其左子树;右子树的上界为70,进一步扩展其左右子树后,计算得到上界分别为69和64。接着,搜索左子树时得到了一个可行解,其总价值为65。随后,考虑其他未搜索的节点,其上界均小于当前已知的可行解65,因而无需继续搜索。最终,整个搜索过程结束,得到最优解65。优先队列的使用在上述过程中,当存在多个未探索的节点时,我们总是优先选择上界最大的节点进行搜索。这样做的原因在于:优先扩展上界较高的节点更有可能在较早阶段发现更优的可行解。一旦找到更优解,就能及时更新当前的最优值,从而提高后续剪枝的效率。这种策略能够在搜索深入之前就淘汰大量无望的分支,减少无效探索,从而使得整个搜索过程更加高效。因此,我们可以使用优先队列来组织节点,并以其上界值作为关键字进行排序。算法时间复杂度分析

虽然评估在平均情况下限界函数和优先队列的剪枝效果较为困难,但直观上看,限界函数越严格,剪枝效果越好,实际需要搜索的节点数就越少,从而降低算法的运行时间。然而,如果限界函数过于复杂,其计算开销可能会抵消剪枝带来的收益,因此在设计限界函数时需要在剪枝效果与计算成本之间取得平衡。分支限界法的求解范式01问题建模与初始化定义解空间树结构;定义限界函数;初始化优先队列。02搜索与分支当优先队列Q不为空时,循环执行:从Q中取出具有最高优先级的节点;如果该节点的上界值小于或等于当前最优解值,则剪枝;否则扩展该节点生成子节点。03终止条件与输出结果当优先队列为空时,搜索过程结束,记录的最优解即为问题的最优解。旅行商问题让我们再次回顾旅行商问题。旅行商问题的目标是找到一条最短路径,使得旅行商从某个城市出发,访问每个城市恰好一次,并最终返回起始城市。之前我们已经讨论了使用枚举法求解该问题的方法。本节中,我们尝试采用分支限界法来求解旅行商问题。由于旅行商问题要求求解最短路径,即一个最小化问题,因此我们需要设计一个下界函数,用以估计从当前节点继续扩展所能达到的最短路径长度。TSP问题的下界估计假设图中有5个节点和10条边,并且以A节点为出发点。我们已知在最优路径中,旅行商需要访问6个节点(起点与终点均为A),因此整条路径由5条边组成,这5条边的权重之和构成了路径的总成本。如果我们在每一步都选择边权最小的边(例如总是选择从A到C的最小边权),则这5条边权重的总和自然可以作为一个下界。然而,单纯采用每条边选择最小权重的策略往往会得到一个过于宽松的下界,从而导致剪枝效果不佳。更精确的下界估计

对所有未访问节点的贡献值求和后,由于每条边会在其两个端点中各被计算一次,为避免双重计数,我们需要将总和除以2,从而得到一个更贴近实际的下界估计。下界估计的局限性例如,在示例图中,节点A的贡献为1+3,节点B的贡献为3+6,节点C的贡献为1+2,节点D的贡献为3+4,节点E的贡献为3+2。因此,计算得到的估计下界为14。然而,这种方法仅考虑了每个节点的入边和出边,虽然反映了局部连通性,但未考虑整体路径的连通性,可能导致形成多个不连通的子路径甚至孤立的节点,而非一个完整的回路。1-树下界那么,如何保证所估计的下限对应的是一条连通的路径。可以从剩余节点(除起点外)构建一颗最小生成树,这就确保所有节点连通而且边的权重之和最小。然后,将最小生成树的代价加上起点的两条最小边权重,就得到了一个下界。以示例图为例,假设起始点为A,则{B,C,D,E}对应的最小生成树为{(D,E),(E,C),(C,B)},代价为3+2+6=11。起点A的两条最小权重边为AC和AB,则估计的下界为15(11+1+3)。这种方法称为1-树下界。它结合了起点两条最小边和剩余顶点的最小生成树,不仅考虑了各节点的局部连通性,还保证了整体路径的连通性,从而提供了一个更紧凑、有效的下界。分支限界法求解TSP问题(1)下面我们以示例图为例,使用分支限界法求解TSP问题:01问题建模与初始化以A为起始顶点。创建根节点node1,并计算其下限为14(采用入边出边方案计算最短路径下限);初始化优先队列Q(关键字为节点下限),并将根节点加入优先队列Q,此时Q={node1(14)}。02扩展根节点从Q中取出下限最低的节点node1,扩展生成根节点的4个子节点。节点2对应于走AB边,计算得到节点2的下限为14。节点3对应于走AC这条边,但由于图是无向图且解空间具有对称性,节点3可剪枝。分支限界法求解TSP问题(2)03扩展节点2从Q中取出下限最低的节点,即节点2。扩展节点2,生成3个子节点。节点6对应于走BC这条边,下限为16。节点7对应于走BD这条边,下限为16。节点8对应于走BE这条边,下限为19。04扩展节点6从Q中取出下限最低的节点,即节点6。扩展节点6,生成2个孩子节点。节点9对应于走CD这条边,其对应着路径A->B->C->D->E->A,代价为24,更新最优解为24。节点10对应于走CE这条边,代价为19,更新最优解为19。分支限界法求解TSP问题(3)05扩展节点7从Q中取出下限最低的节点,即节点7。扩展节点7,生成2个孩子节点。节点11对应于走DC这条边,代价为24。节点12对应于走DE这条边,更新最优解为16。06剪枝与终止从Q中取出下限最低的节点,即节点4。由于节点4的下限为16,等于目前已搜索到的最低的路径代价16,因此,不扩展此节点。从Q中取出下限最低的节点,即节点5,其下限大于已知可行解,不予扩展。同理,节点8也不予扩展。优先队列Q为空,算法结束,求得最短路径为A->B->D->E->C->A,代价为16。图着色问题图着色问题的目标是在给定的无向图中为每个顶点分配颜色,使得任意相邻顶点使用不同的颜色,同时尽可能减少所使用的颜色总数。换句话说,我们需要找到一个最小的合法着色方案,其中"合法"意味着不存在一条边的两个端点使用相同的颜色。图着色问题属于最小化问题,因为我们希望尽量减少使用的颜色数量。当采用分支限界法求解图着色问题时,关键在于设计一个下界函数,用于估计从当前节点(即部分着色状态)继续扩展后所必需的最少颜色数。图着色问题的下界函数以示例图为例,假设该图包含5个顶点和若干条边。若从零开始对图进行着色,最坏情况下每个顶点都需要使用不同的颜色,因此初始下界为5。这一下界虽然简单,但较为宽松,因为在实际图中,由于顶点间的邻接关系,很可能只需要少于5种颜色即可完成合法着色。除此之外,一个简单的下界可以是图的最大度加1。一个度数为Δ的顶点表示该顶点与Δ个其他顶点相邻。为了确保所有相邻顶点颜色不同,理论上最多需要为这些邻接顶点分配Δ种不同的颜色,而且当前顶点需要一种新的颜色来避免与所有邻接顶点颜色冲突。因此,在最坏情况下,一个度数为Δ的顶点确实需要Δ+1种颜色。分支限界法求解图着色问题每个顶点有5种可能的着色方案,解空间树为一棵5叉树A开始着色,为A分配颜色1，进入下一个顶点B的着色决策。对于B来说,若选择颜色1,则与A冲突,直接剪枝;选择颜色2后,与A不冲突,但节点C与A、B均相连,故C不能使用颜色1和颜色2,至少需要颜色3。依此类推,可以计算出不同节点下界。最终,在搜索过程中,某个分支在节点E处得到一种可行的着色方案,所使用的颜色数为3,而其他可行解或叶节点的下界均不低于3,因此可剪枝,算法提前终止,最终得到最优解。分支限界法的一般性说明在本节中,我们将对分支限界法进行概括性的说明。分支限界法适用于一类需要在解空间中搜索最优解或可行解的组合优化问题。这些问题的求解通常可转化为在一个解空间树中寻找最优(或可行)解,其中每个节点代表一个部分解,通过对解空间的有序划分与评估上下界,来决定搜索方向与剪枝时机。分支限界法的要素解空间树的构建将问题通过分支操作逐步分解成子问题,从而形成一棵解空间树。每个节点代表一个子问题,每条边对应对一个变量、边或约束作出某种决策。上下界剪枝分支限界法在搜索过程中通过限界函数估计节点的上下界,以判断该分支是否有潜力产生更优解,从而高效剪枝。在最大化问题中,上界代表当前子问题的解在目标函数上的最大可能值。在最小化问题中,下界代表当前子问题的解在目标函数上的最小可能值。可行解剪枝分支限界法还记录已知可行解的目标值,用来更新剪枝标准。如果一个节点的上界或者下界值比目前已搜索到的最优可行解的值还要差,则直接剪枝,无需搜索。优先扩展策略当存在多个可扩展的节点时,通常按照上界或者下界值从优到差进行扩展,以期先找到较优解,从而提高剪枝的效率。分支限界法的性能尽管分支限界法的最坏时间复杂度通常仍为指数级,但通过有效的下界估计和适当的分支策略,可显著减少需要探索的节点数量。结合启发式下界(如旅行商问题中采用1-树下界),往往能在实践中取得较好的性能。近似算法在多项式时间内求得"足够好"的解引入与动机回溯法与分支限界法能够理论上找到最优解最坏情况下时间复杂度呈指数级增长难以在实际应用中高效求解实际需求许多实际场景中,对精确最优解的需求并不绝对苛刻只要在合理的时间内获得"足够好"的解就能满足需求近似算法应运而生在可接受的计算资源(通常为多项式时间)内求得一个与最优解"接近"的解平衡"解的精确度"与"算法运行效率"近似算法的定义核心思想近似算法关注于在可接受的计算资源(通常为多项式时间)内求得一个与最优解"接近"的解。关键要点关注计算效率与解的质量平衡适用于NP困难问题不保证找到最优解,但保证解的质量运行时间为多项式级别精确算法vs近似算法精确算法:保证找到最优解时间复杂度通常为指数级近似算法:找到接近最优的解时间复杂度为多项式级在时间-精度之间取得平衡近似比(ApproximationRatio)近似比可以定量描述近似解与最优解之间的差距,从而为我们在"解的精确度"与"算法运行效率"之间做出权衡提供了重要依据。最小化问题对于一个最小化问题,其目标函数为f,最优解为s*且对应的目标函数值为f(s*)。设某近似算法返回的解为s,如果对于所有问题实例均满足:则称该算法为一个α-近似算法。最大化问题对于最大化问题,若要求对于所有问题实例都满足:则同样称该算法为α-近似算法。α=2的含义:对于最小化问题,近似解的代价不会超过最优解的两倍;对于最大化问题,算法输出的值不会低于最优值的一半。示例问题——顶点覆盖问题问题定义对于一个无向图G=(V,E),其中V为顶点集合,E为边集合,一个顶点覆盖是V的一个子集C⊆V,满足:对于任意一条边(u,v)∈E,至少有一个端点在C中(即u∈C或v∈C,或两者均成立)。优化目标顶点覆盖问题的目标是在给定的无向图中找到一个最小规模的顶点覆盖。应用场景网络监控:在网络中放置最少的监控设备覆盖所有连接资源分配:用最少的资源点覆盖所有需求关系安全部署:在关键位置部署最少的安全设施顶点覆盖示例可视化以下展示了同一个图的不同顶点覆盖方案。图中包含五个顶点A、B、C、D、E以及若干条边。部分边都集中连接于几个关键节点上,例如节点B和C的度均为3,有多条边在此交汇。01原始图G包含5个顶点和5条边的无向图边的连接关系:A-B,A-C,B-C,B-D,C-E顶点覆盖示例可视化02较大覆盖{A,B,C,E}使用4个顶点覆盖所有边虽然能够覆盖所有边,但包含了4个顶点,显得较为"冗余"03更优覆盖{B,C}仅使用2个顶点就覆盖了所有边规模大大减少,达到了更优的效果关键观察:不同的顶点选择策略会影响覆盖集合的规模。选择度数较高的顶点(如B和C)往往能用更少的顶点覆盖更多的边。顶点覆盖的2-近似算法核心思想：每次选择一条未被覆盖的边,将这条边的两个端点都加入顶点覆盖集合中,然后删除所有与这两个端点相连的边。重复此过程直到所有边都被覆盖。关键特点:算法每次都将选中边的两个端点同时加入覆盖集,这是保证2-近似比的关键。算法运行示例以前面的5节点图为例,假设起始顶点为A。算法的执行过程取决于边的选择顺序。执行路径1第一次迭代选取边AB将A和B加入C:C={A,B}去除所有与A或B相连的边剩余未覆盖的边:CE第二次迭代选取边CE将C和E加入C:C={A,B,C,E}所有边已被覆盖结果:顶点覆盖为{A,B,C,E},规模为4执行路径2第一次迭代选取边BC将B和C加入C:C={B,C}去除所有与B或C相连的边剩余未覆盖的边:空结果:顶点覆盖为{B,C},规模为2重要结论:算法的输出存在随机性,取决于边的选择顺序。但无论如何选择边,算法都能保证返回一个有效的顶点覆盖,且其近似比恒为2。2-近似算法的正确性证明结论:这表明算法返回的顶点覆盖规模最多是最优顶点覆盖规模的两倍,即该算法是一个2-近似算法。

旅行商问题(TSP)引入问题定义在旅行商问题中,输入为一个无向图G=(V,E),其中每条边(u,v)∈E都附有一个非负的整数代价c(u,v)。问题的目标是找出G中一条代价最小的哈密尔顿回路,即旅行商从某个起始城市出发,访问每个城市恰好一次,并最终返回起始城市。之前的求解方法枚举法:遍历所有可能的路径排列,时间复杂度为O(n!)分支限界法:通过剪枝减少搜索空间,但最坏情况仍为指数级共同问题:难以扩展到大规模实例近似算法的目标在多项式时间内得到一条"近似最优"的旅行路径,使得路径代价接近最优解我们将介绍两种方法:基于最小生成树的近似算法基于局部搜索的近似算法基于最小生成树的近似算法思想算法思路是利用最小生成树来构造一条近似最优的路径,这种方法通常称为"绕树两周"算法。01构造最小生成树以起始城市为根节点,对图G中的所有节点构造一棵最小生成树T。可使用Kruskal算法或Prim算法,时间复杂度为Θ(|E|log|E|)。02先序遍历生成树从根节点开始,对这棵最小生成树进行先序遍历。在初次访问一个节点时输出该节点,并且在访问一棵子树返回后输出该节点。节点的访问序列记为W。03删除重复节点扫描第二步中得到的节点访问序列W。从中消除重复出现的节点(不包括起始顶点)。最后得到一条哈密尔顿回路H,将它作为算法的输出。算法示例与可视化以一个包含5个节点的带权图为例,假设起始城市为A。执行步骤原始图G5个节点,多条带权边构造MSTA-D(5),A-C(6),D-E(5),B-E(4)总代价:20先序遍历访问序列W:A,C,A,D,E,B,E,D,A删除重复哈密尔顿回路H:A,C,D,E,B,A结果分析最小生成树T的代价:c(T)=20先序遍历序列W的代价:c(W)=2×20=40最终哈密尔顿回路H:A→C→D→E→B→A算法正确性分析下面我们证明"绕树两周"算法是一个用于解决满足三角不等式的旅行商问题的多项式时间2-近似算法。最优解与MST的关系设最优旅行路径为H*。通过删除H*中任意一条边,可以得到一棵生成树每条边的代价均为非负数,最优路径的代价必然不小于最小生成树T的代价:先序遍历的代价在算法的第二步中,我们对最小生成树T进行先序遍历,得到访问序列W。由于在先序遍历过程中T中的每条边被遍历两次,因此有:三角不等式的应用如果图中的顶点位于平面上,且顶点之间的旅行代价为它们之间的欧几里得距离,则距离满足三角不等式:在算法的第三步中,从访问序列W中删除重复节点。由于满足三角不等式,直接连接两次出现的节点不会比沿原路径更昂贵:近似比推导综合上述公式,可得:这证明了算法返回的哈密尔顿回路H的代价最多为最优旅行路径代价H*的两倍。

算法时间复杂度分析下面分析"绕树两周"算法各个步骤的时间复杂度,以证明该算法是一个多项式时间算法。构造最小生成树假设使用Kruskal算法构造最小生成树,其时间复杂度为:其中|E|为图中边的数量。先序遍历对最小生成树进行先序遍历,访问每个节点和每条边,时间复杂度为:其中|V|为图中顶点的数量。删除重复节点扫描访问序列并删除重复出现的节点,时间复杂度为:总体时间复杂度整个算法的时间复杂度由构造最小生成树的步骤主导:结论:该算法的时间复杂度为多项式级别,能够在合理时间内求解大规模TSP实例的近似解。基于局部搜索的近似算法局部搜索启发式算法是一类基于"邻域"思想的算法,它们从一个初始解出发,在解空间中不断探索当前解的"邻居",并在这些候选解中选择更优者作为新的当前解。核心思想从一个初始解出发定义邻域操作(如交换、插入、删除)在邻域中搜索更优的解迭代改进直到满足终止条件特点不保证找到全局最优解可能陷入局部最优实际应用中效果良好易于实现和理解2-opt算法2-opt算法是一种典型的局部搜索方法,其局部操作是交换路径中的两条边,并判断这种交换是否能够降低路径总长度。基本步骤选择一个初始路径选取两条不相邻的边检查交换后是否缩短路径如果改进则执行交换重复直到无法改进2-opt算法可视化1初始路径路径:A-B-D-E-C-A总代价:11+7+5+9+6=382第一次交换交换边AB和DE新路径:A-D-B-E-C-A新代价:5+7+4+9+6=31代价降低,执行交换3第二次交换交换边DB和EC新路径:A-D-E-B-C-A新代价:5+5+4+6+6=26代价降低,执行交换4第三次尝试尝试交换边AD和BC新路径代价:33代价增加,不执行交换5第四次尝试尝试交换边DE和CA新路径代价:31代价增加,不执行交换6算法终止达到预设迭代次数或无法继续改进最终路径:A-D-E-B-C-A总代价:26关键观察:通过局部交换操作,算法从初始代价38逐步优化到最终代价26,路径质量显著提升。总结与思考近似算法的核心价值效率与精度的平衡在多项式时间内求"足够好"的解避免指数级时间复杂度满足实际应用需求理论保证通过近似比量化解的质量为算法选择提供依据指导算法设计与改进广泛应用适用于NP困难问题在工程实践中效果显著是解决复杂优化问题的重要工具经典2-近似算法回顾顶点覆盖近似比:2时间复杂度:O(|E|)TSP绕树两周近似比:2(满足三角不等式)时间复杂度:Θ(|E|log|E|)TSP局部搜索特点:无严格近似比保证,实践效果好时间复杂度:取决于迭代次数集合覆盖问题问题定义集合覆盖问题是组合优化中的经典问题,广泛应用于诸如资源分配、网络设计和信息检索等领域。输入由一个全集U和一系列子集S={S₁,S₂,...,Sₘ}组成,目标是找到最少数量的子集,使得这些子集的并集等于全集U。贪心近似算法01初始化覆盖集C=∅未覆盖元素集合U'=U02贪心选择当U'不为空时:从子集S中选择一个子集Sᵢ,使得Sᵢ覆盖U'中最多的元素03更新状态将Sᵢ加入覆盖集C从U'中移除Sᵢ覆盖的所有元素04输出结果返回覆盖集C算法示例考虑全集U={1,2,3,4,5},子集集合S={S₁,S₂,S₃,S₄},其中S₁={1,2,3},S₂={2,4},S₃={3,4,5},S₄={1,5}。第一次选择:S₁和S₃都覆盖3个元素,假设选择S₁,则C={S₁},U'={4,5}第二次选择:S₃覆盖2个元素{4,5},选择S₃,则C={S₁,S₃},U'=∅最终结果:覆盖集为{S₁,S₃},共使用2个子集初始化:

C=∅，U′={1,2,3,4,5}。近似比：贪心算法在集合覆盖问题上的近似比为ln|U|背包问题的FPTAS算法我们曾利用动态规划算法求解0-1背包问题,其时间复杂度为Θ(nW),其中n为物品数量,W为背包容量。当W较大时,运行时间可能急剧增加,因为这种算法是一种伪多项式时间算法,而非严格的多项式时间算法。多项式时间算法时间复杂度仅依赖于输入规模(即输入数据的总长度)的多项式函数。例如:排序:O(n²)最小生成树:O(|E|log|E|)伪多项式时间算法不仅依赖于输入规模,还依赖于输入数值的大小。例如:背包问题:Θ(nW)当W很大时,运行时间可能非常高背包问题的FPTAS算法FPTAS核心思想完全多项式时间近似方案(FPTAS)利用值缩放技术,将原问题转化为一个规模较小的近似问题,使得动态规划算法的状态空间从依赖于W转化为依赖于缩放后的总价值。计算缩放因子Vₘₐₓ=max{v₁,v₂,...,vₙ}K=εVₘₐₓ/n缩放价值v'ᵢ=⌊vᵢ/K⌋动态规划求解在缩放后的值域上求解解的还原构建原问题的近似解时间复杂度:O(n³/ε),为多项式时间近似比:算法得到的解V满足V≥(1-ε)V*,是一个(1-ε)-近似算法背包问题的FPTAS算法i\v01234567891011121314151617181920212223242500∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞10∞∞∞2∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞20∞∞∞2∞3∞∞∞5∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞30∞∞∞2∞34∞∞56∞7∞∞∞9∞∞∞∞∞∞∞∞40∞∞∞2∞345∞567789∞91011∞12∞∞∞14

背包问题的FPTAS算法复杂度

子集和问题子集和问题是组合优化中的经典问题,其目标是从一组n个正整数构成的集合A={a₁,a₂,...,aₙ}中选出一个子集,使得该子集内所有元素之和恰好等于给定的正整数d。例如,若A={1,2,6,7}且d=9,则满足要求的子集有A₁={1,2,6}和A₂={2,7}。子集和问题的求解方法枚举法

动态规划

分支限界法为了获得精确解,此问题也可用分支限界法求解,但其最坏情况下时间复杂度仍为指数级。基于贪心策略的近似算法为了在合理时间内获得一个可接受的解,我们可以采用近似算法,其目标是找到一个子集,使得该子集的总和尽可能接近d,但不超过d。考虑如下基于贪心策略的近似算法:对集合A中的元素按降序排序,目的是优先选择较大的元素贪心选择:按顺序从最大元素开始,逐个尝试将元素加入子集中(只要加入后子集的和不超过目标值d)生成子集和s:最终形成一个子集,该子集的和为s,满足s≤d贪心算法示例与分析例如,对于A={1,2,6,7}和d=9:将A排序得到{7,6,2,1}初始子集S=∅,子集和s=0第一次迭代:加入7,S={7},s=7第二次迭代:尝试加入6,s=7+6=13>9,拒绝6第三次迭代:加入2,s=7+2=9,S={7,2}第四次迭代:尝试加入1,s=9+1=10>9,拒绝1最终,算法返回S={7,2}。算法的时间复杂度主要包括排序Θ(nlogn)和遍历Θ(n),总时间复杂度为Θ(nlogn)。2-近似算法证明上述算法是一个2-近似算法,下面进行证明。假设在贪心选择步骤中,u是第一个无法加入子集的元素。此时,总和s'为u之前的部分和。有:合并上述公式可得:因为s'≤d,s≥s',可推出:这说明算法返回的近似解总和s至少为d/2,即该算法是一个2-近似算法。FPTAS近似算法除了上述基于贪心的近似算法,还存在一种基于完全多项式时间近似方案的算法,使得近似解s:其中OPT表示原问题的最优解,d为目标和。精确解法的基本步骤

精确算法示例

迭代次数

移除大于d=9的元素后的集合0

1

2

3

4

修剪策略与近似算法

修剪原理

修剪算法

输出:修剪后的有序数组L'步骤:

返回L'基于修剪的近似算法示例

迭代次数列表修剪后列表删除大于目标值后的列表0

1

2

3

4

近似算法返回的近似解为32,与最优解33之间的误差为3%。启发式近似算法启发式近似算法是一类求解复杂优化问题的有效方法,其核心特征是通过合理的时间成本获得满足实际需求的近似解。这类算法虽不保证理论最优性,但在工程实践中展现出卓越的求解效率与解质量平衡能力。作为进化计算的典型代表,遗传算法(GeneticAlgorithm,GA)通过模拟生物进化机制,在旅行商问题(TSP)、组合优化、生产调度等NP-难问题领域取得了显著成效。本节将系统阐述遗传算法的理论基础、实现框架及其核心算子,并以经典TSP问题为例解析完整求解过程。遗传算法的基本设计思想遗传算法的基本设计思想源于自然进化的过程,即"适者生存,不适者被淘汰"。这种思想将优化问题映射到种群进化上:每个可行解都被编码成一个"个体"。变异操作在进化过程中,个体通过变异操作不断调整自身,提升"适应能力",即逐步朝着优化目标进化交叉繁殖不同个体之间通过交叉(繁殖)产生新的后代,从而有可能融合双方的优秀特性,生成更优的解自然选择经过多代迭代,经过自然选择的淘汰与优胜劣汰,种群中逐渐涌现出最适应环境的个体,也就是近似最优解总之,遗传算法利用模拟生物进化的机制,实现了从一组初始解向更优解逐步进化的过程,从而在复杂优化问题中获得高质量的近似解。遗传算法应用于旅行商问题01定义优化目标目标为从A出发,其余城市各访问一次,然后返回A的最短巡回路径02个体的表示在TSP中,每个可行解都编码为一个不含A的城市排列,例如⟨C,D,E,B⟩表示从城市A出发,依次经过C,D,E,B,最后回到A的路径03种群为丰富个体多样性,通常生成若干随机排列构成初始种群,每个个体代表一条可能的遍历路径。种群的多样性是产生优质后代的基础04选择从种群中选择较优个体作为父代05种群替换根据优化目标将新生成的后代与原种群合并,形成下一代种群06终止条件当达到预设的迭代次数或种群适应度收敛时,终止算法,并返回种群中适应度最高的个体作为近似解交叉操作对两个父代个体进行交叉操作生成后代。以顺序交叉为例:设两个父代个体分别为P₁=⟨B,C,D,E⟩和P₂=⟨C,E,B,D⟩。这里编码只包含城市B,C,D,E;起始城市A固定不变随机选取两个交叉点。假设在P₁中选取位置2和位置3(即第二和第三个城市),复制区间为⟨C,D⟩将复制区间⟨C,D⟩直接复制到后代对应的位置,即后代中位置2和位置3固定为⟨C,D⟩接下来,从P₂中按顺序扫描不在复制区间中的城市,填充后代中空缺的位置。按照P₂=⟨C,E,B,D⟩的顺序,从位置4开始扫描,然后环绕至位置1:第4个元素D已在后代中(固定区间包含D),跳过;环绕到第1个元素C,C也已存在,跳过;第2个元素为E;E不在后代中,将其填入第一个空缺位置(位置1);第3个元素为B;B不在后代中,将其填入下一个空缺位置(位置4)最终构造得到的后代为:Child=⟨E,C,D,B⟩。该后代代表的TSP路径为:从A出发,依次访问E,C,D,B,然后返回A变异操作以一定概率对个体进行变异操作,以保持种群多样性并防止陷入局部最优。以交换变异为例:假设一个个体为⟨C,D,E,B⟩。随机选择两个位置,例如选择位置2和位置3,交换这两个位置的城市,得到新的个体:⟨C,E,D,B⟩。这种具体的变异操作能够有效引入新的解,增加种群多样性,为全局搜索提供更多可能,从而有助于算法跳出局部最优。算法性能总结通过不断迭代,个体的适应度逐渐提高,较优的解逐步进化,最终得到最适应的个体,这个个体即为遗传算法所找到的近似解。虽然遗传算法没有严格的全局近似比保证,但在实践中,经过合理的编码、交叉、变异和参数调节,通常能在多项式时间内获得质量较高的近似解。近似算法的设计思路总结在近似算法领域,并未存在一种通用范式,可以直接应用到所有的困难问题上并立刻给出较好的近似比,因为不同的组合优化问题往往结构差异巨大。下面我们总结几种被广泛使用的设计思路。局部搜索局部搜索的基本思想是先给出一个可行解,然后反复尝试对解做"小扰动"(例如在解中加一个元素、删一个元素或替换一个元素),正如在2-opt算法中交换不相邻的两条边来生成新的路径,只要能令目标函数更好,就进行这一步扰动。局部搜索的思想非常简单,易于理解和实现,往往在实际场景也能获得不错的结果,但理论上证明其近似比非常困难。贪心算法贪心算法是一种非常重要且有效的设计近似算法的思想,贪心策略往往能够提供高效的启发式解法或保证一定近似比的解,正如本章讲述的顶点覆盖和集合覆盖问题。贪心算法的核心是每一步都选择当前最优(局部最优)的解,并希望通过局部最优的累积接近全局最优。这种思路实现起来通常非常直观,且能够快速运行。贪心算法的解容易通过数学分析或归纳法证明其近似比。FPTASFPTAS不仅是一种具体算法的实现方法,更是一种通用的算法设计思想,适用于目标函数可缩放和具有有限解空间的优化问题。它的核心思想包括通过舍入或缩放,将原问题转化为更小规模的等价问题。然后,在缩减后的状态空间上求解简化问题。遗传算法遗传算法是一种基于自然进化过程的启发式近似算法,广泛应用于解决各类组合优化问题,特别是在无法快速获得精确解的NP-难问题中。它将问题中的可行解视为"个体",这些个体在算法中构成种群,通过模拟生物进化的"选择-交叉-变异-替换"过程,逐渐产生适应度更高(目标函数值更优)的解。随机算法在算法设计中，随机算法是一类通过在执行过程中引入随机选择来提高效率或简化实现的算法。这种随机性可以帮助算法避免某些最坏情况，提高平均性能，甚至在许多问题上提供期望意义上的优良解法。随机算法允许在关键步骤中随机选择数据或操作,从而以一定的概率实现更高效的性能。随机算法的主要特点随机性算法的执行过程会依赖随机数的生成，因此即使在相同的输入下，不同的运行可能产生不同的结果。期望分析尽管随机算法的行为可能变化多样，其性能通常通过期望分析来得到理论保证。简单性与适应性随机性常常简化了算法设计，使其无需复杂的逻辑预处理，同时能很好地适应不同的输入特性。快速排序回顾让我们回顾一下快速排序，它的核心在于选择基准元素，并将数组分为两个子数组：一部分包含小于基准元素的值，另一部分包含大于基准元素的值。然而，在传统快速排序中，通常选择数组第一个元素或者最后一个元素作为基准元素，它通常会显著影响算法的效率。

随机化快速排序（RandQS）

核心思想：在数组中随机选择一个元素作为基准元素。

利用线性期望的性质可以得到：

在RandQS中，每次递归调用会选择一个分割元素y，然后将数组划分为左侧子数组（所有小于y的元素）和右侧子数组（所有大于y的元素）。

将概率代入期望公式，我们有：RandQS的独特性质需要注意的是，RandQS算法的运行时间依赖于算法在运行过程中做出的随机选择，而与输入数据的分布无关。即使对于相同的输入，算法在不同执行中可能表现不同，因为其行为受随机选择的影响。相关研究已证明，RandQS以非常高的概率，算法的运行时间不会超过其期望值太多，因此，几乎每次执行中，RandQS都能在一个高效的时间范围内完成，从而很好的解决了传统快速排序存在的性能退化问题。