第5章线性规划与计算复杂性简介.pptVIP

* 例8.12 （SAT问题） 给定布尔变量x1,…,xn的一个布尔表达式c1·c2·…·cm，其中ci为用x1,…,xn构成的句子，问此表达式是可满足的吗？ SAT问题是数理逻辑中的中心问题之一，这一点可从计算机的运算方式看出，故设计一个较好的求解SAT问题的算法具有重要意义。 1972年，R.M.Karp 以多项式转化的方式证明并列出21个NP完全问题。此后，大量NP完全问题一一被证明。短短十几年时间，已知的NP完全问题就达到了 4000多个，其中包括前面提到过的HC和TSP。总之，NP完全类是一个极为庞大的问题类，其中包含着无穷多个问题。按照目前普遍的看法，这些问题中的任意一个都不应当有多项式算法，即求解它的任一算法在遇到最“坏”的实例时都需要化指数时间。 P类、NP完全类及NP类的关系如图8.3所示，即，NP完全类。还有很多离散问题目前尚未搞清它们的计算复杂性。有些将被证明是P问题，有些将被证明是 NP完全的。此外，确实存在着NP以外的问题，其求解更为困难。 * 二、有关离散问题模型及其算法的几点附加说明 最近几十年来，有成千上万离散问题的模型得到了广泛而又较为深入的研究。因而，当我们研究一个离散型的问题时，首先要搞清遇到的实际课题是否为某一别人已研究过的问题的一个实例。搞清这一点十分重要，否则你的努力完全可能是一种徒劳。 例8.13 某工厂在生产一种产品或部件时，需要在一些指定位置上钻孔。问应按怎样的顺序钻孔，才能使加工速度最快。 由于生产是连续进行的，钻头将从一钻孔位置出发到各指定点钻孔，最后返回原位置，以便加工下一个产品或部件。显然，这是一个旅行商问题。 然而，是否为某一问题的实例有时并不是一目了然的。 * 例8.14 在轧钢等生产中，为了保持工件的温度，工件在一台机器上加工以后必需立即转送下台机器加工，中间不允许出现工件等待现象。现设共有n个工件Ji(i=1,…,n)需要进行加工，且加工有以下特点： （i）加工不同工件时，使用机器的顺序可以不同。 （ii）每一工件在每台机器上至少加工一次。 （iii）每台机器加工各工件的顺序相同。 （iv）工件加工中不允许有中间等待。 要求确定{1,…,n}（工件编号）的一个排序{i1,…,in}，使得总加工时间最少。 例8.13是排序（Scheduling）问题的一个子问题，这个子问题的计算复杂性如何呢？下面的分析表明，这一子问题实质上就是旅行商问题，从而是NP—完全的。 * 图8.4给出了一个三台机器二个工件的实例。工作Ji需加工5次，依次使用机器2→1→2→5→2。工作Ji需加工4次，依次使用机器1→2→3→1。该图是设先加工Ji作出的，图中的点表示加工活动，旁边的数字为加工时间，箭线反映加工顺序。 由图8.4可以看出，按Ji、Jj顺序加工，两工件至少要加工12单位时间，两工件开始加工时间至少相差5单位时间，否则必然将出现等待。 * 对于一般问题，设加工顺序为{i1,…,in}，则在此顺序下的最短加工时间T可按如下方法求得：对每一对工件Jik和Jjk+1，先求它们开工时间差的最小值 （可用一子程序计算）， 令 其中 为最后工件在各机器上加工时间的总和。 的出现使得T的计算公式不够整齐，为此引入一个虚工件J0，它需在各机器上加工一次，加工时间均为0，并记Ci0为工件i的总中工时间，Coi=0，则有 其中i0=0， in+1=0，问题化为求{1,…,n}的一个排序{i1,…,in}，使按此 顺序加工， 有最小。显然，这是TSP。 * 从上述讨论容易看出，给定了{J1,…,Jn}，可在O(n2)步内求出所有Cij，从而使问题化为TSP，若TSP多项式可解，则例8.13也多项式可解。反之，对每一TSP的实例，也可在多项式时间内构造出一个不允许等待的排序问题，若不允许等待的排序问题多项式可解，则TSP也多项式可解。这样，就搞清了不允许等待的排序问题多项式可解，则TSP也多项式可解。故不允许等待的机器加工问题是NP完全的，因为它等价于NP完全问题TSP。不过，在大多数情况下，找出此类多项式转化关系并不是一件容易的事，它不仅需要对别人已研究过的各类问题有充分的了解，还可能要用到十分精细而又巧妙的技巧。 在建立起实际问题的数学模型后，还应考虑一下是否有必要将模型标准化。也许，适当的标准化会为下一步的研究及算法设计提供方便。先将模型标准化，然后再去寻找算法的例子屡见不鲜。在上一章中求解线性规划的单纯形法是针对标准形式设计的，容易看出这种做法避免了众多麻烦。虽然人们至今尚未发现求解TSP的好算法，但细心的读者不难看出，一般图G（某些顶点之间可以无边相连）上的TSP的求解与完全图（任意两顶点间均有边相连）上的TSP的求解是等价的。因而，我们只需