近似算法 黄刘生 2013年9月16日 1.

Presentation on theme: "近似算法 黄刘生 2013年9月16日 1."— Presentation transcript:

1 近似算法 黄刘生 2013年9月16日 1

2 目录 Part1 NP-完全性理论 Part2 近似算法

3 1 NP-完全性理论 3 | Presentation Title | Month 2010

4 计算机科学的局限性 可解性：问题及其可解性可用函数和可计算性来代替
可计算性理论：研究计算的一般性质的数学理论，它通过建立计算的数学模型（例如抽象计算机），精确区分哪些是可计算的，哪些是不可计算的。 可计算函数：能够在抽象计算机上编出程序计算其值的函数。这样就可以讨论哪些函数是可计算的，哪些函数是不可计算的。 Church-Turing论题：若一函数在某个合理的计算模型上可计算，则它在图灵机上也是可计算的。 不可计算性：很多问题和函数是无法用具有有穷描述的过程完成计算 产生和历史： 可计算性理论起源于对数学基础问题的研究。20世纪30年代，为了讨论是否对于每个问题都有解决它的算法，数理逻辑学家提出了几种不同的算法定义。K.哥德尔和S.C.克林尼提出了递归函数的概念，A.丘奇提出λ转换演算, A.M.图灵和E.波斯特各自独立地提出了抽象计算机的概念（后人把图灵提出的抽象计算机称为图灵机），并且证明了这些数学模型的计算能力是一样的,即它们是等价的。著名的丘奇-图灵论题也是丘奇和图灵在这一时期各自独立提出的。 C-T论题中“合理”：计算函数的指令时有限条；每条指令只有有限个计算步骤；执行指令的过程是确定的 Church-Turing论题：可计算性是不依赖与计算模型的

5 停机问题 停机问题：能否写一个程序正确判定输入给它的任何一个程序是否会停机？
设程序halts(P,X)总是正确地判定程序P在其输入X上是否停机:若停机，则返回yes；否则死循环，返回no。设另有一程序: diagonal(Y){ a: if halts(Y,Y) then goto a; else halt; } diagonal（diagonal）是否停机？ 不可判定 它停机当且仅当halts(diagonal,diagonal)返回否，也就是： diagonal停机当且仅当它自己不停机，矛盾！ 即：halts(P,X)并不存在，停机问题是不可解的！ 功能：若halts断定当程 序Y用其自身Y作为输入 时Y停机,则diagonal(Y) 死循环；否则它停机 1936年图灵证明了停机问题的不可判定性，采用的是康托对角化方法

6 图灵机 …… 有单带、多带等变 种，计算能力等价 依据控制器的状态和读写头所读字符，决定执行以下3个操作之一、之二或全部：
有限状态控制器 输入带 …… 无限长 读写头 有单带、多带等变 种，计算能力等价 依据控制器的状态和读写头所读字符，决定执行以下3个操作之一、之二或全部： 1）改变有限状态控制器中的状态； 2）读写头在相应的方格中写一符号； 3）读写头左、右移一格或不动。 确定型图灵机DTM：若对任一个状态和符号，要执行的动作都是唯一的 非确定型图灵机NTM：若执行的动作是有穷多个可供选择 1936年图灵证明了停机问题的不可判定性，采用的是康托对角化方法

7 P、NP及NPC类问题 P类问题：一类问题的集合，对 其中的任一问题，都存在一个确定型图灵机M和一个多项式p，对于该问题的任何（编码）长度为n的实例，M都能在p(n)步内，给出对该实例的回答。即：多项式时间内可解的问题 NP类问题：一类问题的集合，对其中的任一问题，都存在一个非确定型图灵机M和一个多项式p，对于该问题的任何（编码）长度为n的实例，M都能在p(n)步内，给出对该实例的回答。 若NTM在每一步都恰有2步可供选择，则回答实例需考察2p(n)种不同的可能性。 存在多项式时间的算法吗？ 多项式时间内可验证问题（指验证其解的正确性）

8 P、NP及NPC类问题 多一归约 假设L1和L2是两个判定问题，f将L1的每个实例I变换成L2的实例f(I)。若对L1的每个实例I，I的答案为“是”当且仅当f(I)是L2的答案为“是”的实例，则称f是从L1到L2的多一归约，记作： L1≤mL2（传递关系） 直观意义：将求解L1的问题转换为求解L2的问题，而问题L1不会难于L2 多项式时间多一归约：若f是多项式时间可计算，则上述归约称为多项式时间多一归约，也称多项式时间变换。记作： ≤m满足反身和传递性 f是从问题L1到问题L2的多项式归约：f以某种方式在多项式时间内把问题L1的实例变换到L2的实例，使得I是问题L1的“是“实例当且仅当f(I)是问题L2的”是“实例

9 P、NP及NPC类问题 NPC问题：对于一个(判定性)问题q，若 (1)q∈NP (2)NP中任一问题均可多项式时间多一归约到q
则称问题q为NP-完全的(NP-complete，NPC) NP-hard问题：若问题q仅满足条件(2)而不一定满足条件(1)，则问题q称为NP-难的(NP-hard，NPH)。显然：NPC⊆NP-hard NPC和NP-hard关系 NP-hard问题至少跟NPC问题一样难。 NPC问题肯定是NP-hard的，但反之不一定 例：停机问题是NP-hard而非NPC的。 ∵该问题不可判定，即无任何算法(无论何复杂度)求解该问题 ∴该问题∉NP。但是 可满足问题SAT≤p停机问题 ≤m满足反身和传递性 NPC⊆NP-hard 有一类问题已被证明属于NP-hard但不属于NP，即，这类问题至少与NP-complete一样难，但这类问题又不属于NP（自然也不属于NPC）。例如围棋的必胜下法，就是这样一个问题。

