组合优化及算法-共36页PPT课件.ppt

1、组合优化组合优化Combinatorial Optimization 组合优化是运筹学的后继课程，同时也是运筹学的一个重要独立分支，是一类重要的优化问题 最优化最优化(数学规划数学规划)连续优化连续优化(数学规划数学规划)：数学规划（线性规划、非线性规划）、非光数学规划（线性规划、非线性规划）、非光滑优化、全局优化、锥优化等滑优化、全局优化、锥优化等 离散优化：网络优化、组合优化、整数规划等离散优化：网络优化、组合优化、整数规划等 不确定规划：随机规划、模糊规划等不确定规划：随机规划、模糊规划等所谓组合所谓组合(最最)优化优化(Combinatorial Optimization)(Combi

2、natorial Optimization)又称离散优化又称离散优化（Discrete OptimizationDiscrete Optimization），它是通过数学方法去寻找），它是通过数学方法去寻找离散离散事件的最事件的最优编排、分组、次序或筛选等优编排、分组、次序或筛选等.这类问题可用数学模型描述为：这类问题可用数学模型描述为：优化问题三要素优化问题三要素:(Min,f,F)或或(Max,f,F),0)(s.t.)(min Dxxgxf其中其中D表示表示有限个点有限个点组成的集合组成的集合(定义域定义域),f为目标函数为目标函数,F=x|x D,g(x)0为可行域为可行域 组合优化组

3、合优化 定义定义组合优化组合优化 例例例例 0-10-1背包问题背包问题(knapsack problem)给定给定n个容积分别为个容积分别为ai，价值分别为，价值分别为ci的物品的物品.设有一个容积为设有一个容积为b的背包，如的背包，如何以最大的价值装包？用数学规划模型表示为：何以最大的价值装包？用数学规划模型表示为：D=0,1nniiixc1maxs ta xbiiin.1.,.,1 ,1,0nixi例例 装箱问题装箱问题(Bin Packing)(Bin Packing)以尺寸为以尺寸为1 1的箱子装进给定的的箱子装进给定的n n个尺寸不超过个尺寸不超过1 1的物品，的物品，如何使所如何

4、使所用的用的箱子箱子个数最少个数最少?组合优化组合优化 例例整数线性规划整数线性规划(Integer Linear Programming)(Integer Linear Programming)(IP).minc xTs tAxb.xxZn0,我们假设线性整数规划的参数（约束矩阵和右端项系数）都是整数我们假设线性整数规划的参数（约束矩阵和右端项系数）都是整数(或有理数或有理数).许多组合优化问题可以用整数规划模型表示许多组合优化问题可以用整数规划模型表示,但有时不如直接用自然但有时不如直接用自然语言描述简洁语言描述简洁 组合优化问题 定义 定义：组合优化问题 是一个极小化问题，或者是一个极大

5、化问题，它由下述三部分组成：（1）实例集合；（2）对每一个实例I，有一个有穷的可行解集合S(I).（3）目标函数 ，对每一个实例I和每一个可行解 ，赋以一个有理数 .如果 是极小化（极大化）问题，则实例I 的最优解为这样一个可行解 ，它使得对于所有 ，它都有f)(IS),(If)(*IS)(IS),(),()(,(),(*IfIfIfIf算法 定义 定义：算法是指一步步求解问题的通用程序，它是定义：算法是指一步步求解问题的通用程序，它是解决问题的程序步骤的一个清晰描述解决问题的程序步骤的一个清晰描述.定型算法，即算法从前一步到后一步的运行是由当定型算法，即算法从前一步到后一步的运行是由当时状态

6、唯一确定的时状态唯一确定的.如果存在一个算法，他它对问题任意一个给定实例，如果存在一个算法，他它对问题任意一个给定实例，在有限步之后，一定能得到该实例的答案，那么我在有限步之后，一定能得到该实例的答案，那么我们称算法能解决该问题们称算法能解决该问题.近似算法、最优算法近似算法：对于一个优化问题，如果给定任意一个实例I,算法A总能找到一个可行解，那么这个算法称为该问题的近似算法.最优算法：如果进一步，如果这个可行解的目标值 总等于最优解值，则称A为最优算法.典型组合优化问题 背包问题 装箱问题 平行机排序问题 图与网络优化问题 最小支撑树、最短路、最大流、最小费用流、最大基数匹配问题 指派问题

7、旅行售货商问题 斯坦纳最小树问题本课程的主要目的讲授这些问题的数学描述和相应算法.背包问题 给定给定n个容积分别为个容积分别为ai，价值分别为，价值分别为ci的物的物品品.设有一个容积为设有一个容积为b的背包，如何以最大的背包，如何以最大的价值装包？的价值装包？平行机排序问题 M个完全相同的机器，个完全相同的机器，n个相互独立的工件，个相互独立的工件，加工时间互不相同，每个工件只需在任一加工时间互不相同，每个工件只需在任一台机器上不中断建工一次，如果安排加工台机器上不中断建工一次，如果安排加工方案，才能使预定的加工时间最短？方案，才能使预定的加工时间最短？计算复杂性的概念计算复杂性的概念 多项

8、式时间算法多项式时间算法 对于组合优化问题，我们关心的一般不是最优对于组合优化问题，我们关心的一般不是最优解的解的存在性存在性和和唯一性唯一性，而是如何找到有效的，而是如何找到有效的算算法法求得一个最优解求得一个最优解.那么如何衡量算法的优劣、那么如何衡量算法的优劣、有效与无效呢？有效与无效呢？完全枚举法可以求得最优解,但枚举时间有时不可能接受 ATSP:(ATSP:(n-1)!-1)!枚举(TOUR,周游或环游)设计算机每秒进行100亿次枚举,需30!/10e+10 2.65e+22(秒)即 2.65e+22/(365*24*60*60)8.4e+13(年)计算复杂性的概念计算复杂性的概念

9、多项式时间算法多项式时间算法 构造构造算法算法的目的是能够解决问题（或至少是问题某个的目的是能够解决问题（或至少是问题某个子类）的所有实例而不单单是某一个实例子类）的所有实例而不单单是某一个实例 问题（Problem）是需要回答的一般性提问，通常含有若干个满足一定条件的参数.问题通过下面的描述给定：（1）描述所有参数参数的特性，（2）描述答案答案所满足的条件.问题中的参数赋予了具体值的例子称为实例(instance).衡量一个算法的好坏通常是用算法中的加、减、乘、衡量一个算法的好坏通常是用算法中的加、减、乘、除和比较等基本运算的总次数（计算时间）除和比较等基本运算的总次数（计算时间）C（I）同

10、）同实例实例I在计算机计算时的二进制输入数据在计算机计算时的二进制输入数据(输入规模输入规模/长长度度d（I）)的大小关系来度量的大小关系来度量.计算模型计算模型C(I)=f(d(I):该函数关系称为算法的计算复杂性（度）计算复杂性（度）计算复杂性的概念计算复杂性的概念 多项式时间算法多项式时间算法 例例 构造构造算法算法将将n个自然数从小到大排列起来个自然数从小到大排列起来 算法 输入自然数自然数a(1),a(2),a(n).for(i=1;in;i+)for(j=i+1;ja(j)k=a(i);a(i)=a(j);a(j)=k;即该算法的计算复杂性（度）为即该算法的计算复杂性（度）为O(n

11、2 2)基本运算的总次数基本运算的总次数(最坏情形）：最坏情形）：2n(n-1)=O(n2 2)计算复杂性的概念计算复杂性的概念 定义定义1.4 假设问题和解决该问题的一个算法已经给定，若存在假设问题和解决该问题的一个算法已经给定，若存在g(x)为多项式为多项式函数且对该问题函数且对该问题任意的一个实例任意的一个实例I，使得计算时间，使得计算时间成立，则称该算法为解决该问题的多项式成立，则称该算法为解决该问题的多项式(时间时间)算法算法(Polynomial time algorithm).当当不存在不存在多项式函数多项式函数g(x)使得使得上式上式成立时，称相应的算法是成立时，称相应的算法是

12、非非多项式时多项式时间算法间算法,或指数或指数(时间时间)算法算法(Exponential time algorithm)输入规模增大时，多项式时间算法的基本计算总次数的增加速度相对较慢.为常数）（其中)()(ILgIC多项式时间算法多项式时间算法注：上面定义中，要求对该问题的任意一个实例均成立注：上面定义中，要求对该问题的任意一个实例均成立 ，这种分析方法称为这种分析方法称为最坏性能分析（最坏性能分析（Worst-Case AnalysisWorst-Case Analysis）1.4 1.4 计算复杂性的概念计算复杂性的概念 1.4.2 1.4.2 多项式时间算法多项式时间算法 近似值n1

13、01001000nlogn336649966n2100104106n31000106109108n41012101610202n10241.27e31.05e3010n101010100101000nlogn20791.93e17.89e29n!3628800101584e2567计算复杂性的概念计算复杂性的概念 多项式时间算法多项式时间算法 算法复杂性研究中算法复杂性研究中:常将算法的计算时间表示为：问题中的简单而典型的参数(如网络优化中网络优化中n,m),以及 问题中出现的数值(如弧上的权)的最大值(按绝对值)K等自变量的函数关系如果算法运行时间的上界是如果算法运行时间的上界是m,n和和K

14、的多项式函数，则称相应的算法为伪的多项式函数，则称相应的算法为伪多项式（多项式（PseudopolynomialPseudopolynomial）（时间）算法，或拟多项式（时间）算法）（时间）算法，或拟多项式（时间）算法.实际问题的输入规模/长度一定是m,n和logK的一个多项式函数.所以：多项式算法等价于其运行时间的上界是m,n和logK的多项式函数.特别地,如果运行时间的上界是m,n的多项式函数（即该多项式函数不包含logK）,则称相应的算法为强多项式(Strongly Polynomial)时间算法.)()()log,()(2211ILgICKnmgIL)log,()(33KnmgIC一

15、般来说，伪多项式算法并不是多项式算法一般来说，伪多项式算法并不是多项式算法.计算复杂性的概念计算复杂性的概念 TSP等许多问题至今没有找到多项式时间算法,但尚未证明其不存在定义定义 对于给定的一个优化问题，若存在一个求解该问题最优解的多项式时间算法，则称给定的优化问题是多项式可解问题，或简称多项式问题，所有多项式问题集记为P(Polynomial).同样道理,可以定义强多项式问题,伪多项式问题等.TSP是否存在是否存在多项式时间算法?-这是21世纪数学和计算机科学的挑战性问题之一多项式问题多项式问题问题、实例与输入规模问题、实例与输入规模评价一个算法的依据是该算法在评价一个算法的依据是该算法在

16、最坏实例下最坏实例下的计算时间与的计算时间与实例输入规模的关系：实例输入规模的关系：ijd问题实例TSP 问题中各参数:100个城市，城市间距离 已知.背包问题问题中各参数:4个物品，大小分别为4,3,2,2.价值分别为8,7,5,7.包的大小为6.整数线性规划问题中的n,A,b,c已知.)()(or)()(IdgOICIdgIC比多项式问题类可能更广泛的一个问题类是非确定多项式比多项式问题类可能更广泛的一个问题类是非确定多项式(Nondeterministic Polynomial，简记，简记 NP)问题类问题类 存在多项式算法的问题集合：多项式问题类（存在多项式算法的问题集合：多项式问题类

17、（P）存在多项式函数存在多项式函数 g(x)满足上式时，算法为多项式算法满足上式时，算法为多项式算法NP 类是通过类是通过判定问题判定问题引入的。引入的。对任何一个优化问题，对任何一个优化问题，可以考虑其三种形式：可以考虑其三种形式：最优化形式（原形：最优解）最优化形式（原形：最优解）计值形式（最优值）计值形式（最优值）判定形式（上界）判定形式（上界）定义定义 如果一个问题的每一个实例只有如果一个问题的每一个实例只有“是是”或或“否否”两种两种答案，则称这个问题为判定问题答案，则称这个问题为判定问题(Decision/recognition(Decision/recognition/feasi

18、bility problem)./feasibility problem).称有肯定答案的实例为称有肯定答案的实例为“是是”实实例例(yes-instance).(yes-instance).称答案为称答案为“否否”的实例为的实例为“否否”实例或实例或非非“是是”实例实例(no-instance).(no-instance).判定问题判定问题 -定义定义 例例 线性规划问题线性规划问题(LP)(LP)的判定形式的判定形式LPLP判定问题：判定问题：给定一个实数值给定一个实数值z z，(LP)(LP)是否有可行解使其目标值不超过是否有可行解使其目标值不超过z z？即：给定即：给定z z，是否有，

19、是否有?|,x c xzAxbxT 0难度降低就有效算法的存在性而言，通常认为三种形式等价！就有效算法的存在性而言，通常认为三种形式等价！文字集文字集 例例 适定性问题适定性问题(Satisfiability problem)(Satisfiability problem)在逻辑运算中，布尔变量在逻辑运算中，布尔变量x的取值只有两个：的取值只有两个：“真真”(1)(1)和和“假假”(0)(0)，逻辑运算有，逻辑运算有“或或（+）”，“与（与（）”和和“非（非（）.判定问题判定问题 -例例存在存在真值分配真值分配的表达式称为适定的的表达式称为适定的(可满足的可满足的)+000011101111

20、000010100111 0110,;,xxxxxxnn1212文字集的任意一个子集中各元素（布尔变量）文字集的任意一个子集中各元素（布尔变量）的的“或或”运算组成一个运算组成一个句子句子,多个句子的多个句子的“与与”运算组成一个运算组成一个表达式表达式，如，如 ()()()()xxxxxxxx12121212适定性问题：适定性问题：给定布尔表达式给定布尔表达式 ，（SATSAT）是适定的吗？是适定的吗？mCCC.21判定问题判定问题 -例例例例 三精确覆盖三精确覆盖(3-Exact Covering：X3C)已知已知 的的n个子集构成的子集族个子集构成的子集族 ，其中每个子集包含其中每个子集

21、包含S中三个元素，中三个元素，F中是否存在中是否存在m个子集个子集 ，使得使得？若若m个子集满足上式，则称这个子集满足上式，则称这m个子集个子集精确精确覆盖覆盖S.FS SSn,.,12Su uum,.,123SSSiiim12,SSmjij1定义定义 若存在一个多项式函数若存在一个多项式函数g(x)和一个验证算法和一个验证算法H，对一类判，对一类判定问题定问题A的任何一个的任何一个“是是”实例实例I，都，都存在一个存在一个字符串字符串S是是I的的可行解，满足其输入长度可行解，满足其输入长度d(S)不超过不超过g(d(I)，其中，其中d(I)为为I的输的输入长度，且算法入长度，且算法H验证验证

22、S为实例为实例I的可行解的计算时间的可行解的计算时间f(H)不超不超过过g(d(I)，则称判定问题，则称判定问题A是非确定多项式的。是非确定多项式的。考虑将求解判定问题的算法分为两个阶段：考虑将求解判定问题的算法分为两个阶段：（1 1）猜测阶段：求出或猜测该问题的一个解）猜测阶段：求出或猜测该问题的一个解（2 2）检查或验证阶段：一旦解已经选定，将猜测的解作为输）检查或验证阶段：一旦解已经选定，将猜测的解作为输入，验证此解是否为该实例入，验证此解是否为该实例“是是”的回答的回答.我们称实例我们称实例“是是”回答的解为实例的回答的解为实例的可行解可行解，否则称为，否则称为不可行解不可行解.所有非

23、确定多项式问题的集合用所有非确定多项式问题的集合用NP表示表示.NPP 非确定多项式问题类非确定多项式问题类(NP)(NP)定义构造字符串（解）的过程及验证算法构造字符串（解）的过程及验证算法H一起构成一个算法，称一起构成一个算法，称为为非确定多项式（时间）算法。非确定多项式（时间）算法。F中中m个元素个元素 是是S的一个精确三覆盖的充分必要条件为：的一个精确三覆盖的充分必要条件为：相应的相应的m个向量满足个向量满足集合集合S中共有中共有3m个元素，子集族个元素，子集族F中的每个子集合对应一个中的每个子集合对应一个3m维向量：向量维向量：向量的的3m个分量对应个分量对应3m个元素，元素包含在对

24、应子集中的分量为个元素，元素包含在对应子集中的分量为1，余下的为，余下的为0.例如：例如：S=，F中的一个元素中的一个元素 ，对应向量为，对应向量为 =(1,1,0,0,0,1)，表示为一个字符串，表示为一个字符串(110001).非确定多项式问题类非确定多项式问题类(NP)(NP)例按字符串向量问题，精确三覆盖按字符串向量问题，精确三覆盖“是是”实例的任何一个解可以用长度为实例的任何一个解可以用长度为3m2 的字符表示的字符表示.验证是否可行解的算法最多需验证是否可行解的算法最多需3m2 个加法和个加法和3m个比较，算法的计算时间为个比较，算法的计算时间为3m2+3m.例例 三精确覆盖属于三

25、精确覆盖属于NP三精确覆盖问题任何一个实例的输入长度三精确覆盖问题任何一个实例的输入长度d(I)3m.,.,u uu126Su uu1126,1,SSSiiim12ijmj1111(,)选选g(x)=x2/3+x，则定义条件满足，所以三精确覆盖属于，则定义条件满足，所以三精确覆盖属于NP.非确定多项式问题类非确定多项式问题类(NP)(NP)问题问题A2A2的难度不低于问题的难度不低于问题A1A1 定义定义 给定问题给定问题A1A1和和A2A2，若存在一个多项式算法，若存在一个多项式算法满足：满足：对对A1A1的任何一个实例的任何一个实例I1，算法，算法将实例将实例I1的输入转换为的输入转换为A

26、2A2的的一个实例一个实例I I2 2的输入；的输入；这种转换过程使得实例这种转换过程使得实例I1和和I I2 2的解一一对应，即的解一一对应，即将实例将实例I1的的一个解一个解x1的输入转换为实例的输入转换为实例I I2 2的一个解的一个解x2的输入，且的输入，且x1为为I1的的“是是”答案答案 x2是是I I2 2的一个的一个“是是”答案；答案；则称则称A1A1问题多项式转换为问题多项式转换为A2A2问题，算法问题，算法称为问题称为问题A1A1到问题到问题A2A2的一个多项式转换（算法）的一个多项式转换（算法）(Transformation).(Transformation).常用的研究方

27、法常用的研究方法 -多项式转换多项式转换(变换变换)、多项式归约、多项式归约(归结归结)若若A1A1多项式转换为多项式转换为A2A2，且A2PA2P，则，则A1PA1P若若A1A1多项式转换为多项式转换为A2A2，且，且A2NPA2NP，则，则A1NPA1NP多项式转换(定义)NPNP完全问题类完全问题类(NPC)-(NPC)-定义定义 已知判定问题已知判定问题A1A1和和A2A2，若存在多项式函数，若存在多项式函数 和和 ，使得对使得对A1A1的任何实例的任何实例I I，在多项式时间内构造，在多项式时间内构造A2A2的一个实例，的一个实例，其输入长度不超过其输入长度不超过 ，并对，并对A2A

28、2的任何一个算法的任何一个算法H2H2，都存在问题都存在问题A1A1的一个算法的一个算法H1H1，使得，使得H1H1算法调用算法调用H2H2算法且使得算法且使得计算时间计算时间，其中其中fH1H1(x)和和fH2H2(x)分别表示算法分别表示算法H1H1和和H2H2的计算时间与实例输的计算时间与实例输入长度入长度x之间的关系，则称问题之间的关系，则称问题A1A1多项式归约为问题多项式归约为问题A2.A2.根据A2A2的算法的算法H2H2，构造构造A1A1的算法的算法H1H1的过程，即映射的过程，即映射 ：H2 H1H2 H1称为从称为从A1A1到到A2A2的一个多项式归约的一个多项式归约(re

29、duction).(reduction).gx1()gx2()(1Idgfd Igfg d IHH1221()()多项式归约多项式归约(定义定义)问题问题A2A2的难度不低于问题的难度不低于问题A1A1若若A1A1多项式归约为多项式归约为A2A2，且A2PA2P，则，则A1PA1P若若A1A1多项式归约为多项式归约为A2A2，且，且A2NPA2NP，则，则A1NPA1NP若若A1A1多项式归约为多项式归约为A2A2，则当把，则当把H1H1对对H2H2的一次调用当成一次基本的一次调用当成一次基本运算时，运算时，H1H1是是A1A1的多项式算法。的多项式算法。NPNP完全问题类完全问题类(NPC)

30、-(NPC)-多项式归约多项式归约多项式转换是多项式归约多项式转换是多项式归约的特例的特例归约映射可以如下构造：归约映射可以如下构造：H1H1：STEP1 STEP1 用多项式转换将用多项式转换将A1A1的实例转换为的实例转换为A2A2的实例的实例 STEP2 STEP2 用用H2H2算法求解算法求解A2A2的实例的实例即多项式转换可以认为是只允许调用一次即多项式转换可以认为是只允许调用一次H2H2的多项式归约的多项式归约NPNP完全问题类完全问题类(NPC)(NPC)-多项式归约多项式归约 （例）（例）例例1.22 1.22 适定问题多项式归约为三精确覆盖问题适定问题多项式归约为三精确覆盖问

31、题 定义（定义（1 1）对于判定问题）对于判定问题A A，若，若A A NPNP且且NPNP中的任何一个问题可在中的任何一个问题可在多项式时间内归约为多项式时间内归约为A A，则称，则称A A为为NPNP完全问题完全问题(NP-Complete(NP-Complete或或NPC).NPC).可以表示为可以表示为A A NPCNPC.NPC和NP-hard两者的区别是:验证一个问题A是否为NP-hard无须判断A是否属于NP.根据定义可知NPCNPH.当已知一个问题属于NPC或NPH时，如果再遇到一个新问题：（1）若已知问题多项式归约为新问题，则新问题属于NPH;NPNP完全问题类完全问题类(N

32、PC)(NPC)定义定义（2 2）对于判定问题）对于判定问题A A，若，若NPNP中的任何一个问题可在多项式时间中的任何一个问题可在多项式时间归约为判定问题归约为判定问题A A，则称，则称A A为为NPNP困难问题困难问题(NP-hard(NP-hard 或或NPH).NPH).可可以表示为以表示为A A NPH.NPH.（2）若还可以验证新问题属于NP，则新问题属于NPC.NPNP完全问题类完全问题类(NPC)(NPC)定理：如果问题定理：如果问题A A是是P P问题，且问题，且B B可以在多项式时间内可以在多项式时间内归约为归约为A A，则，则B B也为也为P P问题问题.定理：P=NP当

33、且仅当存在一个NPC问题有多项式时间算法.定理：如果问题定理：如果问题A是是NPC问题，且问题，且B可以在多项式时可以在多项式时间内归约为间内归约为A，则，则B也为也为NPC问题问题.定理：如果问题定理：如果问题A是是NPH问题，且问题，且B可以在多项式时可以在多项式时间内归约为间内归约为A，则，则B也为也为NPH问题问题.NPNP完全问题类完全问题类(NPC)(NPC)定理：除非定理：除非P=NPP=NP，否则，否则NPHNPH问题没有多项式时间算法问题没有多项式时间算法.Cook定理：定理：SAT为为NP问题问题.Cook计算复杂性理论的奠基性工作之一：第一个被证明的计算复杂性理论的奠基性

34、工作之一：第一个被证明的NPC问题！是证明许多其他问题！是证明许多其他NPC问题的出发点问题的出发点.NPNP完全问题类完全问题类(NPC)(NPC)证明（例）证明（例）例例 三精确覆盖三精确覆盖（X3CX3C）属于属于NPC.NPC.SATSAT多项式归约为多项式归约为X3CX3CX3CX3CNP NP（例例1.191.19）X3CX3C NPC NPC例例 （特殊）（特殊）（0-10-1）背包判定问题属于）背包判定问题属于NPC.NPC.X3CX3C多项式多项式变换变换为为背包判定问题背包判定问题背包判定问题背包判定问题NPNP背包判定问背包判定问题题 NPC NPCNPNP完全问题类完全

35、问题类(NPC)(NPC)补充说明补充说明:算法复杂性研究中算法复杂性研究中:常将算法的计算时间表示为：问题中的简单而典型的参数(如网络优化中网络优化中n,m),以及 问题中出现的数值(如弧上的权)的最大值(按绝对值)K，等自变量的函数关系实际问题的输入规模/长度一定是m,n和logK的一个多项式函数.所以,如果一个算法是多项式时间算法,则运行时间的上界一定也是m,n和logK的多项式函数.特别地,如果运行时间C(I)的上界是m,n的多项式函数（即该多项式函数不包含logK）,则称相应的算法为强多项式（Strongly Polynomial）时间算法，简称强多项式算法.强多项式算法强多项式算法

36、/问题问题)()()log,()(2211ILgICKnmgIL)log,()(33KnmgIC存在强多项式算法的问题称为强多项式问题.NPNP完全问题类完全问题类(NPC)(NPC)补充说明补充说明如果算法运行时间的上界是如果算法运行时间的上界是m,n和和K的多项式函数，则称相应的多项式函数，则称相应的算法为伪多项式（的算法为伪多项式（PseudopolynomialPseudopolynomial）(时间时间)算法，或拟算法，或拟多项式多项式(时间时间)算法。算法。如果采用如果采用“一进制一进制”编码（编码（Unary Encoding,Unary Encoding,即用即用x位表示一位表

37、示一个正整数个正整数x），则伪多项式算法运行时间的上界是实例），则伪多项式算法运行时间的上界是实例输入长输入长度度的多项式函数。的多项式函数。除非除非 P=NP,否则不存在伪多项式算法的否则不存在伪多项式算法的NPC问题称为问题称为强强NPC（Strongly NPC）问题，有时也称为问题，有时也称为Unary-NPC问题。问题。TSP、SAT等是强NPC问题,而背包问题则不是强NPC问题.伪多项式算法、强伪多项式算法、强NPCNPC问题问题),()(33KnmgIC由于采用由于采用“一进制一进制”编码在当前的计算机上是不现实的，所编码在当前的计算机上是不现实的，所以一般来说以一般来说,伪多项式算法并不是多项式算法伪多项式算法并不是多项式算法.NPNP完全问题类完全问题类(NPC)(NPC)补充说明补充说明P=NP吗？吗？-这是21世纪数学和计算机科学的挑战性问题之一