Algorithms Chapter 6 变治法.pptVIP

* * * * * * * * * * Deng Xin The Design and Analysis of Computer Algorithms Deng Xin The Design and Analysis of Computer Algorithms 第六章 变治法Transform and Conquer That’s the secret to life ... replace one worry with another. —— Charles M. Schulz 美国漫画家，Snoopy之父 * * 变治法(Transform and Conquer) 减治是基于变换的思想。 分两个阶段工作，即“变”阶段和“治”阶段. 变治法的三种类型： 1)实例化简(instance simplification) 2)改变表现(representation change) 3)问题化简(problem reduction) 1)实例化简(instance simplification) 预排序 2)改变表现(representation change) 霍纳法则 3)问题化简(problem reduction) Lcm … * * 6.1 预排序(Presorting) 如果列表是有序的话，许多关于列表的问题更容易解决。 例1：检查数组中元素的唯一性 T(n)=Tsort(n)+Tscan(n) ∈ Θ(nlogn)+ Θ(n)= Θ(nlogn) * 预排序(Presorting) 例2 模式计算(Computing a mode) (最常出现的数字) * 预排序(Presorting) 例3 查找问题 对于一个可排序项构成的查找问题，蛮力法在最坏情况下需要进行n次比较。 如果先进行排序，就可利用二分查找，在最坏情况下需要进行[log2n]+1次比较。 T(n)=Tsort(n)+Tsearch(n)= Θ(nlogn)+ Θ(log2n)= Θ(nlogn) 这个效率要比顺序查找差 但是要在同一个序列中查找多次，在排序上花的时间也是值得的。 多项式求值 * * * * 如何计算 整数n的二进制表达： 例如：13=1101 算 a13 * 二进制幂 n的二进制 1 1 0 1Term a8 a4 a2 a Product: a5 a8 = a13 aa4 = a5 a a a2* a2 * 问题化简(Problem Reduction) 问题化简是一种重要的解题策略。如果我们要解决一个问题，可以把它化简为另一个我们知道如何求解的问题。 给策略的难点在于如何找到一个可以化简当前问题的目标问题。 * 最小公倍数(Least Common Multiple) 两个正整数m和n的最小公倍数记作lcm(m,n)，是能够被m和n整除的最小正整数。 如lcm(24,60=120) lcm(11,5)=55 中学的计算方法 24=2×2×2×3 60=2×2×3×5 lcm(24,60)=(2×2×3)×2×5=120 * * 图中的路径数量 计算图中两个顶点之间的路径数量问题 从图(无向图或有向图)中的第i个顶点到第j个顶点之间，长度为k0的不同路径的数量等于Ak的第(i,j)个元素，其中，A是该图的邻接矩阵。 * 优化问题化简(Reduction of Optimization Problem) 求函数的最大值和最小值问题。 * 线性规划(Liner Programming) 线性规划问题是一个多变量线性函数的最优化问题，这些变量所要满足的一些约束是以线性等式或不等式形式出现的。 例1：假定一个大学基金需要进行一亿美元的投资。必须分成三种类型的投资：股票、债券和现金，预期的年收益分别为10%,7%和3%。因为股票风险更高，要求投资在股票上的资金不能超过证券投资的1/3，此外，现金投资至少应相当于股票和债券投资总额的25%。请问如何投资才能使收益最大化？ * 线性规划(Liner Programming) 建立数学模型，设x,y,z分别是投资在股票、债券和现金上的金额(以百万美元为单位, million)，有： 极大化的线性函数 问题约束 非