8.2.26蒙旭虚拟算法与TNl类问题.ppt

* 8.2 图问题中的流塑法 8.2.26 蒙旭虚拟算法与TNl类问题 此算法结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此，它为设计算法和调试程序带来很大方便，是算法设计中的一种强有力的工具。但是，因为算法是一种自身调用自身的算法，随着深度的增加，工作栈所需要的空间增大，调用时的辅助操作增多，因此，算法的运行效率较低。 8.2.26 蒙旭虚拟算法与TNl类问题 定义2.3 设A是求解问题Π的一个算法，如果算法A以如下猜测并验证的方式工作，就称算法A是非确定性（Nondeterminism）算法： （1）猜测阶段：在这个阶段，对问题的输入实例产生一个任意字符串y，在算法的每一次运行时，串y的值可能不同，因此，猜测以一种非确定的形式工作。 （2）验证阶段：在这个阶段，用一个确定性算法验证： ① 检查在猜测阶段产生的串y是否是合适的形式，如果不是，则算法停下来并得到no； ② 如果串y是合适的形式，则验证它是否是问题的解，如果是，则算法停下来并得到yes，否则算法停下来并得到no。 （1）证明问题Π属于NQ类问题，也就是说，可以在多项式时间以确定性算法验证一个任意生成的串，以确定它是不是问题的一个解； （2）证明NQ类问题中的每一个问题都能在多项式时间变换为问题Π。由于多项式问题变换具有传递性，所以，只需证明一个已知的NQ完全问题能够在多项式时间变换为问题Π。 对问题的输入中必须要处理的元素进行计数，同时，对必须要输出的元素进行计数。这种计数方法产生的是一个平凡下界（Ordinary Lower Bound）. 例 ：生成 n 个元素的所有排列对象的算法属于Ω(n!) 平凡下界往往过小而失去意义。 例：TSP问题的平凡下界是Ω(n2) 所谓最优算法（Optimality Algorithm）是指在某一种度量标准下，优于该问题的所有（可能的）算法。 如果能够证明求解问题Π的任何算法的运行时间下界是Ω(g(n))，那么，对以时间O(g(n))来求解问题Π的任何算法，都认为是最优算法。 a1a2 a1a2a3 是 是 是 否 否 否 a1a3 a2a3 a2a1a3 a2a3 a3a2a1 a2a3a1 a1a3 a3a1a2 a1a3a2 否 否 是 是 例：对三个数进行排序的判定树 最坏情况下的时间复杂性是从根节点到叶子结点的最长路径长度，它不会超过判定树的高度。 将一个难以直接解决的大问题，划分成一些规模较小的子问题，以便各个击破，分而治之。更一般地说，将要求解的原问题划分成k个较小规模的子问题，对这k个子问题分别求解。如果子问题的规模仍然不够小，则再将每个子问题划分为k个规模更小的子问题，如此分解下去，直到问题规模足够小，很容易求出其解为止，再将子问题的解合并为一个更大规模的问题的解，自底向上逐步求出原问题的解。 2. 独立子问题：各子问题之间相互独立，这涉及到的效率，如果各子问题不是独立的，则需要重复地解公共的子问题。 1. 平衡子问题：最好使子问题的规模大致相同。也就是将一个问题划分成大小相等的k个子问题（通常k＝2），这种使子问题规模大致相等的做法是出自一种平衡（Balancing）子问题的思想，它几乎总是比子问题规模不等的做法要好。 一般来说，的求解过程由以下三个阶段组成： （1）划分：既然是离治，当然需要把规模为n的原问题划分为k个规模较小的子问题，并尽量使这k个子问题的规模大致相同。 （2）求解子问题：各子问题的解法与原问题的解法通常是相同的，可以用的方法求解各个子问题，有时处理也可以用循环来实现。 （3）合并：把各个子问题的解合并起来，合并的代价因情况不同有很大差异，离治算法的有效性很大程度上依赖于合并的实现。 例：计算an 34 32 32 81 31 31 9 31 31 9 3 3 3 3 分解问题 求解每个子问题 合并子问题的解 不是所有的都比简单的蛮力法更有效。 分析时 间性能 ? ? é ù ? í ì ′ = = 1 1 2 2 n a a n a a n n n 如果 如果 调用函数和被调用函数是同一个函数，需要注意的是函数的调用层次，如果把调用函数的主函数称为第0层，进入函数后，首次调用自身称为第1层调用；从第i层调用自身称为第i+1层。反之，退出第i+1层调用应该返回第i层。采用图示方法描述函数的运行轨迹，从中可较直观地了解到各调用层次及其执行情况。 *