10 P、NP及NPC类问题 NP=？P ∵确定型图灵机是非确定型图灵机的特例，∴P⊆NP 是否有NP⊆P？即是否NP=P？
美国麻省的Clay数学研究所于2000年5月24日在巴黎法兰西学院宣布：对七个“千年数学难题”中的每一个均悬赏100万美元，而问题NP=？P位列其首: 1.P问题对NP问题 2.霍奇猜想 3.庞加莱猜想( ，俄罗斯数学家佩雷尔曼在3篇论文预印本中证明了几何化猜想，2006被授予菲尔兹奖) 4.黎曼假设 5.杨－米尔斯存在性和质量缺口 6.纳维叶－斯托克斯方程的存在性与光滑性 7.贝赫和斯维讷通－戴尔猜想 ≤m满足反身和传递性 NPC⊆NP-hard 有一类问题已被证明属于NP-hard但不属于NP，即，这类问题至少与NP-complete一样难，但这类问题又不属于NP（自然也不属于NPC）。例如围棋的必胜下法，就是这样一个问题。 7个难题：P问题对NP问题 ，霍奇猜想，庞加莱猜想，黎曼假设，杨－米尔斯存在性和质量缺口，纳维叶－斯托克斯方程的存在性与光滑性，贝赫和斯维讷通－戴尔猜想 1. P问题属于NP问题，NPC问题属于NP问题。 2. NPC问题同时属于NP hard问题，是NP与NPhard的交集。

11 P、NP及NPC类问题 P、NP、NPC和NP-hard之关系 NPC是NP中最难的问题，但是NP-hard至少与NPC一样难
如何证明问题q是NP-hard或是NPC的？ 若已知q’∊NPC或q’∊NPH，且q’≤pq，则q∊NPH；若进一步有q∊NP，则q∊NPC。 即：要证q是NPH的，只要找到1个已知的NPC或NPH问题q‘，然后将q’多项式归约到q即可。若还能验证q ∊NP，则q是NPC的。 ∵ NP中任意问题均可多项式归约到q’，由于≤p有传递性 ∴他们也都能多项式归约到q，由定义可知q是NPH的

12 NP-完全性理论 Cook的贡献：第一个NPC问题
史提芬·库克(Stephen Arthur Cook，1939－)NP完全性理论的奠基人，他在1971年论文”The Complexity of Theorem Proving Procedures”中，给出了第一个NP完备的证明，即Cook定理： 可满足性问题（Satisfiablity problem) 是NP完全问题，亦即 SAT∈NPC。且证明了： SAT∈P当且仅当P=NP Cook于1961年获Michigan大学学士学位，1962和1966年分获哈佛大学硕士与博士学位。 ，他在UC Berkeley担任助教授；1970年加盟多伦多大学，现为该校CS和数学系教授，他的论文开启了NP完备性的研究，令该领域于之后的十年成为计算机科学中最活跃和重要的研究。因其在计算复杂性理论方面的贡献，尤其是在奠定NP完全性理论基础上的突出贡献而荣获1982年度的图灵奖。 整个计算机科学的大厦就建立在图灵机可计算理论和计算复杂性理论的基础上 一旦证明P=NP,将是计算机科学的一场决定性的突破,在软件工程实践中,将革命性的提高效率.从工业,农业,军事,医疗到生活,软件在它的各个应用域,都将是一个飞跃 P=NP吗? 这个问题是著名计算机科学家(1982年图灵奖得主)斯蒂文·考克（StephenCook ）于1971年发现并提出的

13 NP-完全性理论 Karp的贡献 理查德·卡普（Richard Karp，1935-）1972年论文”Reducibility among Combinatorial Problems”发展和加强了由库克提出的“NP完全性”理论。 尤其是库 克仅证明了命题演算的可满足问题是NP完全的，而卡普则证明了从组合优化中引出的大多数经典问题(背包问题、覆盖问题、匹配问题、分区问题、路径问题、调度问题等)都是NP完全问题。只要证明其中任一个问题是属于P类的，就可解决计算复杂性理论中最大的一个难题，即P=?NP。 Karp于1955、1956和1959年分别获哈佛大学文学学士、理学硕士和应 用数学博士学位，现任UC Berkeley计算机科学讲座教授，美国科学 院、美国工程院、美国艺术与科学院、欧洲科学院院士。因其在计算机科 学领域的基础贡献曾获图灵奖(1985)、冯诺依曼奖、美国国家科学勋 章、哈佛大学百年奖章等奖项. 理查德·卡普（Richard Karp）1935年1月3日生于波士顿，从小时起就兴趣广泛，聪明过人。在哈佛大学时他文理兼修，1955年先获得文学学士学位，第二年又获得理科硕士学位。之后他进入哈佛大学的计算实验室攻读博士，于1959年取得应用数学博士学位。理查德·卡普教授现任美国加州大学伯克利分校计算机科学讲座教授，美国科学院、美国工程院、美国艺术与科学院、欧洲科学院院士。因其在计算机科学领域的基础贡献曾获图灵奖、冯诺依曼奖、美国国家科学勋章、哈佛大学百年奖章等奖项，还担任美国科学院会刊（PNAS）等多个国际著名刊物编委 UC Berkeley大学教授Richard Karp于1980年当选美国国家科学院院士，1985年当选美国文理科学院院士，1985年获得了美国计算机学会设立的“图灵奖”。 这篇论文(提出了21个NP-完全问题的列表)还有另外一些贡献: 其一就是对计算复杂性理论中的术语进行了规范和统一。把有多项式时间算法的问题命名为P类问题，就是卡普在这篇论文中首次采用的，现在已为学术界所接受并普遍采用，这为学术交流带来了很大的好处。 其二是卡普在刻画NP类中的“最困难”问题类时，提出了与库克归约不同的另一种归约方法，称作“多项式时间多一归约”，有时直接把它叫做“卡普归约”。 其三，卡普的论文给出了“多项式谱系”或叫“多项式层次”(polynomial hierarchy)的基本思想

