算法设计与分析sorrybitlate

1、Last Section减 治插入排序: n2, n, n2/4快速排序+插入排序拓扑排序: 减一生成排列+ Johnson-Trotter生成子集+比特串方法假币问题俄式乘法约瑟夫斯问题欧几里德算法插值查找二叉查找树变治_实例化简预排序检验数组中元素的惟一性： n(n-1)/2, nlogn+n模式计算： n(n-1)/2+n-1, nlogn+(n)高斯消去法Partial pivotingLU 分解矩阵的逆AVL树: 1.39logn, 1.01logn变治_改变表现变换为同样实例的不同表现改变表现(Representation Change)2-3 树堆和堆排序霍纳法则二进制幂变治变换

2、为另一个问题的实例， 这种问题的算法是已知的问题化简(Problem reduction)。Lcm图中的路径数量函数极值综合除法凸包，解析几何线性规划简化为图MST vs. Element Uniqueness动态规划动态规划是解决多阶段决策过程最优化的一种方法。动态规划模型的分类：离散确定性顺序解法与可逆过程两个弱点：得出目标函数方程后，尚无统一的处理方法，必须根据具体问题的性质结合相应的数学技巧来求解；维数障碍。动态规划的基本概念和基本方程例1最短路线问题给出一个线路网络， 从A点要铺设一条管道到G点，其两点之间连线上的数字表示两点间的距离；要求选择一条由A到G的铺管线路，使总距离为最短。

3、如图AE2D2B2B1C4C3C2C1D3D1E1E3F2F1G336625533432122335386631485768最短路线问题最短路线问题从A到G可以分为6个阶段。各个阶段的决策不同，铺管路线就不同。明显地，当某段的始点给定时，它直接影响着后面阶段的引进路线和整个路线的长短，而后面各阶段的路线的发展不受这点以前各段路线的影响。问题的要求是：在各个阶段选取一个恰当的决策，使由这些决策组成的一个策略所决定的一条路线，其总路程最短-最优策略穷举法：共有2 * 3 * 2 * 2 * 2 * 1=48 条路线动态规划的基本概念阶段(Stage)把所给问题的过程，恰当地划分成若干个相互联系的阶

4、段，以便于求解。通常用k表示阶段变量。例中第一阶段为AB，包含2条支路：A B1和A B2状态（State）状态表示某段的出发位置。它既是该段某支路的始点，同时也是前一段某支路的终点。通常一个阶段包含若干个状态。描述过程状态的变量，称为状态变量。常用xk表示在第k段的某一状态。第k段状态集合可表示为Xk = xk(1), xk(2), , xk(i) , , xk(r)故例中第三阶段的状态集合就可记为X3 = x3(1), x3(2), x3(3) , x3(4)=1, 2, 3, 4或X3 = C1, C2, C3, C4动态规划的基本概念决策（Decision）决策就是某阶段状态给定以后，

5、从该状态演变到下一阶段某状态的选择。描述决策的变量，称为决策变量。常用uk(xk)表示第k段当状态处于xk 时的决策变量。决策变量的取值往往限制在某一范围之内，此范围称为允许决策集合。通常以Dk(xk)表示第k段当状态处于xk 时的允许决策集合。uk(xk) Dk(xk)动态规划的基本概念决策（Decision）决策就是某阶段状态给定以后，从该状态演变到下一阶段某状态的选择。描述决策的变量，称为决策变量。常用uk(xk)表示第k段当状态处于xk 时的决策变量。决策变量的取值往往限制在某一范围之内，此范围称为允许决策集合。通常以Dk(xk)表示第k段当状态处于xk 时的允许决策集合。uk(xk)

6、 Dk(xk)例中第二阶段状态集合X2=B1，B2；则从B1出发的允许决策集合D2 ( B1 )=C1，C2， C3；若选择点C2， 则u2 ( B1 )=C2。AE2D2B2B1C4C3C2C1D3D1E1E3F2F1G336625533432122335386631485768最短路线问题动态规划的基本概念策略（Policy）由过程的第1阶段开始到终点为止的过程，称为问题的全过程。由每段的决策ui(xi)(i=1,2,n)组成的决策函数序列就称为全过程策略，简称策略，记为p1,n。即p1,n(xk)= u1(x1), u2(x2), , un(xn)由第k段开始到终点的过程称为原过程的后部

7、子过程（或称为k子过程）。其决策函数序列 uk(xk)，, un(xn)称为k子过程策略，简称子策略。即pk,n(xk)=uk(xk), uk+1(xk+2), , un(xn)在实际问题中，可供选择的策略有一定的范围，此范围称为允许策略集合，用P表示。从允许策略中找出达到最优效果的策略称为最优策略。动态规划的基本概念指标函数在多阶段决策过程最优化问题中，指标函数是用来衡量所实现过程的优劣的一种数量指标，它是一个定义在全过程和所有后部子过程上的确定数量函数，常用Vk,n表示。即Vk,n= Vk,n(xk ,uk ,xk+1 ,xn+1) k=1,2,n不同的问题中，指标的含义也不同：距离、利润

