AlgoDA_LectureNotes_W11.ppt

Last Section Lower Bound Arguments Trivial Lower Bounds Information-Theoretic Arguments Adversary Arguments Problem Reduction Lower Bound on Sorting Decision Trees Determining The Maximum Finding Max and Min NP - Completeness Why the theories ? Classifications Practice Optimization vs. Recognition Polynomially equivalent Problem Reduction and Transformation The TSP-optimization polynomially reduces to TSP-recognition I and III At least as hard as P, NP, NP-complete Certificate Proving NP-completeness Hamiltonian path problem vs. Hamiltonian cycle problem Longest path problem vs. Hamiltonian path problem Approximation Algorithm 近似算法 不同的近似算法有各种各样的复杂度，但其中许多算法都是基于特定问题的直观推断贪婪算法。 直观推断是一种来自于经验而不是来自于数学证明的常识性规则。 *例：在TSP中，我们可以访问最近的未访问城市。 如果我们使用的算法所给出的输出仅仅是实际最优解的一个逼近，我们就会想知道这个逼近有多精确。 近似算法的精度 对于一个对某些函数 f 最小化的问题来说，可以用近似解的相对误差规模 来度量它的精度，其中s* 是问题的一个精确解。 另一种度量发法是，因为 re(sa) = f(sa)/f(s*) – 1, 可以简单地使用 精确率 作为sa的精确度量。 近似算法的精度 为了保证度量标准的一致性，最大化问题的近似解精确度： 以使得这个比率同最小化问题的精确率一样，总是大于等于1。 r(sa)越是接近1，算法近似解的质量就越高 。 近似算法的性能比 对于问题的所有实例，它们可能的r(sa)的最佳（也就是最低）上界，被称为该算法的性能比，计作RA。 性能比是一个来指出近似算法质量的主要指标，我们需要那些RA尽量接近1的近似算法。 遗憾的是某些简单近似算法的性能比趋于无穷大（RA=∞）。 这并不意味着不能使用这些算法，只是需要小心对待它们的输出。 近似算法的性能比 如果一个多项式时间的近似算法的性能比最多是c的话，我们也把它称作一个c近似算法； 即，对于所讨论问题的任何实例， f(sa)≤cf(s*) (极小化问题) TSP的近似算法 Nearest-neighbor algorithm 基于一种最近邻居的直观推断：下一次总是访问最近的未访问城市。 第一步：任意选择一个城市作为起点。 第二步：重复下面的操作直到访问完所有的城市： 访问和最近一次访问的城市k最接近的未访问城市（顺序是无关紧要的）。 第三步：回到起点城市。 最近邻居算法的性能比 例 对于图中所代表的实例，把a作为开始顶点，最近邻居算法生成的旅程（哈密顿回路）sa为 a-b-c-d-a， 长度等于10。 最优解是旅程 s*， a-b-d-c-a， 长度等于8。因此，这个近似解的精确率为 即，旅程sa比最优旅程s* 长25% 。 最近邻居算法的性能比 除了简单之外，最近邻居算法乏善可陈： 无法给出在一般情况下，该算法求解的精确度是多少。 为什么？ 最近邻居算法的性能比 除了简单之外，最近邻居算法乏善可陈： 无法给出在一般情况下，该算法求解的精确度是多少。 为什么？ 因为该算法会在旅程别无选择的情况下，迫使我们穿过一条非常长的边。 最近邻居算法的性能比 如果我们把上例中边（a, d）的权重改成任意一个w≥6 的大数，该算法会给出一条长度为4+w 的旅程a-b-c-d-a，因此， 只要对w选择一个足够大的值，r(sa)可以任意大。因此，对于这个算法，RA=∞。 欧几里得类型实例 对于一类非常重要的，被称为欧几里德类型的实例所构成的子集，我们可以给出最近邻居算法精确度的一个有效断言。 城市间的距离满足下列条件： 三角不等式 对于任意城市i, j, k构成的三角形，d[i,j]≤d[i,k]+ d[k,j] (城市i和j之间的距离不会超过，从i