14 NP-完全性理论 NP-完全性理论的局限性 易解问题：可多项式时间内求解的问题 难解问题：需超多项式时间求解的问题
NP-完全性理论既没有找到第二类问题的多项式时间的算法，也没有证明这样的算法就不存在，而是证明了这类问题计算难度之等价性（彼此间困难程度相当）。因此，NPC具有如下性质：若其中1个问题多项式可解当且仅当其他所有NPC问题亦多项式可解 难解问题与易解问题之相似性 1）最短/最长简单路径 单源最短路径问题：对有向图G，时间O(VE)，P问题 两点间最长路径：NPC问题，即使所有边上权为1 2）欧拉环/哈密尔顿圈（G为无向图或有向图） 欧拉环：G中有通过每条边恰好一次的环？P，多项式时间可解 哈氏圈：G中有通过每个顶恰好1次的圈？NPC 整个计算机科学的大厦就建立在图灵机可计算理论和计算复杂性理论的基础上 一旦证明P=NP,将是计算机科学的一场决定性的突破,在软件工程实践中,将革命性的提高效率.从工业,农业,军事,医疗到生活,软件在它的各个应用域,都将是一个飞跃 P=NP吗? 这个问题是著名计算机科学家(1982年图灵奖得主)斯蒂文·考克（StephenCook ）于1971年发现并提出的

15 减少搜索量：分枝限界法，隐枚举法、动态规划等 可以提高效率，但时间复杂度不变
NP完全问题的求解 减少搜索量 简单算法是穷举搜索，时间为指数 减少搜索量：分枝限界法，隐枚举法、动态规划等 可以提高效率，但时间复杂度不变 优化问题 降低优化要求，求近似解，以得到一个多项式时间的算法。即：找寻在容许的时间内得到容许精度的近似最优解的算法 整个计算机科学的大厦就建立在图灵机可计算理论和计算复杂性理论的基础上 一旦证明P=NP,将是计算机科学的一场决定性的突破,在软件工程实践中,将革命性的提高效率.从工业,农业,军事,医疗到生活,软件在它的各个应用域,都将是一个飞跃 P=NP吗? 这个问题是著名计算机科学家(1982年图灵奖得主)斯蒂文·考克（StephenCook ）于1971年发现并提出的

16 2 近似算法 16 | Presentation Title | Month 2010 16 16 16 16

17 Ch.1导论 现实中许多优化问题是NP-hard的，由复杂性理论知：若P≠NP(很可能为真)，就不可能找到多项式时间的算法来对问题的所有输入实例求出最优解。但若放松要求，就可能存在有效求解算法。 实用中可考虑3种放宽要求的可能性： 1.超多项式时间启发 不再要求多项式时间算法，有时求解问题存在超多项式时间算法，实用中相当快。例如，0/1背包问题是NPC问题，但存在1个伪多项式时间算法很容易解决它. 缺点：该技术只对少数问题有效。 一个具有伪多项式时间复杂度的NPC问题称为弱NPC问题，否则为强NPC问题

18 Ch.1导论 2.启发式概率分析 缺点：选取一个特殊的输入分布往往是不易的。 3.近似算法
不再要求问题的解满足所有的输入实例。在某些应用中，有可能输入实例的类被严格限制，对这些受限实例易于找到其有效算法。而这种结果往往归功于对输入实例约束的概率模型。 缺点：选取一个特殊的输入分布往往是不易的。 3.近似算法 不再要求总是找到最优解。在实际应用中有时很难确定一个最优解和近似最优解(次优解)之间的差别，因问题的输入实例数据本身就可能是近似的。 设计一个算法能够求出所有情况下的次优解来解NP-hard问题往往是真正有效的手段。 一个具有伪多项式时间复杂度的NPC问题称为弱NPC问题，否则为强NPC问题

19 Ch.1导论 优化问题近似解分类 Knapsack，Scheduling，Bin Packing等 2）中等难度
1）容易近似 Knapsack，Scheduling，Bin Packing等 2）中等难度 Vertex Cover，Euclidean TSP，Steiner Trees等 3）难于近似 Graph Coloring，TSP，Clique等 这类问题即使找到很差的近似解也是NP-hard 一个具有伪多项式时间复杂度的NPC问题称为弱NPC问题，否则为强NPC问题

20 §1.1预备知识和基本定义 Def1.1 一个优化问题∏由三部分构成： 实例集D：输入实例的集合
解集S(I)：输入实例I∊D的所有可行解的集合 解的值函数f：给每个解赋一个值，f：S(I)→R 一个最大值优化问题∏是： 对于给定的I∊D，找一个解 使得： =上有三角≜ 此最优解的值称为OPT(I),即： 有时不太严格地可称其为最优解

21 §1.1预备知识和基本定义 装箱问题（BP） 非形式地，给定一个size在0,1之间的项的集合，要求将其放入单位size的箱子中，使得所用的箱子数目最少。故有最小优化问题： 1)实例: I={s1, s2, … , sn}, 满足∀i, si∈[0,1] 2)解: σ={B1, B2, … ,Bk}是I的一个不相交的划分，使得 ∀i, Bi⊂I 且 3)解的值：使用的箱子数,即f(σ)=│σ│=k =上有三角 最小优化问题是求最小的k

22 §1.1 预备知识和基本定义 约定 1）f的值域和I里的所有数是整数 易于扩展至有理数
2）对任何σ ∈S(I)，f(σ)受囿于多项式(对I中数的size) 只讨论NP完全的优化问题，因为它易被转换为判定问题 Def1.2 若一个NPH判定问题Π1是多项式可归约为计算一个优化问题Π2的解，则是Π2 NPH的 。 典型情况是问题Π1是问题Π2的判定版本。若Π2是最大值问题，则Π1的形式为： “是否存在σ ∊D(I)，使得f(σ) ≥k？” NPC原来主要是应用到语言或判定问题问题上，但将最优解的值和输入实例一起作为输入，则可将其转换为判定问题：

23 §1.1 预备知识和基本定义 Def1.3 一个近似算法A，是一个多项式时间求解优化问题Π的算法，使得对一个给定的Π的输入实例I，它输出某个解σ∊S(I)。通常，我们用A(I)表示算法A所获得的解的值f(σ)。（有时不太严格地也可表示其解） 近似算法的性能 算法质量(measure of goodness)是在最优解和近似解之间建立某种关系，这种度量也称为性能保证(Performance guarantees)。 NPC原来主要是应用到语言或判定问题问题上，但将最优解的值和输入实例一起作为输入，则可将其转换为判定问题：