8、、成本、产量、资源消耗等。例中， Vk,n表示第k阶段由点xk至终点G的距离；第k阶段由点xk至uk(xk)的距离为阶段指标（阶段效益），可记为k(xk ,uk ) 。(E1, F1) 。动态规划的基本概念最优指标函数指标函数Vk,n的最优值，称为相应的最优指标函数。记为fk(xk). 例中，fk(xk)表示从第k段xk点到终点G的最短距离。如f4(D1)就表示从第4段中的D1点到G 点的最短距离。动态规划的基本思想和基本方程生活中平常的事例，即可深刻揭示最短路线的重要特性：如果最短路线在第K站通过点Pk, 则由点Pk出发到达终点的这条路线，对于从点Pk出发到达终点的所有可能选择的不同路线来说

9、，必定也是最短路线。动态规划的方法是从终点逐段向始点方向寻找最短路线的一种方法。AE2D2B2B1C4C3C2C1D3D1E1E3F2F1G336625533432122335386631485768最短路线问题最短路线问题按照动态规划的方法，从最后一段开始计算，由后向前逐步推移至A点：当k = 6 时，f6(F1)表示在第6段由F1至G的最短距离，故f6(F1)=4。同理，f6(F2)=3。当k = 5 时，若从E1出发，则有两个选择，一是至F1，一是至F2，则f5(E1)=min= min= 7这说明，由E1至终点G的最短距离为7，其最短路线是E1F1G，而相应的决策变量u5(E1)=F1

