算法课讲稿.doc

第5组 算法课讲稿 小组成员 6-1 集合上的基本操作 在算法设计中，集合是许多重要抽象数据类型的基础。有许多的问题也常常是用集合来描述的。与一个问题有关的数据一般取自某一特定集合，该集合称为问题的定义域（或全集）。求解问题的算法可用问题定义域上的基本操作来实现。如果把问题所考察的数据全体称为集合U（全集），可变子集记为S, SU, 集合中的一个具体数据或唯一表征该数据的关键字称为元素，则在集合S上的操作大致如下：（1） MENBER ( a, S ) 询问元素a 是否属于集合 S（2） INSERT ( a ,S ) 把一个元素a插入集合 S（3） DELETE ( a , S) 把一个元素a 从集合中删除（4） MIN ( S )给出中的最小元素（5） FIND( a )在集合中检索元素（6） SPLIT ( a , S )以为界，将集合分成两个集合、（7） UNION ( S1 , S2 ,S )合并集合、，用代替实际问题往往可以分成几个较小的问题，对于每个问题又可以抽象的描述成某种数据集合上的上述种操作的某一种操作。例如求某一无向连同图的最小耗费树，在他当中就要用到INSETT、 DELETE、 UNION、 FIND及MIN 操作。设G=(V , E ) , 其生成的无向树 S=( V 、T ), 而它的生成森林是一个无向树的集合 （V1 , T1）,（V2 , T2） （Vk , Tk）, 并使得Vi 形成一个 V的划分，即 Vi=V 且 Vi Vj= （ij）例1 给定图G=(V , E ) 构造最小耗费生成树算法6-1 利用集合上的操作求图G的最小耗费生成树 begin 1. T2. VS 3. for 每个顶点vV do 把只有一个元素的集合v加到VS;4. while |VS| 1 do begin 5. 选出E中最低耗费的边 （V, W）6. 从E中删去边（V , W）7. if v和w属于VS中两个不同的集合W1,W2, then8. begin 9. 用 W1 W2 替换VS中的W1和W210. 边（v , w）加入T11. end12. end13. end这个算法中的行5是在集合上运用操作MIN， 行6是执行DELETE操作，执行着两种操作利用对结构（求最大、最小元素）很方便。行7要确定边（v , w）是否连接了生成森林中的两棵树。如果是，那么被（v , w）连接的两棵树就在行8中合并（即执行操作UNION），而行9 把边(v , w)加入最终生成树的边集T(执行操作INSERT)。总的来说，行7要求找到特定节点的集合的名字，即执行FIND, 行8执行UNION操作，而行9执行INSERT操作。6-2 二叉检索前提：U,S是两个集合,S是U的真子集， S中有n个元素，并具有线序 , 而且已经存储在数组A中，A(1)A(2)A(n)。 U中元素a是否在S中？定义：集合S的二叉检索树是一有标记的二叉树，它的每个节点v用一个元素L(v)S来标记，使得1. 对于v的左子树中的每个节点u,有 L(u)L(v)3. 对于每个元素aS, 恰有一个节点v, 使得 L(v)=a显然，集合S中的元素和二叉树中的标号之间存在一一对应的关系。这样L(v)=a 就是在二叉树中寻找节点v , 其标号的值恰恰为a 。算法6-2 在二叉树中寻找元素a 集合S的二叉树及元素a procedure SEARCH(a, v)1. if a=L(v) then return “yes”2. else 3. if aL（v） then 4. if v 有左子树U then return SEARCH(a,U) else return “no”else5. if v 有左子树W then return SEARCH(a,W)6. else return “no ”7. end此算法，显然执行了MENBER(a , S) 操作。对于此算法稍加修改久可以执行MIN 、INSERT操作。（稍后会举例）定理6-1 把n(1)个元素插入开始为空的二叉检索树，所需的平均比较次数是O(nlogn). 62 二叉检索举例 - 计算机2002 任冬冬问题提出：在有n个元素的有序递增集合S中定位某个元素a。(集合S存储在数组A中)算法思想：利用集合的有序性，将a同第log（1+n）/2个位置中存储的元素b进行比较，如果a=b，则停止寻找，并回答“yes”。否则，若ab，就在后一半中重复这个过程。通过反复把检索范围分细一半，要找到a或者确定a不在S中，都不需要多于log（n+1）次比较。算法：procedure SEARCH(a,f,l) (寻找数组A中的第f至第l个位置中寻找元素a)begin if fl then return no else if a=A(（f+l）/2) then return yes else if aA(（f+l）/2) then return SEARCH(a,f,（f+l）/2-1) else return SEARCH(a,f,（f+l）/2+1)end例一：已知如下11个数据元素的有序表：（05，13，19，21，37，56，64，75，80，88，92），现要查找关键字为21的数据元素。初始：f=1，l=11，half=605，13，19，21，37，56，64，75，80，88，92因为2119，所以在half和l之间继续搜索三，f=half+1=4，l=5，half=405，13，19，21，37，56，64，75，80，88，92成功！二叉检索树定义 集合S的二叉检索树是一有标记的二叉检索树，它的每个结点v用一个元素l（v）S来标记，使得1，对于v的左子树中的每个结点u，有 l（u）l(v)3，对于每个元素aS，恰有一个结点v，使得l（v）=a。这样，a=l（v）是否在S中的问题就可以转化为：在二叉树中寻找结点v，其标号恰恰为a。算法： procedure SEARCH(a,v)begin if a=l(v) then return yeselseif a=1）个随机元素插入开始为空的二叉检索树，所需的平均比较次数是O（nlogn）。证明：由序列a1，a2，an二叉检索树所需的在序列元素间进行比较的次数设为T（n）。令T（0）=0，而b1，b2，bn是ai按递增顺序分类的序列。因为ai是随机的，所以a1是同样的概率等于某个bj，1=j=1时 （n）=knlogn，所以平均时间O（nlogn），而最坏情况下的时间复杂性是O(n2)。最优二叉检索树 例子讲解给定集合S=a1,a2,a3,a4, 且a1a2a3a4, q0=1/8,q1=3/16,q2=q3=q4=1/16, p1=1/4, p2=1/8, p3=p4=1/16.求：最小耗费的二叉检索树解法：对于0ijn,按j-i的值的递增次序计算rij和cij。在计算rij之后，再用buildtree(0,n)递归地构造最优树Ton。计算最优子树的根的算法:for i0 to n do beginwiiqicii0 endfor L1 to n do for i0 to n-L dobegin ji+L wijwi,j-1+pj+qj 令m是使得ci,k-1+ ckj最小的k (ikj)的值 cijwij+ci,m-1+cm,j rijamend计算过程为了计算方便，我们把qi,pi乘以16。q0=2, q1=3, q2=q3= q4= 1,p1=4, p2=2, p3= p4=1初始化：w00= q0=2, w11=q1=3, w22=q2=1,w33=w44=q3=q4=1, c00=c11=c22=c33=c44=0L=j-i=1 i=0, j=1w01=w00+p1+q1=2+4+3=9, 0m=1, c00+c11=0c01= w01+0=9, r01=am=a1 i=1, j=2w12=w11+p2+q2=3+2+1=6, 1m=2, c11+c22=0c12= w12+0=9, r12=am=a2 i=2, j=3w23=3, m=3, c23=3, r23=am=a3 i=3, j=4w34=3, m=4 , c34=3, r34=am=a4L=j-i=2 i=0, j=2w02=w01+p2+q2=9+2+1=12, 0k2, k为1，2k=1, c00+c12=6k=2, c01+c22=9m=1, c02=w02+6=12+6=18, r02=am=a1 i=1, j=3w13=w12+p3+q3=6+1+1=81k3, k为2，3k=2, c11+c23=3k=3, c12+c33=6m=2, c13=w13+3=11, r13=am=a2 i=2, j=4 w24=w23+p4+q4=3+1+1=52k4, k为3，4k=3, c22+c34=3k=4, c23+c44=3m=4, c24=w24+3=8, r24=am=a4注：k取3和4时，T24的耗费是一样的，都为3，书上m=k=4 。我认为m也可以取3，这样得到的二叉检索树如图2）。L=j-i=3 i=0, j=3 w03=w02+p3+q3=12+1+1=140k3, k为1,2,3k=1, c00+c13=11k=2, c01+c23=12k=3, c02+c33=18m=1, c03=w03+11=25, r03=am=a1 i=1, j=4w14=w13+p4+q4=8+1+1=10 1k4, k为2,3,4k=2, c11+c24=8k=3, c12+c34=9k=4, c13+c44=11m=2, c14=w14+8=19, r14=am=a2L=j-i=4 i=0, j=4w04=w03+p4+q4=14+2=16 0k4, k为1,2,3,4k=1, c00+c14=18k=2, c01+c24=9+8=17k=3, c02+c34=18+3=21k=4, c03+c44=25m=2, c04=w04+17=33, r04=am=a2在计算rij之后，再调用buildtree(0,n)构造最优树T0nprocedure buildtree(i,j) begin 建立Tij的根结点vij， 用rij标记vij， 令m是rij的下标（即rij= am）， if im-1 then call buildtree (i,m-1); / 造vij的左子树 / if mj then call buildtree(m,j) / 造vij的右子树 /end构造树TO4的过程如下：(1) 建立T04的根结点v04，用r04标记v04，r04= a2， m=2。i=0m-1=1, 调用buildtree (0,1)构造v04的左子树T01；(i)建立T01的根结点v01，用r01标记v01，r01= a1， m=1。i=0=m-1=0, T01 无左子树；j=1=m, T01 无右子树； m=2j=4, 调用buildtree (2,4) 构造v04的右子树T24；(i)建立T24的根结点v24， 用r24标记v24，r24= a4， m=4。 i=2m-1=3, 调用buildtree (2,3) 构造v24的左子树T23；(ii) 建立T23的根结点v23； 用r23标记v23，r23= a3， m=3； i=2=m-1, T23无左子树； m=3=j, T23无右子树。 m=4=j, 因此v24无右子树。T04所得的二叉检索树如下图： V04V04 a2 a2V24 V01 V24 V01 a1 a4 a1 a3 V34 V23 a3 a4 图1 图2最优二叉检索树 马伟锋 20022063前面我们已经知道了如何构造一棵二叉检索树，现在我们来看看如何构造一棵最优二叉检索树。它的前提条件：给出集合S中的所有元素，还给出更大的元素集合U中的所有元素a，给出操作MEMBER（a，s）在中出现的概率。即，设a1，a2，a3，an 是集合S中按递增顺序排列的元素，并设Pi是中指令MEMBER（a，s）出现的概率。q0，qi，qn分别是对于那些a（a a0、ai aan）的形如MEMBER（a，s）的指令在中出现的概率。它的要求：设计S的一个二叉检索树，使得MEMBER操作序列执行的平均比较次数最少，即，求最小耗费。1else begin If then end 02534我们为了定义一棵二叉树的耗费，给这棵树附加n+1个虚叶结点，以反映U-S中的元素。给这些叶结点编号为0、1、n （图6-2）二叉数的耗费确定如下：如果元素a是某个结点v的标记l(v),则执行指令MEMBER（a，s）是所访问的结点的个数比结点的深度多1；如果a不属于S，而ai a ai+1 ，则执行指令MEMBER（a，s）时所访问的结点个数等于虚结点i的深度。 n n Pi *(深度（ai）+1) + Pi *(深度（i）)i=1 i=0有了一棵最小耗费的二叉检索树，就可以在T中使用算法6-3来执行没条MEMBER指令，从而以最小平均访问结点次数来执行MEMBER指令序列。那给定p,q，怎样构造最小耗费的二叉检索树？如果我们确定了根结点，那么问题就是这样构造左、右自树，也就把原来的问题分成了两个自问题。但根元素不易确定（n个），所以就有2n个子问题。这样，就可以利用以前学过的动态规划方法来求解。下面我们假设已经有一最小耗费树，来分析它的耗费跟什么有关？对于0ijn, 设Tij是元素子集ai+1,ai+2aj的最小耗费树，cij是Tij的耗费，rij是Tij的根。树Tij的权Wij定义为qi+（pi+1+qi+1）+（pj+pj）Tij中的左子树Tik-1是有ai+1、ai+2、ak-1组成的最小耗费树。Tij中的右子树Tkj是有ak+1、ak+2、aj组成的最小耗费树。树Tij是有根结点ak 加上左子树，再加上右子树组成。如果i=k-1，则ak没有左子树；如果k=j，则ak没有右子树。Tii表示一棵空树。Tii的权Wii是qi，耗费cii=0。在Tij（ij）中,左、右子树的每个结点的深度是他们在Ti,k-1 和Tkj中深度加1。于是耗费cij为Cij=Wi,k