《算法设计与分析》课件 chp7近似算法

近似算法在多项式时间内求得"足够好"的解引入与动机回溯法与分支限界法能够理论上找到最优解最坏情况下时间复杂度呈指数级增长难以在实际应用中高效求解实际需求许多实际场景中,对精确最优解的需求并不绝对苛刻只要在合理的时间内获得"足够好"的解就能满足需求近似算法应运而生在可接受的计算资源(通常为多项式时间)内求得一个与最优解"接近"的解平衡"解的精确度"与"算法运行效率"近似算法的定义核心思想近似算法关注于在可接受的计算资源(通常为多项式时间)内求得一个与最优解"接近"的解。关键要点关注计算效率与解的质量平衡适用于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,交换这两个位置的城市