8.2.29塔布斯逻辑运算方法问题详解.ppt

* 8.2 图问题中的流塑法 8.2.29 塔布斯逻辑运算方法问题 8.2.29 塔布斯逻辑运算方法问题 问题的解空间太大 如：可满足问题（SAT问题）—判断包含一些变量的合取范式是否为真。 评估函数难以确定 希望评估函数能评价可能解的质量 实际问题很复杂，无法求得精确解 如：运输问题中的不连续性 实际问题的约束条件难以满足 为什么把多项式时间复杂性作为易解问题和难解问题的分界线？ 1．多项式函数与指数函数的增长率有本质的差别 2．计算机性能的提高对多项式时间算法和指数时间算法的影响不同 3．多项式时间复杂性忽略了系数，但不影响易解问题和难解问题的划分 4．多项式时间复杂性的闭包性 5．多项式时间复杂性的独立性 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 如果 如果 Hanio(3,A,B,C) Hanio(2,A,C,B) Hanio(1,A,B,C) Move (A,C) Move (A,B) Hanio(1,C,A,B) Hanio(1,A,B,C) Hanio(2,A,C,B) Move (C,B) Hanio(1,C,A,B) Move (A,C) Hanio(2,B,A,C) Hanio(1,B,C,A) Move (B,C) Hanio(1,A,B,C) Hanio(1,B,C,A) Move (A,C) Hanio(2,B,A,C) Move (B,A) Hanio(1,A,B,C) 结束 算法结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此，它为设计算法和调试程序带来很大方便，是算法设计中的一种强有力的工具。但是，因为算法是一种自身调用自身的算法，随着深度的增加，工作栈所需要的空间增大，调用时的辅助操作增多，因此，算法的运行效率较低。 void MergeSort(int r[ ], int r1[ ], int s, int t) { if (s= =t) r1[s]=r[s]; else { m=(s+t)/2; Mergesort(r, r1, s, m); //归并排序前半个子序列 Mergesort(r, r1, m+1, t); //归并排序后半个子序列 Merge(r1, r, s, m, t); //合并两个已排序的子序列 } } [ r1 … … ri-1 ] ri [ ri+1 … … rn ] 均≤ri 轴值 均≥ri 位于最终位置 归并排序按照记录在序列中的位置对序列进行划分， 快速排序按照记录的值对序列进行划分。 算法4.5——一次划分 int Partition(int r[ ], int first, int end) { i=first; j=end; //初始化 while (ij) { while (ij r[i]= r[j]) j--； //右侧扫描