10、.最短路线问题若从E2出发，也有两个选择，一是至F1，一是至F2，则f5(E2)=min= min= 5这说明，由E2至终点G的最短距离为5，其最短路线是E2F2G，而相应的决策变量u5(E2)=F2.etc.AE2D2B2B1C4C3C2C1D3D1E1E3F2F1G336625533432122335386631485768最短路线问题动态规划的函数基本方程在求解的各个阶段，我们利用了k阶段与k+1阶段之间的如下关系： k = 6,5,4,3,2,1 f7(x7)= 0 (或写成 f6(x6) = d6(x6, G)动态规划最优化原理 动态规划最优化原理：作为整个过程的最优策略具有这样的性

11、质：即无论过去的状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。可逆过程顺序解法：以G为始端，以A为终端的左行解法程序称为顺序解法逆序解法可以把段次颠倒过来求最优解的多阶段决策过程称为可逆过程。顺序解法和逆序解法只表示行进方向的不同或始端的颠倒。但用动态规划方法求最优解时，都是在行进方向规定后，均要逆着这个规定的行进方向，从最后一段向前逆推计算，逐段找出最优途径。 与穷举法的对比 减少了计算量穷举法：要对48条路线进行比较，比较运算要进行47次；求各条路线的距离（288次加法），即使使用逐段累加方法，也要进行0+6+12+32+48+48=146次加法运算。动态规划

12、方法：比较运算（从k=5段开始向前算）共进行3+3+4+4+1=15次。每次比较运算对应两次加法运算，再去掉中间重复两次（即B1C1， B2C4各多算了一次），实际只有28次加法运算。AE2D2B2B1C4C3C2C1D3D1E1E3F2F1G336625533432122335386631485768最短路线问题与穷举法的对比丰富了计算结果在逆序解法中，使我们得到的不仅仅是由A点出发到终点G的最短路线及相应的最短距离；而且得到了从所有各中间点出发到终点的最短路线及相应的距离。即，求出的不是一个最优策略，而是一族的最优策略。这对许多实际问题有重要意义。构成动态规划模型的条件 建立动态规划模型时

13、，除了要将实际问题恰当地划分若干个阶段（一般是根据时间和空间而划分的）外，主要明确以下四个方面：正确选择状态变量xk, 使它既能描述过程的状态，又要满足无后效性。动态规划中的状态与一般所说的状态概念是不同的，它必须具有三个特性：要能够用来描述受控过程的演变特征。要满足无后效性。 所谓无后效性是指：如果某段状态给定，则在这段以后过程的发展不受前面各阶段状态的影响。可知性。即是规定的各段状态变量的值，由直接或间接都是可以知道的。构成动态规划模型的条件2 确定决策变量uk及每段的允许决策集合Dk(xk)=uk。3 写出状态转移方程如果给定第k段状态变量xk的值，则该段的决策变量uk一经确定，第k+1

14、段状态变量xk+1的值也就完全确定。 xk+1的值随xk和uk的值的变化而变化的这种对应关系，用xk+1 = Tk(xk, uk) 表示。它表示由k段到k+1段的整体转移规律，称为状态转移方程。构成动态规划模型的条件4 根据题意，列出指标函数Vk,n 关系，并要满足递推性。正确列出指标函数关系，必须使它具有三个性质：它是定义在全过程和所有后部子过程上的数量函数；要满足递推关系。即 Vk,n（xk, uk，xk+1 , ，xn+1）= 对其变元Vk+1,n来说要严格单调。构成动态规划模型的条件常见的指标函数是取各段指标和的形式。即其中表示第 j 段的指标。它显然是满足上述三个性质的。所以上式可写

15、成构成动态规划模型的条件当初始状态给定，过程的策略也确定了时，指标函数也就确定了。因此，指标函数是初始状态和策略的函数。记为Vk,nxk,pk,n(xk)。 故上面递推关系又可写成：构成动态规划模型的条件因其子策略pk,n(xk)可看成是由决策uk(xk)和pk+1,n(xk+1)组合而成。即对于最优策略的指标函数值，有P*k,n(xk) 表示初始状态为xk的后部子过程所有子策略中的最优子策略构成动态规划模型的条件由上述四个条件（组成部分）得出动态规划的基本方程：动态规划的基本方程 若从xk出发，有： k =n, n-1, 1动态规划的基本方程于是可得：fk(xk) = 及fn+1(xn+1)

16、 = 0动态规划的基本方程以上是逆序解法的基本方程。其递推过程从k = n开始，逐段向前推移，一直到求出f1(x1)时，就得到了整个过程的最优解，包括最优策略和相应的最优指标函数值。问题举例例1最短路线问题给出一个线路网络， 从A点要铺设一条管道到G点，其两点之间连线上的数字表示两点间的距离；要求选择一条由A到G的铺管线路，使总距离为最短。AE2D2B2B1C4C3C2C1D3D1E1E3F2F1G336625533432122335386631485768最短路线问题 4 3 7 5 9 7 6 81310 912131618AE2D2B2B1C4C3C2C1D3D1E1E3F2F1G336

17、625533432122335386631485768最短路线问题问题举例例2 机器负荷分配问题某种机器，可以在高低两种不同的负荷下进行生产。在高负荷下进行生产时，产品的年产量s1和投入生产的机器数量u1的关系为s1 = g (u1)这时，机器的年折损率为a，即如果年初完好机器的数量为u，到年终时完好的机器就为au, 0a1. 在低负荷下生产时，产品的年产量s2和投入生产的机器数量u2的关系为s2= h (u2)相应的机器的年折损率为b, 0bk0时以及计算二项式系数 可以用动态规划技术来对它求解。把二项式系数记录在一张n+1行k+1列的表中，行从0到n 计数，列从0到k计数。为了计算C（n,

18、k），逐行填充表格，从行0开始，到行n结束。每一行（0in）从左向右填充，第一个数字填1，因为C（n,0）=1。行0直到行k也是以1结束在表的主对角线上：当0ik时，C(i,i)=1。用上述公式计算其他单元格的值，即把前一行前一列那个单元格的值和前一行当前列那个单元格的值相加。（帕斯卡三角形）计算二项式系数 算法Binomial(n,k)/用动态规划算法计算C(n,k)/输入：一对非负整数nk0/输出：C(n,k)的值for i 0 to n dofor j0 to min(i,k) doif j= 0 or j=iCi,j 1else Ci,j Ci-1,j-1+Ci-1,jreturn C

19、n,k计算二项式系数 该算法的基本操作是加法，所以把A（n,k）记作该算法在计算C(n,k)时所作的加法总次数。 因为表格的前k+1行构成了一个三角形，而余下的n-k行构成了一个矩形，将求和表达式A（n,k）分成两个部分,有：最长公共子序列一个给定序列的子序列是在该序列中删去若干元素后得到的序列。存在一个严格递增下标序列。例如，序列Z= B，C，D，B是序列X= A，B，C，B，D，A，B的子序列， 相应的递增下标序列为2，3，5，7。给定两个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。例如， 若X= A，B，C，B，D，A，B，Y= B，D，C，A，B，A则序列B，C，A是X和Y的一个公共子序列。最长公共子序列问题：给定两个序列X= x1, x2, , xm和Y= y1, y2, , yn， 找出X和Y的一个最长公共子序列。最长公共子序列蛮力搜索的方法：令A= a1a2an和B= b1b2bm。例举A所有的2n个子序列， 对于每一个子序列在(m) 时间内来确定它是否也是B的子序列。此方法的时间复杂性是