24 §1.2 绝对性能保证 在可行的时间内，求装箱问题的最优解是不可能的，但可求次最优解是多少？显然，比最优解多使用1个箱子的解是次最优的。一般地，我们希望找到1个近似解，其值与最优解的值相差某一小的常数。 Def1.4：绝对性能度量 一个绝对近似算法是优化问题Π的多项式时间近似算法A，使得对某一常数k>0满足： ∀I∈D，|A(I)-OPT(I)| ≤ k K也是算法A的绝对误差。 显然,我们期望对任何NP-hard问题都有一个绝对近似算法，但是对于大多数NP-hard问题，仅当P=NP时，才能找到绝对近似算法(指多项式时间)。

25 §1.2.1 绝对近似算法 1、图的顶点着色 使用最少的颜色数来为图G的顶点上色，使得所有相邻的顶点均有不同的颜色，即使G是平面图，该问题的判定版本也是NP-hard的，它有1个绝对近似算法。 Th1.1：判定一个平面图是否可3着色的问题是NPC的。 近似算法A(G){//对任意平面图G染色 1)检验G是否可2染色(即G是二部图?),若是则G可2染色; 2)否则,计算5染色;//可在多项式时间内,∵任何平面图G是//可5染色的(实际上四色定理告诉我们G是可4染色的) } 这就证明了算法A比最优解多用的颜色数不会超过2： Th1.2：对给定的任意平面图G，近似算法A的性能满足: |A(G)-OPT(G)| ≤ 2 ∵

26 §1.2.1 绝对近似算法 2、图的边着色 使用最少的颜色为图的边上色，使得所有相邻的边有不同的颜色。如下定理(Vizing)说明最大度数Δ与边着色数之关系： Th1.3：任一图至少需要Δ，至多需要Δ+1种颜色为边着色 Vizing定理的证明给出了一个多项式时间的算法A找到Δ+1边着色，但令人惊奇的是边着色问题即使是很特殊的情况也是NP-hard的，正如下述的Holyer定理： Th1.4：确定一个3正则平面图所需的边着色数问题是NPH. 综上所述：存在绝对近似算法A，使得下述定理成立： Th1.5：近似算法A有性能保证：|A(G)-OPT(G)| ≤ 1

27 §1.2.2 绝对近似算法之否定 前面的例子似乎说明只有很特殊的一类优化问题可能有绝对近似算法：已知最优解的值或值所在的小范围。但最优解的值不易确定时是否有绝对近似算法仍然是open. 对于大多数NP-hard问题，存在绝对近似算法(多项式时间)当且仅当存在多项式的精确算法（即：可在多项式时间内找到最优解） 否定结果：证明问题的绝对近似算法的不存在性！ 如何证明一个问题的绝对近似算法是不存在的？否定结果可避免做无用功！

28 §1.2.2 绝对近似算法之否定 0/1背包问题 问题实例： 项集：I={1,2,…,n} 大小：s1,s2,…,sn
0/1背包问题 问题实例： 项集：I={1,2,…,n} 大小：s1,s2,…,sn 利润：p1,p2,…,pn 背包容量：B 问题的一个可行解是子集I’⊆I， 最优解是使得f(I’) = 最大的可行解 注意：我们假定近似算法是多项式时间的 该问题(0/1背包）是NP-hard的，除非存在多项式时间算法能够找到最优解，否则不存在绝对近似算法。

29 §1.2.2 绝对近似算法之否定 即：我们已经找到了一个多项式时间的算法A， 它对背包问题的任一输入实例I，均能找到最优 解。
Th.1.6 若P≠NP，则对任何确定的k，找不到近似算法A可解背包问题使得：|A(I)-OPT(I)| ≤ k Pf：使用扩放法反证。 假定存在算法A具有性能保证k（注意k是正整数） 设∀I∊D，可构造新实例I’使得 si=si’ pi’=(k+1)pi 即：除了利润扩放k+1倍之外，其余参数不变。故I的可行解也是I’的可行解，反之亦然。只是解的值相差k+1倍。 在I’上运行算法A获得解A(I’)，设A在实例I上的解是σ： |A(I’)-OPT(I’)| ≤ k ⇒ | (k+1)f(σ)-(k+1)OPT(I)| ≤ k ⇒ |f(σ)-OPT(I)| ≤ k/(k+1) ⇒ |f(σ)-OPT(I)|=0 即：我们已经找到了一个多项式时间的算法A， 它对背包问题的任一输入实例I，均能找到最优 解。 如何证明一个问题的绝对近似算法是不存在的？ 注意：I、f(σ)和OPT(I)等均为整数

30 §1.2.2 绝对近似算法之否定 上述证明之关键是Scaling性质，输入实例中数字间线性相关很易使其成立。对非数字问题Scaling性质是否仍然成立？ 团(Clique)问题 找图G中最大团（最大完全子图），该问题是NP-hard的。 Th.1.7 若P≠NP，则对于团问题不存在绝对近似算法 Pf：定义图的m次幂Gm：取G的m个拷贝，连接位于不同副本里的任意两顶点。 Claim：G中最大团的size为α当且仅当Gm里最大团的size是mα（Ex.） 这里的例子说明在纯组合问题上，依然可用扩放性质 顶点集C被称为无向图 G=(V,E) 的团，如果C是顶点集V的子集(C⊆V)，而且任意两个C中的顶点都有边连接。另一种等价的说法是，由C诱导的子图是完全图 （有时也用“团”来指这样的子图）。 极大团是指增加任一顶点都不再符合团定义的团，也就是说，极大团不能被任何一个更大的团所包含。 最大团是一个图中顶点数最多的团。图G的团数（clique number）ω(G) 是指G中最大团的顶点数。图G的边团覆盖数（edge clique cover number）是指覆盖G中所有的边所需要的最少的团的数目。图G的二分维数（bipartite dimension）是指覆盖G中所有边所需要的最少的二分团的数目，其中二分团（biclique）就是完全二分子图 。而分团覆盖问题 （Clique cover problem）所关心的是用最少的团去覆盖G中所有的顶点。 独立集（independent set）是刚好和团相反的概念，因为图G中的团和图G的补图中的独立集是一一对应的。

31 §1.2.2 绝对近似算法之否定 反证：设G是任意的无向图，近似算法A给出的绝对误差是k。在Gk+1上运行A，若G中最大团size为α,则我们有 |A(Gk+1)-OPT(Gk+1)| ≤ k ⇒ |A(Gk+1)-(k+1)OPT(G)| ≤ k 对于任给的Gm中体积为β的团，易于用多项式时间在G中找到一个体积为β/m的团。因此我们能够在G中找到一个团C，使得： | |C|-OPT(G) | ≤ k/(k+1) 因为C和OPT(G)均是整数，故C是最优团。 Claim直接给出了最优解之间的scaling性质：OPT(GK+1)=(k+1)OPT(G)

32 §1.3 相对性能保证 虽然我们渴望得到绝对性能保证，但是较难的优化问题很难找到绝对近似算法。因此，需要放松对“好的近似算法”的要求。 §1.3.1 多机调度 考虑简单的多机调度问题：输入n个作业J1，J2，…，Jn，相应的运行时间为P1，P2，…，Pn，设每个Pi是有理数。将n个作业分配到m台同样的机器上，以使得完成时间最短。完成时间定义为：所有机器上作业运行总时间最长的那一台机器的运行时间。 可行解集合：n个作业被划分为m个子集，一个解的值是所有子集中总运行时间最长的子集的运行时间。该问题即使在m=2时也是NP-hard的。

33 §1.3.1 多机调度 List调度算法(Graham)：将n个作业依次以online的方式分配到m台机器中的某一台上，规则是将当前作业分配到当时负载最小的机器上，而机器负载是分配给它的所有作业的总的运行时间。 Th.1.8 设A表示List调度算法，则对于所有输入实例I 界是紧致的，因为存在一个实例I*，使得上式相等： A(I*)/OPT(I*)=2-1/m Pf：先证近似比上界。不失一般性，假定所有作业分配完毕后，机器M1的负载最大。设L表示M1上所有作业总运行时间,

34 §1.3.1 多机调度 Jj L- Pj L ∙∙∙ Mm M2 M1 Pf(续)：设Jj是M1上最后一个分配到的作业，则其它机器上的负载均大于等于L-Pj。这是因为当Jj被分配到M1时，M1是负载最小的机器，其负载为L-Pj。于是可得： 但I的最优解的值显然满足： 由于A(I)=L，故有： OPT(I)≥(L-Pj)+Pj/m=A(I)-(1-1/m)Pj ∵必须有某台机器执行作业Jj，∴OPT(I) ≥Pj 于是：A(I)/OPT(I) ≤2-1/m

35 §1.3.1 多机调度 Pf(续)：现证近似比的紧确界。考虑输入实例I*，设 n = m(m-1)+1
设前n-1个作业每个均有运行时间1，而最后1个作业Jn有Pn=m。易于证明：OPT(I*)=m，而A(I*)=2m-1 故有： A(I*)/OPT(I*)=2-1/m Mm M1 ∙∙∙ Mm-1 m个时间为1的Job Jn 最 优 解 M1 ∙∙∙ Mm-1 m-1 近 似 解 Mm Jn m

36 若RA(I) ≤（1+∊），则称A是(1+∊)－近似算法，1-近似算法产生最优解
§1.3.1 多机调度 上述结果导出了近似算法质量的另一种度量方法：相对性能度量。其形式化定义如下 Def.1.5 设A是优化问题Π的一个近似算法，算法A在一个输入实例I上的性能比RA(I)被定义为： ≥ 若RA(I) ≤（1+∊），则称A是(1+∊)－近似算法，1-近似算法产生最优解 此定义统一使近似比(性能比)RA(I)≥1，越接近1越好

37 RA=inf{r≥1:对于所有的实例I，RA(I) ≤r}
§1.3.1 多机调度 Def1.6 对于优化问题Π，近似算法A的绝对性能比RA是 RA= inf{ r│RA(I) ≤r, ∀I∈D } 即： RA是性能比上界集合中的下确界(最大下界) 例如：对于List调度算法A,我们有: RA=2-1/m 更好的调度是LPT(Longest Processing Time)：将作业按其运行时间递减序排序,然后用List策略调度,其结果: Th.1.9：LPT算法的性能（近似）比： ≥ 注意：绝对性能比与具体实例I无关 RA=inf{r≥1:对于所有的实例I，RA(I) ≤r} RLPT是绝对性能比。即A(I)/OPT(I) ≤4/3-1/3m Pf：当m=1时， ∵ A(I)=OPT(I) ∴A(I)/OPT(I)=4/3-1/3 设对某个m＞1，该定理不成立。

38 §1.3.1 多机调度 Pf(续)：则可设违反该定理具有最少作业数的实例I是J1,J2,…,Jn, 不妨设P1≥ P2≥… ≥Pn
LPT的调度次序是J1,J2,…,Jn,其完成时间是A(I)。设其中最迟完成的作业是Jk，则k=n。否则，若k＜n，算法A运行作业J1,J2,…,Jk(记为实例I’⊂I)的完成时间仍是A(I)，即A(I)=A(I’)，而对最优解显然OPT(I’) ≤OPT(I)，故有： 这与I是违反定理的最少作业数的实例矛盾,∵│I’│<│I│

39 ⇒ §1.3.1 多机调度 现证明：对于实例I的最优调度，在任何机器上分配的作业数不超过2，因此n≤2m
A(I) ∙∙∙ Mm Mi M1 Pn 现证明：对于实例I的最优调度，在任何机器上分配的作业数不超过2，因此n≤2m ∵Jn是LPT调度A中最迟完成的作业，∴在A中它开始于时刻A(I)-Pn，且此刻其它机器均无空余时间，即: ⇒ 另一方面，因为

40 §1.3.1 多机调度 当最优调度在任何机器上至多包含2个作业时，LPT也 是最优的。证明如下：
∵ Pn是时间最短的作业 ∴ 实例I的最优调度中任何机器上的作业≤2 当最优调度在任何机器上至多包含2个作业时，LPT也 是最优的。证明如下： 不妨设n=2m，若n<2m，则令Jn+1,…,J2m的时间均为0，将 其加人I，不妨设P1≥P2≥… ≥ P2m

41 §1.3.1 多机调度 设最优调度使得每台机器恰有2个作业：Ji和Jj，则必有 i≤m,j＞m。否则若某最优调度O有i,j≤m，则定有某台机器 上有Js和Jt，使得s,t>m. ∵Pi,Pj≥Ps,Pt，交换Pj和Pt，则 Pi+Pt≤Pi+Pj Ps+Pj≤Pi+Pj 交换后的调度O’的最迟完成时间只可能减少，故O’也是最 优调度。对于i,j>m可类似证明。 ∴必有最优调度使J1,...,Jm分别分配到M1,…,Mm上，当将 Jm+1,...,J2m分配到M台机器上时，LPT是将长时间的作业分 配到轻负载上，必与该最优调度结果相同。 证明留为作业

42 §1.3 相当性能保证 有时，绝对性能比可能并不是好的性能保障。因为可能存在输入实例使得最优解的值很小，而近似算法的性能也仅与最优值稍有不同，但此时其近似比仍然会过大。为此可定义： Def1.7：一个优化问题Π的近似算法A, 其渐近性能比为: 但未必有: 显然有: 渐近性能比=inf{r≥1：存在n∊Z+，对所有满足OPT(I) ≥n的实例I，RA(I) ≤r} 亦可定义为：渐近性能比=inf{r≥1：存在n∊Z+，对所有满足I≥n的实例I，RA(I) ≤r} 对于有Scaling性质的问题，近似算法的绝对性能比和 渐近性能比是相同的，为什么？但多数优化问题无此 性质！

43 §1.3 相当性能保证 § 1.3.2 装箱问题（BP） 对于一个最小化问题，如何求性能比的上界？ 1）证明A(I) 关于某个参数x的上界；
§1.3 相当性能保证 对于一个最小化问题，如何求性能比的上界？ 1）证明A(I) 关于某个参数x的上界； 2）证明OPT(I)关于x的下界 然后从这两个不等式中消除x即可的性能比。 § 装箱问题（BP） 装箱定义如前。即：设有n件物品，每件物品大小 Si∈[0,1](1≤i≤n)，按某种策略将其装入大小为1的若干 箱子中，使箱子数尽可能小。

44 § 1.3.2 装箱问题（BP） 首次适应(First Fit, FF)算法
FF策略：依次将物品装箱，设当前要装第i件，B1,B2,…,Bj是当前已开过的箱子，则从头依次扫描箱子，将物品i放入第1个适合(指大小够放)的箱子中；若不存在适合的箱子，则新开箱子Bj+1，将物品i放入其中。 Claim：对所有实例，RFF(I)≤2 Pf:在整个装箱过程中至多只有1个箱子是大于半空的。 若否，不妨设Bi和Bj均大于半空且i<j，则第1件放入Bj 的物品大小至多是0.5，按照FF策略该物品应该放入Bi 而不应该打开新箱子Bj。

45 § 1.3.2 装箱问题（BP） 近似算法FF的上界 所有物品总size至少为FF使用的箱子总数的一半：
⌈∑Si⌉≥FF(I)/2，即FF(I) ≤2 ⌈∑Si⌉ 最优解的下界 所有物品总size是最优解的下界： OPT(I)≥⌈∑Si⌉ 故有： 可以证明上述比可达7/4 Th =1.7且更精确地有： ∀I, FF(I)≤1.7OPT(I)+2 ∃I, FF(I)≥1.7(OPT(I)-1) 渐近性能比不同 于绝对性能比！

46 § 1.3.2 装箱问题（BP） 递减首次适合 (First Fit Decreasing FFD)
Th1.11 RFFD≥3/2, 但是： 渐近性能比不同于绝对性能比！

47 § 1.3.3 旅行商问题（TSP） TSP问题（Travelling Salesman Problem)
设G是具有n个城市的地图，旅行商从其中某一城市出发周游，遍历每个城市1次恰好1次后回到出发地，求其最短的周游路线。亦即，求一条最短的哈密顿回路(Hamiltonian Cycle，简称HC)。 因为边的长度可以为无限大，因此不妨设G为边加权 的无向完全图。下面只考虑TSP的特殊版本：满足三角 不等式的ΔTSP（Metric TSP）问题。

48 § 1.3.3 旅行商问题（TSP） Def1.8: ΔTSP是TSP的特例，所有输入满足三角不等式，即对所有顶点i，j和k，边的长度满足：
d(i,k) ≤d(i,j)+d(j,k) 几何意义：去掉途中1个中转站不会使路径长度增加 近邻法(NN) 从任一顶点开始，在每一步从当前顶点出发去访问 一个最近的尚未访问过的顶点，由此构造哈密尔顿 圈。但这种方法性能差。 Th 设ΔTSP的调度数为n，则

49 § 旅行商问题（TSP） MST启发：有几种启发已达到渐近性能比2, 大多数好的启发式是基于找到一个欧拉环(Euler Tour,简称ET)，然后使用“Short-cut”来获得一个哈密尔顿圈。 Def1.9 设G是一个多重图，G的一条欧拉路是一条经 过每个顶点至少一次、经过每条边恰好一次的周游路 线。 Th.1.13 一个多重图G有一个欧拉环当且仅当G连通且 所有顶点的度数为偶数(易在多项式时间内构造一个 欧拉环）。 基于MST启发的ΔTSP的近似算法：求G的任一MST T ； 重复T的边构造一欧拉环ET；从ET产生一哈密尔顿圈 。 连通的无向图G有欧拉路径的充要条件是：G中奇顶点（连接的边数量为奇数的顶点）的数目等于0或者2， 奇数点是起点和终点。 连通的无向图G是欧拉环（存在欧拉回路）的充要条件是：G中每个顶点的度都是偶数

50 § 1.3.3 旅行商问题（TSP） Alg. MST： Input：G(V,E)和距离函数d Output：G里的一个哈密尔顿圈
B C E Alg. MST： Input：G(V,E)和距离函数d Output：G里的一个哈密尔顿圈 1.在G里找一棵最小生成树T； 2.通过将T的每条边复制一copy构造一多重图T’； 3.在T’中找一欧拉圈ET； 4.通过短路欧拉路的方法构造哈密尔顿圈HC： 从任一顶点出发，沿着欧拉圈前进，遇新顶点则访 问，遇到重复顶点则直接跳到下一未访问过的顶点， 最终回到出发点即可。 ET： ABCBDBAEA； HC：ABCDEA 连通的无向图G有欧拉路径的充要条件是：G中奇顶点（连接的边数量为奇数的顶点）的数目等于0或者2， 奇数点是起点和终点。 连通的无向图G是欧拉环（存在欧拉回路）的充要条件是：G中每个顶点的度都是偶数

51 § 1.3.3 旅行商问题（TSP） Th.1.14 用MST启发解ΔTSP时，有：
Pf： 正确性：∵T’连通且每个顶点度为偶数，故可找到欧 拉环；在完全图的假定下，step4产生一个哈密尔顿圈。 若H是G的边集，则d(H)表示H里所有边的长度之和。 ∵任何哈密尔顿圈去掉1条边后都是1棵生成树 ∴OPT(G) ≥ d(某生成树) ≥ d(T) d(ET) = d(T’) = 2d(T) ≤ 2OPT(G) 短路过程确保AMST(G) ≤ d(ET) ≤ 2OPT(G): 因为短路是 用1条非欧拉边取代2或多条欧拉边，三角不等式保证其成 立。故有： 连通的无向图G有欧拉路径的充要条件是：G中奇顶点（连接的边数量为奇数的顶点）的数目等于0或者2， 奇数点是起点和终点。 连通的无向图G是欧拉环（存在欧拉回路）的充要条件是：G中每个顶点的度都是偶数

52 § 旅行商问题（TSP） CH启发(Christofides) 避免从MST T到欧拉环的双边， 为T的每对奇度顶点加一条边使之度数为偶数。∵T中 所有顶点度数之和为2|E|，∴奇度顶点总数为偶数。 V(G)的子集S的一个匹配是E(G)的一个子集，其中所有边 的端点集恰为S，S中每个顶点恰好依附匹配集中的一条 边。∵G是完全图，故任一S均存在一个匹配(|S|为偶数)。已 证明，可在多项式时间内找到S的一个最小权匹配。 连通的无向图G有欧拉路径的充要条件是：G中奇顶点（连接的边数量为奇数的顶点）的数目等于0或者2， 奇数点是起点和终点。 连通的无向图G是欧拉环（存在欧拉回路）的充要条件是：G中每个顶点的度都是偶数 Pf：设M是T中奇数点集O上的最小权匹配集，则可断言：

53 § 1.3.3 旅行商问题（TSP） 在1个最优解中做短路操作以排除不在O中的顶点，所 得的圈X(O上的圈)必满足：
d(X) ≤ OPT(G) (由Δ不等式决定) 点集O上的圈必是O的两个匹配集的并。∵T中奇度顶点 是偶数个, ∴|O|=m为偶数。O上圈有m条边，但是O上的一 个匹配集只有m/2条边，故该圈是2个匹配集之并。 这两个匹配集之一的权必定至多是圈X的一半，而M是 O的最小权匹配集，故有： d(M) ≤ d(x)/2 ≤ OPT(G)/2 A T 连通的无向图G有欧拉路径的充要条件是：G中奇顶点（连接的边数量为奇数的顶点）的数目等于0或者2， 奇数点是起点和终点。 连通的无向图G是欧拉环（存在欧拉回路）的充要条件是：G中每个顶点的度都是偶数 B 例：O={B,C,D,E}.匹配M1={(B,E),(C,D)}, M2={(B,C),(D,E)}.M1∪M2是O上圈 E C D

54 § 1.3.3 旅行商问题（TSP） ∵图T∪M中所有顶点度为偶数，∴可从其构造欧拉环ET
d(ET) = d(T∪M) ≤ 1.5OPT(G) 用短路法从ET构造HC不会使权增加，故有： ACH(G) ≤ d(ET) ≤ 1.5OPT(G)，即： 近似比1.5是目前最好的结果，但是要找一个最小权值 匹配需要O(n3)时间，而MST启发的运行时间几乎是线性 的(求MST除外)。

55 § 相对近似之否定结果 为什么有的问题易于近似，而有的问题难于近似？遗 憾的是问题的近似算法之间似乎没有什么联系，尽管这 些问题的最优算法是紧密相关的(NPC问题彼此相关)。 例：顶点覆盖(VC)和最大独立集(MIS)。设G(V,E)是图。 VC问题：G的顶点覆盖是一顶点集C⊆V使得E中每条边至 少有一端点在C中，VC问题是在图中找一个顶点数最小的 覆盖。 MIS问题：G的独立集是一顶点集I⊆V使得I里任何点对之 间无边，MIS问题是在G中找一个最大的独立集。 设G是任意图，C是一顶点覆盖当且仅当I=V\C是一独立 集，且C是VC的最优解当且仅当I是MIS的最优解

56 § 1.3.4 相对近似之否定结果 VC和MIS的最优解是如此相关，他们的近似是相关问题 吗？否！
§ 相对近似之否定结果 VC和MIS的最优解是如此相关，他们的近似是相关问题 吗？否！ ∵对于VC问题有一个近似比为2的近似算法；但是对于MIS 问题，我们并未找到性能比好于O(n)的近似算法。为什么 VC的近似无助于MIS的近似？ 设VC对图G的1个最优解OPTVC(G)=n/2-1(即最小覆盖的顶 点数)，∵近似比为2，∴近似解AVC(G)≤2OPTVC(G)=n-2.解 AVC给出的顶点覆盖集的补集(即独立集AMIS)的size为2；而 OPTVC(G)的补集(即最优的独立集OPTMIS)的size为n/2+1。 故：

57 § 相对近似之否定结果 尽管NP-hard归约对优化问题的近似行为揭示的不 够，但是我们仍能使用NPC理论来证明：除非P=NP，某 类近似算法不存在。 Def.1.10 对于一个优化问题Π，最佳可达性能比RMIN(Π)定 义为： RMIN=1：最希望的结果，这类问题是容易近似的 RMIN有界：如ΔTSP问题 RMIN无界：难于近似。下面先考虑此类问题

58 § 1.3.4 相对近似之否定结果 Th.1.16 若P≠NP，则RMIN(TSP)=∞ Pf：假定有一算法A对某常数k满足：
§ 相对近似之否定结果 Th 若P≠NP，则RMIN(TSP)=∞ Pf：假定有一算法A对某常数k满足： 基本思想：使用A构造一个多项式时间的算法解决HC问 题，因为HC是NPC的，若P≠NP，则矛盾！ 假定G(V,E)是无向无权图，可为TSP构造实例I： 设H是V上的完全图，H中来自于E的边长度置为1，其余边 长置为kn，n=|V|。 Claim：若G有HC则OPT(I)=n；否则OPT(I)≥(k+1)n-1 将I作为A的输入实例。若G有HC，则A(I)≤kOPT(I)=kn； 否则，A(I)≥OPT(I)≥(k+1)n-1。 因此，可通过A找到的解之值来判定G中是否存在HC。 即：将HC问题多项式时间归约到A，与HC是NPC矛盾！ Claim:若G无HC，则因为H是完全图，存在HC。H的最小HC至少有一条边不是E的，其长为kn

59 § 1.3.4 相对近似之否定结果 绝对近似之否定：很多问题找不到绝对近似算法 相对近似之否定：有些问题的有界性能比近似算法不存在
§ 相对近似之否定结果 绝对近似之否定：很多问题找不到绝对近似算法 相对近似之否定：有些问题的有界性能比近似算法不存在 两类近似算法之间的近似性能（相对误差）：A是一个 f(n)-近似算法当且仅当对每个size为n的输入实例I，有： 假定OPT(I)>0 BP的一个近似算法A满足：|A(I)-OPT(I)|≤O( lg2OPT(I) ) 蕴含着渐近性能比为1。

60 § 1.4 其他 近似方案(Approximation Scheme)
§ 1.4 其他 近似方案(Approximation Scheme) 一个优化问题Π的近似方案是一个算法A，它以实例I和 误差界ε作为输入，且有性能保证: RA( I, ε)≤ 1+ε。 对于最小化问题，ε是相对误差。实际上，算法A对应一 个算法族{Aε：ε>0}使得 多项式近似方案(PAS: Polynomial Approximation Scheme) 是一近似方案{Aε}，对任一确定的ε，每个算法均以其 size[I]的多项式时间运行。 完全多项式近似方案(FPAS: Fully PAS) 是一近似方案{Aε}，对任一确定的ε，每个算法均以 其size[I}和1/ε的多项式时间运行

61 § 1.4 其他 理想的近似方案 近似方案实际上研究近似算法的运行时间和近似质量之 间的关系（二者间如何折衷？）。希望：近似算法的运 行时间并不随着性能比的减少而增长太快！ 理想情况：ε减小1个常数因子，为获得预期的近似质 量，所增加的运行时间不应超过1个常数因子(尽管两常 数因子不一定相同) PAS VS FPAS 背包问题的PAS中，算法Aε的运行时间一般是nO(1/ε)； 多机调度的PAS中，算法Aε的运行时间为O(m1/ε)。显 然，ε减小一点将会引起算法时间的急剧增加。为此， 引进FPAS可克服此缺点。

62 § 1.4 其他 例子：调度问题的近似方案 假定n>m，运行时间为降序(i<j蕴含Pi>Pj)，对每一整数 k∊[0,n]定义算法Ak： Algorithm Ak： Input：n个作业的运行时间{P1,…,Pn}和机器数m； Output：一个可行的调度； Step1：最优调度前k个作业J1,…,Jk； Step2：从前一步所获得的部分调度开始，使用LPT规则 调度剩余作业。 LPT策略：取下一运行时间最长尚未调度的作业，将其分 配到当前负载最轻的机器上。该算法显然是多项式时间的

63 § 1.4 其他 Th.算法AK的绝对性能比 ： Proof： 设K表示step1中找到的调度的完成时间，显然：
M1 § 1.4 其他 ∙∙∙ Th.算法AK的绝对性能比 ： Mi Pj Ak(I ) ∙∙∙ Mm Proof： 设K表示step1中找到的调度的完成时间，显然： 1）若Ak(I)=K，则该算法已找到一个最优调度； 2）若Ak(I)>K(总的调度完成时间>K,n>k)，则必有某个作 业Jj(j>k)是在Ak(I)时间完成的。这蕴含着其它所有机器在 时间区间[0, Ak(I)-Pj]都在忙，否则作业Jj将在此前被调度 (注意：一旦某机器变为空闲，它直到调度结束仍然是空闲 的)。设T=∑Pi是n个作业总的运行时间，则： T≥m(Ak(I)-Pj)+Pj

64 § 1.4 其他 要证性能比：1)先证Ak(I)的上界；2)再证OPT(I)的下界 1)Ak(I)的上界//可能用到OPT(I)和某参数X
§ 1.4 其他 要证性能比：1)先证Ak(I)的上界；2)再证OPT(I)的下界 1)Ak(I)的上界//可能用到OPT(I)和某参数X T≥mAk(I)-(m-1)Pj ≥ mAk(I)-(m-1)Pk+1 // ∵作业是按运行时间降序, j≥k+1, ∴ Pk+1>Pj Ak(I)-(m-1)/mPk+1 ≤T/m ∵OPT(I)≥T/m ∴ Ak(I) ≤OPT(I)+(1-1/m)Pk+1 2)OPT(I)的下界//可能用到A(I)和X ∵Pi≥Pk+1 (1≤i≤k+1)，必有某台机器至少执行这k+1个作 业中的1+⎿k/m⏌个作业 ∴OPT(I) ≥ ( 1+⎿k/m⏌)Pk+1 上面的Pk+1是可以消除的参数X

65 § 1.4 其他 由Ak(I)≤OPT(I)+(1-1/m)Pk+1和OPT(I)≥(1+⎿k/m⏌)Pk+1 可得性能比：
§ 1.4 其他 由Ak(I)≤OPT(I)+(1-1/m)Pk+1和OPT(I)≥(1+⎿k/m⏌)Pk+1 可得性能比： 使用上述结果，可构造一个PAS，该方案用ε作为输入 变量，对任意输入的ε，它计算一个整数k使得

66 § 1.4 其他 Ak的时间分析： Step1中，在m台机器上对k个作业做最优调度的时间,穷 举法O(mk)，这只有当m较小(比如为常数)才是多项式 的；step2中，对于其余n-k个作业，LPT调度时间是 O(nlgn)。 Ak的总运行时间为： 结论：对于固定的m，对m台机器的调度问题有一个多项 式近似方案